That meant a lot of downtime, and I just happened to have a laptop with IntelliJ. We were on our honeymoon at the time, travelling around Europe by train. Two months on, I can think of at least six side projects that are the direct result of my Minesweeper obsession. ![]() It all snowballed from there - implementing the solver was just the beginning. Most of the time, I don’t actually implement that algorithm. When playing a game, I often think about how I’d write an AI for it. It was a dark time - I even spent £3.99 for a Nintendo Switch version! I will cover those algorithms in later posts.In this post, I tell the story of my recent obsession with the game Minesweeper and discuss why having an obsession can be helpful.Ī few months ago, my wife and I were playing a lot of Minesweeper. There are more efficient search algorithms, but many of them start with depth-first search and modify it to be more effective. ![]() Implementing it requires very little code, and it is an algorithm many of us already use for solving mazes or playing video games. That is all there is to depth-first search. Infinite loops don’t happen when doing a depth-first search of a tree but they can occur iwith Minesweeper. If a square is already revealed I do not reveal it again. On line 4 I do one thing I did not mention above. mine_nearby? neighbors = neighbors x, y until neighbors. Here is what it looks like, in Ruby, in my game. reveal x, y focus = square at x, y if focus at x, y has no nearby mines check each neighbor of the focus if a neighbor has no nearby mines reveal neighbor ( recurse! ) After I find a square with mines nearby I check all of its neighbors, (upper right, right, lower right…) going clockwise until I find a neighbor without any mines nearby (value 0) and then making that one my current focus. ![]() If it does not, I check the square above that one and so on until I find a square with mines nearby. Then I check to see if the square above it has any mines nearby. When the player clicks on a square with no mines nearby, I reveal that square. It turns out you can still use depth-first search when revealing squares after a player’s click. So how does this relate to Minesweeper? Minesweeper does not have anything that looks like a tree. If the number is visited again, while backtracking, you do not count that visit. Notice that you only record a number the first time you visit it. Following this pattern the depth-first search of this tree visits each number in the following order: 37, 13, 6, 5, 11, 17, 15, 88, 69, 51, 48, 63, 79. 11 also has no paths branching off of it, so I go back again to 13 and explore 17 which I had skipped on my way down. There are no paths branching off of 5, so I backtrack to 6 and then go right visiting 11. The first four numbers I visit are 37, 13, 6, and 5 in that order. You then go left until you hit a place where you must make a choice, and then again you take the left branch. To traverse or search this tree using depth-first search you start at the top, at 37. With computers, people often explain depth-first search using trees like this one. When they hit a dead end they double back and try a different path. They explore new levels by always going right when they come to an intersection. I know several folks who use this technique when playing first person shooter video games. If you have ever solved a maze by following along a wall you’ve used depth-first search. In a depth-first search, you go as far in any direction you can before backtracking and trying a different direction. So what is depth-first search? It is an algorithm for exploring a graph, a tree, or another data structure in a systematic way. ![]() Using depth-first search, I finished my Ruby2D version of Minesweeper. Then I remembered, when I implemented Minesweeper in college I used depth-first search for the progressive reveal. The first two implementations I tried didn’t work. This behavior, a progressive reveal until you get near a mine, is the trickiest part of implementing the game. If those squares do not have any mines nearby, the process is repeated until you get to a square that has a mine nearby. If there aren’t any mines nearby, the neighboring squares are revealed. In Minesweeper, when you click on a square the game reveals the number of mines nearby. Within a few hours, I had a basic game working. Ruby2D is still under development, but it has enough functionality for me to build Minesweeper. When I learned both Ruby-Processing and Gosu the first thing I implemented was a simple Minesweeper game.
0 Comments
Leave a Reply. |