During the last couple of days we have worked on developing the global planning algorithm which is to be used for navigation. We started off by testing the free version of the A*-algorithm, however it proved to be really inefficient in our implementation. We also read in some papers that much simpler global planning algorithms can be much faster for really large crowds. A decision was made to simply make our own algorithm from scratch, were we chose a simple roadmap approach.
Our roadmap is basically a graph structure consisting of nodes, strategically placed, that are coupled together bilaterally. Upon planning a path we do a simple node-to-node breadth-first-search and store the traversed nodes in a stack, representing the path. In order to reduce computational cost, we introduce an invisible leader for every group of agents with the common target position. The leader is the only object that carries out the path planning and thus it is the only one actually following the path. All the agents then follow this leader and so in a sense they plan the path as a group.
One problem with this approach is that when agents fall behind too much, there is a possibility of getting stuck behind obstacles when following the leader blindly. We solve this problem by having every agent raycast to the leader and store its position as long as it is visible. When an obstacle gets in the way, it is detected by the raycasting and thus the agents follow the last seen position instead of following the leader directly. As soon as the leader is spotted again, it is being followed as usual.
Below is a video of how the algorithm works. The roadmap, with both its nodes and edges, is drawn and so is the calculated path. The leader is shown by the larger object for illustrative purposes.
Now that the last prototype is completed, what remains now is to optimize the code, primarily to implement the MIC(0)-preconditioner for the MPRGP-algorithm, and to import the new models and scenes provided in order to get a nice presentation. After that, given that we have some time left, we will try to extend this project in some cool way.