Solve Maze Game
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:
// 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);
}
// 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);
}
# 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)
}
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:
// 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));
}
}
}
// 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};
}
}
}
# 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}
}
}
}
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);
}
}