Solve Maze Game

labuladongOriginalAbout 3045 words

This is a classic maze game. You can use the keyboard arrow keys or the buttons on the UI to move the character. Reach the bottom right corner to win.

Think About It

Can you guess how mazes with different styles are generated? If you need to generate a maze, what algorithm would you use?

You can switch between different maze styles in the game. Try to solve the maze using DFS or BFS, then replay the solution to see the features of each style.

Maze generation algorithms are very interesting and a bit challenging. We will explain them in the next maze game.

It is simple to solve the maze with an algorithm. Start from the beginning and recursively search in four directions: up, down, left, and right. You can think of this as traversing a "quadtree" or an undirected graph. Both DFS and BFS can solve the maze. BFS will always find the shortest path, but DFS may not.

Here is a DFS solution for your reference:

java

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

// Assume Position class
class Position {
    public int i, j;
    
    public Position(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

// Assume GameController is an interface
interface GameController {
    Position getPosition();
    Position getTargetPosition();
    void setPosition(int i, int j);
    void setVisited(int i, int j, boolean visited);
    boolean isBlock(int i, int j);
    boolean isVisited(int i, int j);
}

public static void solveMaze(GameController gameController) {
    // get the start position and target position
    Position startPos = gameController.getPosition();
    Position targetPos = gameController.getTargetPosition();
    
    // four directions: up, right, down, left
    int[][] directions = {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1}
    };
    
    // external variable to store whether the path is found
    boolean[] pathFound = {false};
    
    class MazeSolver {
        void dfs(int currentI, int currentJ) {
            // Base case: if the path is found, return
            if (pathFound[0]) {
                return;
            }
            
            // check if the current position is the target position
            if (currentI == targetPos.i && currentJ == targetPos.j) {
                pathFound[0] = true;
                return;
            }
            
            // mark the current position as visited
            gameController.setVisited(currentI, currentJ, true);
            
            // try four directions
            for (int[] dir : directions) {
                int nextI = currentI + dir[0];
                int nextJ = currentJ + dir[1];
                
                // if the next position is a wall or visited, skip
                if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
                    continue;
                }

                // move to the next position
                gameController.setPosition(nextI, nextJ);
                
                // recursive search
                dfs(nextI, nextJ);
                
                // after the recursive search, backtrack
                gameController.setPosition(currentI, currentJ);
            }
        }
    }
    
    // start DFS from the start position
    new MazeSolver().dfs(startPos.i, startPos.j);
}

cpp

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

#include <vector>

// Assume Position struct
struct Position {
    int i, j;
};

// Assume GameController is an interface class
class GameController {
public:
    virtual Position getPosition() = 0;
    virtual Position getTargetPosition() = 0;
    virtual void setPosition(int i, int j) = 0;
    virtual void setVisited(int i, int j, bool visited) = 0;
    virtual bool isBlock(int i, int j) = 0;
    virtual bool isVisited(int i, int j) = 0;
};

void solveMaze(GameController* gameController) {
    // get the start position and target position
    Position startPos = gameController->getPosition();
    Position targetPos = gameController->getTargetPosition();
    
    // four directions: up, right, down, left
    std::vector<std::vector<int>> directions = {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1}
    };
    
    // external variable to store whether the path is found
    bool pathFound = false;
    
    std::function<void(int, int)> dfs = [&](int currentI, int currentJ) {
        // Base case: if the path is found, return
        if (pathFound) {
            return;
        }
        
        // check if the current position is the target position
        if (currentI == targetPos.i && currentJ == targetPos.j) {
            pathFound = true;
            return;
        }
        
        // mark the current position as visited
        gameController->setVisited(currentI, currentJ, true);
        
        // try four directions
        for (const auto& dir : directions) {
            int nextI = currentI + dir[0];
            int nextJ = currentJ + dir[1];
            
            // if the next position is a wall or visited, skip
            if (gameController->isBlock(nextI, nextJ) || gameController->isVisited(nextI, nextJ)) {
                continue;
            }

            // move to the next position
            gameController->setPosition(nextI, nextJ);
            
            // recursive search
            dfs(nextI, nextJ);
            
            // after the recursive search, backtrack
            gameController->setPosition(currentI, currentJ);
        }
    };
    
    // start DFS from the start position
    dfs(startPos.i, startPos.j);
}

