When I first tried The Bridge puzzle, I thought I would never get the hang of it. I then focused on multiplayer games and completely forgot about it, until one day I got nostalgic and revisited some old puzzles. Now I want to share a different approach to this one, which is more multi-like.

The Game

You control a set of motorbikes on a runway full of obstacles. The goal of the game is to command the bikes in such a manner that the most of them survive to the far side of the runway. If this sounds vague to you, don’t worry, I’m going to explain…so bear with me!

Game Mechanics

Unlike most of the CG puzzles (which follow an In/Out pattern), this one is played in turns. The first turn of the game supplies the player with general information that normally doesn’t change for the rest of the game. In this case:

  • The number of motorbikes you control (1 to 4 bikes).
  • The number of motorbikes that must survive for a successful outcome. You can ignore this parameter though. I’ll explain why soon.
  • The runway: 4 strings that represent each lane (X axis). The runway is always 4 lanes wide (Y axis).

Afterwards, the actual turns start. Each turn supplies the player with information about the current state of each motorbike:

  • The current speed of the bikes. They share the same speed.
  • The coordinates (X, Y) that represent the position of the bike on the runway.
  • A boolean that states whether or not the bike crashed in a previous round.

By the end of the round, after the player (yeah, that’s you) does his voodoo magic, a common command must be printed to the standard output. The command is to be applied to all motorbikes at the same time, and this is why the speed value is common to all bikes, but the coordinates are not (same x, different y), since bikes cannot share a lane. Let’s talk a bit more about that!

Constraints

As I mentioned before, the command is common for all bikes, so let’s look up the possible commands and what each does:

  • WAIT: It actually does nothing and lets the bikes run their course. Let’s ignore this command for now.
  • UP: It commands all the bikes to move up one lane. For instance, if a single bike is currently traveling in the second lane from the top, it will move to the first. There are also invalid cases (that makes the motorbikes do nothing):
    • If a single bike is currently in the first lane from the top, it will do nothing.
    • If there are 4 bikes still alive, they’d do nothing, since the lanes are always 4.
  • DOWN: The same as “UP”, but downwards. The same concerns also apply.
  • SPEED: The current speed is incremented by 1.
  • SLOW: Same as speed, but decrementing. The minimum speed is 0, though you don’t really want the bikes to not move at all, as there is a maximum turn count (50) which, if exceeded, will make you lose the game. Don’t you worry about that though, everything is coming together very soon!
  • JUMP: This is the most interesting command a motorbike can achieve by itself – to jump. If there is an obstacle in the way, the bike can jump over it by issuing this command. Granted, all bikes will jump and that would make things ridiculous, but the bike will survive if the current speed is sufficient, and that’s all this game is about – survival.

The runway is most often full of holes, and the bikes will have to avoid them in some way. One way would be to steer left or right (up or down) or jump over them.

The steering is the most complicated action in this game. There is a bit of realism added to it: it takes time for a bike to switch lanes, so it can fall in any hole along the way.

Using Up or Down commands

Steering the bikes and avoiding holes

The jumping is a different matter. The best feature of it is that the bike jumps immediately from its current position and travels a distance equals to its speed until it lands. Let’s say that a single bike is driving at a speed of 3 and directly in front of it there is an obstacle 2 units long. Issuing the jumping command will make the bike land just after the obstacle, hence saving it.

But enough of these boring specifics, let’s get into the actual solution already!

The Approach

The game statement suggests using Trees and search algorithms, but I decided to take the high road (yeah, I did!) and go in another direction (I just had to…).
Instead, I build a series of different commands and simulate what would happen if I were to output the commands in each series. Then I evaluate the outcome of the simulation, and based on the score from each simulation, I choose the best one and execute the first command from it. That happens on each round. Have a look at this pseudo-code:

Game start:
   Input initial data
      For each round:
         Input turn’s data
         For each series:
            Simulate
            Check maximum score and save first command
         Output the best command

Maybe it sounds a bit confusing, or just a lot to take in, as in: “There is a lot of road ahead, there are lots of commands; where do I even begin?” Well, let’s see!

First off, you don’t really have to simulate the entire game ahead. Just a few rounds (3 to 5) would be totally fine because the game is not that complicated. Pick one that sounds good in your head and go with it. If it’s not enough, modify and try again.

Second of all, you can narrow down the command list. You don’t really need the “wait” command, because the “jump” command is always better (stay at the same speed but avoid potential holes). So go ahead and scratch that right out of the list. Of course, this could lead to some funny rabid-like behavior.

That being said, generating lists of 5 commands for 3 turns ahead shouldn’t be that difficult. They don’t have to be random, either, as there is enough time (50ms) to test out all possible combos (5^3). I’ll let you figure it out, though.

