How I solved Saboteur 2

The classic game of the year 1987 was a continuation of the famous original, but compared with its predecessor it is something else entirely. But wait, I'll try to clarify from the beginning.

At the beginning of the story is the game Saboteur! from 1986, probably most famous on the ZX Spectrum platform. A classic Ninja arcade game with a reasonably-sized map where you had to find a disk, plant a bomb and fly away by helicopter. On the way were a lot of enemies - including the four-legged kind - which, however, were easy to defeat using martial arts.

A year later, from Durell Software and author Clive Townsend, there appeared on the ZX Spectrum platform a loose sequel called Saboteur II - Avenging Angel. As the title suggests, it was a female ninja-saboteur, smooth and sharp at the same time, and a woman facing an immeasurably more difficult task than her male predecessor.

The map is many times larger, has extensive underground spaces, gardens, warehouses, secret rooms, missile towers and elevators. But your task is not as simple as in the first game. It is a conundrum, before which your saboteur stands: Throughout the house are placed pieces of tape that must be collect and stored in rocket terminals. Meanwhile, it is still necessary to turn off the electric fence. Of course, the game has several missions, from the simple to the heaviest. Here I will deal with only the hardest mission.

The official remake of 2017 can be played and competed online on the website link. The one-time cost is 2.99 GBP, which is less than one hundred crowns, and definitely worthwhile.

The remake, compared to the original, is slightly improved. There is changable weather, you can switch graphics (ZX / C64 / CPC), extra music, you can see the energy-bar of enemies, and there are stairs and other rooms. It has improved sounds underground like the occasional ambient effect (dripping water), but otherwise it deliberately keeps the style of the original.

Before we begin, let me tell a little of the game itself. You will learn about the history of the building and other details in the remake. Intel Points at certain places will explain and illustrate the story.

The setting looks like a crazy experiment by billionaire Elon Musk. The only difference is probably that our billionaire is named Ricardo Alphonso Verdi II and in the building hangs his larger-than-life portrait. One can infer that he inherited money from his father ( Verdi I ) and followed in his footsteps - possibly in an unknown direction. He's built a successful telecommunications company called Viridis, which in the 90s had offices worldwide and was expanding rapidly.

In a house full of experiments and artificial intelligence we will not find a soul. The pleasant thing is that you do not kill the enemies in Saboteur 2 (which I welcome as a follower of games without violence). In the game there are guards everywhere, but they are robotic guardians, androids, who are probably made from sheet metal, because if you hit them you hear a hollow clang. Sometimes they go in tandem with a puma, which is an animal, although even in the game at one Intel Point you wonder whether they are not also robots. You can find some sort of coil to stimulate radio signals from a small radio unit to influence them, so that cougars never rest and just run wild near their master. Anyway, if you do kill something, it's just a puma. However it may be a jaguar or leopard that is dyed black, which you learn about in one garden on the right outside the building.

On the other side, on the left in the garden are laboratory facilities (cleanrooms). It says sign "No Entry!" But they are in fact an armory. They contain weapons of such power that could result in a small war. You, however, need nothing more than a star and a knife.

Above the office complex there are two towers. They are full of antennas - probably intended to communicate. Record your motion and control electric doors throughout the complex. Through the towers the moon shines and somehow indirectly encourages you to embark on an adventure with a convenient rocket.

The huge rocket always attracted players. I suppose it never occurred to them that the ninja should be able to control the rocket :) Actually, it is not obvious how to do so. But going to space is simply thrilling! The rocket is named as the Colonel Briggs Explorer. The satellite inside is Colonel Briggs and two more satellites with two other Colonels have already been launched. This is part of a plan codenamed Operation Fullbright. To the delight of those who wanted the original ZX to take off, I note that the remake's will be able to launch ;)

In the game you will find lots of mysterious places. There's a tower crane, which unloads trucks. You will find a junkyard of discarded pieces of failed robotic experiments. There's even a broken Zilog Z80 processor and broken 16K RAM. This might be what controls the robots. Furthermore you encounter the giant cutter with which they made the underground passageways and mined coal. You will learn that the cutter weighs 125 tons and is "Made in China". There are ultrasonic transmitters that control the bats. Then there is the experimental fuel for a rocket or a ballistic missile. Laboratories with prosthetic limbs and incomplete robots, laboratorys with quantum experiments etc. etc. There is of course even a teleport, which will take you to three very distant locations on the map. But I will not reveal everything.

Once you have explored the map you'll face one of the most difficult mathematical problems. Generally, this role came to be known as the "traveling salesman problem" ( link ) and you will feel the difficult of this task when collecting pieces of tape.

In the game are 15 pieces of tape. You need to collect 14 of them. These tapes must be placed in the rocket terminal and at any time during the game turn off the fence. So the question is: Which 14 tapes out of 15 to collect (ie. You skip one) - and the order in which you pick them, all within a certain time limit? In addition, you can start collecting from any point, since you can hop off at any point during the initial glide over the building.

The remake has an extra dimension where players compete with each other. It is not primarily about finishing the game, but finishing it better than your opponent. You must therefore (abstractly speaking) run around 16 points (14 tapes, one terminal, one switch). If we drop the terminal, you can visit and collect 14 tapes, so you have exactly 15 points for circulation. At first glance there is not much, but the number of possible paths (permutations) between 15 points is incredibly large, it's called 15 factorial

15! = 1,307,674,368.000, ie. Over 1.300 billion trips.

Choosing the shortest of them is intuitively difficult. In addition, there is a problem compounded by the fact that our case is not about the distance, but the time, because the time from point A to point B is not the same as from point B to point A. Somewhere you could jump into a pit but to get back to the same point you have to climb many ladders. In some places you can not only jump, but you have to jump from a certain angle and so on.