python

# The game panel only supports submitting JavaScript code
# The code in other languages is only for understanding

def solve_maze(game_controller):
    # get the start position and target position
    start_pos = game_controller.get_position()
    target_pos = game_controller.get_target_position()
    
    # four directions: up, right, down, left
    directions = [
        [-1, 0],
        [0, 1],
        [1, 0],
        [0, -1]
    ]
    
    # external variable to store whether the path is found
    path_found = [False]
    
    def dfs(current_i, current_j):
        # Base case: if the path is found, return
        if path_found[0]:
            return
        
        # check if the current position is the target position
        if current_i == target_pos['i'] and current_j == target_pos['j']:
            path_found[0] = True
            return
        
        # mark the current position as visited
        game_controller.set_visited(current_i, current_j, True)
        
        # try four directions
        for direction in directions:
            next_i = current_i + direction[0]
            next_j = current_j + direction[1]
            
            # if the next position is a wall or visited, skip
            if game_controller.is_block(next_i, next_j) or game_controller.is_visited(next_i, next_j):
                continue

            # move to the next position
            game_controller.set_position(next_i, next_j)
            
            # recursive search
            dfs(next_i, next_j)
            
            # after the recursive search, backtrack
            game_controller.set_position(current_i, current_j)
    
    # start DFS from the start position
    dfs(start_pos['i'], start_pos['j'])

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

// Assume Position struct
type Position struct {
    I int `json:"i"`
    J int `json:"j"`
}

// Assume GameController is an interface
type GameController interface {
    GetPosition() Position
    GetTargetPosition() Position
    SetPosition(i, j int)
    SetVisited(i, j int, visited bool)
    IsBlock(i, j int) bool
    IsVisited(i, j int) bool
}

func solveMaze(gameController GameController) {
    // get the start position and target position
    startPos := gameController.GetPosition()
    targetPos := gameController.GetTargetPosition()
    
    // four directions: up, right, down, left
    directions := [][]int{
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1},
    }
    
    // external variable to store whether the path is found
    pathFound := false
    
    var dfs func(int, int)
    dfs = func(currentI, currentJ int) {
        // Base case: if the path is found, return
        if pathFound {
            return
        }
        
        // check if the current position is the target position
        if currentI == targetPos.I && currentJ == targetPos.J {
            pathFound = true
            return
        }
        
        // mark the current position as visited
        gameController.SetVisited(currentI, currentJ, true)
        
        // try four directions
        for _, dir := range directions {
            nextI := currentI + dir[0]
            nextJ := currentJ + dir[1]
            
            // if the next position is a wall or visited, skip
            if gameController.IsBlock(nextI, nextJ) || gameController.IsVisited(nextI, nextJ) {
                continue
            }

            // move to the next position
            gameController.SetPosition(nextI, nextJ)
            
            // recursive search
            dfs(nextI, nextJ)
            
            // after the recursive search, backtrack
            gameController.SetPosition(currentI, currentJ)
        }
    }
    
    // start DFS from the start position
    dfs(startPos.I, startPos.J)
}

javascript

function solveMaze(gameController) {
    // get the start position and target position
    const startPos = gameController.getPosition();
    const targetPos = gameController.getTargetPosition();
    
    // four directions: up, right, down, left
    const directions = [
        [-1, 0],
        [0, 1],
        [1, 0],
        [0, -1]
    ];
    
    // external variable to store whether the path is found
    let pathFound = false;
    
    var dfs = function(currentI, currentJ) {
        // Base case: if the path is found, return
        if (pathFound) {
            return;
        }
        
        // check if the current position is the target position
        if (currentI === targetPos.i && currentJ === targetPos.j) {
            pathFound = true;
            return;
        }
        
        // mark the current position as visited
        gameController.setVisited(currentI, currentJ, true);
        
        // try four directions
        for (let dir of directions) {
            const nextI = currentI + dir[0];
            const nextJ = currentJ + dir[1];
            
            // if the next position is a wall or visited, skip
            if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
                continue;
            }

            // move to the next position
            gameController.setPosition(nextI, nextJ);
            
            // recursive search
            dfs(nextI, nextJ);
            
            // after the recursive search, backtrack
            gameController.setPosition(currentI, currentJ);
        }
    }
    
    // start DFS from the start position
    dfs(startPos.i, startPos.j);
}

