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

编程入门行业动态更新时间:2024-10-25 08:19:20

【游戏开发<a href=https://www.elefans.com/category/jswz/34/1770096.html style= 算法每日一记】使用随机prime算法生成错综复杂效果的迷宫（C#和C++）"/>

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

👨‍💻个人主页：@元宇宙-秩沅

👨‍💻 hallo 欢迎点赞👍 收藏⭐ 留言📝 加关注✅!

👨‍💻 本文由秩沅原创

👨‍💻 收录于专栏：Unity基础实战

⭐🅰️⭐

文章目录

- ⭐🅰️⭐
- ⭐前言⭐
- 🎶（==1==）简单的prime算法——十字检测
- c#版本的十字Prim
- c++版本的十字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
{/// <summary>/// 该Prom算法，初始化时全部是墙/// </summary>class PrimOfAlgorithm{public const int max = 40;int[,] Maze = new int[max  , max ];  //默认全为0 ，全为墙Random random = new Random();//X和Y方向的队列List<int> X = new List<int>();List<int> Y = new List<int>();/// <summary>/// 生成迷宫/// </summary>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("  ");elseConsole.Write("囚");}Console.WriteLine();}}static void Main(string[] args){PrimOfAlgorithm aa = new PrimOfAlgorithm();aa.CreatMap();}}}

c++版本的十字Prim


#include <iostream>
#include<vector>
#include <windows.h>
using namespace std;
static const int L = 44;
void CreateMaze();
int main()
{CreateMaze();
}void CreateMaze() {int Maze[L][L] = { 0 };vector<int> X;vector<int> 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");}}