# Determining the end location for AI movement in groups in a 2D RTS

I have written an RTS game (a demo for a game engine of sorts, actually) in which the user's basic interaction with the game is to select a bunch of soldiers and then right-click on the map to move them to the specified location. This is in JavaScript and you can play with it here (code).

Ignoring the problem of how the soldiers move from their current location to their destination, my question is about determining what their actual destination is. Here is what I've tried so far:

• Attempt 1: Tell all selected soldiers to move to the coordinates the mouse clicked. This has the odd behavior that all the soldiers will then go cluster around the target unnaturally.
• Attempt 2: Find the average coordinates of all selected soldiers, then find the offset from that center point for each soldier, and finally translate that offset around the mouse coordinates. This works fine except that if your selected soldiers are far apart they will not get close to the target.
• Attempt 3: Build a grid around the mouse coordinates and place each selected soldier into a cell of the grid. If each soldier makes it to their assigned cell, this works great. However, soldiers are assigned to grid cells in the order the soldiers were spawned, so sometimes they collide (i.e. all the soldiers on the right side will try to go to the left side) which looks unnatural.
• Attempt 4: Use a grid like before, but first sort the soldiers by location so that they line up sensibly, i.e. if you clicked below the group then the soldiers at the bottom of the group will end up on the bottom of the grid when they reach their destination. This works pretty well but there are glitches sometimes and I'm not sure why.

Here is the function that determines the destination coordinates:

function moveSelectedSoldiersToMouse() {
var w = 0, h = 0, selected = [];
// Get information about the selected soldiers.
myTeam.soldiers.forEach(function(soldier) {
if (soldier.selected) {
selected.push(soldier);
w += soldier.width;
h += soldier.height;
}
});
var numSelected = selected.length, k = -1;
if (!numSelected) return;
// Build a grid of evenly spaced soldiers.
var sqrt = Math.sqrt(numSelected),
rows = Math.ceil(sqrt),
cols = Math.ceil(sqrt),
x = Mouse.Coords.worldX(),
y = Mouse.Coords.worldY(),
iw = Math.ceil(w / numSelected), // grid cell width
ih = Math.ceil(h / numSelected), // grid cell height
wg = iw*1.2, // width of gap between cells
hg = ih*1.2; // height of gap between cells
if ((rows-1)*cols >= numSelected) rows--;
w = iw * cols + wg * (cols-1); // total width of group
h = ih * rows + hg * (rows-1); // total height of group
// Sort by location to avoid soldiers getting in each others' way.
selected.sort(function(a, b) {
// Round to 10's digit; specific locations can be off by a pixel or so
var ax = a.x.round(-1), ay = a.y.round(-1), bx = b.x.round(-1), by = b.y.round(-1);
return ay - by || ax - bx;
});
// Place the grid over the mouse and send soldiers there.
for (var i = 0; i < rows; i++) {
for (var j = 0; j < cols; j++) {
var s = selected[++k];
if (s) {
var mx = x + j * (iw+wg) - w * 0.5 + s.width * 0.5,
my = y + i * (ih+hg) - h * 0.5 + s.height * 0.5;
// Finally, move to the end destination coordinates
s.moveTo(mx, my);
}
}
}
}


You can paste this function into your browser's JavaScript console when viewing the demo and mess around with it to change the soldiers' behavior.

My question is: is there a better way to determine the target location for each soldier to move to?

• Something called "flocking" may be very useful to you and may provide you with the type of functionality you are looking for. Try: processing.org/examples/flocking.html or just google "flocking" or "Boids". That may put you in the right direction. – Dean Knight Jul 26 '13 at 12:28
• Related: gamedev.stackexchange.com/questions/44361 I'd say the "glitches" you're experiencing are from units that are trying to move into a position that's already been claimed. Ensure that the position they're moving into isn't the target for another unit already, and you should have pretty decent results. – MichaelHouse Jul 26 '13 at 14:10
• @DeanKnight, I'm aware of how flocking behaviors work, but that governs how the bots get from point A to point B, not what point B is. – IceCreamYou Jul 26 '13 at 21:41
• @Byte56: thanks for the link. I'm not literally putting units into grid slots -- in the implementation there is no way for multiple units to be directed to the same spot. Seems like the problem is more that the sorting sometimes gets confused. – IceCreamYou Jul 26 '13 at 21:43
• Another idea: Swarm Pathfinding. In this case, you wouldn't give each unit a different end-point; you'd just have them stop when there was no path left to the endpoint (because all the other units are in the way), or don't stop at all and let collision detection do its job. – BlueRaja - Danny Pflughoeft Aug 6 '13 at 23:49

