Thia post is about production of Battle of BackYard.
Pathfinding in Battle of BackYard was a real challenge. Unlike many games that rely on 2D navigation layers or predefined paths, our game needed to handle full 3D movement, dynamically changing environments, and a huge, player-modifiable map. Oh, and it had to run smoothly on regular gaming machines.
So why not use something off the shelf? Because nothing really fit within these constraints.
Planning the Pathfinding System
I based my approach on A* pathfinding, as it’s one of the most efficient algorithms for real-time pathfinding. However, plain A* wasn’t enough. With maps as large this one, running A* on every movement would have been disastrous for performance. So, I introduced optimizations and a multi-layered system to balance efficiency and accuracy.
Here’s the basic idea:
- If a plane has a clear line of sight to its target (determined by a raycast), it flies straight there—no heavy calculations needed (and pathfinding calculations turned out to be HEAVY)..
- If an obstacle is in the way, A* finds the shortest path around it.
- For long-distance navigation (across multiple rooms or the entire map), I implemented a higher-level pathfinding system that divides the map into sectors.
- A breadth-first search finds the optimal sequence of sectors before A* refines the local paths.
- Pathfinding is handled server-side to ensure smooth performance for all players.
Breaking it down further, I needed:
- A method to divide the map into small chunks that are quick to check for collisions.
- A system to link areas into a network that can be searched efficiently.
- An optimized A* implementation that wouldn’t overload the game.
Implementation: Making It Work
Mapping the Environment
The game world is stored as a 3D boolean array, where [true] represents an obstacle and [false] represents open space. Since maps are large, I had to be smart about handling data efficiently:
- A static obstacle map is precomputed in the editor for permanent objects (walls, trees, etc.). This process is slow, but it only needs to be done once. It’s my perfect excuse for a coffee break. Still: I divided these calculations into blocks, so I’d have time for a coffee and not re-reading of Dune.
- A dynamic obstacle map is created at runtime for movable objects like doors, furniture, and user-generated content. Any object tagged as PathfindingObstacle updates the array when the mission starts.
Handling Changing Environments
Doors and windows were particularly tricky because they change the connectivity of rooms.
- An open door needs to enable movement in one area while blocking it where the door physically swings.
- Every time an entryway opens or closes, the pathfinding system rechecks connections between rooms.
To prevent constant recalculations, I optimized the system to only update affected areas instead of scanning the entire map.
Bots Need to Move!
Once I had a working traversability map, I had to ensure that AI-controlled planes could move through it efficiently and believably.
The Pathfinding Algorithm
- If the bot can see its target, it flies directly there—simple and effective.
- If the bot can’t see its target, A* pathfinding kicks in. Since A* can be expensive, strict limitations were added:
- A* runs in small bursts (processing max 75 nodes per frame to avoid performance spikes).
- It stops after 10,000 iterations—if no path is found by then, we assume no valid route exists.
- At 60 FPS, path calculations take 2-3 seconds; at 30 FPS, they take 4-5 seconds, which is still acceptable.
- Once a path is found, it’s simplified to remove unnecessary waypoints.
- If position n can see position n+5 but not n+6, the path is optimized to go from n to n+4.
- This prevents planes from making sharp, unnatural turns that will exist in simplification n to n+5.
- If no path is found:
- If the destination is in a different sector, breadth-first search finds the closest sector before A* handles the local navigation.
- If the destination is in the same room but unreachable (e.g., inside a box), the bot gives up and looks for an alternative action.
Final Thoughts
This was one of the toughest problems I’ve tackled in Battle of BackYard, but it was also one of the most rewarding. Balancing efficiency, adaptability, and realism in a destructible, ever-changing environment wasn’t easy, but the end result is an AI that moves in a way that feels… maybe not extremally natural, but is efficient and dynamic.
Pathfinding is often an invisible system—when it works, no one notices it. But making it work in a game where players can reshape the entire battlefield? That was an adventure all on its own.
And now, after all that, I never want to see another pathfinding algorithm again… until the next project, of course.