Shortest walk algorithm – Pathfinder algorithm library swarm integration
Shortest walk algorithm – Pathfinder algorithm library swarm integration by Matthijs la Roi
For my current job at LAVA I found the need to improve the pathfinder capabilities of the agent algorithms I was work with. Swarm logic couldn’t always prevent agents from running into dead ends. I found this pathfinder library from Roboacid.com and tried to integrate it with a simple swarm sketch. The library has three basic pathfinder algorithms that can be used. The differences are explained below.
- A* (Accurate and fast, but ignorant of teleportation)
- Best-First-Search (Stupid – but fastest – good for game A.I.)
- Dijkstra (Accurate – accounts for teleportation, but slow)
The library works with an array of possible nodes that can be used to travel from one coordinate to an other. The on of status of a node is determined with a boolean. To play with some different obstacle courses, I first drew some obstacle closed curves in Rhino. Then generate a grid in grasshopper and see which points are not inside any of the boundary curves. The list of true false values was stored in a txt file and loaded to processing to generate the pathfinder node array.
I have been using swarm logic for a couple projects at LAVA since I started working there in 2012. These design strategies proved various times helpful for the design process. Unfortunately I’m not able to publish any results by now yet. But take some look at some of the experiments I did with the pathfinder library below.