This shows the game map with pieces of tape:

Once you collect the tape, place it into the terminal and turn off the fence, you can go on the long lift to travel down then out of the building by bike. This ends the game.

Since I'm a programmer and not a mathematician, I tried to solve the problem by simulation. So the computer itself tries to navigate each path and calculate the best way for each of them. The route with the shortest time is recorded. This will be closer to the ideal solution.

For such a simulation, you need an optimized program, because 1300 billion combinations are a lot for even a powerful 64-bit processor. It must pass through quickly and ideally not use absurd routes (perhaps like chess programming, so it is advisable to incorporate a minimal artificial intelligence program to detect time-wasting absurd routes). It is necessary to decide whether to go through all the combinations or to test it randomly (ie heuristically or just brute force).

I decided to use heuristics. The program can be written in any language, each with a different advantage. Some languages ​​are faster, some have a better generation of pseudo-random numbers.

First, it is necessary to measure the time intervals between points. When the saboteur ​​flies over the building, there are 4 places with tape that are close to jump to. It can be said that you can start your mission from one of these 4 places because starting from any of the other 15 points will always make the route more time consuming. This yields one major limitation right for the beginning and we can exclude the first garbage route.

You need to carefully measure combinations of points separately. It's about making it accurate (so use the stopwatch), because this can have a major impact. Second - and this is not so easy - you have to anticipate what the route will have obstacles. After all, the game is not just about running from point A to point B, etc., but also dealing with the way that the guards can delay you. If you return to the same spot again, they will probably be dead (because you killed them on the way there), but the first time they will be there.

Thus, it is necessary to consider the real situation in the game and predict not only as a time-abstract, geometric. E.g. The journey from point no. 12 to the point no. 11, is short if you measure it while having a full energy bar. But if you're on the floor at 12 you should note that after the jump from the rope you have barely 1/3 of your energy left, and below the 12 there are two guards waiting. So the journey from point 12 to point 11 forces you to recover for at least 10 seconds. Similarly, a path ABC, where A is the nearest place, could take longer than if you saved A for later. It is best therefore to go through it several times under real conditions and to measure it consistently.

It's important to ensure that you really have measured the shortest path between points A and B. Sometimes the points are quite far apart and just intuitively you can believe that you've found the shortest runs. But over time you will find that it could be further shortened somewhere. Clive increased the complexity in the remake by adding staircases in all the offices While they tend to be more time-consuming, they are a good place to regain energy.

Another thing we can do to speed up the algorithm is to connect tapes 3 and 4. They are next to each other so it's unnecessary to pass through a combination of 3 to 15 and then from 4 to 14 ... they can thus be fixed together.

The question is tape 17. Whatever I went through and however I combined the results, it always felt that tape 17 was redundant. Although on the route there are almost no guards, it is still far away and there's no way to do anything on the way. I believe that by excluding it the algorithm will gain a further optimization feature.

Probably the last thing you can optimize is to connect points 14, 15, 16. They are so close together that it is not possible to find a combination that would be time saving and at the same time would not associate these 3 points. Number 16 is the terminal, where we have put all parts of the tape are collected, no. 14 is an electric fence. So the last tape collected will be tape 15, then the terminal and plot. This condition can be fixed to the algorithm.

The resulting program is thus surprisingly simple enough, even allowing for the assumptions I have made. So I wrote it in several languages, I was not dependent on the speed of one. And in PureBasic ( link ) BlitzMax ( link ) FreeBASIC ( link ) MonkeyX ( link ) AGK2 ( link ) and Python ( link ).

The fastest ever proved to be MonkeyX and to my surprise FreeBASIC. Finding solutions in tens of minutes, we can say that in 24 hours you can be 100% sure that there is no better solution. PureBasic again has the advantage that you do not need to program the function to generate a random field, but it has a direct command RandomizeArray ().

It is interesting that there are multiple paths that start from 12 (and follow a completely different route) and are timed almost identically. Therefore, it is too difficult to solve it just by machine. Some paths that are one second longer are longer, but on them you meet fewer guards and danger. I think it's best to go through the time-shortest routes, identify risks, and really learn one of them. Your opponents may think they have a shorter path, unless they allow for delays caused by the enemy. But if you take your longer route with fewer hazards you can eventually overtake them.

As to the records in the game Saboteur II, it is necessary to distinguish the original from the remake. The remake for me personally is more comfortable, due to engine speed and not having to measure the time yourself. Among the players at the top is quite a lot of competition - on some missions strictly in terms of hundredths of a second. On the last mission I hold the record still. In the original ZX version one Russian exceeded me by less than 1 second, when he chose a totally different route and wrote an article about it. The video in this article refers to my reaction times ( link ). My route is definitely a little shorter, but in terms of risk is perhaps more difficult, so overall these routes are almost all the same and it is just a matter of how much time you are able to avoid the guards. I think that in his record he had a bit more luck :)

In the remake I ran for 9: 26.06. Perhaps you will even beat this, because there are some reserves there, I noticed, but it's very difficult. You must have the correct route, all rehearsed and all of your actions have to be perfect. A delays of half a second can be hard to recover from, even on such a long path.

In conclusion, I do not explicitly disclose the route it runs. I'll keep it as know-how. But trying to solve the whole program and was a challenge for me and incredible fun lasting for years, ever since my youth :-)

Zdeněk Šimek, programmer. Author of several information systems of government and GIS raster maps. Developer of games and mobile applications in their free time. Development in Java, VB.NET, OGRE3D, JavaScript / HTML5, MonkeyX, Monkey2, DBPRO, BlitzMax, PureBasic.