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

[Kai Sterker]

On Sun, Jul 8, 2012 at 4:34 PM, Kai Sterker <address@hidden> wrote:

> Committed my first changes to the pathfinding code. It's basically
> some code cleanup, better test and a few small improvements to get it
> working with the test map. To see stuff in action, run
>
>   ./path_test -g ../../adonthell/test/ path
>
> Press 'p' to assign a new goal to the NPC (out of a list of three).
> You should see the path drawn on top of everything and hopefully the
> NPC will reach the goal.

Added a real z-coordinate to the pathfinding, and that alone allows a
character to find its way down to a lower level. Up does not work yet,
as the collision check cannot distinguish between a stair and other
blocking objects.

There's another problem, however, that needs to be solved first. Since
a path can now be found on different levels, the number of iterations
allowed to calculate the path is too small. Simply increasing it
doesn't seem to be a good idea either. One way to further tweak the
result is finding a proper heuristic for the remaining distance to the
goal for a given point. The most likely candidates should have the
smallest distance, as those are checked first. This worked well on a
plane, but when the final path might go up and down and back and forth
it's not so simple any more. Ideas certainly welcome.


> I found one instance where the NPC will get stuck for no obvious
> reason. Not sure what happens there, haven't debugged yet.

Fixed.


> It's also possible for the player to get stuck under the higher level
> paths. Levels are exactly 80px above each other and the character is
> 80px tall. There seems to be certain positions where the collision
> detection will report a collision, even though things should just fit.
> Haven't debugged that either.

Sort of fixed, but not sure if this is the right thing to do.
See 
https://github.com/ksterker/adonthell/commit/14cc8a407b630046cb4a1f9d7bc9bf2b376d7879

Kai