I’m a senior engineer on a fairly big > 10 years and running survival zombie franchise, with a large focus on the AI side of things. The game has been using the A* pathfinding project since 2018, before my time.
The game has evolved significantly over the years, and in terms of geometric and navigational complexity, it goes way beyond what is typical of the complexity of many voxel games, even though it is a voxel game. 1 meter voxels conceptually map well to 1 meter grid cells, but in practice, with 24000 block types(including rotational variants), the grid is increasingly more of a hindrance to the granularity we need, even though grid based pathing is still the favorable approach. Pretty confident navmeshes really aren’t a viable option.
It’s becoming increasingly evident to me that I’m going to have to either replace this plugin with something more custom or continue spinning it out into a highly customized solution. I don’t say that as a slight to the plugin in any way, I’m a fan of it in fact, but the truth is, the limitations of a grid based pathing system is not super conducive to games with modern environmental complexity.
Are you interested at all in discussing the problems/limitations we are running into, for the purpose of considering solutions to them at the plugin level? This could mutually benefit both of our goals. The plugin could cement its offering of best in class pathfinding middleware, and it helps me avoid a completely custom navigation tech spinoff.
I’ll give Aron a good tag on this, I think he’d be interested in talking about this. Maybe I’m just projecting though haha. That said, I did want to mention upfront that since it sounds like your graph is what’s causing you issues specifically, there actually is already a way to make custom graph types in Astar. Honestly I think it’s a powerful but underused part of the asset:
I’d recommend giving this a look for sure! You kinda get to have your cake and eat it too here. I’ve actually always wanted to work on a generator for a sorta “smart density” graph where it chooses a density for the nodes based on the complexity of the geometry in the area. (I think I have enough ADHD projects though)
But something native to Astar could be, as you said, beneficial to all users, so I’ll put this on his radar. Thanks for posting! Congrats on the success of your title as well!
I haven’t dug into the graph generation part to see if that’s a good launching point for something custom, but it definitely seems like it probably would be. And save a lot of effort. For now I’m trying to limp along with the layered grid we’ve been using for years. The schedule doesn’t yet give me the flexibility of a total replacement. And in many ways, the things lacking are things that would be highly valuable in a grid based implementation anyways. Games are rarely so navigationally simple that the limitations of grid based pathing don’t come with some significant sacrifices.
No. I don’t think navmesh is viable, since zombies in this game have path weighting associated with voxels that reflect the health of breaking through them, so from that perspective, it’s highly conducive to a grid based approach. Most blocks can be broken by zombies, so they need to exist as both a navigable part of the graph to move into that voxel space(with a cost that reflects the block health), and there still needs to be enough structure to the rest of the graph to path for units that don’t break blocks. Navmesh tends to be one or the other. Navigable or obstacle. Not both.
Another big disqualifier for navmesh is the edge erosion would cut off a ton of navigability of zombies along thin edges like halfblocks and plates.
In an ideal world it would be grid based, but with intra grid cell graph support, for lack of a better term.
A simple example, you can kinda see how a singular grid cell often needs intra grid node navigational island to support branched navigation that occurs within the footprint of a singular grid cell.
I don’t think it’s feasible for us to use 1/2 meter path grid cell resolution. That would probably address this specific example. But many others shapes are not fixed as easily, and the memory/cost of halfing the path grid size seems undesirable, on top of all the unknown consequences of mismatching pathing grids to voxel sizes. There would also be navigation along the thin top edge of this as well, producing potentially 3 different connectivity patterns within these grid nodes. Plus the sky traces associated with the graph generation misses a lot of situations. Some thin plate situations are not centered in their grid cell, so the top edge won’t be found at all by the generator.
I suspect this is just too specialized to expect we’d be able to get bolt this onto the layered grid system, and a custom system is likely the only real option.
I think what you’re essentially looking for is a sparse voxel octtree, I am not sure how customizable custom graphs are, but couldn’t you “just” write a grid graph and then check for every node in the grid graph in smaller steps, that only get occupied if there is a colliding object there, then the node gets split into 4 smaller nodes, which then again get split again until the geometry is fully covered or your minimum node size is reached.
That way you could also have less nodes when there is lots of empty space which is always nice.
If @aron_granberg adds new graphs to the base package that would be a way better grid graph option, even though baking could take longer.
For placement you could then just update the affected nodes i.e if there is a free space and the player builds something, when the graph is updated only check the nodes that the player interacted with and run that same algorithm, maybe at first at reduced resolution and when nothing changes for a few seconds do the full recalculation for the affected voxels.
