Search This Blog

Explore Simple Game Algorithms with Color Walk: Part 11

In this installment of exploring game algorithms using the simple game Color Walk, we're going to do something a little different. Last time we explored a number of variations and hybrids of Dijkstra's algorithm—the classic, efficient graph algorithm for finding shortest paths—and found that pairing it with a pre-run of Greedy Look-Ahead (GLA) performed better than any other algorithm we've seen so far. This time we're not going to explore any new algorithms. Instead, we're going to look into what makes Dijkstra's algorithm tick: the priority queue. Save for this variant of a standard queue, Dijkstra's algorithm is conceptually the same as Breadth-First Search (BFS), so we want to see what makes this priority queue so special and how we can implement one efficiently with a binary heap.