6
\$\begingroup\$

I'm working on a game where a player's party can have various formations. At the moment, I'm trying to find an algorithm for box formation, where units are distributed on the perimeter of a box, spaced at a certain distance from each other (pretty common in strategy games). For the purposes of this question, I'm not concerned with the movement or rotation of the square, once it's formed -- I'm only trying to figure how to generate points on the perimeter of a box, given number of points and spacing distance between them.

I made a quick sketch of how it might look. Ideally, points would get distributed as shown in the sketch (clockwise or counterclockwise), but even distribution is perfectly fine as well, as long as minimum distance is maintained between points and away from origin.

illustration showing distributions of N=1 through N=12

In the above sketch, for N of 1 through 4, the distances between points around origin are 2D and \$\sqrt{2\text{D}^2}\$ from origin, but they don't have to be that way -- they can be D distance away from each other and from origin, to make things simpler. So, it should look more like this: illustration showing some alternate distributions The distance to the origin should not be less than D and of course will be greater as N grows, and distance between points should be no less than D, but can be greater if a side has less points than any other side.

New contributor
B.K. is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

3 Answers 3

Reset to default
4
\$\begingroup\$

Another way that should give you basically the same results as DavidT's answer, but perhaps with simpler code:

Step 1: Divide your square formation into four rows. Each row starts at a corner position and extends from there in a consistent direction (let's say clockwise, it doesn't really matter much) around the square.

Adapting DavidT's ASCII art notation, here are the four lines of 3 units each in formations of N = 4, 8 and 12 units. I've labeled the units in each line as F(front), L(left), R(right) and B(ack):

N = 4     N = 8      N = 12

F R       F-F R      F-F-F R
              |            |
L B       L   R      L     R
          |          |     |
          L B-B      L     R
                     |
                     L B-B-B

Step 2: Arrange all the units in each line so that the spaces between them and between the last unit and the next corner are equal.

(This effectively hides the asymmetric choice of whether to extend the lines clockwise or counterclockwise from the corners. Either way, the corner spots will always be filled as long as N ≥ 4 and the rest of the units on each side of the square will be evenly spaced between the corners.)

Step 3: Decide how many units to put in each line.

If the number of units is divisible by 4, you can (and probably should) just put the same number of units in each line. If not, you will have to add one extra unit to some lines.

The pictures in your question effectively match a filling order of F(ront) -> R(ight) -> B(ack) -> L(eft), and if that's what you like, it should work perfectly fine.

DavidT, however, suggests what's effectively an alternative filling order where you start by putting the first extra unit in the F(ront) row and the second in the B(ack) row, but if there's a third extra unit, you remove the second unit from the back row and move it and the third unit into the L(eft) and R(ight) rows. This has the arguable advantage of always keeping the same number of units on the left and right sides of the square and thus keeping the formation always symmetrical. (Well, at least for N ≠ 3.)

Of course there are also other options, like F(ront) -> R(ight) -> L(eft) -> B(ack), which doesn't quite always maintain symmetry but avoids moving units between rows as new units are added to the formation.

Or you could even let the player explicitly choose how many units they want on each side of the formation. If most threats are coming from the front, maybe they'd rather have only one or two units in the back and a bunch of extra units in the front, for example. Of course whether it makes sense to offer the player such flexibility (and the associated UI complexity) depends on the type of game you're making.

Step 4: Decide how big the square should be.

It probably makes sense to make the size of the square proportional to the number of units in the longest line. That way, the minimum distance between adjacent units in the square will be constant.

The distance between the units and the PC in the middle of the square will also always be at least 1/sqrt(2) ≈ 0.7 times the minimum distance between two units. If this feels too crowded, you could make a special case for N ≤ 4 and multiply the size of the square by some scaling factor between sqrt(2) ≈ 1.4 and 2 in that case. To me, a factor of 1.5 suggests itself as a pretty simple and natural approximation of sqrt(2), but you can decide for yourself what looks and feels best to you.

\$\endgroup\$
2
  • \$\begingroup\$ Yep, that's basically what I ended up doing. Was about to post my solution, but yours is pretty close to mine. Ended up being a pretty clean approach, with no special-case handling, aside from having a few properties to control point spacing and minimum distance away from origin, in case it gets crowded with small numbers. \$\endgroup\$ Commented yesterday
  • \$\begingroup\$ Oh and I also made it so that while I'm filling up the four side groups, I'm doing it in order of Front > Right > Left > Rear, so that point distribution favors filling up sides completely before finishing up the rear, instead of the circular approach in my question's diagram. \$\endgroup\$ Commented yesterday
5
\$\begingroup\$

I think it best to tackle this on a case by case basis:

N = 1, 2, 3 or 4

