# Locust Swarm algorithm for path finding (devour and move on)

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?

x: position v: velocity vector

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

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.

• Yes I want to that but I need to reach multiple targets. I forget to add "multiple targets" – acs Apr 19 '16 at 12:39
• @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. – yyny Apr 19 '16 at 12:47
• Swarm should split if stack is not enough to feed them. – acs Apr 19 '16 at 12:53
• @acs I updated the answer – yyny Apr 19 '16 at 13:17
• 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. – Niels Apr 20 '16 at 6:09