AI 2008 FLD2 & Pathfinding

Wrote new code? Fixed a bug? Want to discuss technical stuff? Feel free to post it here.

Moderator: Moderators

Message
Author
Motivus
Developers
Developers
Posts: 157
Joined: 04 Apr 2008, 13:33
Noob?: Yes

AI 2008 FLD2 & Pathfinding

#1 Post by Motivus »

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: Select all

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: Select all

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: Select all

#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: Select all

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]
Last edited by Motivus on 17 Jun 2008, 13:39, edited 5 times in total.
Oh no.

sli
Perl Monk
Perl Monk
Posts: 811
Joined: 04 Apr 2008, 17:26
Noob?: No

Re: FLD2 proposal [for the future]

#2 Post by sli »

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

Cozzie
Spam Generator
Spam Generator
Posts: 499
Joined: 04 Apr 2008, 09:30
Noob?: No
Location: Melbourne, City of beer and awful sushis

Re: FLD2 proposal [for the future]

#3 Post by Cozzie »

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.

kali
OpenKore Monk
OpenKore Monk
Posts: 474
Joined: 04 Apr 2008, 10:10

Re: FLD2 proposal [for the future]

#4 Post by kali »

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.

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#5 Post by Technology »

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: Select all

	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: Select all

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: Select all

		# 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!

kali
OpenKore Monk
OpenKore Monk
Posts: 474
Joined: 04 Apr 2008, 10:10

Re: FLD2 proposal [for the future]

#6 Post by kali »

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

Motivus
Developers
Developers
Posts: 157
Joined: 04 Apr 2008, 13:33
Noob?: Yes

Re: FLD2 proposal [for the future]

#7 Post by Motivus »

They are supposed to be bit flags for each "unique" tile feature

Code: Select all

#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: Select all

#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: Select all

	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.
Last edited by Motivus on 23 Jan 2009, 10:35, edited 1 time in total.
Oh no.

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#8 Post by Technology »

Motivus wrote:

Code: Select all

	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: Select all

	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!

Motivus
Developers
Developers
Posts: 157
Joined: 04 Apr 2008, 13:33
Noob?: Yes

Re: FLD2 proposal [for the future]

#9 Post by Motivus »

Technology wrote:
Motivus wrote:

Code: Select all

	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: Select all

	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.

Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#10 Post by Technology »

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!

Post Reply