I’m working on an AI system for a territory capture game (like the classic arcade games where you draw lines to claim areas). The AI needs to identify the best spots to create enclosures and claim empty territory.
In my game setup, I have a 2D grid where blue represents already owned territory, black shows unclaimed empty space, and I need to calculate optimal waypoints for the AI to traverse. The goal is to find the most efficient path that will surround and capture the largest possible area of empty space.
I’m thinking this might be solved using boundary detection algorithms or pathfinding techniques, but I’m not sure which approach would work best for identifying these concave regions that would be good targets for enclosure.
I built something like this for a mobile territory game a couple years back. What worked best was mixing flood fill with a scoring system that looked at perimeter-to-area ratios. Instead of hunting for the biggest possible area, I had the AI find spots where it could close off territory with the shortest path while grabbing the most space. The trick was treating it like a cost-benefit problem, not just pure optimization. I used a tweaked A* algorithm to check potential enclosure paths - the heuristic weighed both how far you’d need to go to complete the loop and how much area you’d actually capture. One thing that really helped was pre-processing the grid to spot “natural boundaries” where existing territory or obstacles could cut down the perimeter needed. Made the AI way more strategic about going for quick, easy captures versus risky big area grabs.