当前位置：网站首页>[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);
}
}
边栏推荐
- 点屏注意事项
- Dijkstra 求最短路
- Lua basic grammar
- C语言进阶（一）动态分配内存
- Redis数据结构详解，结合书本
- How accurate is the IP address? What are dynamic IP and static IP? The most common method of switching IP
- 光纤通信中信号劣化的原因
- Arthas watch command to view the properties of objects in the array
- Server available resources query script
- Docker高级篇-Mysql主从复制
猜你喜欢
What are the ways to quickly improve programming skills in the process of programming learning?
Introduction to API testing
Redis数据结构详解，结合书本
Detailed explanation of rest assured interface testing framework
U++学习笔记 UStruct、UEnum声明以及函数库简单函数实现
Arthas watch 命令查看数组中对象的属性
网络文件传输之零拷贝
Cross-lingual Transfer of Correlations between Parts of Speech and Gaze Features 阅读笔记
Game thinking 17: Road finding engine recast and detour learning II: recast navigation grid generation process and limitations
代理IP服务器如何保证自身在网络中的信息安全呢
随机推荐
Docker高级篇-Mysql主从复制
Special topic of distributed micro service e-commerce (I) - Project Introduction
Leetcode537. 复数乘法(可以,已解决)
换ip软件的用途很广及原理 动态IP更换的四种方法来保护网络隐私
Case when of SQL
《分布式微服务电商》专题(一)-项目简介
Tutorial on the principle and application of database system (057) -- MySQL exercises
机器学习：贝叶斯网络
Paged query design of scenarios
[CTF] crypto preliminary basic outline
What are the ways to quickly improve programming skills in the process of programming learning?
数据库系统原理与应用教程（054）—— MySQL 查询（十六）：日期时间型函数的用法
The application and principle of changing IP software are very wide. Four methods of dynamic IP replacement are used to protect network privacy
Fundamentals of MATLAB shift operation
U++学习笔记 UStruct、UEnum声明以及函数库简单函数实现
Working principle of ZK rollups
Handler message mechanism - FWK layer
点屏注意事项
Codeforces Round ＃810 (Div. 2)A~C
[Go]三、最简单的RestFul API服务器