Awhile back I did a Dev Video detailing our process for building navigation meshes and calculating routes to destinations using that mesh as an A* graph. Welp - that didn't work out.
After doing some play testing (in preparation for our latest combat video) we realized that we didn't want map makers to be responsible for the quality of this core functionality - the algorithm only works as well as the data that backs it - but automatic navigation mesh generation solutions weren't something we were interested in. So we had to change plans and come up with something that worked without the user having to worry about anything. Enter the grid graph.
This ended up being very simple to implement and didn't require much change to our pahthfinding algorithm. Once we finish loading all the objects for a map we cast a series of rays in a set interval (some might even call it a grid) and placing a point on the terrain when we don't encounter a building or some other obstacle. You can see this in the image above with a helper sphere placed at each point. We then hook the points up to each other and we have our nav grid!
Buildings that can be entered get their own mini-grid that a garrisoned unit uses to navigate around inside. This is calculated by taking the bounding boxes that make up the exterior building object and performing roughly the same process using those bounds instead of the map bounds.
As you can see with the two factories above there are some points lying outside the interior. This is because the bounds are set slightly higher than the actual mesh that makes up the exterior - so this is something we'll need to fix moving forward. There is still no support for interior walls but that'll be coming shortly and will play a bigger role in buildings like the tenement where interior walls might also block line of sight. Stay tuned!