For the BFS solution, there is a small trick. You need to record the path while doing BFS.

We use a parent array to record the previous position for each node. This way, you can trace back from the end to the start to get the full path.

Here is a reference solution:

java

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

import java.util.*;

// Assume Position class
class Position {
    public int i, j;
    
    public Position(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

// Assume GameController is an interface
interface GameController {
    Position getPosition();
    Position getTargetPosition();
    void setPosition(int i, int j);
    void setVisited(int i, int j, boolean visited);
    boolean isBlock(int i, int j);
    boolean isVisited(int i, int j);
}

// reconstruct path and execute moves
public static void reconstructAndExecutePath(GameController gameController, 
                                           Map<String, Position> parent, 
                                           Position startPos, Position targetPos) {
    // start from target, reconstruct path through parent nodes
    List<Position> path = new ArrayList<>();
    Position current = new Position(targetPos.i, targetPos.j);
    
    while (current != null) {
        path.add(current);
        String key = current.i + "," + current.j;
        Position p = parent.get(key);
        if (p != null && (p.i != -1 || p.j != -1)) {
            current = p;
        } else {
            current = null;
        }
    }
    
    // reverse the path
    Collections.reverse(path);
    
    // execute path movement (skip start position)
    for (int i = 1; i < path.size(); i++) {
        gameController.setPosition(path.get(i).i, path.get(i).j);
    }
}

public static void solveMaze(GameController gameController) {
    // get the start position and target position
    Position startPos = gameController.getPosition();
    Position targetPos = gameController.getTargetPosition();
    
    // four directions: up, right, down, left
    int[][] directions = {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1}
    };
    
    // use queue to store positions to visit and their paths
    Queue<Position> queue = new LinkedList<>();
    
    // store parent node for each position to reconstruct path
    Map<String, Position> parent = new HashMap<>();
    
    // mark start position as visited and add to queue
    gameController.setVisited(startPos.i, startPos.j, true);
    queue.offer(new Position(startPos.i, startPos.j));
    parent.put(startPos.i + "," + startPos.j, new Position(-1, -1));
    
    // BFS main loop
    while (!queue.isEmpty()) {
        Position current = queue.poll();
        
        // check if current position is the target
        if (current.i == targetPos.i && current.j == targetPos.j) {
            // target found, reconstruct and execute path
            reconstructAndExecutePath(gameController, parent, startPos, targetPos);
            return;
        }
        
        // explore four directions
        for (int[] dir : directions) {
            int nextI = current.i + dir[0];
            int nextJ = current.j + dir[1];
            
            // if next position is wall or visited, skip
            if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
                continue;
            }
            
            // mark as visited and add to queue
            gameController.setVisited(nextI, nextJ, true);
            queue.offer(new Position(nextI, nextJ));
            parent.put(nextI + "," + nextJ, new Position(current.i, current.j));
        }
    }
}

cpp

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

#include <vector>
#include <queue>
#include <unordered_map>
#include <string>

// Assume Position struct
struct Position {
    int i, j;
};

// Assume GameController is an interface class
class GameController {
public:
    virtual Position getPosition() = 0;
    virtual Position getTargetPosition() = 0;
    virtual void setPosition(int i, int j) = 0;
    virtual void setVisited(int i, int j, bool visited) = 0;
    virtual bool isBlock(int i, int j) = 0;
    virtual bool isVisited(int i, int j) = 0;
};

// reconstruct path and execute moves
void reconstructAndExecutePath(GameController* gameController, 
                              const std::unordered_map<std::string, Position>& parent, 
                              const Position& startPos, const Position& targetPos) {
    // start from target, reconstruct path through parent nodes
    std::vector<Position> path;
    Position current = targetPos;
    bool hasParent = true;
    
    while (hasParent) {
        path.push_back(current);
        std::string key = std::to_string(current.i) + "," + std::to_string(current.j);
        auto it = parent.find(key);
        if (it != parent.end() && (it->second.i != -1 || it->second.j != -1)) {
            current = it->second;
        } else {
            hasParent = false;
        }
    }
    
    // reverse the path
    std::reverse(path.begin(), path.end());
    
    // execute path movement (skip start position)
    for (size_t i = 1; i < path.size(); i++) {
        gameController->setPosition(path[i].i, path[i].j);
    }
}

