Re: [Adonthell-devel] Pathfinding in 3rd dimension

[Kai Sterker]

On Mon, Aug 6, 2012 at 10:33 PM, Kai Sterker <address@hidden> wrote:
> On Mon, Jul 23, 2012 at 8:58 AM, Kai Sterker <address@hidden> wrote:
>
> Pushed the latest pathfinding code, with a few open issues resolved
> and at least generally in a clean state. Still not done completely,
> though.

Did more of the same.


>> Going up stairs also works now, although not perfectly.

Much better now. From the little testing I did yesterday, it seemed
that the NPC can now reach every goal on the path-test map, with only
few exceptions. (One goal would require a jump, which is not
implemented yet and in rare cases, the path search would require more
iterations than allowed).

>> There are
>> instances where the nodes falling on the stairs get skipped and even
>> if they are present, sometimes the character fails to follow them.
>> Latter might be a problem with the collision detection. Although right
>> now I do not understand why it works for the player, but sometimes not
>> for the NPC.

That was actually so simple that I didn't even consider it. Only when
I had the node search visualization in place did I notice what the
problem is: to check if the character became stuck, we store the last
position on the map at the end of the move and compare that with the
position at the end of the next move. The problem is that this
position is pixel-based, but movement can be less than a pixel for
slow characters or when collisions occur, like when going up the
stairs. Changed the code to wait for 5 frames before deciding that a
character is stuck and everything is good :-).


> I have also spend some time yesterday reading up on collision
> detection in general, and found one article that looks quite
> interesting:
>
>   
> https://harablog.wordpress.com/2011/08/26/fast-pathfinding-via-symmetry-breaking/
>
> Especially the Jump Point Search described there could be something
> very beneficial to us. As it appears to vastly reduce the number of
> nodes to search, it might offset the additional cost of finding paths
> across multiple levels. There's a lua implementation to take as a
> reference:
>
>   https://github.com/Yonaba/Jumper/

Did not look further into that yet. But it might help with those
instances where searching the path takes too long with the current
approach.

Looking at the node search visualization (which is turned off in the
code I pushed), one can see that it searches towards the goal first,
but when the goal is on a different level, it starts spreading out
from the point beneath (or above) the code in a ever growing circle,
until it discovers a stair that brings it closer to the level of the
goal. With the test map, that only has narrow paths to walk this isn't
so much an issue (except when search starts on the ground level), but
on actual maps it could be pretty wasteful.


> Another bit for my todo list are doorways. Blocked node detection
> needs to be able to distinguish between solid walls and doors, which
> are basically just walls with a hole in them. Not too difficult, but
> needs to be done.

That's the next point on my list. That probably means building a
better Waste's Edge map first, to test with that.

Kai