One of the challenges during the early development of Tower was pathfinding. The traditional gamedev solution is to use some variant of A* – a basic version actually comes bundled with the engine, in my case – but that wasn’t quite enough for what I wanted to do.
The Problem
First of all, I knew I wanted fairly large maps. The design of the game is in the vein of 90’s ~ early 2000’s RPGs like Baldur’s Gate. That means large pathfinding grids, which is something basic A* doesn’t perform too well on. The engine itself is fundamentally tile-based, but I wanted the characters for all intents and purposes to look and feel like they’re moving continuously, not locked-in to any particular grid.
One way of achieving this is to subdivide the grid for more precise movement. Subdividing an 85×85 map 3 times leaves you with a 255×255 grid (or ~65k tiles). If a character needs to path from one end of the map to the other, that’s potentially a very large amount of tiles for A* to explore. This is potentially fixable with one of any number of A* optimizations, such as JPS, but it’s clear at this point that whatever I do, I’d have to come up with something better than the built-in basic unoptimized solution.
After doing some more research on this, I noticed another issue: A* normally only deals with either 4-directional or 8-directional movement on a grid. It can’t actually model characters that can move in any arbitrary angle, so the resulting paths will still look jagged and somewhat “gamey”. I wanted more natural-looking paths which allowed characters to move in any direction. This isn’t entirely an aesthetic issue either – if you can move in any angle, A* (and all of its standard variants) is no longer is guaranteed to produce optimal paths.
There are a few algorithms out there for doing some post-process smoothing on paths, but the results aren’t always the best.
After doing a little bit of research, I discovered there’s an entire class of Any-Angle Pathfinding algorithms. Shunhao Oh has a project on Github that does a very thorough examination of these, with benchmarks and performance comparisons, running on a good number of sample datasets. This was the starting point for my eventual solution.
After investigating the results, it was clear that Visibility Graphs provide most of what I was looking for: they generate paths which contain turns in arbitrary angles, paths are guaranteed to be optimal, which also means it doesn’t require any further smoothing step, and once you know the full Visibility Graph of a scene, you can generate paths between any two nodes very efficiently. Unfortunately, Visibility Graphs have to be precomputed, and it’s an extremely slow operation. That’s what led to the discovery of the ENLSVG algorithm.
Edge N-Level Sparse Visibility Graphs
The full algorithm is described in detail here, so I won’t go through the specifics too much. The key insight is that it’s possible to construct a partial (that’s the ‘Sparse’ in the name) visibility graph in significantly less time than the full graph, while still retaining all of the information you need to generate optimal paths.
This is based on the observation that any optimal path will always be ‘Taut’ – that is, any time you round a corner, if you imagine the path as a string connecting the start and end point, that string is always fully stretched, as if you were pulling it on both ends. This is easier to understand visually:
The above images are from a presentation given by Shunhao Oh and Hon Wai Leong of the National University of Singapore on this topic.
Some further optimizations are done which both reduce the cost of computing the graph and of finding paths between nodes. The result is a highly performant algorithm which can compute paths between any two nodes on extremely large grids in a very short amount of time (millisecond runtimes in grids with several million tiles).
I implemented a version of this algorithm in Javascript, using Shunhao Oh’s Java implementation as a reference. As expected, it performed significantly better than the prior A* implementation.
However, there are still issues. Since it is still a Visibility Graph, a pre-computation step is still required every time the grid changes. With the above optimizations and a reasonable grid size, this can still happen quite fast (around ~10ms for the grids representing maps in my game, using my ENLSVG implementation), but not fast enough to be an operation you’d want to run every time a character moves.
That is fast enough to run during level loading, so for a short time I considered precomputing the grid at load time for level geometry and static objects and simply using some other algorithm to deal with pathing around dynamic objects, like AI Steering Behaviors found in many RTS games.
Anya
Ultimately, however, I decided I really would prefer it if I could use a single algorithm to deal with all pathfinding issues at once. Ideally, it could just handle everything ENLSVG does, but with a dynamic grid, and in a way that doesn’t require modifying paths after they’ve been calculated.
Turns out the Anya algorithm does just that. It’s described in detail here by Daniel Harabor et al, with a reference Java implementation available in Daniel Harabor’s Code Repository.
I implemented a Javascript version of the algorithm, to compare it with ENLSVG. It’s not quite as blazingly fast, but is still more than fast enough – more than an order of magnitude faster than my previous A* implementation – and works perfectly fine with a dynamic grid.
Additional Work
Both Anya and ENLSVG have a few additional advantages over A*. First, their runtime is proportional to map complexity, rather than map size. This means in very large grids with significant amounts of open spaces – a very typical scenario in 2D RPGs, and the one I’m working on is no exception – they inherently scale significantly better with large maps.
Second, they’re much better at dealing with situations where there is no valid path. A* is fundamentally a breadth-first search with extra bits on top, and BFS can’t really determine if a destination is reachable or not without fully exploring every single reachable tile. When you have very large maps, this can lead to extremely bad performance.
Normally you’d have to implement some kind of optimization to deal with this specific case, such as counting and labeling each connected “island” on the map. However, since both Anya and ENLSVG search through specific waypoints rather than examining every single node on the grid (ENLSVG by looking at the sparse visibility graph, Anya by examining intervals between visible points on the grid), they can both determine that a path is unreachable in a short amount of time, without requiring any additional work.
There was still quite a bit of work to do afterwards to make this usable as part of a game: hooking it up to the movement and collision systems, adjusting for the fact that both algorithms calculate paths from the edges on the grid, not from tile centers, among other problems.
The most significant of all of these issues was: how can we deal with the fact that the pathfinding assumes entities are infinitesimal points on the grid, when the actual game characters most definitely have real size constraints? If a character’s collision volume is a circle with radius r (in the arbitrary game-engine units of your choice – I’m making a 2D sprite-based game, so I just measure things in pixels), we have to make sure we’re always at least r units away from any blockers we path around.
Grid Dilation
To solve this problem, I incorporated an idea from image processing: Dilation. If you have a grid of tiles consisting of X pixels each, treat tiles on the grid as if they were pixels on an image and apply the dilation algorithm with an NxN kernel, it has the effect of “expanding” pathfinding blockers in all directions by ⌊N/2⌋ tiles, or (⌊N/2⌋ * X) pixels, effectively pushing any entity walking on the grid away from blockers by that many pixels.
A similar idea can be applied to character collision volumes after projecting them onto the pathfinding grid, to ensure characters can’t path too close to each other. The result is something like this:
I implemented this in RPG Maker to keep things simple, but the same concept applies in any kind of 2D game engine. Red squares are tiles blocked for the purposes of pathfinding, while the darker red polygons are collision volumes. In this scene, I just quickly created some arbitrary collision volumes not attached to any particular objects to simulate the behavior of walls, or other static level collision.
A working version of this can be found in my GitLab here. An updated version of the code in the project is the pathfinding method that’s currently being used by Tower.