【游戏】求解迷宫
原创约 2057 字
这是经典的迷宫游戏,你可以使用键盘方向键或 UI 上的按钮控制角色移动,移动到右下角的终点即可通关。
思考题
猜猜不同风格的迷宫地图是如何生成的?如果让你来生成迷宫地图,应该使用什么算法?
游戏页面支持切换不同风格的迷宫地图,你可以切换不同的地图使用 DFS/BFS 算法求解,然后回放求解过程,就能直观地看出不同风格地图的特点了。
迷宫生成算法是非常有趣的话题,而且有一定的难度,我们会在下一个迷宫游戏中讲解。
用算法求解迷宫比较简单,从起点开始递归遍历上下左右四个方向,可以理解为遍历「四叉树」或者遍历一幅无向图,用 DFS 或 BFS 算法肯定可以解决。其中 BFS 算法找到的路径必然是最短路径,而 DFS 解法找到的路径不一定是最短路径。
首先贴一个 DFS 解法供大家参考:
java
// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑
// 假设 Position 类
class Position {
public int i, j;
public Position(int i, int j) {
this.i = i;
this.j = j;
}
}
// 假设 GameController 是一个接口
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) {
// 获取起始位置和目标位置
Position startPos = gameController.getPosition();
Position targetPos = gameController.getTargetPosition();
// 四个方向:上、右、下、左
int[][] directions = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
// 外部变量存储是否找到路径
boolean[] pathFound = {false};
class MazeSolver {
void dfs(int currentI, int currentJ) {
// Base case: 如果已经找到路径,直接返回
if (pathFound[0]) {
return;
}
// 检查是否到达目标位置
if (currentI == targetPos.i && currentJ == targetPos.j) {
pathFound[0] = true;
return;
}
// 标记当前位置为已访问
gameController.setVisited(currentI, currentJ, true);
// 尝试四个方向
for (int[] dir : directions) {
int nextI = currentI + dir[0];
int nextJ = currentJ + dir[1];
// 如果下一个位置是墙或者已访问,跳过
if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
continue;
}
// 移动到下一个位置
gameController.setPosition(nextI, nextJ);
// 递归搜索
dfs(nextI, nextJ);
// 递归搜索完成后,回退
gameController.setPosition(currentI, currentJ);
}
}
}
// 从起始位置开始DFS
new MazeSolver().dfs(startPos.i, startPos.j);
}
cpp
// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑
#include <vector>
// 假设 Position 结构体
struct Position {
int i, j;
};
// 假设 GameController 是一个接口类
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) {
// 获取起始位置和目标位置
Position startPos = gameController->getPosition();
Position targetPos = gameController->getTargetPosition();
// 四个方向:上、右、下、左
std::vector<std::vector<int>> directions = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
// 外部变量存储是否找到路径
bool pathFound = false;
std::function<void(int, int)> dfs = [&](int currentI, int currentJ) {
// Base case: 如果已经找到路径,直接返回
if (pathFound) {
return;
}
// 检查是否到达目标位置
if (currentI == targetPos.i && currentJ == targetPos.j) {
pathFound = true;
return;
}
// 标记当前位置为已访问
gameController->setVisited(currentI, currentJ, true);
// 尝试四个方向
for (const auto& dir : directions) {
int nextI = currentI + dir[0];
int nextJ = currentJ + dir[1];
// 如果下一个位置是墙或者已访问,跳过
if (gameController->isBlock(nextI, nextJ) || gameController->isVisited(nextI, nextJ)) {
continue;
}
// 移动到下一个位置
gameController->setPosition(nextI, nextJ);
// 递归搜索
dfs(nextI, nextJ);
// 递归搜索完成后,回退
gameController->setPosition(currentI, currentJ);
}
};
// 从起始位置开始DFS
dfs(startPos.i, startPos.j);
}
python
# 游戏面板仅支持提交 JavaScript 代码
# 其他语言代码的作用是帮助大家理解算法逻辑
def solve_maze(game_controller):
# 获取起始位置和目标位置
start_pos = game_controller.get_position()
target_pos = game_controller.get_target_position()
# 四个方向:上、右、下、左
directions = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1]
]
# 外部变量存储是否找到路径
path_found = [False]
def dfs(current_i, current_j):
# Base case: 如果已经找到路径,直接返回
if path_found[0]:
return
# 检查是否到达目标位置
if current_i == target_pos['i'] and current_j == target_pos['j']:
path_found[0] = True
return
# 标记当前位置为已访问
game_controller.set_visited(current_i, current_j, True)
# 尝试四个方向
for direction in directions:
next_i = current_i + direction[0]
next_j = current_j + direction[1]
# 如果下一个位置是墙或者已访问,跳过
if game_controller.is_block(next_i, next_j) or game_controller.is_visited(next_i, next_j):
continue
# 移动到下一个位置
game_controller.set_position(next_i, next_j)
# 递归搜索
dfs(next_i, next_j)
# 递归搜索完成后,回退
game_controller.set_position(current_i, current_j)
# 从起始位置开始DFS
dfs(start_pos['i'], start_pos['j'])
go
// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑
// 假设 Position 结构体
type Position struct {
I int `json:"i"`
J int `json:"j"`
}
// 假设 GameController 是一个接口
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) {
// 获取起始位置和目标位置
startPos := gameController.GetPosition()
targetPos := gameController.GetTargetPosition()
// 四个方向:上、右、下、左
directions := [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}
// 外部变量存储是否找到路径
pathFound := false
var dfs func(int, int)
dfs = func(currentI, currentJ int) {
// Base case: 如果已经找到路径,直接返回
if pathFound {
return
}
// 检查是否到达目标位置
if currentI == targetPos.I && currentJ == targetPos.J {
pathFound = true
return
}
// 标记当前位置为已访问
gameController.SetVisited(currentI, currentJ, true)
// 尝试四个方向
for _, dir := range directions {
nextI := currentI + dir[0]
nextJ := currentJ + dir[1]
// 如果下一个位置是墙或者已访问,跳过
if gameController.IsBlock(nextI, nextJ) || gameController.IsVisited(nextI, nextJ) {
continue
}
// 移动到下一个位置
gameController.SetPosition(nextI, nextJ)
// 递归搜索
dfs(nextI, nextJ)
// 递归搜索完成后,回退
gameController.SetPosition(currentI, currentJ)
}
}
// 从起始位置开始DFS
dfs(startPos.I, startPos.J)
}
javascript
function solveMaze(gameController) {
// 获取起始位置和目标位置
const startPos = gameController.getPosition();
const targetPos = gameController.getTargetPosition();
// 四个方向:上、右、下、左
const directions = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1]
];
// 外部变量存储是否找到路径
let pathFound = false;
var dfs = function(currentI, currentJ) {
// Base case: 如果已经找到路径,直接返回
if (pathFound) {
return;
}
// 检查是否到达目标位置
if (currentI === targetPos.i && currentJ === targetPos.j) {
pathFound = true;
return;
}
// 标记当前位置为已访问
gameController.setVisited(currentI, currentJ, true);
// 尝试四个方向
for (let dir of directions) {
const nextI = currentI + dir[0];
const nextJ = currentJ + dir[1];
// 如果下一个位置是墙或者已访问,跳过
if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
continue;
}
// 移动到下一个位置
gameController.setPosition(nextI, nextJ);
// 递归搜索
dfs(nextI, nextJ);
// 递归搜索完成后,回退
gameController.setPosition(currentI, currentJ);
}
}
// 从起始位置开始DFS
dfs(startPos.i, startPos.j);
}
对于 BFS 解法,稍微有点小技巧,因为你要在 BFS 遍历的同时记录路径。
我们用一个 parent
数组记录每个位置的前驱节点,这样就可以从终点开始,反向回溯到起点,得到完整的路径。
参考解法如下:
java
// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑
import java.util.*;
// 假设 Position 类
class Position {
public int i, j;
public Position(int i, int j) {
this.i = i;
this.j = j;
}
}
// 假设 GameController 是一个接口
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 reconstructAndExecutePath(GameController gameController,
Map<String, Position> parent,
Position startPos, Position targetPos) {
// 从目标位置开始,通过父节点重建路径
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;
}
}
// 反转路径
Collections.reverse(path);
// 执行路径移动(跳过起始位置)
for (int i = 1; i < path.size(); i++) {
gameController.setPosition(path.get(i).i, path.get(i).j);
}
}
public static void solveMaze(GameController gameController) {
// 获取起始位置和目标位置
Position startPos = gameController.getPosition();
Position targetPos = gameController.getTargetPosition();
// 四个方向:上、右、下、左
int[][] directions = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
// 使用队列存储待访问的位置和路径
Queue<Position> queue = new LinkedList<>();
// 存储每个位置的前驱节点,用于重建路径
Map<String, Position> parent = new HashMap<>();
// 标记起始位置为已访问,并加入队列
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 主循环
while (!queue.isEmpty()) {
Position current = queue.poll();
// 检查是否到达目标位置
if (current.i == targetPos.i && current.j == targetPos.j) {
// 找到目标,重建并执行路径
reconstructAndExecutePath(gameController, parent, startPos, targetPos);
return;
}
// 探索四个方向
for (int[] dir : directions) {
int nextI = current.i + dir[0];
int nextJ = current.j + dir[1];
// 如果下一个位置是墙或者已访问,跳过
if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
continue;
}
// 标记为已访问并加入队列
gameController.setVisited(nextI, nextJ, true);
queue.offer(new Position(nextI, nextJ));
parent.put(nextI + "," + nextJ, new Position(current.i, current.j));
}
}
}
cpp
// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
// 假设 Position 结构体
struct Position {
int i, j;
};
// 假设 GameController 是一个接口类
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 reconstructAndExecutePath(GameController* gameController,
const std::unordered_map<std::string, Position>& parent,
const Position& startPos, const Position& targetPos) {
// 从目标位置开始,通过父节点重建路径
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;
}
}
// 反转路径
std::reverse(path.begin(), path.end());
// 执行路径移动(跳过起始位置)
for (size_t i = 1; i < path.size(); i++) {
gameController->setPosition(path[i].i, path[i].j);
}
}
void solveMaze(GameController* gameController) {
// 获取起始位置和目标位置
Position startPos = gameController->getPosition();
Position targetPos = gameController->getTargetPosition();
// 四个方向:上、右、下、左
std::vector<std::vector<int>> directions = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
// 使用队列存储待访问的位置和路径
std::queue<Position> queue;
// 存储每个位置的前驱节点,用于重建路径
std::unordered_map<std::string, Position> parent;
// 标记起始位置为已访问,并加入队列
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 主循环
while (!queue.empty()) {
Position current = queue.front();
queue.pop();
// 检查是否到达目标位置
if (current.i == targetPos.i && current.j == targetPos.j) {
// 找到目标,重建并执行路径
reconstructAndExecutePath(gameController, parent, startPos, targetPos);
return;
}
// 探索四个方向
for (const auto& dir : directions) {
int nextI = current.i + dir[0];
int nextJ = current.j + dir[1];
// 如果下一个位置是墙或者已访问,跳过
if (gameController->isBlock(nextI, nextJ) || gameController->isVisited(nextI, nextJ)) {
continue;
}
// 标记为已访问并加入队列
gameController->setVisited(nextI, nextJ, true);
queue.push({nextI, nextJ});
parent[std::to_string(nextI) + "," + std::to_string(nextJ)] = {current.i, current.j};
}
}
}
python
# 游戏面板仅支持提交 JavaScript 代码
# 其他语言代码的作用是帮助大家理解算法逻辑
from collections import deque
def solve_maze(game_controller):
# 获取起始位置和目标位置
start_pos = game_controller.get_position()
target_pos = game_controller.get_target_position()
# 四个方向:上、右、下、左
directions = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1]
]
# 使用队列存储待访问的位置和路径
queue = deque()
# 存储每个位置的前驱节点,用于重建路径
parent = {}
# 标记起始位置为已访问,并加入队列
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 主循环
while queue:
current = queue.popleft()
# 检查是否到达目标位置
if current['i'] == target_pos['i'] and current['j'] == target_pos['j']:
# 找到目标,重建并执行路径
reconstruct_and_execute_path(game_controller, parent, start_pos, target_pos)
return
# 探索四个方向
for direction in directions:
next_i = current['i'] + direction[0]
next_j = current['j'] + direction[1]
# 如果下一个位置是墙或者已访问,跳过
if game_controller.is_block(next_i, next_j) or game_controller.is_visited(next_i, next_j):
continue
# 标记为已访问并加入队列
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']}
# 重建路径并执行移动
def reconstruct_and_execute_path(game_controller, parent, start_pos, target_pos):
# 从目标位置开始,通过父节点重建路径
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]
# 反转路径
path.reverse()
# 执行路径移动(跳过起始位置)
for i in range(1, len(path)):
game_controller.set_position(path[i]['i'], path[i]['j'])
go
// 游戏面板仅支持提交 JavaScript 代码
// 其他语言代码的作用是帮助大家理解算法逻辑
import "strconv"
// 假设 Position 结构体
type Position struct {
I int `json:"i"`
J int `json:"j"`
}
// 假设 GameController 是一个接口
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 reconstructAndExecutePath(gameController GameController, parent map[string]Position, startPos, targetPos Position) {
// 从目标位置开始,通过父节点重建路径
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
}
}
// 反转路径
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
// 执行路径移动(跳过起始位置)
for i := 1; i < len(path); i++ {
gameController.SetPosition(path[i].I, path[i].J)
}
}
func solveMaze(gameController GameController) {
// 获取起始位置和目标位置
startPos := gameController.GetPosition()
targetPos := gameController.GetTargetPosition()
// 四个方向:上、右、下、左
directions := [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}
// 使用队列存储待访问的位置和路径
var queue []Position
// 存储每个位置的前驱节点,用于重建路径
parent := make(map[string]Position)
// 标记起始位置为已访问,并加入队列
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 主循环
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
// 检查是否到达目标位置
if current.I == targetPos.I && current.J == targetPos.J {
// 找到目标,重建并执行路径
reconstructAndExecutePath(gameController, parent, startPos, targetPos)
return
}
// 探索四个方向
for _, dir := range directions {
nextI := current.I + dir[0]
nextJ := current.J + dir[1]
// 如果下一个位置是墙或者已访问,跳过
if gameController.IsBlock(nextI, nextJ) || gameController.IsVisited(nextI, nextJ) {
continue
}
// 标记为已访问并加入队列
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) {
// 获取起始位置和目标位置
const startPos = gameController.getPosition();
const targetPos = gameController.getTargetPosition();
// 四个方向:上、右、下、左
const directions = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1]
];
// 使用队列存储待访问的位置和路径
const queue = [];
// 存储每个位置的前驱节点,用于重建路径
const parent = new Map();
// 标记起始位置为已访问,并加入队列
gameController.setVisited(startPos.i, startPos.j, true);
queue.push({ i: startPos.i, j: startPos.j });
parent.set(`${startPos.i},${startPos.j}`, null);
// BFS 主循环
while (queue.length > 0) {
const current = queue.shift();
// 检查是否到达目标位置
if (current.i === targetPos.i && current.j === targetPos.j) {
// 找到目标,重建并执行路径
reconstructAndExecutePath(gameController, parent, startPos, targetPos);
return;
}
// 探索四个方向
for (let dir of directions) {
const nextI = current.i + dir[0];
const nextJ = current.j + dir[1];
// 如果下一个位置是墙或者已访问,跳过
if (gameController.isBlock(nextI, nextJ) || gameController.isVisited(nextI, nextJ)) {
continue;
}
// 标记为已访问并加入队列
gameController.setVisited(nextI, nextJ, true);
queue.push({ i: nextI, j: nextJ });
parent.set(`${nextI},${nextJ}`, { i: current.i, j: current.j });
}
}
}
// 重建路径并执行移动
function reconstructAndExecutePath(gameController, parent, startPos, targetPos) {
// 从目标位置开始,通过父节点重建路径
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);
}
// 反转路径
path.reverse();
// 执行路径移动(跳过起始位置)
for (let i = 1; i < path.length; i++) {
gameController.setPosition(path[i].i, path[i].j);
}
}