Algorithm Game Introduction

labuladongOriginalAbout 1341 words

The main goal of this site is efficiency. We hope readers can quickly master algorithms and pass interview and written tests.

Besides that, I also hope the learning process can be interesting. If you only do problems for interviews, it can get boring.

If readers can really feel the charm of algorithms and think of learning as an exploration, then you will have inner motivation. This not only makes you learn better, but also adds some fun.

Finding a job these days is stressful. Algorithm problems are now a must for most tech jobs. So why not make it a bit more fun?

After some research, I think combining algorithm learning with games is a good idea. It’s interesting, and it also helps you see how algorithms work in real situations. You get both fun and knowledge.

Gamification vs Visualization

If we already have Visualization Panels, why do we need algorithm games?

I have thought about this. I think both are needed because they solve different problems.

The visualization panel answers questions like: What happens step by step in this code? Why do we do n + 1 and not n + 2?

Algorithm games answer different questions: In what real scenarios can we use this algorithm? How do we use it?

So, in my game designs, it’s not just about showing how the algorithm runs. The game combines real scenarios, and asks players to use data structures and algorithms together to finish tasks. You can see how algorithms work in the game.

Below is a simple guide to using the game panel on this site.

How to Use the Game Panel

At the top right of the panel, there is a full-screen button. Full screen mode makes it easier to write code.

On the left is the game screen. On the right, the top part is the problem description, and the bottom part is the code editor. You need to write code in the editor to solve the problem. Then click "Submit" to run your code in the game engine. You can interact with the game to see if your code works.

Below is a "Snake" game panel. If you click "Begin", the snake won’t move at first. This problem is about how double linked lists work in real life. You need to add the logic so the snake can move.

Write the right code in the editor, click "Submit" to send it to the game engine, then click "Begin". Now the game will run, and you have a playable mini-game:

Sample solution:

java

// The game panel only supports submitting JavaScript code
// Java solution is provided to help readers understand the algorithm logic
public void move(List<Point> snake, String direction, Point foodPosition) {
    Point currentHead = snake.get(0);
    // Calculate new head position
    Point newHeadPos = new Point(currentHead.x, currentHead.y);
    switch (direction) {
        case "right":
            newHeadPos.x += 1;
            break;
        case "left":
            newHeadPos.x -= 1;
            break;
        case "up":
            newHeadPos.y += 1;
            break;
        case "down":
            newHeadPos.y -= 1;
            break;
        default:
            throw new IllegalArgumentException("Invalid direction");
    }
    // Add new head node
    snake.add(0, newHeadPos);
    if (!newHeadPos.equals(foodPosition)) {
        // Remove tail node if not eating food
        snake.remove(snake.size() - 1);
    }
}

cpp

// The game panel only supports submitting JavaScript code
// C++ solution is provided to help readers understand the algorithm logic
void move(vector<Point>& snake, const string& direction, const Point& foodPosition) {
    Point currentHead = snake.front();
    // Calculate new head position
    Point newHeadPos(currentHead.x, currentHead.y);
    if (direction == "right") {
        newHeadPos.x += 1;
    } else if (direction == "left") {
        newHeadPos.x -= 1;
    } else if (direction == "up") {
        newHeadPos.y += 1;
    } else if (direction == "down") {
        newHeadPos.y -= 1;
    } else {
        throw invalid_argument("Invalid direction");
    }
    // Add new head node
    snake.insert(snake.begin(), newHeadPos);
    if (!newHeadPos.equals(foodPosition)) {
        // Remove tail node if not eating food
        snake.pop_back();
    }
}

python

# The game panel only supports submitting JavaScript code
# Python solution is provided to help readers understand the algorithm logic
def move(snake, direction, food_position):
    current_head = snake[0]
    # Calculate new head position
    new_head_pos = Point(current_head.x, current_head.y)
    if direction == 'right':
        new_head_pos.x += 1
    elif direction == 'left':
        new_head_pos.x -= 1
    elif direction == 'up':
        new_head_pos.y += 1
    elif direction == 'down':
        new_head_pos.y -= 1
    else:
        raise ValueError('Invalid direction')
    # Add new head node
    snake.insert(0, new_head_pos)
    if not new_head_pos.equals(food_position):
        # Remove tail node if not eating food
        snake.pop()

// The game panel only supports submitting JavaScript code
// Go solution is provided to help readers understand the algorithm logic
func move(snake *[]Point, direction string, foodPosition Point) {
    currentHead := (*snake)[0]
    // Calculate new head position
    newHeadPos := Point{X: currentHead.X, Y: currentHead.Y}
    switch direction {
    case "right":
        newHeadPos.X += 1
    case "left":
        newHeadPos.X -= 1
    case "up":
        newHeadPos.Y += 1
    case "down":
        newHeadPos.Y -= 1
    default:
        panic("Invalid direction")
    }
    // Add new head node
    *snake = append([]Point{newHeadPos}, *snake...)
    if !newHeadPos.Equals(foodPosition) {
        // Remove tail node if not eating food
        *snake = (*snake)[:len(*snake)-1]
    }
}

javascript

var move = function(snake, direction, foodPosition) {
    const currentHead = snake[0]
    // Calculate new head position
    const newHeadPos = new Point(currentHead.x, currentHead.y)
    switch (direction) {
        case 'right': 
            newHeadPos.x += 1
            break
        case 'left': 
            newHeadPos.x -= 1
            break
        case 'up': 
            newHeadPos.y += 1
            break
        case 'down': 
            newHeadPos.y -= 1
            break
        default:
            throw new Error('Invalid direction')
    }

    // Add new head node
    snake.unshift(newHeadPos)

    if (!newHeadPos.equals(foodPosition)) {
        // Remove tail node if not eating food
        snake.pop()
    }
}

Game Collection

Game chapters are scattered throughout the site (look for sections marked with ). Here is a summary for easy access.

The game features are still being tested. I have many fun ideas, but only a few are online now. More interesting games are coming soon!

Snake Game

This game helps you learn how to use doubly linked lists in real problems. See Implementing Snake Game:

Huarong Road

Huarong Road is an advanced puzzle that uses the BFS Algorithm. It is fun and I suggest turning on the background music when you play. For solutions, see Implementing Huarong Road Game:

Connect Two

This game tests your BFS skills. See Implementing Connect Two Game:

One Stroke Puzzle

This game is about Eulerian graphs. See Eulerian Graph and One Stroke Puzzle:

Minesweeper

This game tests several algorithms.

First, you need to use random algorithms like the shuffle algorithm and reservoir sampling. See Implementing Minesweeper:

We usually use the Monte Carlo method to check the randomness of the algorithm. The site also has a Monte Carlo verifier. You can use it to test your random Minesweeper generation algorithm:

Minesweeper also tests your DFS skills. See Implementing Minesweeper II:

You can also think about how to write an algorithm to solve Minesweeper, and make a "Minesweeper Cheat Tool":