Pathfinding enhancements

[collinsmith]

In the process of implementing #52 I've found that my current path finding system is not sufficient -- the generated path assumes entity size is 0 and the smoothed path will occasionally pass through the corner of an invalid subtile. This results in the entities getting stuck and really sticky corners. It may be possible to alleviate these issues using some kind of entity censor to veer off the path slightly (around the obstacle) and then back onto it -- but I wanted to look into enhancing the existing system first.

I've performed some optimizations today to the underlying MapGraph in an attempt to firstly transition from Point2 to Vector2 (the actual data type the rest of the code base uses for map coordinates), and then I want to look into other changes I can make to improve pathing -- which is essential for desktop movement through doorways and around basic obstacles/corners.

One thing that I'd like to look into is changing my graph representation. It might be easier to only use cardinal directions for generating node connections and having path smoothing generate the other directions. I'd also like to look into reducing the graphs -- but I don't know if this is realistic with how the tiles have flags (path finding for a mercenary is different from a player is different from a monster is different from light rays, etc).

Just throwing this in here too -- it could be the case that path finding is not needed at all and attaching sensors to entities to move around obstacles could be sufficient. Path finding seems to be used when navigating reasonable distances around corners though where it doesn't appear sensors alone could make these decisions. Also, monster pathing seems "dumber", so it could be the case that they could use a more dynamic approach where if they see a player they will switch over from path finding to sensors.

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html https://www.redblobgames.com/pathfinding/grids/algorithms.html

[collinsmith]

I included a couple of pictures which might help show what I'm talking about for only using cardinal directions for path finding and then letting the smoothing algorithm take control. First picture is the current path finding. Second one shows what the path finding algorithm might generate as yellow and then the smoothed path as pink. I think in this case the smoothed paths will be more desirable, especially because it appears the maps are generally not designed for diagonal movement.

[collinsmith]

I copied the A* path finder from the gdx-ai library and added support for a clearance field when checking if successors should be added to the open list -- it was actually pretty straightforward. It's a bit hacky and specific to my use case, but the resulting path works perfectly (I had to disable smoothing in my build, because smoothing doesn't take into account clearance yet). This implementation assumes that all non-zero tile flags are walls (will change to 1<<0) -- no support for masking the tiles and path finding that result -- this shouldn't be a problem except that some tiles only block players (1<<3) which in this implementation would mean that the path finding result would cause them to run into a wall -- I'll look into that problem when it arises. The other known flags are all used for ray casting it seems (light, line of sight, jumping from A to B, etc), so I'm not too worried about them in pathfinding.

Next I'm going to look into improving the path smoothing algorithm and then possibly implementing support for JPS path finding (this may be deferred to a later date, as it should really only be an optimization, but path smoothing is a necessity). I'd also like to look into a built-in path finding length limiter -- an upper limit on the successor heuristic value to stop the algorithm.

https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/

Pathing with size 3 clearance (red line only):

[collinsmith]

I rolled back the changes on storing non-point data into in additional data structures for the time being -- I'll explore this more when I implement JPS path finding. I added support back for direction-8 node successors instead of direction-4 -- direction-8 seems to provide better pathing for now, but there are probably cases where entities will become stuck around certain obstacles. I also fixed a bug where invalid sized coordinates (too close to an obstacle for a specific entity size) were still being added and added a limiter onto the path finding algorithm to return no path found after a certain number of nodes have been explored -- will possibly change over to adding time constraint, but this avoids the serious performance penalty I was getting from the case where the entire map was being scanned.

[collinsmith]

See https://github.com/collinsmith/riiablo/commit/a5898b568fb579830eed480b8dc9f87d91d47495#commitcomment-36087368

I'm fairly satisfied with how this issue has turned out and may close it and begin looking into supporting JPS path finding and fixing other deficiencies with my IndexedAStarPathFinder implementation.

One area I've been monitoring is with how map tile flags data are stored and mutated. Until now all map areas are loaded synchronously to their correct world locations -- i.e., they exist within the same world-space and all their collision data is all loaded at once. This hasn't been a problem because the current playable area is fairly small, but I need to start thinking about how I'd like to change over to an instancing loading method -- which the current path finding implementation won't like (since I'm working on that now). The idea I've been thinking over is to load more manageable areas at once -- depending on connectivity. This would mean that all connected outdoor areas are loaded at once and all dungeons are loaded separately -- this could be what the Layer column in levels.txt indicates. Loading a new area would mean clearing the collision map and clearing the A* indexes.

e.x. two outdoor areas in act 1 Rogue Encampment, Blood Moor, Cold Plains, Stony Field, Burial Grounds Dark Wood, Black Marsh, Tamoe Highland, Monastery Gate, Outer Cloister

Going by this assumption here are the more interesting areas -- bottom two are specific to act 5 -- the pandemonium event maps tack onto existing layers and because it's a different act -- replaces them?

layer	area (in tiles)	desc
0	87264	act 1 abc
27	29760	act 2
57	60160	act 3
77	16128	act 4a
78	54400	act 4b
79	13122	act 5
11	80000	pandemonium 1
92	80000	pandemonium 3

The largest unbroken areas are probably act 1b (because of inclusion of Barracks), act 3 and act 4b. If I recycle the collision maps and make the default size 1MB (200x200x25), it might be reasonable (act 1 in its entirety is ~2.2MB then). I can load these areas when the connecting zones are entered or stream them if distance permits. Possible I could have a pool of 80x80x25 for most outliers, except 1 area, act 5 siege, is 240x48 and not under 200 width and it doesn't really make sense to increase the max size for such a special case -- could maybe use 1-d arrays.

Anyways, not a huge concern right now, just need to make sure path finding class supports flushing if map were to change or update collision data so that any existing cache would be corrupted.

[collinsmith]

While looking through the JPS path finding algorithm, I noticed a lot of grid graph specific optimizations and decided it was appropriate to throw out my old path finding classes and start fresh without all of the generics and dependence on the gdx-ai pfa package. I think gdx-ai pfa was getting in the way and I'd like to try and go without it. One optimization that I implemented was removing the whole Connection abstraction in favor of just retrieving the neighboring nodes -- in grid maps like mine I really only care about neighboring nodes anyways -- and this is also what JPS wants too (gdx-ai pfa was more concerned with the connections between nodes and generalized for waypoints/nav meshes). This also seems to indicate that implementing search independent flags should be possible.

I also moved Point2 out of MapGraph and am looking into making this specific to path finding (it should already be invisible to non-pfa classes as they use Vector2). This means that removing NodeRecord should be possible and merging those fields in with Point2 could provide additional memory optimizations that just weren't possible with gdx-ai pfa.

[collinsmith]

I've implemented a JPS path finder, but my short tests show it isn't performing nearly as well as I expected -- actually noticeably worse than my A. I think this is because of how the jumps are generating/looking up nodes. Perhaps some kind of intermediate Point2 implementation may be necessary in order to avoid calling MapGraph#getOrCreate(int,int) (thus avoiding the cost of generating those graph nodes until they are actually resolved by the algorithm). For now the algorithm is there, it just needs to be optimized -- my A actually performs pretty well. I'm closing this issue as this is outside the original scope and will create another one for JPS path finding improvements.