Instead of exploring all possible paths equally, it favors lower cost paths. This is an incredibly useful algorithm, not only for regular path finding, but also for procedural map generation, flow field pathfinding, distance maps, and other types of map analysis.ĭijkstra’s Algorithm (also called Uniform Cost Search) lets us prioritize which paths to explore. I’m going to cover these:īreadth First Search explores equally in all directions. There are lots of algorithms that run on graphs. For the explanations on the rest of the page, I’m going to use grids because it’s easier to visualize the concepts. This page covers the A* algorithm but not graph design see my other page for more about graphs. A* runs fastest with the fewest graph nodes grids are often easier to work with but result in lots of nodes.
A grid game map can use a non-grid pathfinding graph, or vice versa. The pathfinding graph doesn’t have to be the same as what your game map uses.
0 kommentar(er)