void solveMaze(GameController* gameController) {
    // get the start position and target position
    Position startPos = gameController->getPosition();
    Position targetPos = gameController->getTargetPosition();
    
    // four directions: up, right, down, left
    std::vector<std::vector<int>> directions = {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1}
    };
    
    // use queue to store positions to visit and their paths
    std::queue<Position> queue;
    
    // store parent node for each position to reconstruct path
    std::unordered_map<std::string, Position> parent;
    
    // mark start position as visited and add to queue
    gameController->setVisited(startPos.i, startPos.j, true);
    queue.push({startPos.i, startPos.j});
    parent[std::to_string(startPos.i) + "," + std::to_string(startPos.j)] = {-1, -1};
    
    // BFS main loop
    while (!queue.empty()) {
        Position current = queue.front();
        queue.pop();
        
        // check if current position is the target
        if (current.i == targetPos.i && current.j == targetPos.j) {
            // target found, reconstruct and execute path
            reconstructAndExecutePath(gameController, parent, startPos, targetPos);
            return;
        }
        
        // explore four directions
        for (const auto& dir : directions) {
            int nextI = current.i + dir[0];
            int nextJ = current.j + dir[1];
            
            // if next position is wall or visited, skip
            if (gameController->isBlock(nextI, nextJ) || gameController->isVisited(nextI, nextJ)) {
                continue;
            }
            
            // mark as visited and add to queue
            gameController->setVisited(nextI, nextJ, true);
            queue.push({nextI, nextJ});
            parent[std::to_string(nextI) + "," + std::to_string(nextJ)] = {current.i, current.j};
        }
    }
}

python

# The game panel only supports submitting JavaScript code
# The code in other languages is only for understanding

from collections import deque

def solve_maze(game_controller):
    # get the start position and target position
    start_pos = game_controller.get_position()
    target_pos = game_controller.get_target_position()
    
    # four directions: up, right, down, left
    directions = [
        [-1, 0],
        [0, 1],
        [1, 0],
        [0, -1]
    ]
    
    # use queue to store positions to visit and their paths
    queue = deque()
    
    # store parent node for each position to reconstruct path
    parent = {}
    
    # mark start position as visited and add to queue
    game_controller.set_visited(start_pos['i'], start_pos['j'], True)
    queue.append({'i': start_pos['i'], 'j': start_pos['j']})
    parent[f"{start_pos['i']},{start_pos['j']}"] = None
    
    # BFS main loop
    while queue:
        current = queue.popleft()
        
        # check if current position is the target
        if current['i'] == target_pos['i'] and current['j'] == target_pos['j']:
            # target found, reconstruct and execute path
            reconstruct_and_execute_path(game_controller, parent, start_pos, target_pos)
            return
        
        # explore four directions
        for direction in directions:
            next_i = current['i'] + direction[0]
            next_j = current['j'] + direction[1]
            
            # if next position is wall or visited, skip
            if game_controller.is_block(next_i, next_j) or game_controller.is_visited(next_i, next_j):
                continue
            
            # mark as visited and add to queue
            game_controller.set_visited(next_i, next_j, True)
            queue.append({'i': next_i, 'j': next_j})
            parent[f"{next_i},{next_j}"] = {'i': current['i'], 'j': current['j']}

# reconstruct path and execute moves
def reconstruct_and_execute_path(game_controller, parent, start_pos, target_pos):
    # start from target, reconstruct path through parent nodes
    path = []
    current = {'i': target_pos['i'], 'j': target_pos['j']}
    
    while current is not None:
        path.append(current)
        key = f"{current['i']},{current['j']}"
        current = parent[key]
    
    # reverse the path
    path.reverse()
    
    # execute path movement (skip start position)
    for i in range(1, len(path)):
        game_controller.set_position(path[i]['i'], path[i]['j'])

// The game panel only supports submitting JavaScript code
// The code in other languages is only for understanding

import "strconv"

// Assume Position struct
type Position struct {
    I int `json:"i"`
    J int `json:"j"`
}

// Assume GameController is an interface
type GameController interface {
    GetPosition() Position
    GetTargetPosition() Position
    SetPosition(i, j int)
    SetVisited(i, j int, visited bool)
    IsBlock(i, j int) bool
    IsVisited(i, j int) bool
}

