I’m working on an AI for a territory capture game like Paper.io or Qix. The bot needs to find the best spots to draw lines and claim empty areas.
Basically I have a 2D grid where some cells are already owned (my territory) and others are empty (unclaimed space). The AI should figure out which empty areas are worth capturing and what path to take to surround them.
I need help with detecting these capture opportunities automatically. The algorithm should find routes that maximize the amount of empty space enclosed while keeping the path as short as possible.
Has anyone implemented something similar? I’m thinking maybe edge detection or pathfinding algorithms could work but not sure which approach would be most effective for this type of problem.
check out voronoi diagrams for this. i used them on a similar project - you calulate voronoi cells for territory boundaries, then find the largest empty regions. the diagram shows which areas are ‘closest’ to your existing territory vs enemies. add some basic distance calculations and you’ll get solid priority scoring for capture targets without overcomplicating things.
I had a similar problem with a Snake-like territory game last year. Flood fill + convex hull calculations worked great for me. Here’s the approach: use flood fill to find clusters of empty cells, then calculate the convex hull for each cluster. Check which parts of that hull you can connect to your existing territory without crazy long paths. Score each opportunity by dividing enclosed area by path cost. Watch out for concave shapes though - convex hull misses some good irregular areas you could capture more efficiently. I added A* pathfinding as a backup to test alternative routes around cluster perimeters. Performance was fine for real-time play on medium-sized grids.