javascript - 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?

Answer

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.