Here are my suggestions on your ideas:

Attempt 1: To fix this situation, you could implement the "close enough" idea Spencer brought up. I would do something like drawing a bubble around the end point, that grows based on a ratio of the number and size of the units already in it. Say the bubble starts the size of one unit, then when the first gets there, the radius doubles for the next two units, etc.

Attempt 2: A fix for this one, would be take the average distance of the group from each other, then cut the distance of the outliers to that, so the group ends up more bunched than they originally were (the metric could be shorter/longer than the average, whatever makes it look decent, or possibly set a maximum form size based on the number/size of troops again) The only thing you'd have to worry about is when you alter the path of an outlier, you'd have to check and make sure it doesn't interfere with the other paths

Attempt 3: You improved on this one in attempt 4

Attempt 4: Sounds like this one would work fine if you find whatever glitches are throwing it off. I would recommend playing with spahes other than just a grid formation, though, to make the movement look a bit more natural, unless you're going for a realism/military style, in which case it might be neat to have them "form up" before moving, but that might get annoying to the player after a while.

Attempt 4 seems the closest to removing the milling behavior in your problem, but in terms of keeping the movement flowingwithout any adjusting other than what's necessary, my favorite would probably be attempt 2.

But as a different solution entirely, you can have two types of objects when it comes to pathfinding; each unit, as well as an invisible "squad" object.

Squad- You build the squad object at the center of the group, like the other solutions, and use your pathfinding to direct it towards the objective.

Units- The units ignore the goal entirely, and instead use the pathfinding to keep within a certain distance (or formation, or any other metric ends up making the movement look best) from the squad object.

This separates the different aspects of the pathfinding, and allows you to tweak either side in isolation for more control on how it looks.

• Great answer. Thanks for the new ideas. The Squad+Unit approach is interesting, probably requires that units can move faster in "catch-up" mode – IceCreamYou Aug 6 '13 at 19:01
• Yeah, a solution there is set the "squad" object's movement speed to a little under the max the single units can move, to allow them to shift around if needed without falling behind. – David M Aug 6 '13 at 19:13

Attempt 3 could work, but it needs a bit of a refinement.

Think about the concept of a formation (your grid is a start). A formation should have a location (i.e. the click coordinates, or the target soldier/building) and a rotation (this could be fixed, random or deterministic). The formation must have the same number of positions as the number of selected soldiers.

A simple example formation may be a circle around the target. Space positions equally around and increase the circle radius to fit all the soldiers without colliding.

The next problem is to decide which soldier walks to which position in the formation. A simple solution could be to make each soldier move to the position which is closest to him. If that one is already 'chosen' by another soldier, take the next closest position, etc.

Formations can become quite interesting. Below is an image of the 'bull horn formation' used with great success by Shaka the Zulu. (The image comes from the TotalWar Formation Mod)

• "The next problem is to decide which soldier walks to which position in the formation." Actually, that is the entire problem of this question. :) Upvoted for the suggestion of a circle formation instead of a grid, but that is ineffective for more than a few soldiers, and moving soldiers to the location closest to them causes more conflicts than my solution above of sorting the units by location. – IceCreamYou Jul 29 '13 at 16:55

Upon user click, draw a vector from every soldier to the clicked location. Get the average vector angle from the vectors drawn for each soldier and move each soldier the length of their individual vector in that direction with the same angle. This should give the appearance of the units moving in formation to the point and should keep the units from clumping up.

If you want the units to move out of formation, you can point every soldier's angle directly at the clicked location. However, without collision the units will start to converge. To counter this, add collision and force the units to stop moving once they're "close enough" to the point clicked. The first units to arrive will be exactly on the point and the last ones to arrive should be directed to stop moving once they are either close enough or a certain amount of time has passed.

You could calculate the length of the path and unit speed to determine when a single unit should arrive and then force the unit to stop moving if it exceeds that time by a certain amount. You'll need to play with that number a bit.

• The vector solution you're suggesting is the same as my Attempt 2 above. One of the requirements of this question is that selected units may not be in a formation. – IceCreamYou Jul 29 '13 at 16:53
• And I wrote about a solution in which they would not move in formation. (2nd paragraph) – Spencer Jul 30 '13 at 20:19