I’m working on an AI for a territory capture game (like Paper.io or similar area-claiming games). The bot needs to find the best spots to draw lines and claim empty spaces.
Basically I have a grid where some cells are already owned (marked as occupied) and others are empty (need to be captured). The AI should figure out which path to take so it can surround the biggest empty area with the shortest possible route.
Right now I’m thinking about using some kind of boundary detection method, but I’m not sure if that’s the right approach. Has anyone worked on something like this before? What algorithms would work best for finding these optimal enclosure paths?
The main challenge is that the AI needs to balance between capturing large areas and keeping the path length manageable.
Had this exact problem building a mobile territory game. Stopped thinking about it as pathfinding and treated it like risk vs reward optimization instead.
I calculate a “capture efficiency score” for each move. Three factors: area size, path length, and how long you’re exposed while drawing.
Run BFS from your position to find all empty regions you can reach. For each region, calculate the minimum rectangle that’d capture it. Key trick - use existing occupied cells as anchor points. Leverage walls and boundaries already there.
My scoring formula: (area_gained^1.5) / (path_length + exposure_penalty). The 1.5 exponent makes bigger areas way more valuable, which matches how these games actually work.
Caching boundary calculations was huge for performance. Most of the map doesn’t change between moves, so you can reuse tons of computation.
Biggest takeaway - perfect optimization is pointless. Players can’t execute pixel-perfect paths anyway. An 80% solution that runs smooth beats a 100% solution that lags.
Been dealing with this exact problem in my game dev work. What worked best for me was Voronoi diagrams to find territory boundaries, then dynamic programming for path optimization. Don’t bother with individual empty cells - segment the map into regions based on distance from existing borders. You get natural capture zones you can evaluate for area gained vs perimeter cost. The trick is treating it like a convex hull problem. Find the minimal path that grabs maximum empty space. My scoring function penalizes sharp turns and rewards smooth curves since they’re easier to defend. For performance, preprocess the grid into distance fields - saves tons of computation when making real-time decisions.
Honestly, treating it like a TSP variant was the easiest approach for me. I’d find clusters of empty cells first, then calculate the minimum spanning tree between cluster centers. Way less complex than Voronoi stuff and runs faster too. Just remember to add some randomness or your opponents will predict your moves easily.
I built something similar for a strategy game last year. Here’s what worked: I combined flood fill with modified A* pathfinding. Flood fill identified all empty regions and calculated their value by size. Then A* found the shortest path around each region, weighing both path cost and area reward. The trick was preprocessing the grid to spot bottlenecks and natural boundaries that’d cut down the enclosure path. I’d suggest starting with a greedy approach as your baseline - it performs way better than you’d expect and helps you validate the fancier algorithms later. One gotcha: partial enclosures can be more valuable than complete ones, especially with opponents nearby.