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
<<attachment: corner-issue.png>>
_______________________________________________ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel
