• Create Account

We need 7 developers from Canada and 18 more from Australia to help us complete a research survey.

Support our site by taking a quick sponsored survey and win a chance at a \$50 Amazon gift card. Click here to get started!

# Making flocking groups?

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1falconmick  Members   -  Reputation: 80

Like
0Likes
Like

Posted 28 March 2012 - 11:54 PM

For a game I am working on, I decided to reduce the computational load that I would split the units which have been given the same command, as in a move or an attack command. That way, rather than having 100 A* algorithm implementations I would have 15 or so. right now I am working on the theory on how the units will be split up, I want to make these groups as big as possible within a given radius without impacting computational requirements too much... As little processor time, the better.

This is my idea.

start at the start of the selection of units. Get it's location and find all of the units around it within a given radius (the flocking group radius) then, combine all of the locations of the items selected and form an average of all the units in the flock group. From that once again check and see if there are any more units to add to the flock... see the image below. The only issue I have with it is that if it keeps on adding units it will start to no longer include the bottom left unit, therefore I would have to every time it formed a new flock radius have to check to ensure that none of the older units were dropped... This would be computationally expensive possible :\... Is there some magical algorythm which splits units up into smaller groups? Something like what I have but less computationally expensive

### #2falconmick  Members   -  Reputation: 80

Like
0Likes
Like

Posted 29 March 2012 - 02:15 AM

Ok, talked to my tutor... We made an idea that rather than forming groups through radius we form them by splitting the map into quadrants and when an entity moves it checks if it has moved quadrants if the next iteration of the server is updating the A*, if so, removes from quadrant, and adds to new quadrant, during A* algorithm update, assigns A* to all of the quadrant groups that have one or more units in them...

haha hopefully this helps someone

### #3Álvaro  Crossbones+   -  Reputation: 16538

Like
1Likes
Like

Posted 29 March 2012 - 06:09 AM

Instead of a hundred A* you can run a single Dijkstra from the target and compute all the paths at the same time. Is that an option?

### #4menyo  Members   -  Reputation: 560

Like
0Likes
Like

Posted 30 March 2012 - 12:24 PM

Instead of a hundred A* you can run a single Dijkstra from the target and compute all the paths at the same time. Is that an option?

I say that is a great suggestion, at least i think that will fit my current project very well. I used to use Dijkstra when i started pathfinding, but now using a lot of A* while i could simply do a Dijkstra on a specific region to attract enemies to the player. This should be pretty quick on something like a 32*32 tile/node region and can be done every time the player changes from tile/node. Collision should be easy to handle too, entities could wait for the next tile/node to be free, look for another cheaper tile/node or move to a tile/node with the same value this could easily lead to surrounding the target.