Old Pathfinding - Unity Nav Mesh
Winkeltje, as many have known it since early access nearly 5 years ago, uses the built-in navigation solution that is provided by the Unity game engine. This solution is also known as Nav Mesh pathfinding. Nav Mesh is short for Navigation Mesh. Unity is able to generate a Nav Mesh during gameplay which then returns a mesh surface area on which the agents, like customers, employees and the cat, can navigate. We use the term agent for any entity that uses the pathfinding system to navigate.
Here you see an old example of the Nav Mesh being regenerated when furniture gets moved.
Using the Unity Nav Mesh as our default pathfinding solution had several advantages:
- It is the go-to solution for pathfinding in Unity.
- It runs fast enough for Winkeltje.
- It is easy to set up and implement.
- It is easy to work with and adjust.
- It may cause agents to get stuck in seemingly random places without clear feedback as to why.
In games, when there is a static environment that does not move, it is relatively easy to fix issues when a pathfinding agent gets stuck on the Nav Mesh by manually adjusting the Nav Mesh. It is also common in static environments to cover up the issue by placing a random crate where the agent would get stuck. It is a blessing and a curse that Winkeltje provides players with a lot of freedom in building and decorating their shop. So it is not unthinkable that sometimes, a player creates a shop that sometimes just.. breaks.
We have tried a lot of things to try to get to the root of the problem where agents get stuck such as creating a higher resolution Nav Mesh, having the agent calculate a more accurate path, simply checking if an agent got stuck and probably about a dozen other things. Sometimes a week and a half would pass without any reported issues for this problem to pop up again. And on occasion, it would rightfully earn us a negative review.
Many of our attempts fixed the symptom of the issue in singular reproduction cases. But then the symptom would appear again in other reproduction cases. None of our attempts fixed the actual root of the issue, and we could not manage to dive into the black-box Nav Mesh pathfinding system that was provided by Unity.
A Nav Mesh is made up out of triangles and here you see an example of how an agent could very rarely potentially get into a pathfinding problem on a randomly generated sliver of a Nav Mesh splinter.
Obviously, it's madness to rely on such an unreliable pathfinding outcome with such a big negative impact to the gameplay experience. And so we made the tough decision to replace the entire pathfinding solution...
New Pathfinding - A* Grid
A thought that gained more popularity as we got increasingly more frustrated with this problem, was to just throw the entire Nav Mesh pathfinding system out the window and replace it with something else. Internally, we have fought against this notion for a very long time, because replacing such an integral system of a live game that has shipped on multiple platforms after about 5 years of development is a very risky, substantially complicated, and potentially incredibly problematic idea.
After doing significant research for a solution that addresses our use case, we arrived at the very popular and effective A* pathfinding plugin. A* pathfinding has been around for a long time and has been used in hundreds of games. Fortunately, someone by the name of Aron Granberg has developed and maintained a Unity implementation of the A* pathfinding algorithm since 2017, which has been used by Unity games like Cult of the Lamb and Void Bastards.
Here you can see an example of how the A* navigation grid looks in a shop that we have created for testing the pathfinding replacement.
The biggest difference between the two systems is that the old implementation uses a mesh and the new uses a grid. This is currently proving to be much more consistent and reliable to work with and makes debugging generally a lot easier. Hopefully, this also results in fewer problems for us to solve in the future.
The main advantage that the A* package has over the Nav Mesh system is the reduction of complexity in the surface that an agent has to traverse. The A* grid squares simply have a certain size. If an object intersects with that square, that square simply can not be traversed by an agent. Smaller sized squares will increase pathfinding precision at the expense of computation speed. We have tried to find a middle ground between accuracy and performance with our current implementation.
You will notice the A* grid the most when you rotate rectangular pieces. In the example below, you can see how some areas in blue would previously be accessible using the old Nav Mesh system but are now blocked.
Replacing the pathfinding system can cause some shop interiors to become invalid depending on how dense players have designed their shop. Most shops that we have tested work just fine. But knowing Winkeltje players, some will certainly have pushed the building system to its limits and will find that those limits have shifted a little bit. All things considered, we believe this is an overall improvement to the gameplay experience when you consider that some players would sometimes lose a lot of progress due to a pathfinding agent soft-locking the game.
We hope to have given you a valuable glimpse into this issue that, until now, has plagued Winkeltje's shopkeepers and its developers.
Patch Notes
- Gameplay - Interact radius now increases up to double the starting value at max shop level.
- Language - Updated all translations to reflect community feedback.
- Pathfinding - Replaced old pathfinding system with a new system because agents would get stuck.
- UI - The unlock menu would incorrectly show that unlocking walls at 30 appeal would increase the appeal cap.
