游戏引擎 【游戏开发算法每日一记】使用随机prime算法生成错综复杂效果的迷宫（C#，C++和Unity版）

‍个人主页：@元宇宙-秩沅

‍ hallo 欢迎 点赞 收藏⭐ 留言 加关注✅!

‍ 本文由 秩沅 原创

‍ 收录于专栏：Unity基础实战

⭐️⭐

文章目录

⭐️⭐⭐前言⭐（==1==）简单的prime算法——十字检测 c#版本的十字Primc++版本的十字PrimUnity版本的十字Prim（==2==）prime算法生成的效果 ⭐️⭐

⭐前言⭐

（1）简单的prime算法——十字检测

1.首先全部判定为墙，最外的为路包裹墙（类似于防止数组越界） 2.红色为它的检测范围(假设检测点在如图所示的位置)———（可先忽略此步骤）

——————

3.该检测点（紫色）需要在起点的旁边或者外墙旁边，已保证它可以生成主路线而不是死迷宫 4.生成后是这样的，没有出口，它不会自动打破墙 5，所以需要我们自己检测一波打出一个出口

运行结果

c#版本的十字Prim

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace algorithm

{

///

class PrimOfAlgorithm

{

public const int max = 40;

int[,] Maze = new int[max , max ]; //默认全为0 ，全为墙

Random random = new Random();

//X和Y方向的队列

List X = new List();

List Y = new List();

///

public void CreatMap()

{

//设置迷宫进口

Maze[2, 1] = 1;

//将最外围设置为路，包裹最外层的的墙，防止出界

for (int i = 0; i < max; i++)

{

Maze[i ,0]= 1;

Maze[i, max - 1] = 1;

Maze[0, i] = 1;

Maze[max - 1, i] = 1;

}

//设置一个坐标.该检测点需要在起点的旁边，或者旁边是外围路

X.Add (2);

Y.Add (2);

while( Y.Count > 0)

{

int index = random.Next(0, X.Count - 1); //随机性则有错综复杂的效果

int xPosition= X[index];

int yPosition = Y[index];

//判断上下左右是否有路

int count = 0;

for (int i = xPosition - 1; i <= xPosition + 1; i++) //左右位置

{

for (int j = yPosition - 1; j <= yPosition + 1; j++) //上下位置

{

//判断它是不是十字检测中的点，和判断它是否为路

if (Math.Abs(xPosition - i) + Math.Abs(yPosition - j) == 1 && Maze[i,j] > 0)

{

++count; //路++

}

}

}

//如果十字检测的路标记少于或等于1条？（为甚不直接小于1呢，因为它要保证生成一条主路）

if (count <= 1)

{

//将此刻的位置变成路

Maze[xPosition, yPosition] = 1;

for (int i = xPosition - 1; i <= xPosition + 1; i++)

{

for (int j = yPosition - 1; j <= yPosition + 1; j++)

{

//判断它是不是十字检测中的点并且是墙

if (Math.Abs(xPosition - i) + Math.Abs(yPosition - j) == 1 && Maze[i, j] == 0)

{

//把十字检测到的墙放入XY墙列表

X.Add(i);

Y.Add(j);

}

}

}

}

//删除列表中已经变成路的点

X.RemoveAt(0 + index );

Y.RemoveAt(0 + index ); //记住不能是Remove

}

//设置迷宫出口（出口不可能是四个底脚）

for (int i = max - 3; i >= 0; i--)

{

if (Maze[i, max - 3] == 1)

{

Maze[i, max - 2] = 1;

break;

}

}

//画迷宫

for (int i = 0; i < max; i++)

{

for (int j = 0; j < max; j++)

{

if (Maze[i, j] == 1)

Console.Write(" ");

else

Console.Write("囚");

}

Console.WriteLine();

}

}

static void Main(string[] args)

{

PrimOfAlgorithm aa = new PrimOfAlgorithm();

aa.CreatMap();

}

}

}

c++版本的十字Prim

#include

#include

#include

using namespace std;

static const int L = 44;

void CreateMaze();

int main()

{

CreateMaze();

}

void CreateMaze() {

int Maze[L][L] = { 0 };

vector X;

vector Y;

//最外围设置为路，可以有效的保护里面一层墙体，并防止挖出界

for (int i = 0; i < L; i++) {

Maze[i][0] = 1;

Maze[0][i] = 1;

Maze[L - 1][i] = 1;

Maze[i][L - 1] = 1;

}

//设置迷宫进口

Maze[2][1] = 1;

//任取初始值

X.push_back(2);

Y.push_back(2);

//当墙队列为空时结束循环

while (X.size()) {

//在墙队列中随机取一点

int r = rand() % X.size();

int x = X[r];

int y = Y[r];

//判读上下左右四个方向是否为路

int count = 0;

for (int i = x - 1; i < x + 2; i++) {

for (int j = y - 1; j < y + 2; j++) {

if (abs(x - i) + abs(y - j) == 1 && Maze[i][j] > 0) {

++count;

}

}

}

if (count <= 1) {

Maze[x][y] = 1;

//在墙队列中插入新的墙

for (int i = x - 1; i < x + 2; i++) {

for (int j = y - 1; j < y + 2; j++) {

if (abs(x - i) + abs(y - j) == 1 && Maze[i][j] == 0) {

X.push_back(i);

Y.push_back(j);

}

}

}

}

//删除当前墙

X.erase(X.begin() + r);

Y.erase(Y.begin() + r);

}

//设置出口 （从最下往上面判断）

for (int i = L - 3; i >= 0; i--) {

if (Maze[i][L - 3] == 1) {

Maze[i][L - 2] = 1;

break;

}

}

//画迷宫

for (int i = 0; i < L; i++){

for (int j = 0; j < L; j++) {

if (Maze[i][j] == 1) printf(" ");

else printf("囚");

}

printf("\n");

}

}

