Openkore.com
http://forums.openkore.com/

AI 2008 FLD2 & Pathfinding
http://forums.openkore.com/viewtopic.php?f=36&t=1350
Page 1 of 5

Author:  Motivus [ 10 Jun 2008, 04:03 ]
Post subject:  AI 2008 FLD2 & Pathfinding

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]

Author:  sli [ 10 Jun 2008, 11:52 ]
Post subject:  Re: FLD2 proposal [for the future]

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.

Author:  Cozzie [ 10 Jun 2008, 20:10 ]
Post subject:  Re: FLD2 proposal [for the future]

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.

Author:  kali [ 12 Jun 2008, 06:30 ]
Post subject:  Re: FLD2 proposal [for the future]

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).

Author:  Technology [ 23 Jan 2009, 01:11 ]
Post subject:  Re: FLD2 proposal [for the future]

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

Author:  kali [ 23 Jan 2009, 03:42 ]
Post subject:  Re: FLD2 proposal [for the future]

-_- I really did reply to this topic, huh?

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

Author:  Motivus [ 23 Jan 2009, 03:44 ]
Post subject:  Re: FLD2 proposal [for the future]

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.

Author:  Technology [ 23 Jan 2009, 10:32 ]
Post subject:  Re: FLD2 proposal [for the future]

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

Author:  Motivus [ 23 Jan 2009, 10:35 ]
Post subject:  Re: FLD2 proposal [for the future]

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)

Author:  Technology [ 23 Jan 2009, 11:24 ]
Post subject:  Re: FLD2 proposal [for the future]

Oh i see, uhm, comments?

Page 1 of 5 All times are UTC - 5 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/