Openkore.com

OpenKore Forums
It is currently 21 Sep 2018, 21:31

All times are UTC - 5 hours [ DST ]





Post new topic Reply to topic  [ 41 posts ]  Go to page 1, 2, 3, 4, 5  Next
Author Message
 Post subject: AI 2008 FLD2 & Pathfinding
PostPosted: 10 Jun 2008, 04:03 
Offline
Developers
Developers

Joined: 04 Apr 2008, 13:33
Posts: 157
FLD2 proposal [for the future]
This post is mostly an idea.

Reasons
1) Tile Type
2) Index [minor]
3) Map edges

1) Tile Type
Look at the current field tile types:
Code:
0 = walkable block
1 = non-walkable block
2 = non-walkable water (not snipable)
3 = walkable water
4 = non-walkable water (snipable)
5 = cliff (snipable)
6 = cliff (not snipable)
Everything else = unknown
This creates a lot of if statements with redundant information if you want to do line of sight or other checks.

Proposed bit flags for type:
Code:
0 = Unwalkable
1 = Walkable
2 = Snipable
4 = Water
8 = Cliff
16,32,64,128 = Reserved
Example: Type 3 becomes type 5 (walkable, water). 5&1 for a walkable check, 5&4 for a water check.

It's slightly less human readable as a file format, but the code becomes simpler and easier to read. Especially if you do defines like this:
Code:
#define TILE_NOWALK 0
#define TILE_WALK 1
#define TILE_SNIPE 2
#define TILE_WATER 4
#define TILE_CLIFF 8

#define TILE_LOS 3
#define TILE_HASWATER 5


2) Index
The index size is not currently stored in the file. While it can be calculated on the fly, I think we might as well store it in the v2 fld file.

Pseudo code (not much has changed):
Code:
struct FLD2  {
   unsigned int index;
   unsigned short x;
   unsigned short y;
   unsigned char type[index];
};


3) Map edges
In gat files the top edge and the right edge of the map are defined as walkable. I am pretty sure OpenKore's code compensates for this currently by ignoring those tiles, but the fld file format itself does not. We could easily convert all existing fields to ignore this and not need a version update, but for the v2 specification we should remove this. There is no need to code exceptions for something that serves no purpose.


If we really wanted to we could do 4 bits per tile instead of the current 8 and halve map size, but there's not much of a point.

Please leave any feedback or suggested modifications to the fld2 specification. I don't expect this to be put in to use by... anyone. When/if I (or someone else) decides to finish rewriting the pathing this might be a change worth considering. If you think this is a stupid idea tell me that, too.

[EDIT: Technology -> change of title + sticky]

_________________
Oh no.


Last edited by Motivus on 17 Jun 2008, 13:39, edited 5 times in total.

Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 10 Jun 2008, 11:52 
Offline
Perl Monk
Perl Monk

Joined: 04 Apr 2008, 17:26
Posts: 811
That involves a lot of byte-shifting that the current format does not. Honestly, I think the walkable water byte could be removed because it's still just walkable ground. Although that might affect acolytes using Aqua Benedicta, the bot won't be able to know it's standing in water.

Just some thoughts.

_________________
cs : ee : realist


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 10 Jun 2008, 20:10 
Offline
Spam Generator
Spam Generator

Joined: 04 Apr 2008, 09:30
Posts: 501
Location: Melbourne, City of beer and awful sushis
sli wrote:
Although that might affect acolytes using Aqua Benedicta, the bot won't be able to know it's standing in water.

Just some thoughts.


Not just Aqua Benedicta but also water ball and a few other I believe. It should be specifically implied that it is a water walkable tile.

_________________
Make Openkore Awesome. Join the team.


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 12 Jun 2008, 06:30 
Offline
OpenKore Monk
OpenKore Monk

Joined: 04 Apr 2008, 10:10
Posts: 474
I agree with all three proposals (especially the first one).

In fact, the first proposal could be easily implemented in the current FLD format (by regenerating all FLD files and rewriting the modules that use FLD). The bit-shifting can save some cpu cycles (especially for complicated conditions).

_________________
Got your topic trashed by a mod?

Trashing topics is one click, and moving a topic to its proper forum is a lot harder. You expend the least effort in deciding where to post, mods expend the least effort by trashing.

