Pathfinding
Hi 👋, for the last months I have been working on my free time on an RTS game without a name: Unnamed RTS. I have been doing that while streaming and it has been, for the moment, a really great experience!
Investigation 🧠
We started from the beginning: learning the framework (Phaser) and the language (JS). But recently I have been working on something I find more interesting: pathfinding.
The first thing I did was checking if Phaser had something already included for that. It’s not an easy answer. Apparently it doesn’t and the way-to-go is to use an external library like easystar.js. But these libraries need a grid-based world and ours (for the moment) is not.
For non grid-based worlds I found out that a common solution is to rely on Navigation Mesh. Basically it consists of splitting the map into “walkable areas” and apply a pathfinding algorithm to the generated graph. So yes,💡, basically we get a non-grid based system and generate some kind of non-regular grid on it. There’s an additional benefit to this: it is also faster than exploring the equivalent grid-based world.
How did we do it?
We started looking for libraries and I found a couple that were supposed to work with phaser as a plugin: phaser-navmesh-generation and navmesh.
The first one, after some hours trying to get it working I realized it was implemented only for Phaser-CE edition, which is now quite old. So it was missing support for Phaser3.
The second one, looked promising but the phaser plugin included in the library relied on the fact that you had a TileMap, and I don’t. Anyway the library provides also a solution for pathfinding if you generate the mesh of polygons yourself. So we did this.
Basically the algorithm that I figured out was: start with a walkable area (square) the full size of the map. And then for every new entity in the map (buildings, resources, etc) we would just find in which square the entity would sit and then split that square into 4 different ones.
In the image above ☝️ the surrounding square is the initial polygon (P) which consists initially of the full map. Then there’s the new element (E) which basically generates the sub-squares 1 to 4.
And then there are some equations about the new squares generated (probably with some errors that I later polished).
After some trial and error we got the basic algorithm to work ⚠️ take into account that there are some corner cases that we haven’t considered yet like Elements that do not fit completely in a single square or Elements that eat previous whole subsquares.
💡 For the sake of debugging, a really good idea was to implement a debug() method that draw the full navigation mesh with multiple different colors for every square.
After this, useing the navmesh library was a no-brainer. And we could get the path and integrated it pretty easily into our Villager entities.
Issues
There were (and there are) some issues that I would like to mention.
Mesh generation corner cases
I have identified some corner cases for the basic algorithm that I have implemented. But they should be easily solvable so I am not really concerned about them. I noted them in my todo list and moved on.
- Entities occupying more than one square. Idea: divide entity into multiple squares and apply the same algorithm for every subsquare.
- Entities being bigger than some subsquares. Idea: detect and remove these subsquares as if they never existed.
- Removing elements. Idea: Either regenerate the full mesh or just create a walkable are the size of the element removed in the same place.
Getting stuck
When moving around the corner, some entities got stuck because of the way they detected when they got to a point which the path consisted of. To solve this I just made the “element” square slightly bigger than the real element size. That way there was a margin around the buildings that allowed for the entities to move with some extra space.
This originated a new issue, which was that because of collisions an entity (Villager) could potentionally be moved out of a walkable are (this extra space we added around the buildings). For this, the library had a shrink parameter that was precisely for that 💪.
Not following the shortest path
So after all this, some pretty obvious movements were following a really strange path (much longer than needed). After reading a little the code on navmesh’s GitHub I saw that it was expected and that there is an open issue about that waiting for a future version that the owner is re-writting.
The main issue was that the heuristic being used was the distance between centroids of the polygons. So if you have pretty wide or tall polygons the centroids distance would make the heuristic to take a non-shortes path. My take on this was a silly idea: 💡 get big polygons and break them down into smaller ones.
Yes, I ended up implementing an unoptimize() method. Which is silly, but for the moment has given be good results and I have reduced this non-shortest paths to a minimum.
Conclusion
It has been a more challenging situation than the rest of the project (for the moment) and even though I used some libraries that helped me avoid some work I had to implement myself something for the mesh generation which was entertaining.
There are still some parts that I need to polish, but probably when I am done with it I will try to extract that as a plugin I will share. I think it could be helpful for somebody else or even me in the future.
That’s all folks! 🥕
PS: Remember you can take a look at the code at Unnamed RTS’s GitHub.