🔒 Locked

War Strategy

Started by daniel_i_l Mar 10, 2007 at 1:02 PM 7 replies 2.2k views

Original Post

Mar 10, 2007 at 1:02 PM

I was browsing the web to see how a RTS ai was implemented (i was looking into the fighting part) - how to get the ai to use it's troops in an coordinated way... Almost everything i read used some kind of FSM together with a hierarchy of general->squad->unit or something like that. As i was reading a different approach suddenly came to me. What you do is divide the map (or at least the part that they're fighting in) into a grid with the size of each cell about the size of 5 units. Then you make the whole fight into an attempt to occupy the best (or most) squares (the occupier is the ones with the most units in the square). then, every few frames the ai has 3 options for every occupied square: 1) move troops (not necessarily all) from this square to another (neighboring) empty square. 2) move troops (not necessarily all) from this square to another (neighboring) occupied square. 3) "clear out" an enemy square (by killing the troops in the enemy square). Then you have to define what "good square" are. I'm not sure about this but you could define the value of a position by the number of squares that it lets you control - you decide who controls a square by checking who has an occupied square closest to that square. So for example, if the enemy occupies 4 squares in the middle: (-1,1),(1,1),(-1,-1),(1,-1) then occupying the 4 squares (-2,2),(2,2),(-2,-2),(2,-2) would be optimal because that means that you control the whole map except for the 4 ones in the middles. now the only move left to control more squares is move 3 - to kill the ones in the middle. so if the enemy is in the middle and the ai is scattered around the map the ai would surround and then kill the enemy. A refined version of this model could potentially give a flexible and pretty unpredictable (in the good way:) ) ai. What do you think?

Timkin

Mar 11, 2007 at 9:41 PM

You're describing a technique known as Influence Mapping... or more precisely, the use of influence maps to design strategic behaviours.

ID Merlin

Mar 14, 2007 at 8:16 PM

The influence map seems like a good, simple approach to use. I read that there's a two-pass algorithm to generate that. I have something close, but the factors aren't quite right. Anyone know of a source for the correct code?

	// generate influence map	for ($u = 0; $u < count($map_units); $u++) {		$x = $map_units[$u]['tactical_x'];		$y = $map_units[$u]['tactical_y'];		$z = $map_units[$u]['number'] * $map_units[$u]['level'];		if ($map_units[$u]['player_id'] == $player_id)			$inf[$x][$y] -= $z;		else			$inf[$x][$y] += $z;	}	for ($x = 0; $x < X_MAX; $x++) {		for ($y = 0; $y < Y_MAX; $y++) {			$tmp1[$x][$y] = $inf[$x][$y] / 2 + ($tmp1[$x-1][$y] + $tmp1[$x][$y-1] + $tmp1[$x-1][$y-1]/2) / 3;		}	}	for ($x = X_MAX - 1; $x >= 0; $x--) {		for ($y = Y_MAX - 1; $y >= 0; $y--) {			$tmp2[$x][$y] = $inf[$x][$y] / 2 + ($tmp2[$x+1][$y] + $tmp2[$x][$y+1] + $tmp2[$x+1][$y+1]/2 + $tmp1[$x+1][$y-1] + $tmp1[$x-1][$y+1]) / 3;		}	}	for ($x = 0; $x < X_MAX; $x++) {		for ($y = 0; $y < Y_MAX; $y++) {			$inf[$x][$y] = round($tmp1[$x][$y] + $tmp2[$x][$y]);		}	}

ID Merlin

Mar 15, 2007 at 10:02 PM

There's no NN suggestion?

tonyg

Mar 16, 2007 at 4:47 AM

Quote:
Original post by ID Merlin
There's no NN suggestion?

There is if you check 'Strategic Decision-Making with Neural Networks and Influence Maps' in AI Programming Wisdom 2

LorenzoGatti

Mar 16, 2007 at 5:04 AM

The influence map idea seems good, but I see some potential weaknesses that should be addressed:
a) Spreading forces to control a large area instead of concentrating them to attack individual targets.
A typical RTS, like real warfare, obeys Lanchester's laws (Wikipedia) and rewards overwhelmingly stronger forces with a swifter victory and reduced losses.
There should be a plan of what enemy units and map locations that should be attacked as strongly as possible one after the other.
b) Sending forces to useless places, letting the enemy penetrate weakly defended locations. There should be some evaluation of defensive needs, to prudently delay advance until attacking enemy forces are engaged and defeated.
c) neglecting reserves in controlled territory, sending all troops to the front in a wide and shallow formation that the enemy can pierce like a balloon. Maybe there could be designated reserve units that advance behind front line units.

Palidine

Mar 19, 2007 at 7:44 PM

Just to be pedantic an "influence map" is just a data structure, not a strategy. What the OP suggest would be one of thousands of ways to use an influence map to create RTS AI strategy.

LorenzoGatti points out some pretty significant weaknesses in the OP's theory. Specifically, the way in which you're using the influence map is basically a flood fill. A flood fill would maximally thin out your troops to occupy the maximum amount of area: not a very sound military strategy because any point along your line is therefore maximally weak.

An influence map is definitely a good place to start thinking about RTS strategy, but you should think of it more as data and less of a self-contained strategy.

Interesting old thread about influence mapping and various ways in which they could be used in a wargame:
http://www.gameai.com/influ.thread.html

Other things that influence maps are great for: unit behaviors (by querying a local influence map you will easily see which gradients to follow for attacking or retreating. You can easily identify flanks and weak points along the enemy lines. You can pass over it with some clustering algorithms to get an understanding about how many discreet armies you are facing.

-me

Timkin

Mar 20, 2007 at 6:14 AM

Quote:
Original post by Palidine
Just to be pedantic an "influence map" is just a data structure, not a strategy.

I don't believe anyone was claiming that an influence map was a strategy. But an Influence Map is more than a data structure; it's a functional statement regarding influence. In that vein, it is a tool for strategic analysis, which is what has been mentioned previously.

IADaveMark

Mar 20, 2007 at 8:28 AM

One good thing to do is to layer the influence maps in terms of structures and military, for example. If you find a delta in a certain area that shows unprotected structures, you have identified it as a "weak spot". Send your military there. Of course, you can also add these sorts of things as terrain cost weights in pathfinding. (Traversing the swamp actually might be better than going through the teeth of the enemy.) Like Timkin says, it's a tool. What you do with it is up to you.

On that note, the OP's idea of surrounding units is not exactly a flood fill. You can use an IM to determine flanking positions, etc.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.