Since there are only 4 possible cases I wouldn't spend too much time trying to create rules for these small groups, I would just hard code 4 patterns I liked.

Your rule of at least D from the origin forces these formations to spread out more than the later "generic" rules would - hence why I think it's better to hand code these formations.

N % 4 = 0

When the group size is an exact multiple of 4 (8, 12, 16, ...) the pattern is totally symmetric/regular, with all corners and sides filled.

The overall width (and height) of the formation is just: N / 4 * D

So you can just loop through generating each of the positions.

One caveat is that N = 12 (and 20, 28, ...) there is a 0.5D offset from the origin. For N = 8, 16, 24 etc the origin is on the regular grid with all the other locations.

N = 5, 6 or 7

This is just the N = 8 formation with some position removed.

I am calling this out as being different to larger groups, since you only need to delete positions where as larger group also have to move some positions from the "regular" grid.

N % 4 = 2

I think it might make sense to review N = 10 in that you may want to use:

O O O O
O     O
O O O O

If so, that would generalize to all N % 4 = 2 formations, specifically all such formation will always be 1 position wider than they are high, however otherwise they are regular patterns.

All other sizes

In all other cases I would simply take the formation 1 larger (N + 1) then delete a position on the back rank and adjust the remaining positions so that they are evenly spaced, so the progression looks like this:

N = 8        N = 9          N = 10       N = 11       N = 12       N = 13

O O O        O O O O        O O O O      O O O O      O O O O      O O O O O
O   O        O     O        O     O      O     O      O     O      O       O
O O O        O  O  O        O O O O      O     O      O     O      O       O
                                         O  O  O      O O O O      O  O O  O

ASCII Art is a little lacking for N = 13 the last row should be evenly spaced.

Note: You might want to review the smaller sizes so that the are consistent with this pattern.

\$\endgroup\$
0
\$\begingroup\$

Code by example.

The array edges defines 4 edges that hold the tokens, this lets you set the direction (CW or CCW or interweaved).

All the coordinated are for a unit square with 0.5, 0.5 at the center. The coords are scale just when each mark is drawn.

The constant spacing defines the distance between tokens (the big spacing).

The call to drawTokens(count) does it all, sets the number of tokens, scales the edges, and draw each edge in turn.

Use the buttons to add and remove tokens (Note I have not set a limit so if the count is too high the tokens will be drawn outside the canvas)

Example code

const ctx = canvas.getContext("2d");
const w = canvas.width;
const h = canvas.height;
var count = 0;
const spacing = 0.1;

const edges = [
    { count: 0, start: {x: -0.5, y: -0.5}, end: {x:  0.5, y: -0.5} },
    { count: 0, start: {x:  0.5, y: -0.5}, end: {x:  0.5, y:  0.5} },
    { count: 0, start: {x:  0.5, y:  0.5}, end: {x: -0.5, y:  0.5} },
    { count: 0, start: {x: -0.5, y:  0.5}, end: {x: -0.5, y: -0.5} }
];
function setTokenCount(n) {
    const edgeMin = Math.floor(n / 4);
    const remain = n % 4;
    var idx = -1;
    while (++idx < 4) { edges[idx].count = edgeMin + (remain > idx ? 1 : 0) }
    countEl.textContent = "Count: " + n;
}

function drawToken(x, y, col, rad) {
    ctx.fillStyle = col;
    ctx.beginPath();
    ctx.arc(x * w, y * h, rad, 0, Math.PI * 2);
    ctx.fill();
}

function drawEdge(edge, scale) {
    if (edge.count) {
        const sx = (edge.end.x - edge.start.x) / edge.count;
        const sy = (edge.end.y - edge.start.y) / edge.count;
        var i = -1;
        while (++i < edge.count) {
            drawToken(
                0.5 + (edge.start.x + sx * i) * scale, 
                0.5 + (edge.start.y + sy * i) * scale,
                "#C00", 5
            );
        }
    }
}
function drawTokens(n) {
    ctx.clearRect(0, 0, w, h);
    drawToken(0.5, 0.5, "#000", 8);
    setTokenCount(n);
    const scale = spacing * (Math.floor((n - 1) / 4) + 1);
    for (const edge of edges) { drawEdge(edge, scale) }
}

drawTokens(0);
removeBtn.addEventListener("click",() => { if (count > 0) { count --; drawTokens(count); }});
addBtn.addEventListener("click",() => { count ++; drawTokens(count); });
#removeBtn{
    position: absolute;
    top: 10px;
}
#addBtn{
    position: absolute;
    top: 40px;
}
#countEl{
    position: absolute;
    top: 70px;
}
<canvas id="canvas" width="256" height="256"></canvas>
<input id="removeBtn" type="button" value="remove"><input id="addBtn" type="button" value="add"><span id="countEl">Count: 0</span>

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.