[Adonthell-devel] Pathfinding ... done for now

[Kai Sterker]

With the last commit (which is nearly two weeks old by now) I believe
I'm done with pathfinding for the purpose of a Waste's Edge remake.

Finding paths through doorways works and pathtest shows that it's
pretty much possible for NPCs to find a way from any point on the
(unfinished) map to any other point. So I do not want to delay things
any longer and spent some time on finishing the map instead.

However, there are some issues and open items left with the
pathfinding code that I'd like to document below:

Issues

* Getting stuck on corners
  For diagonal moves, we do not really check if the complete path from
one cell of the grid to the next is clear, only if each cell itself is
clear (see corner-issue.png). I've seen that happen a couple of times,
although in each case, the path-recalculation on getting stuck kicked
in and the NPC could move on. A little odd to look at, but hardly
noticeable.

* Getting stuck on stairs.
  Sometimes, walking up stairs still fails, even with the correct
ground-pos calculation in place. Increasing the base speed of NPCs a
little should help here. Or, in the future, always switch to running
mode when going up stairs.

* End of path
  If you run pathtest and look closely, you'll notice that the
character never reaches the last cell of the calculated path. The
reason for that is this check:
  
https://github.com/ksterker/adonthell/blob/master/src/world/pathfinding_manager.cc#L333
But without it, there's a SEGFAULT a little further down in that
method (don't recall the exact position). There's certainly a better
fix for it that will actually let the NPC reach the true end of the
path, but I guess for Waste's Edge, it does not really matter if
characters stop a few pixels short of their goal.

Open Items

* Loading/Saving
  There's code in place to save and load the state of
pathfinding_manager. Not quite sure if this really makes sense, as
pathfinding will usually occur as part of a character's schedule. I
would not really think we'd save and restore the exact state of such
schedules, so any actions a character takes would be recalculated
newly after loading a saved game.

So loading/saving should not be required for anything to do with
pathfinding. We might have to take a little bit of care once
climbing/jumping is implemented. Loading a state where a NPC is in the
middle of a jump should not result in that character falling down and
dying. But this should be achievable by storing current velocity and
direction, so that any move in progress can continue and will end at a
safe place.

* Caching visited cells
  The pathfinding code caches visited cells so they will not get
re-evaluated during the search phase. However, this does not work
perfectly when cells fall on different height levels (mainly because
the actual height level of a cell is determined at a later stage of
the search). That means that cells that fall onto stairs might get
evaluated over and over again, wasting precious cycles and limiting
the range of the pathfinding. I don't think it is a big problem on a
small map like Waste's Edge, but something that needs to be addressed
for the future.

* Jump point search
  http://harablog.wordpress.com/2011/09/07/jump-point-search/
Still looks like something that might be worth implementing as a
general performance improvement for pathfinding, but I am not 100%
sure if it will work out as well in our case. The thing is, that it
needs to check cells for whether they are walkable before they are
even considered by the A* algorithm. But in our case, checking whether
a cell is walkable or not is quite an expensive operation that right
now is only performed if a cell is actually selected as a candidate
for the shortest path.

Checking whether a cell is walkable or not is something where I don't
see much potential for speedup, unless we start pre-calculating the
pathfinding-grid. Which will be made more difficult by allowing
addition and removal of map objects at runtime. NPCs walking around on
the map already change what is walkable or not.

OTOH, a pre-calculated grid and JPS together would certainly create a
dramatic speed-up of the whole pathfinding code. I could imagine that
we might gather this information from our world octree and keep it
up-to-date as that changes. But we'd still have to consider
differently shaped/sized creatures walking around, so some
calculations still have to be done during the actual path search.

* Jumping
  Pathfinding still does not support jumping across holes in the
ground. To implement it, we'd have to check the first few cells across
the hole for walkable ground. The number of cells to check is given by
the distance a character can jump, which is determined by its base
speed. An extra complication is that we need to make sure that there
is enough space in Z direction to perform the jump, as a low ceiling
will limit the length of the jump. We'd also need a way to embed a
jump "command" in the resulting path, which right now is nothing but a
list of cells to visit.

* Climbing
  A bit like jumping, with the difference that we need to check
upwards when in front of an obstacle. It might also be more tricky to
implement correctly as we don't want NPCs to walk across tables or
crates in their attempt to cross a room. I guess we can prevent this
with a high enough cost for climbing, so that walking around small
obstacles is always the cheaper path. Other than that, it's just
checking whether an obstacle is low enough to climb onto the top and
if there is enough space left in Z position to actually allow the
move.


Sounds like there is still a lot of work left in that area, but only
little of it seems truly essential. I'll be sure to update the Wiki
with a link to this listing, so if anyone now or in the future feels
up for a little challenge, there should be enough information around
to get started.

Kai

corner-issue.png
Description: PNG image