Pathfinding for 2d tile based large world games

[erlend-sh]

The following is a Discourse transcript:

ululator said:

i have a bit of an open question regarding pathfinding for 2d tile based large world games. Common advice seems to be to use an a* variant on a macro level (some connectivity graph) and micro level (tile array) for optimal results.

However, on the micro level i feel tile arrays are wasteful for pathfinding. They are too granular/needlessly detailed to run searches on effectively. If you compare the memory size of a tile array to a vertex mesh describing the same shape, the latter is almost always a lot smaller.

This makes me feel using a navmesh on the micro level is more appropriate, even for tile based games. I guess navmeshes are more complicated to implement and do not support fun things like immediate updates to the tile map as easily?

Basically, I am wondering if people have been successful in using navmeshes for simple 2d tile games. https://github.com/PsichiX/navmesh seems to be the only open source library for rust navmeshes for now?

[erlend-sh]

jamadazi said:

in my (limited) experience, unless the world is really huge, an optimized (not naive) depth-first-search has worked better than A* for me, because it can be made to not require any extra memory
by optimized, i mean, storing a few bits of state alongside other per-node data (wherever the data of the nodes is), rather than allocating a queue to keep track of nodes to search
but really depends
might be just my specific niche :person_shrugging:

redblobgames said:

I think navmesh on a micro level will be better than a grid, but a grid is easier if your map is already using a grid because you don't have to construct a navmesh out of it.
Another thing you can do on a tile grid is to construct a pathfinding graph using only the exterior corners. This would be a waypoint graph, not a navmesh, but I -think- exterior corners are sufficient. That is, where # is a wall and . is an open space:

. . . <-- exterior corner, put a waypoint here
# # . 
# # .

# # #
. . # <-- interior corner, do not put a waypoint here
. . # 

There are tons of grid-specific approaches other than navmeshes, as it's an active field of research. Jump Point Search is well known but there are lots of others (much faster than JPS). Many of them are essentially constructing a smaller graph from the grid. See https://webdocs.cs.ualberta.ca/~nathanst/papers/GPPC-2014.pdf for an overview. I don't think you'll find Rust code for most of these though.

ululator said:

yeah i made a jump point search port to elixir before as an exercise, but the compilation step was heavy and the end result is still a large array. It felt kind of pointless to do a heavy compilation step to end up with a representation that is still overdefined.

So i wondered what kind of compilations/representations would be better, thought meshes or rectangles could describe a tile grid 1 to 1 pretty well. I have tried making a path finder that bases itself on overlapping rectangles in rust. It worked except that my distance measures were kind of messed up (had not bothered to track exactly where you enter the rectangle and account for the distance from there to an exit point of the rectangle).

I used the rstar library to store the rectangles, positional lookup and query for overlaps etc. My solution felt kind of messy, I think non-overlapping rectangles (using edges for connectivity instead of overlap) might have been better.

I have not looked into waypoint graph approaches before, that is a good tip. I do like the idea of a representation that can also exactly describe the tile map (like a mesh or rectangles) though.
With overlapping rectangles as a representation, staircase bits in your tilemap will still make a lot of rectangles, overdefining the areas

redblobgames said:

Yeah, the best representation will depend a lot on the shape of the maps. If you are using rooms and corridors for example, there's an approach called Rectangular Symmetry Reduction (https://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/) that reduces tile maps to a smaller graph. Or maybe you make each room a graph node.

I think that's also why it's harder to find articles and code for these techniques — they're specialized for each map type rather than being something general but slower (like grids) :-/

wilsk said:

I've been playing around with bevy + bevy_tiled + pathfinding. Basically I set it up so that the grid costs are loaded from bevy_tiled. It was "working" up until the transform changes. I abstracted the pathfinding and tried a few different crates. The hierarchical pathfinding crate https://crates.io/crates/hierarchical_pathfinding seemed to work OK and also the pathfinding crate https://crates.io/crates/pathfinding. For grids up to 100x100 with randomly scribbled obstacles there was no perceptible lag / frame rate drop when pathfinding (only tried a couple of entities at once) so I think for starters I'm just planning to do A* and minimise the number of calls (i.e. through grouping units, throttling pathfinding updates etc).
I've looked at building my own navmesh and did some really naive "flood fill" experiments in typescript, which reduced the grid a bit, but as you say the kind of "staircase" effect of the diagonals causes a lot of rects to be built up. I think something like marching cubes to find the outlines / dissolve vertices etc might make a difference.
A pathfinding method like this one https://github.com/mikolalysenko/l1-path-finder looks promising with a simplified grid, but I haven't ported it to rust yet.
There are some interesting resources on building your own navmesh grid, but it seems non-trivial e.g. https://gamedev.stackexchange.com/questions/38721/how-can-i-generate-a-navigation-mesh-for-a-tile-grid. Depending on your grid you could manually build meshes or a really course waypoint graph for bulk pathfinding and then using steering behaviours or something like that for more local navigation

redblobgames said:

I tried mikolalysenko's l1-path-finder library on an 800x800 map and it was lightning fast, <1ms even in javascript. Test page: https://www.redblobgames.com/pathfinding/l1-clarkson/