2
\$\begingroup\$

I need to model a locust swarm that devour food stacks and move on to next stacks. I searched for articles and found few articles. These papers is about optimization applications but I want to convert it to a path finding algorithm to reach multiple targets (like randomly seeded many food stack). Swarm should split when food stack is not enough to feed them( multiple objective problem). How can I do this?

Locust Swarm Algorithm

x: position v: velocity vector

\$\endgroup\$
2
\$\begingroup\$

Is this what you want?

As for finding the closest food stack, calculating the center of the swarm and using a simple A* algorithm to search all other food stack from the lowest minimum distance to the highest works, or even just a lookup table to map food stacks with their nearest neighbours (Only works if your food stacks are static and regrow).

EDIT

To further answer the question:

The above solution might or might not work based on the new requirements stated in the comments. Or rather, it works, but becomes quite a heavy computation quite quickly.

You can assign N swarm members to stay at the food stack, and let the rest search for another stack. However, I would predict that the swarm members would spread out quite quickly, to the point where individual swarm members are searching for stacks. The Goal-Based Vector Field Pathfinding can handle that, but the A* might suffer.

If you want to take this aproach, you should really create a lookup table, or assign a array with the closest M stacks (Where M is some constant) to a field (so for each path-finding node in the world), which would use up a lot of memory.

Assigning swarm members to swarms might also help (Where every swarm gets a food stack assigned). This way the A* algorithm can operate on N members at once, as long as no member made it to the stack you can just make all members move in the same direction.

Best case

You can of course just create a vector field for every food stack with a weight, If you store the closest M stacks again. However, this would take up A LOT of memory (Multiple vector fields, so struct { int dx; int dy; int weight } ~= 12*M bytes PER NODE. This REALLY doesn't work for large world. If the world is small, this is the solution, but if the world is large, I think I can't help further.

\$\endgroup\$
  • \$\begingroup\$ Yes I want to that but I need to reach multiple targets. I forget to add "multiple targets" \$\endgroup\$ – acs Apr 19 '16 at 12:39
  • \$\begingroup\$ @acs multiple targets at once? As in, split the swarm if a part of it is closer to another food stack? The above solution/video works perfectly for finding one food stack at a time. \$\endgroup\$ – YoYoYonnY Apr 19 '16 at 12:47
  • 1
    \$\begingroup\$ Swarm should split if stack is not enough to feed them. \$\endgroup\$ – acs Apr 19 '16 at 12:53
  • \$\begingroup\$ @acs I updated the answer \$\endgroup\$ – YoYoYonnY Apr 19 '16 at 13:17
  • 1
    \$\begingroup\$ Right, walls, I knew I was missing something. You might still be able to make it work by making your nodes larger or not gridbased but I guess you'll then end up creating a navmesh. \$\endgroup\$ – Niels Apr 20 '16 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.