// reconstruct path and execute moves
func reconstructAndExecutePath(gameController GameController, parent map[string]Position, startPos, targetPos Position) {
    // start from target, reconstruct path through parent nodes
    var path []Position
    current := targetPos
    
    for {
        path = append(path, current)
        key := strconv.Itoa(current.I) + "," + strconv.Itoa(current.J)
        if p, exists := parent[key]; exists && (p.I != -1 || p.J != -1) {
            current = p
        } else {
            break
        }
    }
    
    // reverse the path
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    
    // execute path movement (skip start position)
    for i := 1; i < len(path); i++ {
        gameController.SetPosition(path[i].I, path[i].J)
    }
}

func solveMaze(gameController GameController) {
    // get the start position and target position
    startPos := gameController.GetPosition()
    targetPos := gameController.GetTargetPosition()
    
    // four directions: up, right, down, left
    directions := [][]int{
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1},
    }
    
    // use queue to store positions to visit and their paths
    var queue []Position
    
    // store parent node for each position to reconstruct path
    parent := make(map[string]Position)
    
    // mark start position as visited and add to queue
    gameController.SetVisited(startPos.I, startPos.J, true)
    queue = append(queue, Position{I: startPos.I, J: startPos.J})
    parent[strconv.Itoa(startPos.I)+","+strconv.Itoa(startPos.J)] = Position{I: -1, J: -1}
    
    // BFS main loop
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        
        // check if current position is the target
        if current.I == targetPos.I && current.J == targetPos.J {
            // target found, reconstruct and execute path
            reconstructAndExecutePath(gameController, parent, startPos, targetPos)
            return
        }
        
        // explore four directions
        for _, dir := range directions {
            nextI := current.I + dir[0]
            nextJ := current.J + dir[1]
            
            // if next position is wall or visited, skip
            if gameController.IsBlock(nextI, nextJ) || gameController.IsVisited(nextI, nextJ) {
                continue
            }
            
            // mark as visited and add to queue
            gameController.SetVisited(nextI, nextJ, true)
            queue = append(queue, Position{I: nextI, J: nextJ})
            parent[strconv.Itoa(nextI)+","+strconv.Itoa(nextJ)] = Position{I: current.I, J: current.J}
        }
    }
}

javascript

function solveMaze(gameController) {
    // get the start position and target position
    const startPos = gameController.getPosition();
    const targetPos = gameController.getTargetPosition();
    
    // four directions: up, right, down, left
    const directions = [
        [-1, 0],
        [0, 1],
        [1, 0],
        [0, -1]
    ];
    
    // use queue to store positions to visit and their paths
    const queue = [];
    
    // store parent node for each position to reconstruct path
    const parent = new Map();
    
    // mark start position as visited and add to queue
    gameController.setVisited(startPos.i, startPos.j, true);
    queue.push({ i: startPos.i, j: startPos.j });
    parent.set(`${startPos.i},${startPos.j}`, null);
    
    // BFS main loop
    while (queue.length > 0) {
        const current = queue.shift();
        
        // check if current position is the target
        if (current.i === targetPos.i && current.j === targetPos.j) {
            // target found, reconstruct and execute path
            reconstructAndExecutePath(gameController, parent, startPos, targetPos);
            return;
        }
        
        // explore four directions
        for (let dir of directions) {
            const nextI = current.i + dir[0];
            const nextJ = current.j + dir[1];
            
            // if next position is wall or visited, skip
            if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
                continue;
            }
            
            // mark as visited and add to queue
            gameController.setVisited(nextI, nextJ, true);
            queue.push({ i: nextI, j: nextJ });
            parent.set(`${nextI},${nextJ}`, { i: current.i, j: current.j });
        }
    }
}

// reconstruct path and execute moves
function reconstructAndExecutePath(gameController, parent, startPos, targetPos) {
    // start from target, reconstruct path through parent nodes
    const path = [];
    let current = { i: targetPos.i, j: targetPos.j };
    
    while (current != null) {
        path.push(current);
        const key = `${current.i},${current.j}`;
        current = parent.get(key);
    }
    // reverse the path
    path.reverse();
    
    // execute path movement (skip start position)
    for (let i = 1; i < path.length; i++) {
        gameController.setPosition(path[i].i, path[i].j);
    }
}