In this devlog, I want to share how a simple and familiar algorithm Flood fill helped me massively speed up pathfinding in my game.

Why Bother?

Imagine you have a big map filled with obstacles: houses, walls, trees, etc. When a creature wants to move from point A to point B, the game needs to figure out if its even possible to get there.

Running a full pathfinding algorithm every time even when there's clearly no path wastes time and resources. So I decided to precalculate which areas are actually connected and only allow pathfinding when it makes sense.

[img src="https://clan.cloudflare.steamstatic.com/images/40199210/6f9de5bc1de8914116a4da35a00402f2085ed85d.png"][/img]

The Idea: Divide the Map into isolated zones

Every time the player places an unwalkable structure (like a wall) on a tile, the game runs a Flood fill algorithm from each walkable side of that tile.

The algorithm explores all reachable walkable tiles connected to that side and tries to form a new isolated zone.

You can think of it like pouring paint from each side of the blocked tile each "puddle" becomes its own zone.

[img src="https://clan.cloudflare.steamstatic.com/images/40199210/ca8132393eee939e20e913233ca8a8206be299ed.gif"][/img]

As a result, instead of running expensive pathfinding calculations, creatures in the game now simply check whether their destination tile is in the same zone theyre currently in.

If it is go ahead and search for a path.

If its not no need to try: there's clearly no way to get there!

Support me on Boosty: https://boosty.to/ricktechnolithic