Have a nice day.


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 01:11 
Offline
Super Moderators
Super Moderators
User avatar

Joined: 06 May 2008, 12:47
Posts: 801
RESSURECT ! ;)
No really, this idea by Motivus needs some attention, and since people were suffering from amnesia.

First, i need to get some things straight:
- do maps have a 0,0 coordinate or do they start with 1,1?
- is it the intention only to add the following:
Code:
   NON_WALKABLE => 0
   WALKABLE => 1
   SNIPABLE => 2
   WATER => 4
   CLIFF => 8
   UNKNOWN => 16

because theoretically types like the following will be created aswell (if we look at the water level):
Code:
WATER_WALKABLE => WATER + WALKABLE #5
WATER_SNIPABLE => WATER + SNIPABLE #6
WATER_CLIFF => WATER + CLIFF # 12
WATER_CLIFF_SNIPABLE => WATER + CLIFF + SNIPABLE # 14
WATER_UNKNOWN => WATER + UNKNOWN # 20
CLIFF_SNIPABLE => CLIFF + SNIPABLE # 10

Or will all water area's (with exeption of water + walkable and water + snipable) get type 4? (or even type 0? because non walkable water being redundant information to us?) (and thus water + snipable becoming type 2)
What will happen to water + cliff then? Or is that redundant information too? (will it get 4, 8 or 12 OR is it non existant in practical?)
Is cliff even used somewhere, or did i miss something?


If anyone wants to know how i got to those theoretical possible types:
Code:
      # Block is below water level.
      } elsif ($averageDepth > $waterLevel) {

         # walkable block + water = 1 + 4 OR walkable water = 1 + 4
         if ($type == 0 || $type == 3) { print $out pack("C", 5) }
         # non-walkable block + water = 0 + 4 OR non-walkable water = 0 + 4
         elsif ($type == 1 || $type == 2) { print $out pack("C", 4) }
         # non-walkable water (snipable) = 0 + 4 + 2
         elsif ($type == 4) { print $out pack("C", 6) }
         # cliff (snipable) + water = 8 + 2 + 4 = 14
         elsif ($type == 5) { print $out pack("C", 14) }
         # cliff (not snipable) + water = 8 + 0 + 4 = 12
         elsif ($type == 6) { print $out pack("C", 12) }
         # unknown + water = 16 + 4  (for consistancy & future new types)
         else { print $out pack("C", 20) }

      # Block is above water level
      } else {

         # walkable block = 1
         if ($type == 0) { print $out pack("C", 1) }
         # non-walkable block = 0
         elsif ($type == 1) { print $out pack("C", 0) }
         # non-walkable water (not snipable)  = 0 + 4 + 0
         elsif ($type == 2) { print $out pack("C", 4) }
         # walkable water = 1 + 4
         elsif ($type == 3) { print $out pack("C", 5) }
         # non-walkable water (snipable) = 0 + 4 + 2
         elsif ($type == 4) { print $out pack("C", 6) }
         # cliff (snipable) = 8 + 2
         elsif ($type == 5) { print $out pack("C", 10) }
         # cliff (not snipable) = 8 + 0
         elsif ($type == 6) { print $out pack("C", 8) }
         # unknown
         else { print $out pack("C", 16) }
      }

If its stated like this, there won't even be a type 2. (snipable is either combined with cliff or non walkable water)

EDIT: covered map edges problem

_________________
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 03:42 
Offline
OpenKore Monk
OpenKore Monk

Joined: 04 Apr 2008, 10:10
Posts: 474
-_- I really did reply to this topic, huh?

But then again, I guess my impression didn't change :P I'm still supporting it.

_________________
Got your topic trashed by a mod?

Trashing topics is one click, and moving a topic to its proper forum is a lot harder. You expend the least effort in deciding where to post, mods expend the least effort by trashing.

Have a nice day.


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 03:44 
Offline
Developers
Developers

Joined: 04 Apr 2008, 13:33
Posts: 157
They are supposed to be bit flags for each "unique" tile feature
Code:
#define TILE_NOWALK 0
#define TILE_WALK 1
#define TILE_SNIPE 2
#define TILE_WATER 4
#define TILE_CLIFF 8


The last two were supposed to be examples of how bit flags are useful, and truthfully they are the only useful examples
Code:
#define TILE_LOS 3
#define TILE_HASWATER 5