Unity版本的十字Prim

using System.Collections;

using System.Collections.Generic;

using UnityEngine;

//-------------------------------------

//—————————————————————————————————————

//___________项目:

//___________功能： 生成迷宫

//___________创建者：_____秩沅_____

//_____________________________________

//-------------------------------------

public class Muze : MonoBehaviour

{

const int max = 40;

//建立迷宫数组

private int[,] mauz = new int [max ,max ];

//墙列表

private List X = new List();

private List Y = new List();

//待加载资源

private GameObject m_prefab_tile;

private GameObject m_prefab_wall;

private void Awake()

{

//资源加载

m_prefab_tile = Resources.Load("prefabs/tile_white");

m_prefab_wall = Resources.Load("prefabs/cube_bread");

}

void Start()

{

//初始坐标

CreatMazu(new Vector2(2,1));

}

///

public void CreatMazu( Vector2 position)

{

//step1.设置外墙

for (int i = 0; i < max ; i++)

{

mauz[0, i] = 1;

mauz[i, 0] = 1;

mauz[i, max - 1] = 1;

mauz[max - 1, i] = 1;

}

//step2.将初始位置放入队列当中

X.Add((int )position.x);

Y.Add((int )position.y);

mauz[(int )position.x, (int )position.y] = 1; //它为起点

while(X.Count > 0) //当列表里面有值的时候，也代表有墙的时候

{

//step3:从列表中取判定点

int index = Random.Range(0, X.Count - 1); //从墙队列里面随机取一个下标

int xPosition = X[index];

int yPosition = Y[index];

int count = 0; //路的数量

//step4:道路判定

for (int i = xPosition - 1; i <= xPosition + 1; i++)

{

for (int j = yPosition - 1; j <= yPosition + 1; j++)

{

if (Mathf.Abs(xPosition - i) + Mathf.Abs(yPosition - j) == 1 && mauz[i, j] > 0)

{

count++;

}

}

}

//step5:变成路，添加墙

if (count <= 1)

{

mauz[xPosition, yPosition] = 1; //变成路

for (int i = xPosition - 1; i <= xPosition + 1; i++)

{

for (int j = yPosition - 1; j <= yPosition + 1; j++)

{

if (Mathf.Abs(xPosition - i) + Mathf.Abs(yPosition - j) == 1 && mauz[i, j] == 0)

{

X.Add(i);

Y.Add(j);

}

}

}

}

//step6:移除列表里面的墙

X.RemoveAt(0 + index);

Y.RemoveAt(0 + index);

}

//step7:检测一下设置出口

for (int i = max - 3 ; i > 0 ; i-- )

{

if(mauz[i,max - 3 ] == 1 )

{

mauz[i, max - 2] = 1;

break;

}

}

//step8:加载迷宫

for (int i = 0; i < max ; i++)

{

for (int j = 0; j < max ; j++)

{

if(mauz[i,j] == 0 )

{

GameObject ob = Instantiate(m_prefab_wall,new Vector3(i * 0.254f, 0 , j * 0.254f),Quaternion.identity );

ob.transform.SetParent(transform);

}

}

}

}

}

（2）prime算法生成的效果

迷宫相对比较自然，但迷宫的分岔路会比较多，适合生成错综复杂的地图效果，主路不是特别明显

初始化大地图，0代表墙，1代表道路，墙为地图边缘包裹 靠近地图边缘随机选取状态为1的道路点，作为出生点a 然后将 a 点周围所有的墙体点标记为待检测点，加入到待检测集合 从待检测集合随机取一个点 b ，判断顺着它方向的下一个点 c，是否是道路 如果是，则将这个待检测点墙体打通，将其移出待检测集合；将下一个点 c作为新的起点，重新执行第3步 如果不是就把这个待检测点移出待检测集合，重新作为墙体点 不断重复，直到待检测集合全部检查过，重新为空

⭐️⭐

⭐【Unityc#专题篇】之c#进阶篇】

⭐【Unityc#专题篇】之c#核心篇】

⭐【Unityc#专题篇】之c#基础篇】

⭐【Unity-c#专题篇】之c#入门篇】

⭐【Unityc#专题篇】—进阶章题单实践练习

⭐【Unityc#专题篇】—基础章题单实践练习

⭐【Unityc#专题篇】—核心章题单实践练习

你们的点赞 收藏⭐ 留言 关注✅是我持续创作，输出优质内容的最大动力！、

文章链接