New pathfinding system

A browser game made in HTML5

Posted March 17, 2025 by Mount Fuji Software

#rts #pathfinding

When I get a negative feedback about how 535 performs, the most common issue is about units' pathfinding.

This was implemented using a very simple script that updated the direction at every step analyzing the solid object around the moving character, and while it was ok for most of the situations, it lacked precision in more long and complex paths.

I'm now implementing a new movement and pathfinding system based on the Dijkstra algorithm (Flow field), subidividing the map in small cells (32x32 pixels each) and calculating the path from the start. It's still work in progress and I know it will take a lot of time to implement, but here you can see the first results:

So, each time a solid object (a building or a resource like a tree) is added/removed from the map the system creates a grid like this one, called cost field: green cells are free and have a cost of 1, while red cells are in collision with a solid object and have a cost of 1000, like the image below (old one btw, the new algorithm is even more precise)

The final field (the flow field itself) is calculated on the goal field, giving for each cell the direction (in degrees) to follow in order to reach the destination on its shortest path avoiding solid object.

Files

535_250126.zip 53 MB
Jan 26, 2025