Sammendrag
Modern GPUs are capable of rendering millions of artificial intelligence agents on the screen at once. Consequently, the CPU struggles to keep up in games with large crowds of agents, and pathfinding in particular is a often a performance bottleneck. Existing work has been done \cite{emerson2019crowd} to combat this issue by combining pathfinding algorithms that are specialized in finding the shortest path from all points to the destination with hierarchical pathfinding methods, such that the expensive all to one pathfinding can be performed only in a subset of the game environment. The all to one algorithms are effective for games with a large amount of pathfinding agents, because they can share the computed path. We propose to further improve the performance of this method by using precomputation of the path, as well as accelerating the algorithms on the GPU. Additionally, we were able to invent a new Eikonal solver, which can be used to improve the quality of the generated paths. Our results showed that the GPU acceleration method was not as worthwhile as expected, but the precomputation and our proposed Eikonal solver brings a great improvements.