I’m working on an AI for a territory capture game similar to Paper.io and Qix where players draw lines to claim areas. The challenge is getting the computer player to recognize good opportunities for territory expansion.
In my game, blue represents claimed territory, black shows unclaimed space, and I need the AI to find the best path (green/white points) to surround and capture the maximum black area with minimal movement.
Basically I need to solve this problem: what’s the most efficient route that can enclose the largest possible empty region?
I’ve been thinking about edge detection or boundary following algorithms but I’m not sure if that’s the right approach. Has anyone implemented something similar or know what algorithms work best for this type of pathfinding problem?
Been there with a similar game project a few years back. The breakthrough came when I stopped thinking about it as pure geometry and started treating it like resource allocation.
What worked for me was using a heat map approach combined with safety zones. I divided the grid into influence regions and calculated ‘heat values’ based on both opportunity and risk.
Each empty cell gets scored on three factors: how much area it could unlock, how safe the capture path is, and how it affects your overall territory shape. The safety part is crucial - I learned this the hard way when my AI kept making aggressive moves that left it exposed.
I used a modified Dijkstra to find capture paths, but weighted the edges by exposure time rather than just distance. Cells closer to opponents or territory boundaries get higher risk weights.
The real game changer was adding momentum tracking. Instead of evaluating each move in isolation, I tracked multi-move capture sequences. Sometimes a mediocre first move sets up an amazing second move.
For performance, I only recalculate the full heat map when territory changes by more than 5%. Between updates, I just adjust scores locally around the changes.
This video breaks down some solid opening strategies that might give you ideas for scoring different territory shapes:
One more tip - cap your lookahead at 2-3 moves max. Territory games are too chaotic for deep planning to pay off.
I hit the same problem making a grid expansion game. The trick is realizing you’re solving two problems at once - geometric efficiency AND strategic positioning. I used Voronoi diagrams to find natural expansion boundaries, then dynamic programming for optimal capture sequences. Each potential expansion has immediate value plus future potential. I scored regions by their ‘expansion coefficient’ - basically how much extra territory they’d unlock later. Took me months to learn this: don’t just grab maximum area per move. You need defensive value and connections to your existing territory. Isolated captures look tempting but they’ll bite you later. For performance, I did rough scoring on 4x4 blocks first, then detailed analysis only on the good spots. Aggressive pruning helped too - I’d eliminate any paths crossing existing optimal routes. The algorithm evaluates during opponent turns so decisions stay snappy even with weird territory shapes.
Hit this exact problem building a mobile territory game last year. Stopped thinking pure pathfinding and switched to risk-reward optimization - that’s what cracked it. I built a sector-based system that works great. Don’t analyze every possible path - divide unclaimed areas into sectors using a modified watershed algorithm. Score each sector on capture difficulty vs potential reward. My scoring looks at distance from current territory, turns needed for capture, and defensibility of the final shape. Long skinny captures give you area but make you vulnerable. Pre-computing ‘capture templates’ was huge for performance. I made common patterns like L-shapes, rectangles, corner cuts that work in most situations. AI picks the best template per sector instead of computing paths from scratch. Watch out though - account for opponent interference. Territory games change fast so your AI needs to bail on captures that get too risky.
just go with greedy BFS and weight by area. calculate how much area each move could enclose, then pick the best one. way simpler than voronoi - i went down that rabbit hole and totally overengineered it. only look ahead 3-4 moves though, anything more is pointless since the game changes too fast.