The next big step is to build the simulation. If you haven’t done anything like this before, this part probably confuses you the most. Worry not! Let’s dive in:

  1. You already have a list of sequences with possible combinations.
  2. Select one of them and feed it to the simulator.
  3. Apply each command from the sequence to all bikes that are still alive.

What does it mean to apply a command?

  1. Is the command “UP”?
  2. Is my uppermost bike below the first lane? If not, mark this command as “invalid,” as you don’t really do anything with it. You can even break the simulation at this point.
  3. Is the road ahead suitable for such a maneuver? Set all bikes that are still alive to the new position based on the speed, and mark all crashed bikes as “dead.”
  4. And so on…

Step by step, just add a function or a simple block of code that would handle each command and would modify the properties of a bike as a result of this command; you’re nearly there!

I chose to mark some commands as “invalid”:

  • Commands that would do nothing: UP when the first lane is occupied, DOWN when the fourth lane is occupied, etc.
  • Commands that would make my bikes stop (speed = 0). In such a case, the game is pointless and we don’t really want that, do we?
  • Commands that would make my bikes go too fast (speed > 10). You don’t really need much speed to reach the other end in time, but also at faster rates the bikes are difficult to maneuver.

Now it’s time to evaluate the simulations and we are done!

Once a simulation is complete, I scored the outcome thus:

  • Combinations that contain an invalid command get a huge penalty (scoring is set to a negative value). I chose a value low enough to filter them off completely when checking for the best score.
  • For each bike that is alive that has a speed value greater than 0, I granted a bonus: its X coordinate. I want my bikes to move forward, so driving is encouraged the most. And, of course, stayin’ alive.
  • For each dead or completely stopped bike, I gave a big penalty (big enough to make it worse than a simulation where no bike was destroyed, but low enough to not make it “invalid”).

I mentioned at the start that you don’t really have to worry about how many bikes must survive in each test case. Well, this scoring method ensures that the most possible “alive” bikes will continue, so you don’t have to add any logic.

Code Up!

I’m not going to share my actual code, but I’m going to go over some details about the design and structure, as you might find it useful.

I chose to do it in C++, because it does very well performance-wise, but also because I have a lot of control over the program. I feel comfortable with C-like languages, but if you don’t, just select one that suits you, as performance is not really an issue in this puzzle.

I’ve created two classes: BIKE and GAME.

The BIKE class handles motorbikes’ data (obviously) and handles their specific behavior.

  • Properties:
    • int X, Y, speed, aliveness
    • int X_old, Y_old, speed_old, aliveness_old
  • Methods:
    • Load( speed )
    • Reload()
    • Jump()
    • Move()
    • Steer( direction )

At the beginning of each turn, I invoke the Load method that reads the standard input and sets the bikes characteristics, but I also save these values in the “_old” variables. When simulating, I manipulate the values a lot, so I need to have copies to be able to revert them back (Reload method) once a simulation is complete.

The rest of the functions apply different commands; they also check for obstacles when doing so and set the “aliveness” property if necessary.

The GAME class handles all of the game’s data and the general algorithm. I didn’t really need it, but it’s a lot cleaner this way.

  • Properties:
    • BIKE bikes[4]
    • int bikeCount, surviveCount
    • string map[4]
  • Methods:
    • InitOnce()
    • InitRound()
    • Simulate(combo)
    • Solve()

The bikeCount is the initial number for the current test case, and the surviveCount is ignored, really (every input should be read though, else it would desynchronize the rest of the input). The map is the runway itself.

InitOnce reads the initial general data before the game loop, and the InitRound reads the current turn’s data by invoking the bike’s Load method.

The Simulate method does what is says; it simulates a combination and returns the evaluated score (don’t forget to revert the last state no matter the score). The Solve method is actually the main function that generates the combinations (calling the Simulate function for each one) and finds the best one (with the maximum score).

Is simulation the best approach?

Dependency graph of the solution

This whole shindig is not by all means necessary, but I use this kind of skeleton all the time so I’d be familiar quickly with what is what.

Conclusion

I think “The Bridge” is a great introduction to the multiplayer section of CG, because this kind of approach may lead to very impressive results. Here are some pointers that can be useful in the future:

  • Filtering combinations out is risky, but it also can be highly rewarding. Be careful when minimizing the search field.
  • Many games offer a longer first round – use it. In this case, the possible combinations are to be tested each round, so this list could be created at the start of the game.
  • Optimization is almost always a thing! Using the simulation results from the previous rounds is a great way of saving precious time, but it’s also two-faced. Everyone makes errors, or maybe approximations are used here and there, or maybe the particular game is not suitable for it. Starting each game turn with a clean slate could be better.
  • Building a simulation is difficult, no doubt about it. Still, there are certain games where no amount of heuristics could be a match for it. Take your time to test each step.

Now go on and build your own simulator and experiment a lot.

Good luck and have fun!

Solve The Bridge