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

[Kai Sterker]

On Sun, Jul 15, 2012 at 11:17 PM, Kai Sterker <address@hidden> wrote:

This weekends code changes aren't ready to commit, but I made some
progress, but also uncovered more problems.

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

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.


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

The solution I implemented for that now tries to process nodes on the
same level as the goal first. That should work well when the terrain
is not too complex and multiple up/down level changes are required.
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.


So there is still work to do, and there are two more issues that need
to be addressed:

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. So I
think that piece of code
(https://github.com/ksterker/adonthell/blob/master/src/world/pathfinding_manager.cc#L342)
needs to be rewritten. I tried patching it up, but wasn't really
successful. So maybe starting with a fresh design would be the better
solution.

Another bit that bothers me is the case when the path gets suddenly
blocked (i.e. by another character getting in the way). Right now it
throws the whole path away and calculates a new one. The better
approach might be to only remove the blocked nodes and newly calculate
the path to the first unblocked node. Only if no such path can be
found, we should try to find a completely new path to the goal.


And lastly, I have run into another issue with the collision code.
When the NPC fell down from a higher level, his z position should have
been -72.0, as that is where the ground floor is located. Instead it
ended up at -72.18 and from that time on, he became stuck in the
floor. Again, I haven't really been able to reproduce it with the
player character, but it happens quite regularly with the NPC.


So with all those open items, I guess it might be at least two more
weekends before having something ready to show. But if anyone feels
like helping out, I can open a branch for you to see where I'm at.

Kai