Wrecking Crew is one of the classic title for the Nintendo Entertainment System (NES), featuring an odd-looking Mario. The goal of the game is to destroy construction-related materials like brick walls and ladders using a hammer. In the meantime, the player has to steer clear of the enemies. The game successfully combine both the puzzle and platform genre for a challenging experience. While the premise of the game is rather simple, finding the ultimate optimal route in each level may require advanced algorithms.
In this blog post, we’ll try to develop a method for finding the optimal path and test it on the first level. In the first section, we’ll discuss of the theory and the similar problems. In the second section, we’ll develop a naive approach to the problem. In the third section, we’ll develop an exact method that spits out the optimal path given the assumptions made. Finally, in the conclusion, we’ll discuss what could be improved on this methodology.
1. Understanding the problem
As said previously, the difficulty arise from the great amount of possible routes. Animation 1.1 shows me playing the game and beginning a route before getting hit by an enemy. This route started by first climbing on the right ladder but I could have started with the center ladder or the left ladder. This shows that there are a lot of possible routes and it’s not necessarily intuitive which one is the best. —–Parler de qu’est-ce qu’une tile —–
Let’s have a look on the number of possibilities. In this level, there are 13 objects to demolish (figure 1.2 shows the 4 types of objects that needs to be smashed) meaning there are 13 possibilities for the first object to destroy, 12 of the second object (knowing the first one), 11 of the third object, and so on. This means that there are 13 x 12 x 11 x … x 3 x 2 x 1 = 13! = 6 227 020 800 possible routes. That’s too much to test them all via brute force. Of course, most of these routes are pretty bad as they go all over the place instead of destroying everything one area at the time.
The problem that will be tackled in this blog post is “What is the shortest possible route to break all the objects?”. Interestingly, this problem is a variant of the Travelling Salesman Problem (TSP): “What is the shortest possible route that visits each city exactly once and returns to the origin city?” Here, instead of visiting cities, Mario has to break things but the principle is similar. In the following sections of this blog post, we’ll try variants of TSP solutions in this game. Here are the main differences between Wrecking Crew and the Travelling Salesman Problem:
- Mario doesn’t need to go back to his starting position;
- Some ladders
need to be destroyed; meaning that they can’t be climbed on after; - Enemies
can hit Mario and make him lose a life. For simplicity sake, we will disable enemies in this analysis; - Bombs
can be used to destroy adjacent objects. Again, for simplicity, we will ignore bombs in this analysis.
2. Visualization using graph theory
When dealing with a problem like this one, it is useful to visualize it using a network diagram. This can be done here by drawing arrows between tiles that are connected. (You might be wondering what are tiles? Animation 2.2 demonstrates what I mean by tiles.) Figure 2.1 shows the graph diagram for this first level. Tiles that are unreachable by Mario were removed from this graph for the sake of simplification. As said previously, some ladders need to be destroyed (see for example the right ladder in Figure 1.1). This change the graph and altered are in orange the figure.
Animation 2.2 shows how figure 2.1 was generated from the initial position of the tiles as seen in the game. The disposition of tiles was done by using the force-directed graph drawing algorithm.
For those curious of how the graph would look like if we add the unreachable tiles, I have added figure 2.3. We can see that, of course, the unreachable tiles don’t have arrows pointed towards them, but from them only.
3. Simplistic Approach for Solution
We’ll first try a simple method for approximating the optimal solution. It will be useful as a benchmark for the exact method we’ll use in the 4th paragraph. The simple method we’ll use is the nearest neighbour algorithm. As the name says, Mario will go break the nearest object until all objects are destroyed.
Timing Estimation
Before going further, some testings were done manually to compute the time required to go from tiles to tiles. A test run was deeply analyzed and analyzed to gather how much time it takes to go from the center of a tile to the center of an adjacent tile. Table 3.1 summarizes the results using frame per seconds as the time unit. Note that the NES produces 60 images or frames per seconds which mean that all these movements take less than a second to run. The difference between the maximum and minimum time required can be explained by Mario needing to accelerate to reach his “cruising speed”. This behavior is most notable when he is falling.
| Movement | Minimum Time (in number of frames) | Maximum Time (in number of frames) |
|---|---|---|
| Left or right | 16 | 17 |
| Ladder | 37 | 53 |
| Falling | 10 | 21 |
Using the results, we can compute an approximated number of frames it would take to reach each object to break. We’ll use the minimum time for our computations so we have a lower bound estimate for the solution.
Nearest neighbour
Figure 3.2 shows how the first step of the nearest neighbour algorithm is decided. In this figure, all 13 breakable objects are shown with the approximated time (in frames) it would take Mario to reach them from the starting location.
The grey brick wall 
is the closest object, needing only 69 frames to reach it (the route and number of frame is shown in red). This is the one we’ll go break first.
After this first step, we’ll go to the next closest one from this new location. Animation 3.3 shows the iterations to select the route to break all 13 objects in the first level.
Summing all movements suggested by the algorithm, we get an estimation of 737 frames for movement + 374 frames for breaking the objects =1111 frames to finish the level. Of course, like I said earlier, this is a lower bound estimation as it doesn’t take into account that Mario accelerate when moving. Now, animation 3.4 shows the resulting route tested on the actual game. This run was controlled by the computer by generating a set of button presses meaning that the game was played without human input. In a sense, this is like a player piano where instead of a melody being played, it is a video game. So, in this practice run, the run time was 1194 frames (820 for movement and 374 for breaking objects), which is around a second more than what we estimated earlier (1194 – 1111 = 83 frames which is a little bit more than one second). Now can we do better than that with a more sophisticated algorithm?
4. Exact Method
In the last section, we used a naive method, the nearest neighbour algorithm to arrive at a solution for the first level of Wrecking Crew. Looking at the result in animation 3.3, we have the feeling that this solution might not be the fastest. By breaking the leftmost ladder, Mario had to go through a big detour to climb up to the highest floor. This operation cost him a considerable amount of time (as said previously, the bomb will be ignored in this analysis, although it would have also improved the run time).
Branch and bound
Now, since the number of breakable objects is limited (but still too high to brute force), we will be able to use the branch and bound algorithm to come up with the optimal solution. The branch and bound algorithm, as the name implies . We can see the as . For example, at the start of the level, since there are 13 objects that need to be broken, the number of branches at this step is 13. On the second step, the number of branches is 12 and so on until all objects are broken. The idea here is to compare at each step the number of frames that were required to reach the step with the best solution found so far. We can even use the nearest neighbor solution that we found in section 3 (820 frames without considering the time to break objects) as a first solution to compare to. For example, in figure 4.1, we see the beginning of a run with the five first steps highlighted (labelled #1, …, #5). It takes 1023 frames to reach the fifth object, which is higher than the current best of 820 frames. Therefore, we don’t have to test all the ramifications of this run’s beginning and we can now start to test other paths’ beginning. This method save a lot of computing time but we can do even better than that.
Minimum Spanning Tree
With the previous method, we’re only considering the distance traveled so far (but not the distance yet to be traveled). So, to complement this method, we could add a lower bound estimate of the distance that needs to be completed. For example, in the figure 4.1 run, there are still 8 objects left to destroy which would take time for Mario to reach. An easy algorithm to apply to this problem is the Minimum Spanning Tree. To summarize, this algorithm returns the minimum distance to connect points in the network. Applied to our problem, this algorithm computes the minimum distance to connect all the remaining destructible objects, regardless of if it’s a valid path. For example, a back and forth is only counted once instead of twice with this method. This algorithm also doesn’t take into account that going from one tile to the other can only be done one way (ex: falling from a platform). Fortunately, there are functions that can quickly compute the solution on modern programming languages so it is quick to implement.
Figure 4.2 shows a visual example of the MST algorithm on the beginning of a run that’s not completed (only one object breakable object is reached). The red path represent the route taken by Mario and is takes 69 frames to go through. Using the MST algorithm, this figure adds to the previous ones a very simple approximation of the remaining path to run through in purple. 300 frames is a crude lower bound estimation of the remaining distance and if we would actually test the path generated by this method, we are not certain it would be feasible. Still, using this method has its advantages (mostly speed) and the beginning of a route like figure 4.1 for example could have been rejected even sooner.
Now we can use this method until we have a solution. Animation 4.3 shows all branches that were tested by the algorithm with both the tested path in red and the approximated remaining path in purple for each of them. After 1097 branches tested, the best theoretical solution was found with 926 frames (552 for movement and 374 for breaking objects) and can be seen on figure 4.4. The major difference with the NN solution comes essentially from waiting until the end to destroy the top left ladder. It’s worth noting that there are multiple solutions that also give the same number of frames. For all those cases, the difference is minimal and comes from the permutation of adjacent objects (for example permuting the #12 and #13 objects results in the same number of frames).
Now let’s see how much time it takes to complete the level using this newfound route in the actual game.
In practice
I’m skipping the details, but the branch and bound method was adapted to prove that the route found by the methodology is also the best practical solution. Animation 4.5 shows the results on the actual game and, like animation 3.4, this run was controlled automatically by the computer without human input. This run took only 976 frames to complete (602 for movement and 374 for breaking objects)! When compared to the Nearest Neighbor result of 1194 frames, it is 22% faster with almost 4 seconds saved. It’s interesting to see that in this sequence, Mario is so fast (and lucky) that the enemy doesn’t even attain Mario. In this case, we didn’t have to disable the enemies from the game.
5. Conclusion
Today, we had a glimpse on how find the optimal route for a problem. The methodology is useful in logistics, planning and… video games of course! We learned about two algorithms: the nearest neighbor and the branch and bound. The former method was easy and gave us a good but suboptimal answer. The second method was more computationally expensive but gave us the optimal strategy (given the simplification that we applied: no bombs and no enemies).
It would be interesting to see if and how these algorithms can be modified to allow for the bombs and enemies to be taken into account. Additionally, in later stages, a golden hammer can be acquired that change significantly the game. All these elements could be incorporated in a future blog post maybe?
GG 