Rts unit formation, creating a grid from random cell count

I'm creating a small RTS project and trying to implement some kind of unit formation

I'm trying to create a grid of cells which will be the formation for all the selected units. I want the formation to be as close to a square as possible.

The problem is the selected unit count might not necessarily have a count which has a square root.

This is fine when the count has a square root such as 100 units. I could just do the following

Code (CSharp):

1. for(int =0; i < 10; i++){
2.     for(int j =0; j < 10; j++){
3.     }
4. }

My problem lies when the number is something random like 74.
I know that I could grab all the factors and get the 2 closest factors and loop through them. But this won't work properly

Can anyone think of a way that I could create a grid formation when the cell counts would be random?

Thanks

 

Why not? You need to define how you want it to work.

Start with the obvious degenerate case: a prime number of units.

There are no two factors beside the count and 1 that can be multiplied to get your amount.

For instance if you have 7 units, there are no factors beside 1 and 7 that can be a side.

Draw in a picture what you want to happen and perhaps we could suggest some approaches.

 

You probably don't want to do that (because the result for primes would just be a line), but I'm not sure what you mean by "won't work properly".

Your problem is a bit unclear: "As close to a square as possible" could mean a few different things, in mathematical terms.

I would think what you probably want to do is to round up to the next square and then just put units into that grid until you run out, leaving some empty spaces. (Maybe with some additional rules about where you position the empty spaces to make it look neat, like centering the last row, or removing equally from all corners or something.)

 

Firstly thanks to both of you for responding

@Kurt-Dekker @Antistone So in the case of prime units this is what I had in mind with regards to it thinking it won't work. If was to say have 13 units selected. I'd want to create a grid like so



Obviously, 13 being a prime number, I'd only get factors 1 and 13 which would be no good to create a grid from. I would need a 4 x 4 grid in order to create this pattern.

My problem is how I get there. Despite say, 74 not being a prime number. I still don't really know how I could programmatically figure out the grid I would need. I know myself it's a 9 x 9 grid, but I don't know how to get there via the code.

I haven't even got to the stage to how I would plot the units positions using the grid itself but will hopefully figure that out once I've got a starting point.

 

Oh gotcha... it's not too hard at aall if you break it into steps.

Assuming you want the shape as close to square as possible, start with width = 1 and height = 1;

Now loop and alternately increase width and height by one and stop as soon as you have an area big enough

Code (csharp):

1. int width = 1;
2. int height = 1;
3.  
4. int count = ???
5.  
6. while(true)
7. {
8.   if (width * height >= count)
9.   {
10.     break;
11.   }
12.   width++;
13.   if (width * height >= count)
14.   {
15.     break;
16.   }
17.   height++;
18. }

Now you know the count WILL fit in width x height.

Now you can start filling that in. You have

count

units... iterate them and jam them in:

Code (csharp):

1. for (int i = 0; i < count; i++)
2. {
3.   x = i % width;    // percent is modulo
4.   y = i / width;      // divide
5. }

Using x,y you can put them in a grid.

Is that what you're thinking? Do the above steps in your mind with 13 and you'll see it will be what you want.

Antistone above lists some great ways to make it look more "reasonable" and organic.

 

@Kurt-Dekker This is exactly what I'm after. I'll go ahead and implement this now.

I'll look at further implementing some of the ideas as suggested, aswell as some different unit formations.

Thanks a lot for you help

 

Here's a one-liner, though it's always going to be square (Kurt's would be better if you want options for not-quite-square):

Code (CSharp):

1. print(Mathf.Ceil(Mathf.Pow(74, 0.5f)));

Also, for how to position them with gaps, you can easily remove X number of them randomly after they're placed too.