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

[Kai Sterker]

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.

> Going up stairs also works now, although not perfectly. 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.

Haven't really solved that issue yet. Seems I need to better
understand in what order nodes on the path grid get evaluated. Adding
a visualization to the pathfinding phase should help with that, so
this will be the next thing on my list.


> All in all, the allotted number of iterations for pathfinding needs to
> be increased as well. But to allow that, the actual finding of the
> path needs to be distributed over several frames (maybe allowing 1000
> iterations per frame(. This change shouldn't be too difficult, but it
> will require to keep some data around that right now is only kept
> locally. And we must ensure that multiple simultaneous pathfinding
> operations each use their own set of data.

Done.

> Following along the path does not work well if the NPC deviates too
> much from that path, i.e. due to being deflected by obstacles.

Fixed. Also, if obstacles appear during the walking phase, not the
complete path to the goal is recalculated. Instead, just a path from
the current spot to the next unblocked part of the path is sought.


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/


Unfortunately, there isn't much information about multi-level
pathfinding around. I still have not figured out what a good heuristic
would be. Experimenting in that area will be easier with the
visualization suggested above in place.


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.

Later we'd also need to accommodate for closed doors, allowing NPCs to
open them. For locked doors, we also would have to check if the NPC
possesses the matching key in its inventory. That's for after v0.4,
though.


Keep you updated once there is more progress. Getting visitors next
weekend, so might take a little bit of time.

Kai