0

I'm creating a game, and part of the game involves large numbers of independent actors that are grouped into "divisions". The player can't control the actors directly, but they can give orders to the division, such as "move to this area". I'm looking for an algorithm that would allow the player to effectively say something like "organize into a rectangle with this aspect ratio centered around this point". I don't expect anyone to hand me the algorithm, but I haven't found a whole lot with googling so I'm wondering if anyone could point me in the right direction. Thanks!

Drew Pereli
  • 224
  • 1
  • 7
  • Why do the actors have to self-organise? Can you not just take that "4:3 rectangle at (x,y)" order, then pick *n* points on the perimeter of that rectangle and dish out those points to the actors? – Blorgbeard Nov 25 '16 at 00:54
  • What artificial-inteligence means in a game is "this game has a lot of code to make things-out-of-user-control work on their own". IOW you have to code such "automagic organizations" – Ripi2 Nov 25 '16 at 01:14
  • Do you have any additional constraints? For example, should the algorithm minimize the total distance travelled by all actors to get to their target locations? – samgak Nov 25 '16 at 01:26
  • @Blorgbeard that's my backup plan, but I wanted to avoid that route both because I'm interested in this concept more generally, and because it somehow feels less elegant. – Drew Pereli Nov 25 '16 at 02:34
  • @samgak ideally the total distance would be minimized, but in practice only to the point where the actors appear to be behaving logically. – Drew Pereli Nov 25 '16 at 02:36
  • https://en.wikipedia.org/wiki/Flocking_%28behavior%29 should give you some starting points for research – AakashM Nov 25 '16 at 09:21
  • See also [this q from the Related list over there --------------->](http://stackoverflow.com/questions/1727375/what-are-some-good-resources-on-flocking-and-swarm-algorithms?rq=1) – AakashM Nov 25 '16 at 09:45

2 Answers2

0

I'm not quite sure I'm answering the question, but here are my thoughts.

I assume the pathfinding itself isn't the problem, but rather determining the end points for each unit's movement.

Let the number of (equally sized, 1x1) units be N, and the desired rectangle's sides ratio 0<r<=1. We want to find the lengths of the rectangle's sides a and b that meets above criteria. Let's reformulate them.

a/b = r and a*b = N

In other words, a = r*b and thus r*a*a = N, which leads us to a = sqrt(N/r) and b = sqrt(r*N)

After ceiling a and b we become the size of the rectangle we were looking for (a small improvement here would be to first ceil one value, say a and calculate b as ceil(N/ceil(a))).

Tymur Gubayev
  • 468
  • 4
  • 14
-1

You could calculate a number of target locations equal to the number of agents, match each agent to a location pairwise (preferably choosing the matching that minimizes the longest distance any agent has to travel) and then have each agent find a path to its destination, such as with an A* search.

If you can’t coordinate them top-down like that, I suppose you could give each agent a goal of ending up in some target destination, preferably the closest, and have it recalculate its path whenever it sees that someone else will or already has gotten there first. That would be more complicated.

For specific shapes, you might be able to define goals that naturally result in that shape forming: if, for example, the agents try to be a specific distance from the center point and as far away from any other agent as possible, they will form the vertices of a regular polygon.

Davislor
  • 14,674
  • 2
  • 34
  • 49