I’m working on an AI for a territory capture game similar to Paper.io where players draw lines to claim areas. The AI needs to find the best spots to create enclosures and capture empty territory.
The game works on a 2D grid where blue represents owned territory and black shows unclaimed space. The AI should identify key waypoints to create the most efficient capture path.
Basically I need an algorithm that finds the shortest route to surround the largest possible empty area. I’m thinking about using boundary detection methods but not sure which approach works best.
Has anyone implemented something similar? What algorithms would you recommend for detecting these optimal enclosure opportunities?
I built something similar for a mobile game last year. Best approach I found was mixing flood fill with modified A* pathfinding. Instead of just finding the shortest path, I weighted searches based on area-to-perimeter ratios of potential enclosures. The trick was identifying “bottlenecks” in empty territory using distance transforms from owned boundaries. These bottlenecks are usually the best spots to close off big areas with short paths. I used two phases: first finds promising enclosure spots by analyzing empty region topology, second calculates the actual optimal path for each enclosure. Watch out for concave shapes though. Basic boundary following misses chances where you could capture multiple disconnected regions with one path. I added preprocessing to merge nearby empty regions - helped tons with this problem.