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
Technology
Super Moderators
Super Moderators
Posts: 801
Joined: 06 May 2008, 12:47
Noob?: No

Re: FLD2 proposal [for the future]

#21 Post by Technology »

sli wrote:Which reminds me, need to write a FLD -> FLD2 converter.
Hmm maybe, but the current .fld format lacks certain information:
- water + cliff was converted to "Non-walkable water". (instead of cliff + water)
- water + unknown was converted to "Unknown". (instead of unknown + water)

Now the first might not be so much of a big deal for kore now, but might become so in the future.
For the second, it might cause a problem when one wants to calculate the size of an area of water. (waterball damage)

So i recommend conversion from .gat (and .rsw) to .fld2 over conversion of .fld to .fld2
Ofcourse, when .gat are missing (old maps), we have no other choise.
But well, if a server has such maps, .gat/.rsw will be provided with the client.
So, do we really need a fld->fld2 converter?

EDIT:
committed .fld tools
(also a fld->fld2 converter, for when the grf data is encrypted, and fld is available)
Last edited by Technology on 27 Jan 2009, 20:37, edited 1 time in total.
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!

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

Re: FLD2 proposal [for the future]

#22 Post by sli »

I was just going to write it for myself to get the fields I'm missing. Good to know, though, but I suppose if there are any problems, my users can just create their own fields. Erok requires Python and my gat2fld2 script uses only standard library. Shouldn't be a problem (write those down as my last words :roll: ).
cs : ee : realist

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

Re: FLD2 proposal [for the future]

#23 Post by Motivus »

A converter works fine. No information is lost.
Oh no.

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

Re: FLD2 proposal [for the future]

#24 Post by Technology »

Motivus wrote:A converter works fine. No information is lost.
Information IS lost when converting fld->fld2. Read my previous post.

EDIT:
oh wait, information was already lost when converting gat->fld ofcourse!
Thats why i recommend gat->fld2 conversion wich keeps all data.
Last edited by Technology on 28 Jan 2009, 10:15, edited 2 times in total.
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!

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

Re: FLD2 proposal [for the future]

#25 Post by sli »

And as I said on IRC, I believe that data loss in unacceptable.
cs : ee : realist

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

Re: FLD2 proposal [for the future]

#26 Post by Technology »

Routing in the old days
In the old days Kore used to just use the .fld instead of .dist to do the routing right?
I found this in Route.pm : $weights = join('', (map chr($_), (255, 7, 6, 3, 2, 1)));
And even here walkable water IS flagged as 255 weight, wich is equal to the weight of a wall lol, thats bad.
Note that the snipables are NOT flagged as 255 weight, wich is good, we want our bot to take advantage of snipable.
But hey, the non-default weights have no function anymore, want to know why? Read next paragraph.

Disadvantage of .dist over .fld in routing
Actually, at this moment there is no point in specifying these weights for specific types of tiles,
since the pathfinding algorithm only looks at the .dist and not the .fld!
Its not possible anymore to avoid specifical blocks like we could in the old days. (if my hypothese about the past is right)
And therefore the weights argument when creating a pathfinding object has no real function anymore.

But what if we want our bot to walk on water (waterball) and avoid non-water walkable blocks.
Or what if we want our bot to not avoid snipable walls. (an even better alternative would be that kore would take advantage of this, and walk close to it)

We could always not use the "do not walk close to a wall" function but is that really a solution?
Maybe we could generate a different .dist according to our preferences during routing.

Kore = wall-hugger by default now?
newg = fullList->array[cur].g + weight[CalcPath_getMap(map, width, height, &fullList->array[suc].p)];

CalcPath_getMap(map, width, height, &fullList->array[suc].p) will return the closest distance to a wall/nonwalkable (0 for a tile that is non walkable)
weight[CalcPath_getMap(map, width, height, &fullList->array[suc].p)]
will return:
255 if distance to the closest wall is 0,
1 if distance to the closest wall is 1,
2 if distance to the closest wall is 2, ... and so on

But wait lol, one bug here fixes another, thanks to the weights argument,
we do (unknowingly) give the tiles that have a distance 7, 6, 3, 2 or 1, weight 255.
So the bot will actually avoid walking in a distance of 7 to a wall.
LOL or CRY?
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]

#27 Post by Motivus »

The dist is passed as the weighting, or at least that's how it works functionally. The anti-wall hugging is only noticable in maps like sphinx.
Oh no.

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

Re: FLD2 proposal [for the future]

#28 Post by Technology »

Motivus wrote:The dist is passed as the weighting, or at least that's how it works functionally.
Atleast, thats how its supposed to work yea. ;)

I've read the whole pathfinding algorithm.
And atm the dist is doing the contrary of what it is supposed to do. (except for the tiles with distance 0 to a wall, aka walls or non walkable tiles)
But as i stated, there is yet another bug, that still allows kore to walk in some distance from walls.
(the option that was supposed to be set to avoid certain tile types, when fld routing)
Both bugs propagated at the time someone replaced .fld routing (by tile type) by .dst routing (by distance to walls).
But one bug hided another, so we didn't notice that untill now.

Should i even bother posting this in the bug report section.
Kore's pathfinding is seriously crippled.
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!

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

Re: FLD2 proposal [for the future]

#29 Post by sli »

It seems like it would be easier to generate fields with increased weight near walls.
cs : ee : realist

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

Re: FLD2 proposal [for the future]

#30 Post by Technology »

sli wrote:It seems like it would be easier to generate fields with increased weight near walls.
You mean some sort of merge, to have both advantage of the "ancient" (.fld) and the "new" (.dist) pathfinding?
How is that practically possible tho?
And will the advantages (possible walldistance & tiletype dependant routing) outweight the disadvantages (possibly more CPU usage)?

I had this idea of dynamicly creating the .dist (or .weight in that case) according to our needs.
But then there should be a way to have different bots running from the same folders to use different .dists.
Its probably better not to have different .dist around, but just pass tiletype weight info with the creation of the pathfinding object. (how it was with the ancient pathfinding)

We could make the pathfinding to act differently, dependant on wich info it gets too:
- .dist => avoid walls and weight tiles near them
- .fld2 => avoid ( or weight certain tile type(s)
- .fld2 and .dist => do both

(tho using .dist and .fld2 together provides allot of redundant information, all the 0's in the dist are nonwalkable)
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