Java迷宫生成与寻路算法：基于数组实现37

本文将详细介绍如何使用Java语言，结合数组数据结构，实现迷宫的生成和寻路。我们将探讨两种常见的迷宫生成算法：深度优先搜索 (DFS) 和递归分割法，以及一种高效的寻路算法：A* 算法。整个过程都基于数组来表示迷宫地图，方便理解和实现。

一、迷宫表示：基于二维数组

我们使用一个二维整型数组来表示迷宫。数组的每个元素代表一个单元格，其值表示该单元格的状态：
* 0: 可通行路径
* 1: 墙壁

例如，一个 5x5 的迷宫可以表示为：
int[][] maze = {
{1, 1, 1, 1, 1},
{1, 0, 0, 0, 1},
{1, 1, 1, 0, 1},
{1, 0, 0, 0, 1},
{1, 1, 1, 1, 1}
};

其中，1表示墙壁，0表示可以通行的路径。起始点和终点可以分别用额外的变量记录坐标。

二、迷宫生成算法

2.1 深度优先搜索 (DFS) 生成迷宫

DFS 算法是一种递归算法，它从一个随机单元格开始，随机选择一个方向前进，直到访问所有单元格或到达边界。在前进过程中，它会打通与相邻单元格的墙壁，形成迷宫通路。
import ;
public class MazeGeneratorDFS {
private int[][] maze;
private int rows, cols;
private Random random;
public MazeGeneratorDFS(int rows, int cols) {
= rows;
= cols;
= new int[rows][cols];
= new Random();
// 初始化迷宫为墙壁
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
maze[i][j] = 1;
}
}
generateMaze(0, 0);
}
private void generateMaze(int row, int col) {
maze[row][col] = 0; // 标记当前单元格为通路
int[] directions = {0, 1, 2, 3}; // 上右下左
shuffleArray(directions);
for (int dir : directions) {
int newRow = row + (dir == 0 ? -2 : (dir == 2 ? 2 : 0));
int newCol = col + (dir == 1 ? 2 : (dir == 3 ? -2 : 0));
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && maze[newRow][newCol] == 1) {
maze[row + (dir == 0 ? -1 : (dir == 2 ? 1 : 0))][col + (dir == 1 ? 1 : (dir == 3 ? -1 : 0))] = 0; // 打通墙壁
generateMaze(newRow, newCol);
}
}
}
// Fisher-Yates shuffle algorithm
private void shuffleArray(int[] arr) {
for (int i = - 1; i > 0; i--) {
int j = (i + 1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public int[][] getMaze() {
return maze;
}

public static void main(String[] args) {
MazeGeneratorDFS generator = new MazeGeneratorDFS(15, 15);
int[][] maze = ();
for (int[] row : maze) {
for (int cell : row) {
(cell + " ");
}
();
}
}
}