Walkable + water = 4|1 = 5
snipe+nowalk = 2|0 = 2
snipe+cliff = 8|2 = 10
los check = 1|2 = 3 (walkable or snipable)

You just do if (tile&5 == 5) to check walkable water or if (tile&3) to check line of sight (tile&TILE_HASWATER == TILE_HASWATER, tile&TILE_LOS)

Code:
   unsigned char TILE_TYPE[9];
   TILE_TYPE[0]=TILE_WALK; //Non-Walkable
   TILE_TYPE[1]=TILE_NOWALK; //Walkable
   TILE_TYPE[2]=TILE_WATER; //Non-walkable water
   TILE_TYPE[3]=TILE_WALK|TILE_WATER; //Walkable water
   TILE_TYPE[4]=TILE_WATER|TILE_SNIPE;//Non-walkable water (snipable)
   TILE_TYPE[5]=TILE_CLIFF|TILE_SNIPE; //Cliff (snipable)
   TILE_TYPE[6]=TILE_CLIFF; //Cliff (not snipable)
   TILE_TYPE[7]=TILE_NOWALK; //Unknown

That is a conversion from all the current types.

I honestly don't know the point of cliffs. There is no real distinction between a cliff and non-walkable in game, even though there is in a gat file.

_________________
Oh no.


Last edited by Motivus on 23 Jan 2009, 10:35, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 10:32 
Offline
Super Moderators
Super Moderators
User avatar

Joined: 06 May 2008, 12:47
Posts: 801
Motivus wrote:
Code:
   unsigned char TILE_TYPE[9];
   TILE_TYPE[0]=TILE_NOWALK; //Non-Walkable
   TILE_TYPE[1]=TILE_WALK; //Walkable
   TILE_TYPE[2]=TILE_WATER; //Non-walkable water
   TILE_TYPE[3]=TILE_WALK|TILE_WATER; //Walkable water
   TILE_TYPE[4]=TILE_WATER|TILE_SNIPE;//Non-walkable water (snipable)
   TILE_TYPE[5]=TILE_CLIFF|TILE_SNIPE; //Cliff (snipable)
   TILE_TYPE[6]=TILE_CLIFF; //Cliff (not snipable)
   TILE_TYPE[7]=TILE_NOWALK; //Unknown


first 2 the other way around no?
Code:
   TILE_TYPE[0]=TILE_WALK; //Walkable
   TILE_TYPE[1]=TILE_NOWALK; //Non-Walkable

_________________
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 10:35 
Offline
Developers
Developers

Joined: 04 Apr 2008, 13:33
Posts: 157
Technology wrote:
Motivus wrote:
Code:
   unsigned char TILE_TYPE[9];
   TILE_TYPE[0]=TILE_NOWALK; //Non-Walkable
   TILE_TYPE[1]=TILE_WALK; //Walkable
   TILE_TYPE[2]=TILE_WATER; //Non-walkable water
   TILE_TYPE[3]=TILE_WALK|TILE_WATER; //Walkable water
   TILE_TYPE[4]=TILE_WATER|TILE_SNIPE;//Non-walkable water (snipable)
   TILE_TYPE[5]=TILE_CLIFF|TILE_SNIPE; //Cliff (snipable)
   TILE_TYPE[6]=TILE_CLIFF; //Cliff (not snipable)
   TILE_TYPE[7]=TILE_NOWALK; //Unknown


first 2 the other way around no?
Code:
   TILE_TYPE[0]=TILE_WALK; //Walkable
   TILE_TYPE[1]=TILE_NOWALK; //Non-Walkable
Fixed it, I thought I had it backwards in my code (bceause I had walk/nowalk reversed at first)

_________________
Oh no.


Top
 Profile  
 
 Post subject: Re: FLD2 proposal [for the future]
PostPosted: 23 Jan 2009, 11:24 
Offline
Super Moderators
Super Moderators
User avatar

Joined: 06 May 2008, 12:47
Posts: 801
Oh i see, uhm, comments?

_________________
One ST0 to rule them all? One PE viewer to find them!
One ST_kRO to bring them all and in the darkness bind them...

Mount Doom awaits us, fellowship of OpenKore!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 41 posts ]  Go to page 1, 2, 3, 4, 5  Next

All times are UTC - 5 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group