【游戏开发算法每日一记】使用随机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("  ");
                    else
                        Console.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");
	}

	
}