Solving Match-3 Games with Graph Algorithms
Welcome to my technical blog series on graph algorithms. At rideOS, we use graphs and graph algorithms extensively, such as for routing of autonomous vehicles. In this series, we will be exploring how to solve Match-3 games using graph algorithms. An example of a Match-3 game is Candy Crush Saga by King, a game where the player performs swaps of adjacent candies to form contiguous lines of 3 or more candies of the same type.
Candy Crush is arguably one of the most popular games worldwide, with over 9 million people who play it for 3 hours or more daily. While the mechanics of Candy Crush seem simple, i.e., swap adjacent candies to match them, the game is mathematically complex. It is a good example of a game that follows Bushnell’s law: “All the best games are easy to learn and difficult to master. They should reward the first quarter and the hundredth.”
This blog series will not be focusing on Candy Crush specifically. Instead, we will be investigating Match-3 games in general. The topics covered in this series will be directly applicable to Candy Crush as well as other games of the genre.
In this first post, we will first start with an introduction to graph theory. Namely, what is a graph? How can it be used to represent and solve problems? What are some problems that graph theory and graph algorithms have been…
