Roguelike电子游戏这一概念起源于上世纪八十年代的电子游戏——《Rogue》，该游戏具有随机地图、敌人、战利品，玩家永久死亡，游戏非线性等特点。
游戏的随机性保证玩家的每一次冒险体验都独一无二，在操作角色与敌人射爆厮杀时，永久死亡的机制让人血脉喷张，加上非线性游戏流程的特点能让玩家在每次战斗交替中间，根据自己的战斗、生存能力选择合适的探索路线，适当地将主导权交给玩家。
《Rogue》推出后大受好评，随之而来的是优秀的传承者们，如当时的《矮人要塞》、《马基埃亚尔的传说》，再到现在的《以撒的结合》、《死亡细胞》、《空洞骑士》等游戏（由于具有类似机制的游戏太多，因此业界将它们定义为“Roguelike”游戏）。它们继承了《Rogue》的优秀设计理念，并在其基础上再次创新，将Roguelike游戏发扬光大。
在Roguelike游戏中，随机地图的生成是最基础的功能。现在我们自己设计一套算法来实现它，具体需求如下：
- 随机生成N个房间，这每个房间至少要与一个房间连接（上下左右四个连接方向）
- 设置房间的门：如果有一个方向连接着另一个房间，则房间的该方向要有一扇门
- 生成的房间中要有一个开始房间（玩家出生的房间），和一个结束房间（BOSS房或通关房）
- 开始房间和结束房间要尽可能远
该功能的Demo类似于：
准备工作
由于房间是游戏开始前自动生成，因此我们需要做一个房间预制体：
白色部分为房间主体，黄色部分为房间的门，房间上的UI文本用于显示初始房间到这里的步数（方便调试）。
Room.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;
/// <summary>
/// 每个房间身上挂在该脚本，
/// 用于设置房间的门，在房间模型上显示开始房间走到该房间的步数
/// </summary>
/// <param name="upDoor">房间上方的门</param>
public class Room : MonoBehaviour
{
//房间四个方向的门，在开始时设置它们
public GameObject upDoor, downDoor, leftDoor, rightDoor;
//房间四个方向是否有其他房间，若有，则添加门
public bool upRoom, downRoom, leftRoom, rightRoom;
//开始房间到该房间的步数文本显示
public Text stepsText;
//房间门的个数
public int numDoors;
void Start()
{
upDoor.SetActive(upRoom);
downDoor.SetActive(downRoom);
leftDoor.SetActive(leftRoom);
rightDoor.SetActive(rightRoom);
}
}
随机生成房间
我们在场景里新建一个空物体，命名为 RoomGenerator ，将脚本 RoomGenerator.cs 挂在它身上，并在该物体下再新建一个空物体 Point
算法流程大致如下，从 Point 位置开始，生成一个房间，然后将 Point 随机向四个方向移动一个单位，若移动后的位置没有房间，则生成房间，若有则继续移动，直到找到可以生成房间的位置。
代码如下：
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.SceneManagement;
public class RoomGenerator : MonoBehaviour
{
//生成房间的四个方向
public enum Direction { up,down,left,right};
public Direction direction;
[Header("房间信息")]
public GameObject roomPrefab;
public int roomNumber;
[Header("位置控制")]
public Transform generatorPoint;
public float xOffset, yOffset;
public List<Room> rooms = new List<Room>();
public LayerMask roomLayer;
void Start()
{
GenerateRoom();
}
void Update()
{
if(Input.anyKeyDown)
{
SceneManager.LoadScene(SceneManager.GetActiveScene().name);
}
}
/// <summary>
/// 随机生成房间：
/// 在generatorPoint的位置生成room，并加入List →→
/// 随机移动generatorPoint →→ #1 or #2
/// 如果移动后的位置没有room，则执行开头步骤 #1
/// 如果移动后的位置有room，则继续随机移动 #2
/// </summary>
private void GenerateRoom()
{
for (int i = 0; i < roomNumber; i++)
{
//生成房间并将其脚本加入进rooms数组
rooms.Add(Instantiate(roomPrefab, generatorPoint.position, Quaternion.identity).GetComponent<Room>());
//移动generatorPoint
//为了解决room重叠问题而添加循环检测
//当generatorPoint走到有room的位置时，继续走，直到走到空位置
do
{
direction = (Direction)UnityEngine.Random.Range(0, 4);//取值为0到3整数
switch (direction)
{
case Direction.up:
generatorPoint.position += new Vector3(0, yOffset, 0);
break;
case Direction.down:
generatorPoint.position += new Vector3(0, -yOffset, 0);
break;
case Direction.left:
generatorPoint.position += new Vector3(-xOffset, 0, 0);
break;
case Direction.right:
generatorPoint.position += new Vector3(xOffset, 0, 0);
break;
}
} while (Physics2D.OverlapCircle(generatorPoint.position,0.2f,roomLayer));
}
}
}
设置房间
设置房间，包括房间的门、添加房间的墙壁和初始房间到次房间的距离。最后一项我们留到后面讨论，这里只设置前两项。
设置门的大致思路：遍历每个房间，查看它们上下左右是否有其他房间，若有，则将对应方向的布尔值设置为真，房间会根据四个方向的布尔值来设置让哪些门显示出来。
房间的墙壁我也做成了预制体，包括了所有开口情况一共十五个预制体。为了方便管理和调用，我们将它们声明在一个类里。
代码如下：
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.SceneManagement;
public class RoomGenerator : MonoBehaviour
{
//生成房间的四个方向
public enum Direction { up,down,left,right};
public Direction direction;
[Header("房间信息")]
public GameObject roomPrefab;
public int roomNumber;
[Header("位置控制")]
public Transform generatorPoint;
public float xOffset, yOffset;
public List<Room> rooms = new List<Room>();
public LayerMask roomLayer;
public Wall wall;
void Start()
{
GenerateRoom();
SetupRooms();
}
void Update()
{
if(Input.anyKeyDown)
{
SceneManager.LoadScene(SceneManager.GetActiveScene().name);
}
}
/// <summary>
/// 随机生成房间：
/// 在generatorPoint的位置生成room，并加入List →→
/// 随机移动generatorPoint →→ #1 or #2
/// 如果移动后的位置没有room，则执行开头步骤 #1
/// 如果移动后的位置有room，则继续随机移动 #2
/// </summary>
private void GenerateRoom()
{
for (int i = 0; i < roomNumber; i++)
{
//生成房间并将其脚本加入进rooms数组
rooms.Add(Instantiate(roomPrefab, generatorPoint.position, Quaternion.identity).GetComponent<Room>());
//移动generatorPoint
//为了解决room重叠问题而添加循环检测
//当generatorPoint走到有room的位置时，继续走，直到走到空位置
do
{
direction = (Direction)UnityEngine.Random.Range(0, 4);//取值为0到3整数
switch (direction)
{
case Direction.up:
generatorPoint.position += new Vector3(0, yOffset, 0);
break;
case Direction.down:
generatorPoint.position += new Vector3(0, -yOffset, 0);
break;
case Direction.left:
generatorPoint.position += new Vector3(-xOffset, 0, 0);
break;
case Direction.right:
generatorPoint.position += new Vector3(xOffset, 0, 0);
break;
}
} while (Physics2D.OverlapCircle(generatorPoint.position,0.2f,roomLayer));
}
}
/// <summary>
/// 设置房间，包括房间的门、到初始房间的距离、添加房间的墙壁
/// </summary>
/// <remarks>
/// 1、设置房间的门，若房间四个方向上有其他房间，则添加门
/// 2、计算初始房间到每个房间的距离（走几步）
/// 3、给房间添加墙壁：先看该room有几扇门，再判断是哪几扇门，最后生成对应墙壁的预制体
/// </remarks>
private void SetupRooms()
{
foreach(var room in rooms)
{
//设置门
room.upRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(0, yOffset, 0), 0.2f, roomLayer);
room.downRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(0, -yOffset, 0), 0.2f, roomLayer);
room.leftRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(-xOffset, 0, 0), 0.2f, roomLayer);
room.rightRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(xOffset, 0, 0), 0.2f, roomLayer);
//计算初始房间到该房间的步数
//在这里调用方法来设置房间到初始房间的步数
//生成房间的墙壁
if (room.upRoom)
room.numDoors++;
if (room.downRoom)
room.numDoors++;
if (room.leftRoom)
room.numDoors++;
if (room.rightRoom)
room.numDoors++;
switch (room.numDoors)
{
//只有一扇门的墙壁，下同
case 1:
{
if (room.upRoom)
Instantiate(wall.Wall_Up, room.gameObject.transform.position, Quaternion.identity);
else if (room.downRoom)
Instantiate(wall.Wall_Down, room.gameObject.transform.position, Quaternion.identity);
else if (room.leftRoom)
Instantiate(wall.Wall_Left, room.gameObject.transform.position, Quaternion.identity);
else if (room.rightRoom)
Instantiate(wall.Wall_Right, room.gameObject.transform.position, Quaternion.identity);
break;
}
case 2:
{
if (room.upRoom && room.leftRoom)
Instantiate(wall.Wall_UpLeft, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.rightRoom)
Instantiate(wall.Wall_UpRight, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.downRoom)
Instantiate(wall.Wall_UpDown, room.gameObject.transform.position, Quaternion.identity);
else if (room.leftRoom && room.rightRoom)
Instantiate(wall.Wall_LeftRight, room.gameObject.transform.position, Quaternion.identity);
else if (room.downRoom && room.rightRoom)
Instantiate(wall.Wall_DownRight, room.gameObject.transform.position, Quaternion.identity);
else if (room.downRoom && room.leftRoom)
Instantiate(wall.Wall_DownLeft, room.gameObject.transform.position, Quaternion.identity);
break;
}
case 3:
{
if (room.leftRoom && room.rightRoom && room.upRoom)
Instantiate(wall.Wall_LeftRightUp, room.gameObject.transform.position, Quaternion.identity);
else if (room.leftRoom && room.rightRoom && room.downRoom)
Instantiate(wall.Wall_LeftRightDown, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.downRoom && room.leftRoom)
Instantiate(wall.Wall_UpDownLeft, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.downRoom && room.rightRoom)
Instantiate(wall.Wall_UpDownRight, room.gameObject.transform.position, Quaternion.identity);
break;
}
case 4:
{
Instantiate(wall.Wall_All, room.gameObject.transform.position, Quaternion.identity);
break;
}
}
}
}
}
//新建一个类来保存所有墙壁的预制体，方便管理
[Serializable]//让它显示在Inspector面板上
public class Wall
{
public GameObject Wall_Up, Wall_Down, Wall_Left, Wall_Right,
Wall_UpLeft, Wall_UpRight, Wall_UpDown, Wall_LeftRight, Wall_DownRight, Wall_DownLeft,
Wall_LeftRightUp, Wall_LeftRightDown, Wall_UpDownLeft, Wall_UpDownRight,
Wall_All;
}
设置开始与结束房间
设置开始与结束房间，关键在于计算每个房间与初始房间的距离。接下来将介绍三种方法：
-
坐标计算方法
-
DFS寻找方法
-
坐标计算方法
我们的 RoomGenerator 游戏物体和它下面的 Point （代码里为generatorPoint）物体的坐标都为 (0,0,0) ，并且我们直接将生成在这里的房间（第一个房间）看作是开始房间。剩下的就是找结束房间，要求是尽可能离开始房间远，也就是离 (0,0,0) 远，因此我们可以直接通过计算得到。
遍历每个房间，将它们横纵坐标的绝对值加起来，得到步数，将步数写道房间的UI文本上。
得到了每个房间的步数，最后就是标记开始房间和结束房间了，这里我们通过改变房间的颜色来简单实现——开始房间为绿色，结束房间为红色。
方法代码如下：
private int CalculateToFindSteps(Vector3 position)
{
int res = (int)(Mathf.Abs(position.x / xOffset) + Mathf.Abs(position.y / yOffset));
return res;
}
//选择开始房间和结束房间并上色，方便区分
private void PaintRooms()
{
//开始房间
rooms[0].GetComponent<SpriteRenderer>().color = startColor;
Room tempRoom = null;
int count = 0;
foreach(var room in rooms)
{
if(int.Parse(room.stepsText.text)>count)
{
tempRoom = room;
count = int.Parse(room.stepsText.text);
}
}
tempRoom.GetComponent<SpriteRenderer>().color = endColor;
}
计算坐标方法的缺陷，如下图：
该方法将最右下角的房间标记为结束房间，虽然它是距离上最远的，但不是“路程”上最远的房间，虽然不是什么致命的缺陷，但看起来就是很不爽啊！
在下一节 “DFS寻找方法” 结尾来讨论 这两个方法的优缺点。
DFS寻找方法
DFS寻找结束房间的方法是为了解决坐标计算方法而提出的，能够避免结束房间后面还连接着普通房间的情况。
主要思路是：遍历所有房间，每个房间调用DFS方法，将自己的坐标当作参数传进去；DFS方法通过递归，从开始房间即 (0,0,0) 位置开始寻找参数坐标位置，每递归一次步数加一，当走到参数坐标位置时，返回步数。
方法代码如下：
/// <summary>
/// 用DFS的方法计算每个房间到初始房间的步数
/// </summary>
/// <param name="roomTransform">该房间的坐标</param>
/// <param name="pointPosition">当前点的坐标，初始值为初始房间的坐标即(0,0,0)</param>
private void DfsToFindSteps(Transform roomTransform,Vector3 pointPosition)
{
//当已经走到了目标房间，则不继续递归，返回
if (isFindRoom)
return;
//当当前位置没有房间或走到了重复房间，则返回剪枝
if (!Physics2D.OverlapCircle(pointPosition, 0.2f, roomLayer) || record.Contains(pointPosition))
{
return;
}
//走到了目标房间
if (pointPosition == roomTransform.position)
{
isFindRoom = true;
return;
}
//已走过房间也要排除在外，剪枝，用list存储已走过房间
stepsToStart++;
record.Add(pointPosition);
DfsToFindSteps(roomTransform, pointPosition + new Vector3(0, yOffset, 0));
DfsToFindSteps(roomTransform, pointPosition + new Vector3(0, -yOffset, 0));
DfsToFindSteps(roomTransform, pointPosition + new Vector3(-xOffset, 0, 0));
DfsToFindSteps(roomTransform, pointPosition + new Vector3(xOffset, 0, 0));
if (!isFindRoom)
{
//进入这里，说明当前坐标延申出的四个房间走不通，因此执行下面两句
stepsToStart--;
record.Remove(pointPosition);
}
}
DFS有寻找顺序
可以看到，由于我们算法写的搜索顺序为上、下、左、右，因此最后的结束房间为——从开始房间上方开始，绕了一圈回到了开始房间下方。（好蠢啊，虽然这种情况是小概率事件，具体看生成的房间分布情况）
坐标计算方法与DFS寻找方法优缺点：
坐标计算方法的优点在于：算法简单，快；不会出现路程较远的房间在开始房间旁边的情况。 但也有一个缺陷：会出现步数最大房间的后哦面还连通着另一个房间——这就导致，若步数最大的房间作为BOSS通关房间，那么后面一个房间就进不去了。 解决方案是在击败BOSS后，仍然可以探索地图（设计上）；或者在该房间周围再生成一个新房间作为BOSS房（技术上）。
DFS方法优点在于：不会出现必须经过BOSS房才能进入下一个房间的情况。 但缺点也很明显：算法较难，当房间较多时时间成本高；可能会出现步数最大房间在初始房间旁边的情况； 第二个缺点，是因为DFS其实也是有搜索方向优先级的，这个优先级由我们自己定义。 解决方案也有两种：设置一个成就，比如探索第一个房间就为BOSS房，并击败了BOSS，这样会让玩家以为这是游戏的隐藏机制（设计上）；或者计算房间与初始房间的相对坐标通过相对坐标来决定DFS的查找方向优先级——比如房间在初始房间的左上角，则优先执行向上和向左的搜索，其他情况同理（技术上）。
BFS寻找方法
BFS寻找方法能完美解决上面两种方法的缺陷，为什么不先介绍BFS呢？因为如果先介绍了那前面两种算法该放在文章的哪里呢嘎嘎嘎嘎嘎（？
BFS是一轮一轮地检查队列里的元素的，我们让每一轮只检查上一轮所有房间的所有邻居房间，如果检查到的位置与目标房间位置相等，则返回；若这一轮没有检查到，则将这一轮房间的所有邻居房间入队，并且记录步数加一，直到找到目标房间位置。
具体方法代码如下：
/// <summary>
/// 用BFS的方式来计算开始房间到该房间的步数
/// </summary>
/// <param name="roomTransform">该房间的位置</param>
/// <remarks>
/// 从开始房间开始BFS，每次对内元素出队就与 roomTransform 的位置进行比较
/// 若相等，表示找到了，将它的 stepsToStart 值设置好，并返回
/// stepsToStart 的值如何确定？——
/// 每执行完“一轮”出队操作，将 count + 1，count 就是步数
/// </remarks>
private void BfsToFindSteps(Transform roomTransform)
{
stepsToStart = 0;
record.Clear();
int count = 0;
bfsQueue.Enqueue(rooms[0].transform.position);
Vector3 pointPosition;//用来找邻居坐标
while(bfsQueue.Count!=0)
{
int size = bfsQueue.Count;
for(int i=0;i<size;++i)
{
Vector3 tempTransform = bfsQueue.Dequeue();
if(roomTransform.position==tempTransform)//走到了目标房间，给出步数并返回
{
stepsToStart = count;
bfsQueue.Clear();
return;
}
record.Add(tempTransform);
pointPosition = tempTransform;//要开始找邻居坐标了！站好位置
//邻居入队
if(!record.Contains(pointPosition + new Vector3(0, yOffset, 0)) && Physics2D.OverlapCircle(pointPosition+new Vector3(0,yOffset,0),0.2f,roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(0, yOffset, 0));
}
if (!record.Contains(pointPosition + new Vector3(0, -yOffset, 0)) && Physics2D.OverlapCircle(pointPosition + new Vector3(0, -yOffset, 0), 0.2f, roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(0, -yOffset, 0));
}
if (!record.Contains(pointPosition + new Vector3(-xOffset, 0, 0)) && Physics2D.OverlapCircle(pointPosition + new Vector3(-xOffset, 0, 0), 0.2f, roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(-xOffset, 0, 0));
}
if (!record.Contains(pointPosition + new Vector3(xOffset, 0, 0)) && Physics2D.OverlapCircle(pointPosition + new Vector3(xOffset, 0, 0), 0.2f, roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(xOffset, 0, 0));
}
}
count++;
}
}
总结
RoomGenerator.cs
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.SceneManagement;
public class RoomGenerator : MonoBehaviour
{
//生成房间的四个方向
public enum Direction { up,down,left,right};
public Direction direction;
[Header("房间信息")]
public GameObject roomPrefab;
public int roomNumber;
public Color startColor, endColor;
private int stepsToStart;
[Header("位置控制")]
public Transform generatorPoint;
public float xOffset, yOffset;
public List<Room> rooms = new List<Room>();
public LayerMask roomLayer;
public List<Vector3> record = new List<Vector3>();//DFS和BFS的记录数组
public bool isFindRoom;//DFS查找方式会用到
public Queue<Vector3> bfsQueue = new Queue<Vector3>();//BFS的队列
public Wall wall;
void Start()
{
GenerateRoom();
SetupRooms();
PaintRooms();
}
void Update()
{
if(Input.anyKeyDown)
{
SceneManager.LoadScene(SceneManager.GetActiveScene().name);
}
}
/// <summary>
/// 随机生成房间：
/// 在generatorPoint的位置生成room，并加入List →→
/// 随机移动generatorPoint →→ #1 or #2
/// 如果移动后的位置没有room，则执行开头步骤 #1
/// 如果移动后的位置有room，则继续随机移动 #2
/// </summary>
private void GenerateRoom()
{
for (int i = 0; i < roomNumber; i++)
{
//生成房间并将其脚本加入进rooms数组
rooms.Add(Instantiate(roomPrefab, generatorPoint.position, Quaternion.identity).GetComponent<Room>());
//移动generatorPoint
//为了解决room重叠问题而添加循环检测
//当generatorPoint走到有room的位置时，继续走，直到走到空位置
do
{
direction = (Direction)UnityEngine.Random.Range(0, 4);//取值为0到3整数
switch (direction)
{
case Direction.up:
generatorPoint.position += new Vector3(0, yOffset, 0);
break;
case Direction.down:
generatorPoint.position += new Vector3(0, -yOffset, 0);
break;
case Direction.left:
generatorPoint.position += new Vector3(-xOffset, 0, 0);
break;
case Direction.right:
generatorPoint.position += new Vector3(xOffset, 0, 0);
break;
}
} while (Physics2D.OverlapCircle(generatorPoint.position,0.2f,roomLayer));
}
}
//选择开始房间和结束房间并上色，方便区分
private void PaintRooms()
{
//开始房间
rooms[0].GetComponent<SpriteRenderer>().color = startColor;
//用Dfs方法后，上色
//DfsPaint();
//上色
Paint();
}
/// <summary>
/// 用DFS方法后的上色方法
/// </summary>
/// <remarks>
/// 为什么要给用DFS方法计算步数后再单独写一个它专属的上色方法？
/// 因为DFS的bug(feature)，可能会出现两个或以上的最大步数房间
/// 但这两个房间与初始房间的直线距离可能不同
/// 我们就将直线距离长的作为最终房间
/// </remarks>
private void DfsPaint()
{
int index = 0;
//存放步数相同房间的索引
List<int> tempRooms = new List<int>();
for (int i = 1; i < roomNumber; ++i)
{
if (int.Parse(rooms[i].stepsText.text) > int.Parse(rooms[index].stepsText.text))
index = i;
//如果有步数相同的，则存储起来，后面选择距离远的那一个房间
if (int.Parse(rooms[i].stepsText.text) == int.Parse(rooms[index].stepsText.text))
tempRooms.Add(i);
}
if (tempRooms.Count > 0)
{
for (int i = 0; i < tempRooms.Count; ++i)
{
//如果该房间步数等于最大步数
if (int.Parse(rooms[tempRooms[i]].stepsText.text) == int.Parse(rooms[index].stepsText.text))
{
//并且该房间离开始房间的距离比index房间距离长
if (rooms[tempRooms[i]].gameObject.transform.position.sqrMagnitude > rooms[index].gameObject.transform.position.sqrMagnitude)
{
//那么index更改为该房间的索引
index = tempRooms[i];
}
}
}
}
rooms[index].GetComponent<SpriteRenderer>().color = endColor;
}
/// <summary>
/// 给最终房间上色
/// </summary>
private void Paint()
{
Room tempRoom = null;
int count = 0;
foreach(var room in rooms)
{
if(int.Parse(room.stepsText.text)>count)
{
tempRoom = room;
count = int.Parse(room.stepsText.text);
}
}
tempRoom.GetComponent<SpriteRenderer>().color = endColor;
}
/// <summary>
/// 设置房间，包括房间的门、到初始房间的距离、添加房间的墙壁
/// </summary>
/// <remarks>
/// 1、设置房间的门，若房间四个方向上有其他房间，则添加门
/// 2、计算初始房间到每个房间的距离（走几步）
/// 3、给房间添加墙壁：先看该room有几扇门，再判断是哪几扇门，最后生成对应墙壁的预制体
/// </remarks>
private void SetupRooms()
{
foreach(var room in rooms)
{
//设置门
room.upRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(0, yOffset, 0), 0.2f, roomLayer);
room.downRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(0, -yOffset, 0), 0.2f, roomLayer);
room.leftRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(-xOffset, 0, 0), 0.2f, roomLayer);
room.rightRoom = Physics2D.OverlapCircle(room.transform.position + new Vector3(xOffset, 0, 0), 0.2f, roomLayer);
//计算初始房间到该房间的步数
/******************************************************/
//用DFS的方法计算初始房间到该房间的步数
//stepsToStart = 0;
//record.Clear();
//isFindRoom = false;
//DfsToFindSteps(room.gameObject.transform, new Vector3(0, 0, 0));
//room.stepsText.text = stepsToStart.ToString();
/******************************************************/
/******************************************************/
//用计算坐标的方法计算初始房间到该房间的步数
//room.stepsText.text = CalculateToFindSteps(room.gameObject.transform.position).ToString();
/******************************************************/
/******************************************************/
//用BFS的方法计算初始房间到该房间的步数
BfsToFindSteps(room.gameObject.transform);
room.stepsText.text = stepsToStart.ToString();
/******************************************************/
//生成房间的墙壁
if (room.upRoom)
room.numDoors++;
if (room.downRoom)
room.numDoors++;
if (room.leftRoom)
room.numDoors++;
if (room.rightRoom)
room.numDoors++;
switch (room.numDoors)
{
//只有一扇门的墙壁，下同
case 1:
{
if (room.upRoom)
Instantiate(wall.Wall_Up, room.gameObject.transform.position, Quaternion.identity);
else if (room.downRoom)
Instantiate(wall.Wall_Down, room.gameObject.transform.position, Quaternion.identity);
else if (room.leftRoom)
Instantiate(wall.Wall_Left, room.gameObject.transform.position, Quaternion.identity);
else if (room.rightRoom)
Instantiate(wall.Wall_Right, room.gameObject.transform.position, Quaternion.identity);
break;
}
case 2:
{
if (room.upRoom && room.leftRoom)
Instantiate(wall.Wall_UpLeft, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.rightRoom)
Instantiate(wall.Wall_UpRight, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.downRoom)
Instantiate(wall.Wall_UpDown, room.gameObject.transform.position, Quaternion.identity);
else if (room.leftRoom && room.rightRoom)
Instantiate(wall.Wall_LeftRight, room.gameObject.transform.position, Quaternion.identity);
else if (room.downRoom && room.rightRoom)
Instantiate(wall.Wall_DownRight, room.gameObject.transform.position, Quaternion.identity);
else if (room.downRoom && room.leftRoom)
Instantiate(wall.Wall_DownLeft, room.gameObject.transform.position, Quaternion.identity);
break;
}
case 3:
{
if (room.leftRoom && room.rightRoom && room.upRoom)
Instantiate(wall.Wall_LeftRightUp, room.gameObject.transform.position, Quaternion.identity);
else if (room.leftRoom && room.rightRoom && room.downRoom)
Instantiate(wall.Wall_LeftRightDown, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.downRoom && room.leftRoom)
Instantiate(wall.Wall_UpDownLeft, room.gameObject.transform.position, Quaternion.identity);
else if (room.upRoom && room.downRoom && room.rightRoom)
Instantiate(wall.Wall_UpDownRight, room.gameObject.transform.position, Quaternion.identity);
break;
}
case 4:
{
Instantiate(wall.Wall_All, room.gameObject.transform.position, Quaternion.identity);
break;
}
}
}
}
/// <summary>
/// 用DFS的方法计算每个房间到初始房间的步数
/// </summary>
/// <param name="roomTransform">该房间的坐标</param>
/// <param name="pointPosition">当前点的坐标，初始值为初始房间的坐标即(0,0,0)</param>
private void DfsToFindSteps(Transform roomTransform,Vector3 pointPosition)
{
//当已经走到了目标房间，则不继续递归，返回
if (isFindRoom)
return;
//当当前位置没有房间或走到了重复房间，则返回剪枝
if (!Physics2D.OverlapCircle(pointPosition, 0.2f, roomLayer) || record.Contains(pointPosition))
{
return;
}
//走到了目标房间
if (pointPosition == roomTransform.position)
{
isFindRoom = true;
return;
}
//已走过房间也要排除在外，剪枝，用list存储已走过房间
stepsToStart++;
record.Add(pointPosition);
DfsToFindSteps(roomTransform, pointPosition + new Vector3(0, yOffset, 0));
DfsToFindSteps(roomTransform, pointPosition + new Vector3(0, -yOffset, 0));
DfsToFindSteps(roomTransform, pointPosition + new Vector3(-xOffset, 0, 0));
DfsToFindSteps(roomTransform, pointPosition + new Vector3(xOffset, 0, 0));
if (!isFindRoom)
{
//进入这里，说明当前坐标延申出的四个房间走不通，因此执行下面两句
stepsToStart--;
record.Remove(pointPosition);
}
}
private int CalculateToFindSteps(Vector3 position)
{
int res = (int)(Mathf.Abs(position.x / xOffset) + Mathf.Abs(position.y / yOffset));
return res;
}
/*DFS和计算房间坐标两种方法都可以实现查找房间与起点房间的步数
* 计算房间坐标的方法优点在于：
* 算法简单，快；不会出现步数较大的房间在起点房间旁边的情况
* 但也有一个缺陷：会出现步数最大房间的后面还连通着另一个房间——
* 这就导致，若步数最大房间作为boss通关房间，那么后面一个房间就进不去了
* 解决方案是在击败boss后，仍然可以探索地图（设计上）；或者在该房间周围再生成一个新房间作为boss房（技术上）
*
* DFS方法优点在于：不会出现必须经过boss房才能进入下一个房间的情况
* 但缺点也很明显：算法较难，当房间较多时时间成本高；可能会出现步数最大房间在初始房间旁边的情况
* 第二个缺点，是因为DFS其实也是有搜索方向优先级的，这个优先级由我们自己定义
* 如上面的代码就是以“上下左右”的顺序来查找到达房间的路径
* 解决方案也有两种：
* 设计上：设置一个成就，如探索第一个房间就为boss房，并击败了boss，这样会让玩家以为这是游戏的隐藏机制
* 技术上：计算房间与初始房间的相对坐标，通过相对坐标来决定DFS的查找方向优先级——
* 比如若房间在初始房间的左上角，则优先执行向上和向左的搜索，其他情况同理
*/
/// <summary>
/// 用BFS的方式来计算开始房间到该房间的步数
/// </summary>
/// <param name="roomTransform">该房间的位置</param>
/// <remarks>
/// 从开始房间开始BFS，每次对内元素出队就与 roomTransform 的位置进行比较
/// 若相等，表示找到了，将它的 stepsToStart 值设置好，并返回
/// stepsToStart 的值如何确定？——
/// 每执行完“一轮”出队操作，将 count + 1，count 就是步数
/// </remarks>
private void BfsToFindSteps(Transform roomTransform)
{
stepsToStart = 0;
record.Clear();
int count = 0;
bfsQueue.Enqueue(rooms[0].transform.position);
Vector3 pointPosition;//用来找邻居坐标
while(bfsQueue.Count!=0)
{
int size = bfsQueue.Count;
for(int i=0;i<size;++i)
{
Vector3 tempTransform = bfsQueue.Dequeue();
if(roomTransform.position==tempTransform)//走到了目标房间，给出步数并返回
{
stepsToStart = count;
bfsQueue.Clear();
return;
}
record.Add(tempTransform);
pointPosition = tempTransform;//要开始找邻居坐标了！站好位置
//邻居入队
if(!record.Contains(pointPosition + new Vector3(0, yOffset, 0)) && Physics2D.OverlapCircle(pointPosition+new Vector3(0,yOffset,0),0.2f,roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(0, yOffset, 0));
}
if (!record.Contains(pointPosition + new Vector3(0, -yOffset, 0)) && Physics2D.OverlapCircle(pointPosition + new Vector3(0, -yOffset, 0), 0.2f, roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(0, -yOffset, 0));
}
if (!record.Contains(pointPosition + new Vector3(-xOffset, 0, 0)) && Physics2D.OverlapCircle(pointPosition + new Vector3(-xOffset, 0, 0), 0.2f, roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(-xOffset, 0, 0));
}
if (!record.Contains(pointPosition + new Vector3(xOffset, 0, 0)) && Physics2D.OverlapCircle(pointPosition + new Vector3(xOffset, 0, 0), 0.2f, roomLayer))
{
bfsQueue.Enqueue(pointPosition + new Vector3(xOffset, 0, 0));
}
}
count++;
}
}
}
//新建一个类来保存所有墙壁的预制体，方便管理
[Serializable]//让它显示在Inspector面板上
public class Wall
{
public GameObject Wall_Up, Wall_Down, Wall_Left, Wall_Right,
Wall_UpLeft, Wall_UpRight, Wall_UpDown, Wall_LeftRight, Wall_DownRight, Wall_DownLeft,
Wall_LeftRightUp, Wall_LeftRightDown, Wall_UpDownLeft, Wall_UpDownRight,
Wall_All;
}