当前位置：网站首页>[unity] random generation of two-dimensional cave map
[unity] random generation of two-dimensional cave map
2022-07-26 01:22:00 【Cheap meow】
See others' examples ：
https://blog.csdn.net/l773575310/article/details/72803191
https://github.com/ZeroChiLi/CaveGeneration
1. Map generation method
1. Create a new two-dimensional array of enumeration types map, Each element represents each lattice , The enumeration content represents the kind of lattice , For example, open space 、 wall
2. Custom random fill algorithm initialization map
3. Custom smoothing algorithm processing map
for example ： Traverse map Every element , Calculate its surroundings 8 Elements are the number of walls , be equal to 4 Hours remain the same , More than half of them become walls , Otherwise, it is open space
4. Remove small walls 、 empty
The walls and cavities to be removed are map Some consecutive elements of the same enumeration type in , use List<Vector2> Express , Find out by breadth first
Delete the small wall first , In this way, some rooms will become larger , When looking for a small hole , The size of all rooms is the final size
Then delete the small hole , And save what hasn't been deleted as a room
Finally, take the largest room as the main room
5. Room connection
Traverse all rooms , For every room , Look for possible , The one closest to you , Rooms not connected to yourself
Traverse the edge nodes of two rooms when connecting , Find the nearest pair of edge nodes between the two rooms , Calculate the slope of the straight line generated by two points , Calculate the node on the straight line through the slope , Put it in the list , Traverse the list , Taking the given channel width as the radius , List elements are centered , All map nodes in the circle , All set as open space
Iterate several times , Until the number of rooms connected to the main room is equal to the number of all rooms -1
After that mesh I may not be able to use it , I don't want to see it hhh
2. Modifications to the sample code
Assets/Scripts/Room.cs in UpdateEdgeTiles The function may put duplicate boundary points
// Update the room edge tile set
public void UpdateEdgeTiles(TileType[,] map)
{
edgeTiles.Clear();
// Traverse the upper, lower, left and right grids , Judge whether there is a wall
foreach (Coord tile in tiles)
for (int i = 0; i < 4; i++)
{
int x = tile.tileX + upDownLeftRight[i, 0];
int y = tile.tileY + upDownLeftRight[i, 1];
if (map[x, y] == TileType.Wall)
{
edgeTiles.Add(tile);
continue;
}
}
}
take Coord The structure is changed to Vector2Int And then use Contain Judge whether you have let go
// Update the room edge tile set
public void UpdateEdgeTiles(TileType[,] map)
{
edgeTiles.Clear();
// Traverse the upper, lower, left and right grids , Judge whether there is a wall
foreach (Vector2Int tile in tiles)
for (int i = 0; i < 4; i++)
{
int x = tile.x + upDownLeftRight[i, 0];
int y = tile.y + upDownLeftRight[i, 1];
if (map[x, y] == TileType.Wall && !edgeTiles.Contains(tile))
{
edgeTiles.Add(tile);
}
}
}
I can't understand this step of connecting the source code to the room ……
// Connect rooms . Compare each room by two , Find the nearest room （ Relative to the previous room ） Connect it , The second room is not necessarily the nearest .
// The second parameter is False when , Step 1 operation ： Connect all rooms to the nearest room .
// The second parameter is True when , Step 2 operation ： Is to connect all rooms to the main room .
private void ConnectClosestRooms(List<Room> allRooms, bool forceAccessibilityFromMainRoom = false)
{
#region It belongs to the second step ：roomListA It is a room queue that has not been connected to the main room , roomListB Yes, it is connected to the room B Queues .
List<Room> roomListA = new List<Room>();
List<Room> roomListB = new List<Room>();
if (forceAccessibilityFromMainRoom) // Whether forced connection is required （ Directly or indirectly ） Go to the main room .
{
foreach (Room room in allRooms)
if (room.isAccessibleFromMainRoom)
roomListB.Add(room); // Add... That has been connected to the main room ListB.
else
roomListA.Add(room); // Add... That is not connected to the main room ListA. Null will end recursion .
}
else
{
roomListA = allRooms;
roomListB = allRooms;
}
#endregion
int bestDistance = 0;
Vector2Int bestTileA = new Vector2Int();
Vector2Int bestTileB = new Vector2Int();
Room bestRoomA = new Room();
Room bestRoomB = new Room();
bool possibleConnectionFound = false;
foreach (Room roomA in roomListA) // Traverse those not connected to the main room ListA.
{
if (!forceAccessibilityFromMainRoom) // First step ： If there is no request to connect to the main room .
{
possibleConnectionFound = false; // Then you can't complete the connection task , More than one connection is required .
if (roomA.connectedRooms.Count > 0) // There are connecting rooms , skip , Continue to find the next connecting room .
continue;
}
#region Traverse roomListB, Find the distance from the current roomA Current roomB.
foreach (Room roomB in roomListB)
{
if (roomA == roomB || roomA.IsConnected(roomB))
continue;
foreach (var tileA in roomA.edgeTiles)
foreach (var tileB in roomB.edgeTiles)
{
int distanceBetweenRooms = (tileA - tileB).sqrMagnitude;
// If you find something closer （ relative roomA） room , Update shortest path .
if (distanceBetweenRooms < bestDistance || !possibleConnectionFound)
{
bestDistance = distanceBetweenRooms;
possibleConnectionFound = true;
bestTileA = tileA;
bestTileB = tileB;
bestRoomA = roomA;
bestRoomB = roomB;
}
}
}
#endregion
// First step ： Find two new connecting rooms , But there is no requirement to connect to the main room . Create channels .
if (possibleConnectionFound && !forceAccessibilityFromMainRoom)
CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB);
}
// Step one to step two ： When all rooms are connected , But it is not required to connect all to the main room , Then start connecting to the main room .
if (!forceAccessibilityFromMainRoom)
ConnectClosestRooms(allRooms, true);
// The second step ： When successfully found, it can be connected to the main room , access , Continue to find a room that can be connected to the main room .
if (possibleConnectionFound && forceAccessibilityFromMainRoom)
{
CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB);
ConnectClosestRooms(allRooms, true);
}
}
Based on the principle of simplicity first, I changed it to
/// <summary>
/// Connect all rooms to the main room
/// </summary>
private void ConnectAllRoomsToMainRoom(List<Room> allRooms)
{
Room mainRoom = null;
foreach (var room in allRooms)
{
if (room.isMainRoom)
{
mainRoom = room;
break;
}
}
if (mainRoom == null)
return;
foreach (var room in allRooms)
{
ConnectToClosestRoom(room, allRooms);
}
if (mainRoom.connectedRooms.Count != allRooms.Count - 1)
{
ConnectAllRoomsToMainRoom(allRooms);
}
}
/// <summary>
/// Connect this room to the nearest room that is not connected to you
/// The room to be connected that meets the conditions may not be found
/// </summary>
/// <param name="roomA"></param>
/// <param name="roomListB"></param>
private void ConnectToClosestRoom(Room roomA, List<Room> roomListB)
{
int bestDistance = Int32.MaxValue;
Vector2Int bestTileA = new Vector2Int();
Vector2Int bestTileB = new Vector2Int();
Room bestRoomB = null;
foreach (Room roomB in roomListB)
{
if (roomA == roomB || roomA.IsConnected(roomB))
continue;
foreach (var tileA in roomA.edgeTiles)
foreach (var tileB in roomB.edgeTiles)
{
int distanceBetweenRooms = (tileA - tileB).sqrMagnitude;
// If you find something closer （ relative roomA） room , Update shortest path .
if (distanceBetweenRooms < bestDistance)
{
bestDistance = distanceBetweenRooms;
bestTileA = tileA;
bestTileB = tileB;
bestRoomB = roomB;
}
}
}
if(bestRoomB != null)
CreatePassage(roomA, bestRoomB, bestTileA, bestTileB);
}
The effect is the same
3. All codes related to map generation
Assets/Scripts/MapGenerator.cs
using UnityEngine;
using System.Collections.Generic;
using System;
public enum TileType {
Empty, Wall }
public class MapGenerator : MonoBehaviour
{
#region Public Variables
public int width = 64;
public int height = 36;
public string seed; // Random seeds .
public bool useRandomSeed;
[Range(0, 100)]
public int randomFillPercent = 45; // Random fill percentage , The bigger the hole, the smaller .
[Range(0, 20)]
public int smoothLevel = 4; // Smoothness .
public int wallThresholdSize = 50; // Threshold for clearing small walls .
public int roomThresholdSize = 50; // Threshold value for clearing holes .
public int passageWidth = 4; // passageway （ Room to room ） Width .
public int borderSize = 1;
public bool showGizmos;
#endregion
private TileType[,] map; // Atlas ,Empty Is empty ,Wall For solid walls .
readonly int[,] upDownLeftRight = new int[4, 2] {
{
0, 1 }, {
0, -1 }, {
-1, 0 }, {
1, 0 } };
// Store the last actual and effective empty room .
private List<Room> survivingRooms = new List<Room>();
private void Start()
{
GenerateMap();
}
private void Update()
{
if (Input.GetMouseButtonDown(0))
{
survivingRooms.Clear();
GenerateMap();
}
}
// Generate random map .
private void GenerateMap()
{
map = new TileType[width, height];
RandomFillMap();
for (int i = 0; i < smoothLevel; i++)
SmoothMap();
// Clear the small hole , Small wall .
ProcessMap();
// Connect the surviving rooms .
ConnectAllRoomsToMainRoom(survivingRooms);
}
// Fill the map randomly .
private void RandomFillMap()
{
if (useRandomSeed)
seed = Time.time.ToString();
System.Random pseudoRandom = new System.Random(seed.GetHashCode());
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
if (x == 0 || x == width - 1 || y == 0 || y == height - 1)
map[x, y] = TileType.Wall;
else
map[x, y] = (pseudoRandom.Next(0, 100) < randomFillPercent) ? TileType.Wall : TileType.Empty;
}
// Smooth map
private void SmoothMap()
{
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
{
int neighbourWallTiles = GetSurroundingWallCount(x, y);
if (neighbourWallTiles > 4) // There are more than four solid walls around , It's also a solid wall .
map[x, y] = TileType.Wall;
else if (neighbourWallTiles < 4) // More than four around are cavities , Then I'm empty .
map[x, y] = TileType.Empty;
// And if it's four four open , Then keep it the same .
}
}
// Get around the point 8 Points are solid walls （map[x,y] == 1） The number of .
private int GetSurroundingWallCount(int gridX, int gridY)
{
int wallCount = 0;
for (int neighbourX = gridX - 1; neighbourX <= gridX + 1; neighbourX++)
for (int neighbourY = gridY - 1; neighbourY <= gridY + 1; neighbourY++)
if (neighbourX >= 0 && neighbourX < width && neighbourY >= 0 && neighbourY < height)
{
if (neighbourX != gridX || neighbourY != gridY)
wallCount += map[neighbourX, neighbourY] == TileType.Wall ? 1 : 0;
}
else
wallCount++;
return wallCount;
}
// Processing maps , Clear the small hole , Small wall , Connecting rooms .
private void ProcessMap()
{
// Get the index of the largest room
int currentIndex = 0, maxIndex = 0, maxSize = 0;
// Get wall area
List<List<Vector2Int>> wallRegions = GetRegions(TileType.Wall);
foreach (List<Vector2Int> wallRegion in wallRegions)
if (wallRegion.Count < wallThresholdSize)
foreach (Vector2Int tile in wallRegion)
map[tile.x, tile.y] = TileType.Empty; // Shovel out those less than the threshold .
// Get empty area
List<List<Vector2Int>> roomRegions = GetRegions(TileType.Empty);
foreach (List<Vector2Int> roomRegion in roomRegions)
{
if (roomRegion.Count < roomThresholdSize)
foreach (Vector2Int tile in roomRegion)
map[tile.x, tile.y] = TileType.Wall; // Fill in everything less than the threshold .
else
{
survivingRooms.Add(new Room(roomRegion, map)); // Add to the list of surviving rooms .
if (maxSize < roomRegion.Count)
{
maxSize = roomRegion.Count;
maxIndex = currentIndex; // Find the index of the largest room .
}
++currentIndex;
}
}
if (survivingRooms.Count == 0)
Debug.LogError("No Survived Rooms Here!!");
else
{
survivingRooms[maxIndex].isMainRoom = true; // The largest room is the main room .
survivingRooms[maxIndex].isAccessibleFromMainRoom = true;
}
}
// Get the area
private List<List<Vector2Int>> GetRegions(TileType tileType)
{
List<List<Vector2Int>> regions = new List<List<Vector2Int>>();
bool[,] mapFlags = new bool[width, height];
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
if (mapFlags[x, y] == false && map[x, y] == tileType)
regions.Add(GetRegionTiles(x, y, tileType, ref mapFlags));
return regions;
}
// Get the area from this point , Breadth first algorithm .
private List<Vector2Int> GetRegionTiles(int startX, int startY, TileType tileType, ref bool[,] mapFlags)
{
List<Vector2Int> tiles = new List<Vector2Int>();
Queue<Vector2Int> queue = new Queue<Vector2Int>();
queue.Enqueue(new Vector2Int(startX, startY));
mapFlags[startX, startY] = true;
while (queue.Count > 0)
{
Vector2Int tile = queue.Dequeue(); // Pop up the first in the queue , Add to the list to return .
tiles.Add(tile);
// Traverse the upper, lower, left and right grids
for (int i = 0; i < 4; i++)
{
int x = tile.x + upDownLeftRight[i, 0];
int y = tile.y + upDownLeftRight[i, 1];
if (IsInMapRange(x, y) && mapFlags[x, y] == false && map[x, y] == tileType)
{
mapFlags[x, y] = true;
queue.Enqueue(new Vector2Int(x, y));
}
}
}
return tiles;
}
/// <summary>
/// Connect all rooms to the main room
/// </summary>
private void ConnectAllRoomsToMainRoom(List<Room> allRooms)
{
Room mainRoom = null;
foreach (var room in allRooms)
{
if (room.isMainRoom)
{
mainRoom = room;
break;
}
}
if (mainRoom == null)
return;
foreach (var room in allRooms)
{
ConnectToClosestRoom(room, allRooms);
}
if (mainRoom.connectedRooms.Count != allRooms.Count - 1)
{
ConnectAllRoomsToMainRoom(allRooms);
}
}
/// <summary>
/// Connect this room to the nearest room that is not connected to you
/// The room to be connected that meets the conditions may not be found
/// </summary>
/// <param name="roomA"></param>
/// <param name="roomListB"></param>
private void ConnectToClosestRoom(Room roomA, List<Room> roomListB)
{
int bestDistance = Int32.MaxValue;
Vector2Int bestTileA = new Vector2Int();
Vector2Int bestTileB = new Vector2Int();
Room bestRoomB = null;
foreach (Room roomB in roomListB)
{
if (roomA == roomB || roomA.IsConnected(roomB))
continue;
foreach (var tileA in roomA.edgeTiles)
foreach (var tileB in roomB.edgeTiles)
{
int distanceBetweenRooms = (tileA - tileB).sqrMagnitude;
// If you find something closer （ relative roomA） room , Update shortest path .
if (distanceBetweenRooms < bestDistance)
{
bestDistance = distanceBetweenRooms;
bestTileA = tileA;
bestTileB = tileB;
bestRoomB = roomB;
}
}
}
if(bestRoomB != null)
CreatePassage(roomA, bestRoomB, bestTileA, bestTileB);
}
// Create a passage for two rooms .
private void CreatePassage(Room roomA, Room roomB, Vector2Int tileA, Vector2Int tileB)
{
Room.ConnectRooms(roomA, roomB);
//Debug.DrawLine(Vector2IntToWorldPoint(tileA), Vector2IntToWorldPoint(tileB), Color.green, 100);
List<Vector2Int> line = GetLine(tileA, tileB);
foreach (Vector2Int coord in line)
DrawCircle(coord, passageWidth);
}
// Get the point where the two direct line segments pass .
private List<Vector2Int> GetLine(Vector2Int from, Vector2Int to)
{
List<Vector2Int> line = new List<Vector2Int>();
int x = from.x;
int y = from.y;
int dx = to.x - from.x;
int dy = to.y - from.y;
bool inverted = false;
int step = Math.Sign(dx);
int gradientStep = Math.Sign(dy);
int longest = Mathf.Abs(dx);
int shortest = Mathf.Abs(dy);
if (longest < shortest)
{
inverted = true;
longest = Mathf.Abs(dy);
shortest = Mathf.Abs(dx);
step = Math.Sign(dy);
gradientStep = Math.Sign(dx);
}
int gradientAccumulation = longest / 2; // Gradient accumulation , Half of the longest side .
for (int i = 0; i < longest; i++)
{
line.Add(new Vector2Int(x, y));
if (inverted)
y += step;
else
x += step;
gradientAccumulation += shortest; // The gradient grows to the length of the short side each time .
if (gradientAccumulation >= longest)
{
if (inverted)
x += gradientStep;
else
y += gradientStep;
gradientAccumulation -= longest;
}
}
return line;
}
// With a little c Origin ,r As the radius of , draw a circle （ Dismantles wall ）.
private void DrawCircle(Vector2Int c, int r)
{
for (int x = -r; x <= r; x++)
for (int y = -r; y <= r; y++)
if (x * x + y * y <= r * r)
{
int drawX = c.x + x;
int drawY = c.y + y;
if (IsInMapRange(drawX, drawY))
map[drawX, drawY] = TileType.Empty;
}
}
// Determine whether the coordinates are in the map , No matter the wall or the hole .
private bool IsInMapRange(int x, int y)
{
return x >= 0 && x < width && y >= 0 && y < height;
}
}
Assets/Scripts/Room.cs
using System;
using System.Collections.Generic;
using UnityEngine;
class Room : IComparable<Room>
{
public List<Vector2Int> tiles; // All the coordinates .
public List<Vector2Int> edgeTiles = new List<Vector2Int>(); // The coordinates of the side .
public List<Room> connectedRooms; // A room directly connected to it .
public int roomSize; // Namely tiles.Count.
public bool isAccessibleFromMainRoom; // Whether it can be connected to the main room .
public bool isMainRoom; // Whether the main room （ The biggest room ）.
readonly int[,] upDownLeftRight = new int[4, 2] {
{
0, 1 }, {
0, -1 }, {
-1, 0 }, {
1, 0 } };
public Room() {
}
public Room(List<Vector2Int> roomTiles, TileType[,] map)
{
tiles = roomTiles;
roomSize = tiles.Count;
connectedRooms = new List<Room>();
UpdateEdgeTiles(map);
}
// Update the room edge tile set
public void UpdateEdgeTiles(TileType[,] map)
{
edgeTiles.Clear();
// Traverse the upper, lower, left and right grids , Judge whether there is a wall
foreach (Vector2Int tile in tiles)
for (int i = 0; i < 4; i++)
{
int x = tile.x + upDownLeftRight[i, 0];
int y = tile.y + upDownLeftRight[i, 1];
if (map[x, y] == TileType.Wall && !edgeTiles.Contains(tile))
{
edgeTiles.Add(tile);
}
}
}
// If you can connect to the main room , Mark that other connected rooms can also be connected to the main room .
public void MarkAccessibleFromMainRoom()
{
if (!isAccessibleFromMainRoom)
{
isAccessibleFromMainRoom = true;
foreach (Room connectedRoom in connectedRooms) // The room connected with him can be connected to the main room .
connectedRoom.MarkAccessibleFromMainRoom();
}
}
// Connecting rooms
public static void ConnectRooms(Room roomA, Room roomB)
{
// If any room can be connected to the main room , The other room can also be connected .
if (roomA.isAccessibleFromMainRoom)
roomB.MarkAccessibleFromMainRoom();
else if (roomB.isAccessibleFromMainRoom)
roomA.MarkAccessibleFromMainRoom();
roomA.connectedRooms.Add(roomB);
roomB.connectedRooms.Add(roomA);
}
// Whether to connect to another room
public bool IsConnected(Room otherRoom)
{
return connectedRooms.Contains(otherRoom);
}
// Compare room sizes
public int CompareTo(Room otherRoom)
{
return otherRoom.roomSize.CompareTo(roomSize);
}
}
边栏推荐
- 腾讯员工晒出薪资：真实985毕业薪资，大家看我还有救吗？网友：日薪？
- Leetcode537. Complex multiplication (yes, solved)
- Redis数据结构详解，结合书本
- 【Code】剑指offer 03数组中重复的数字
- [software development specification III] [software version naming Specification]
- NodeJS 基于 Dapr 构建云原生微服务应用，从 0 到 1 快速上手指南
- FastJson 处理泛型
- 1.30 升级bin文件添加后缀及文件长度
- 光纤通信中信号劣化的原因
- [RTOS training camp] course learning methods and structural knowledge review + linked list knowledge
猜你喜欢
Jushi ｜ Haitai Fangyuan appears at the 5th Digital China Construction Summit
《分布式微服务电商》专题(一)-项目简介
MulDA: A Multilingual Data Augmentation Framework for Low-Resource Cross-Lingual NER 阅读笔记
聚势｜海泰方圆亮相第五届数字中国建设峰会
两阶段提交和三阶段提交
8、学习MySQL 创建数据表
Machine learning: Bayesian Networks
NLP introduction + practice: Chapter 3: gradient descent and back propagation
![[CTF] crypto preliminary basic outline](/img/a9/bbaff7a23396dff4e486d5cd026b31.png)
[CTF] crypto preliminary basic outline
1.30 升级bin文件添加后缀及文件长度
随机推荐
数据库系统原理与应用教程（057）—— MySQL 练习题
[data mining] differences, advantages and disadvantages between generative model and discriminant model
NLP introduction + practice: Chapter 4: using pytorch to manually realize linear regression
Modify CSV
FastJson 处理泛型
Cross linguistic transfer of correlations between parts of speech and Gazette Features Reading Notes
Special topic of distributed micro service e-commerce (I) - Project Introduction
【Go】如何控制协程的最大并发数
中心对称的二进制模式CSLBP，matlab
Centrosymmetric binary mode cslbp, matlab
健身房一年关店8000家，逆势盈利的工作室是怎么开的？
Format JS code and debug JS code
Handler message mechanism - FWK layer
数据库系统原理与应用教程（056）—— MySQL 查询（十八）：其他类型函数的用法
Mulda: a multilingual data augmentation framework for low resource cross linguistic ner reading notes
手游多开用模拟器多开游戏如何切换IP搬砖
《nlp入门+实战：第四章：使用pytorch手动实现线性回归 》
Leetcode537. Complex multiplication (yes, solved)
The gym closes 8000 stores a year. How does the studio that bucks the trend and makes profits open?
Nodejs builds cloud native microservice applications based on dapr, a quick start guide from 0 to 1