I am envisioning a game/problem where there are two teams of players and the goal of each team is to capture all other players. The way you capture a player or group of players is by surrounding them. This is similar to the game of Go, but I''m thinking of a real time situation (doesn''t have to be a fast, high-speed real time situation though, just fast enough to see the two teams fight it out). I don''t have any set rules yet. I''m considering several variations. I think I will start with a set number of neutrally placed players and let them go. One variation might be to add extra players every so often (every few seconds?) via some entry point. A team could block off an opposing team''s entry point by surrounding it, preventing new players from entering the game. Maybe you could have multiple entry points per team. Another variation is that if you surround an enemy player, that player becomes a member of your team. Another idea I had was to allow the players to build walls, allowing them to imprison the enemy that way. So far this wouldn''t be very interactive, and more of a spectator thing. One idea I had was to make it a turn based game, where each turn a player could either move a player on his team, add another player from the entry point, or build a piece of a wall. I think the problem of surrounding an opponent is an interesting one, and the fact that computer Go playing programs are very weak against humans hints that this is probably not an easily solved problem. I''m not particularly good at Go myself, but the few times I have played I thought I had my opponent surrounded, only to realize that my group that was doing the surrounding was being surrounded. Anyway, I''d like some input on how I could go about creating AI for this, and also any variations on the game are welcome, and any ideas about how to allow a single player to play against the computer are also welcome.

Is the playarea going to be discrete/tile-based, like most board games, or continuous like most computer games? The algorithms you use would probably differ depending on this.

My initial thoughts would revolve around splitting it into attack and defence.

Attack could be done with some sort of influence map, measuring opponent concentration. The more densely they are concentrated, the more you will gain by capturing that area and the less work it involves, due to the smaller radius required.

Defence could involve finding rough circles of opponents by sampling an area and finding the centroid, then evaluating the threat to one of your team as being proportional to how close they are to that point. Or perhaps by running a search to some arbitrary depth from a team member, counting how many opposing units are nearby and therefore posing a threat.

Ideally then, at a coarse level, players would move from areas where the Attack:Danger ratio was low to where the Attack:Danger ratio was high. Orchestrating the actual surrounding of an opponent sounds tricky, but not impossible. You'd be looking for positions that are both adjacent to a friend and of an equal distance to an opponent as that friend is. Eventually a circle would be formed.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

[edited by - Kylotan on April 15, 2003 5:44:40 AM]