Published on

Devlog #56 - Path Finding v1

Path Finding v1

When it comes to moving characters through a game world, pathfinding algorithms help figure out which steps to take to reach a destination efficiently. Many of these algorithms rely on something called a heuristic, which is a smart guess that estimates how far a point is from the goal. This helps guide the algorithm toward better routes without checking every possible option.

Here are some of the most commonly used pathfinding algorithms in games:

  • A* – Finds the shortest path using both distance traveled and estimated distance remaining. Great for accuracy and performance.

  • Dijkstra’s – Like A* but without a heuristic. Guarantees shortest paths but is slower and explores more.

  • Breadth-First Search (BFS) – Simple and guarantees the shortest path on uniform grids. Not efficient for large or weighted maps.

  • Greedy Best-First Search – Fast and heuristic-driven, but doesn’t guarantee the shortest path.

  • Jump Point Search (JPS) – Optimized for grids; skips unnecessary nodes, speeding up A* without sacrificing optimality.

You can actually play around with all these algorithms and visualize how they work here:
https://clementmihailescu.github.io/Pathfinding-Visualizer/

This is what A* looks like. The blue are visited nodes and the yellow is the path it found.

After doing a deep dive on A* I found that there's a version called Bi-Directional which searches from the start and the goal at the same time. This is even faster. Check it out here:
https://qiao.github.io/PathFinding.js/visual/

This shows what FO2's new path finding algorithm is doing. It's Bi-Directional A* using the Manhattan heuristic which performed best for FO2's map type.

Now that we have a good overview of what path finding is and which algorithm we're using, we can dive into FO2's actual implementation.

CollisionMap

A collision map like https://game.fantasyonline2.com/tiled/maps/crab-coast-collision-1bit.png is a pixel-perfect binary mask that defines where movement is allowed or blocked.

Each pixel represents a single in-game coordinate:

  • Black pixel = blocked (you can’t walk there)

  • White pixel = walkable (you can move freely)

When the game loads a collision map, it downloads this image and reads it pixel by pixel on another thread. To save memory and speed things up, the game compresses this data into a compact format, using just a single bit per pixel. The game can then instantly check if any location is blocked just by looking up that bit in memory.

What Happens When You Click

When you click to move in FO2, the game runs Bi-Directional A* with the Manhattan heuristic to calculate a path from your character to the target location using a collision map. Once a path is found, it trims waypoints that are too close to avoid jitter and then runs a line-of-sight pass to remove unnecessary steps. The first valid point becomes the new movement target, and the remaining waypoints are saved for continued movement.

To keep pathfinding performant on FO2's 4096×3072 pixel collision maps, we limit how far the algorithm is allowed to search. Instead of scanning the entire map, we define a square search area centered on the player. This area has a fixed dimension, currently 512 pixels in each direction, which keeps memory usage low and avoids long computation times. On an M1 MacBook, typical pathfinding requests take anywhere from 1ms to 120ms depending on how many obstacles are nearby and how winding the path is. All of this runs in a background thread so the main game thread stays responsive. If there’s a clear line from the player to the destination with no collisions, we skip the full pathfinding and return a simple 2-point path immediately.

All of this pathfinding logic runs entirely on the client. The server doesn’t calculate paths, it only receives movement updates from the client at fixed intervals. These updates include where the character started moving from and where they’re heading. By limiting how often these messages are sent, the game avoids flooding the server while still keeping player movement in sync across the network.

That covers the basics of pathfinding in FO2. The system is designed to balance accuracy and performance, handling detailed collision maps while keeping the game responsive.

FO2 Path Finding v1 will go live with ToLS on April 1st.

Have Fun & Keep Gaming!
See you next patch notes!

P.S. - This makes walking around Frozen North so much nicer. Just click on the other side of a wall and your character will start walking there!