【Unity3d】 (广度优先搜索)简单的迷宫寻路与返回路径

自嘲的快乐 2017-08-11

思路:

1.在生成迷宫的txt文件中,画出迷宫。

2.读取迷宫的时候,标记哪个位置有墙。

3.寻路使用BFS算法,从(0,0)开始上下左右扩散,找到(1,0)(0,1)(-1,0)(0,-1)这几个点,并判断这几个点中是否有为迷宫的墙的位置,没墙就标记一个新的起点,记录当前位置与搜索的步数为1,并依次起点扩散,直到迷宫的所有位置都已找完。(如在一个迷宫起点倒水,水会从起点扩散到终点);

4.扩散完,往回找一条线性的路径,就需要把终点位置,当作起点,找与该位置相差为1步的点,直到找到起点的位置结束。


寻路:

//墙的预制体

public GameObject prefabsWall;

//点击屏幕生成起点和终点的预制体

public GameObject prefabsPoint;

//寻路扩散的预制体

public GameObject prefabsRoad;

//寻路完成返回直线路径的预制体

public GameObject prefabsBack;

public GameObject prefabsMove;

//开始的X坐标

public int startX = 0;

//开始的Y坐标

public int startY = 0;

//结束的X坐标

public int endX = 0;

//结束的Y坐标

public int endY = 0;

//生成迷宫的列数

public int row;

//生成迷宫的行数

public int colum;

//标记迷宫的路径

int[,] map;

//标记寻路时保存路径

SearchData[,] searchMap;

//记录寻路的路径

List<Pos> record = new List<Pos>();

//记录寻路完成后返回路径

List<Pos> line = new List<Pos>();

public List<Pos> move = new List<Pos>();

int count = 0;

Ray ray;

RaycastHit hit;

RaycastHit hit_other;

bool IsBack = false;

GameObject move1;

GameObject move2;

void Start()

{

//初始化

searchMap = new SearchData[row, colum];

map = new int[row, colum];

ReadMapFile();

StartCoroutine(PrintMap());

//在unity中,输入起点终点位置,来寻路

//StartCoroutine(Search()));

}

void Update()

{

//在迷宫范围内点击指定起点和终点来寻路

Click();

if (count == 2)

{

StartCoroutine(Search());

count += 1;

}

//显示返回路径

if (IsBack == false && Input.GetKeyDown(KeyCode.Space))

{

StartCoroutine(RoadBack());

}

}

//读取迷宫,并标记墙的位置

public void ReadMapFile()

{

//找到画墙的txt,文件要保存在Assets中

string path = Application.dataPath + "//" + "Map.txt";

if (!File.Exists(path))

{

return;

}

FileStream fs = new FileStream(path, FileMode.Open, FileAccess.Read);

StreamReader read = new StreamReader(fs, Encoding.Default);

string strReadline;

int y = 0;

while ((strReadline = read.ReadLine()) != null)

{

for (int x = 0; x < strReadline.Length; ++x)

{

if (strReadline[x] == '-')

{

//标记找到的‘-’为1

map[x, y] = 1;

}

}

y += 1;

}

}

//打印迷宫

IEnumerator PrintMap()

{

for (int i = 0; i < row; ++i)

{

for (int j = 0; j < colum; ++j)

{

if (map[i, j] == 1)

{

Instantiate(prefabsWall, new Vector3(i, 0, -j), Quaternion.identity);

yield return new WaitForSeconds(0.01f);

}

yield return null;

}

}

}

//点击屏幕,获取寻路起点和终点

public void Click()

{

if (Input.GetMouseButton(0) && count == 0)

{

ray = Camera.main.ScreenPointToRay(Input.mousePosition);

if (Physics.Raycast(ray, out hit, 100f))

{

if (hit.collider.name == "Plane")

{

move1 = Instantiate(prefabsPoint, new Vector3((int)hit.point.x, 0, (int)hit.point.z), Quaternion.identity);

startX = (int)hit.point.x;

startY = Mathf.Abs((int)hit.point.z);

count += 1;

}

}

}

if (Input.GetMouseButton(1) && count == 1)

{

ray = Camera.main.ScreenPointToRay(Input.mousePosition);

if (Physics.Raycast(ray, out hit_other, 100f))

{

if (hit_other.collider.name == "Plane")

{

move2 = Instantiate(prefabsMove, new Vector3((int)hit_other.point.x, 0, (int)hit_other.point.z), Quaternion.identity);

endX = (int)hit_other.point.x;

endY = Mathf.Abs((int)hit_other.point.z);

count += 1;

}

}

}

}

//BFS寻路方法

IEnumerator Search()

{

//从(startX,startY)开始搜索

Pos origin = new Pos(startX, startY);

//把坐标添加到列表中存起来

record.Add(origin);

//起点的步数为0

SearchData originStep = new SearchData();

originStep.step = 0;

//标记起点

searchMap[startX, startY] = originStep;

while (record.Count > 0)

{

//判断起点(依次累计)的上方位置是否被访问

if (record[0].x + 1 < row && searchMap[record[0].x + 1, record[0].y] == null)

{

if (map[record[0].x + 1, record[0].y] != 1)

{

Pos nextPos = new Pos(record[0].x + 1, record[0].y);

SearchData nextSearchData = new SearchData();

//标记这个位置

searchMap[record[0].x + 1, record[0].y] = nextSearchData;

//将当前位置,与上一个位置的步数始终保持为1

nextSearchData.step = searchMap[record[0].x, record[0].y].step + 1;

//添加到列表

record.Add(nextPos);

//生成一个寻路的方块

Instantiate(prefabsRoad, new Vector3(record[0].x + 1, 0, -(record[0].y)), Quaternion.identity);

//若现在的位置,与终点的位置相等,则跳出循环

if (record[0].x + 1 == endX && record[0].y == endY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

}

//下

if (record[0].x - 1 > 0 && searchMap[record[0].x - 1, record[0].y] == null)

{

if (map[record[0].x - 1, record[0].y] != 1)

{

Pos nextPos = new Pos(record[0].x - 1, record[0].y);

SearchData nextSearchData = new SearchData();

//nextSearchData.step += 1;

searchMap[record[0].x - 1, record[0].y] = nextSearchData;

nextSearchData.step = searchMap[record[0].x, record[0].y].step + 1;

record.Add(nextPos);

Instantiate(prefabsRoad, new Vector3(record[0].x - 1, 0, -(record[0].y)), Quaternion.identity);

if (record[0].x - 1 == endX && record[0].y == endY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

}

//左

if (record[0].y - 1 > 0 && searchMap[record[0].x, record[0].y - 1] == null)

{

if (map[record[0].x, record[0].y - 1] != 1)

{

Pos nextPos = new Pos(record[0].x, record[0].y - 1);

SearchData nextSearchData = new SearchData();

//nextSearchData.step += 1;

searchMap[record[0].x, record[0].y - 1] = nextSearchData;

nextSearchData.step = searchMap[record[0].x, record[0].y].step + 1;

record.Add(nextPos);

Instantiate(prefabsRoad, new Vector3(record[0].x, 0, -(record[0].y - 1)), Quaternion.identity);

if (record[0].x == endX && record[0].y - 1 == endY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

}

//右

if (record[0].y + 1 < colum && searchMap[record[0].x, record[0].y + 1] == null)

{

if (map[record[0].x, record[0].y + 1] != 1)

{

Pos nextPos = new Pos(record[0].x, record[0].y + 1);

SearchData nextSearchData = new SearchData();

//nextSearchData.step += 1;

searchMap[record[0].x, record[0].y + 1] = nextSearchData;

nextSearchData.step = searchMap[record[0].x, record[0].y].step + 1;

record.Add(nextPos);

Instantiate(prefabsRoad, new Vector3(record[0].x, 0, -(record[0].y + 1)), Quaternion.identity);

if (record[0].x == endX && record[0].y + 1 == endY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

}

//删除当前这个点,表示已经找完了上下左右四个点

record.RemoveAt(0);

}

yield return null;

}

//寻路完成后,返回一条线性路径,从末端

IEnumerator RoadBack()

{

//将上次寻路完成的终点的位置,记为线性路径的起点

Pos posBack = new Pos(endX, endY);

line.Add(posBack);

//若上下左右都能走,那么就找一个位置

while (line.Count > 0)

{

//判断该点上方的位置是否有标记,(有标记都是没有墙的位置),并用步数来作为搜索的方法

if ((searchMap[line[0].x + 1, line[0].y] != null) && (searchMap[line[0].x + 1, line[0].y].step == searchMap[line[0].x, line[0].y].step - 1))

{

Instantiate(prefabsBack, new Vector3(line[0].x + 1,0,-(line[0].y)), Quaternion.identity);

line.Add(new Pos(line[0].x + 1, line[0].y));

move.Add(new Pos(line[0].x + 1, line[0].y));

if (line[0].x + 1 == startX && line[0].y == startY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

//下

else if ((searchMap[line[0].x - 1, line[0].y] != null) && (searchMap[line[0].x - 1, line[0].y].step == searchMap[line[0].x, line[0].y].step - 1))

{

Instantiate(prefabsBack, new Vector3(line[0].x - 1, 0, -(line[0].y)), Quaternion.identity);

line.Add(new Pos(line[0].x - 1, line[0].y));

move.Add(new Pos(line[0].x - 1, line[0].y));

if (line[0].x - 1 == startX && line[0].y == startY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

//左

else if ((searchMap[line[0].x, line[0].y - 1] != null) && (searchMap[line[0].x, line[0].y - 1].step == searchMap[line[0].x, line[0].y].step - 1))

{

Instantiate(prefabsBack, new Vector3(line[0].x, 0, -(line[0].y - 1)), Quaternion.identity);

line.Add(new Pos(line[0].x, line[0].y - 1));

move.Add(new Pos(line[0].x, line[0].y - 1));

if (line[0].x == startX && line[0].y - 1 == startY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

//右

else if ((searchMap[line[0].x, line[0].y + 1] != null) && (searchMap[line[0].x, line[0].y + 1].step == searchMap[line[0].x, line[0].y].step - 1))

{

Instantiate(prefabsBack, new Vector3(line[0].x, 0, -(line[0].y + 1)), Quaternion.identity);

line.Add(new Pos(line[0].x, line[0].y + 1));

move.Add(new Pos(line[0].x, line[0].y + 1));

if (line[0].x == startX && line[0].y + 1 == startY)

{

break;

}

yield return new WaitForSeconds(0.05f);

}

//删除当前点,并用下一个点进入循环

line.RemoveAt(0);

}

IsBack = true;

yield return null;

}

}

//一个记录步数的类

public class SearchData

{

public int step;

}

//记录坐标的类,跟Vector2作用相同,但是整数型的

public class Pos

{

public int x = 0;

public int y = 0;

public Pos()

{

}

public Pos(int x, int y)

{

this.x = x;

this.y = y;

}

}


移动:

Rouge move;

bool isMove = false;

private void Start()

{

move = GameObject.Find("GameMode").GetComponent<Rouge>();

}

void Update ()

{

if(isMove == false && Input.GetKeyDown(KeyCode.M))

{

StartCoroutine(Moves());

}

}

IEnumerator Moves()

{

for(int i = 0;i<move.move.Count;i++)

{

transform.position = new Vector3(move.move[i].x, 0, -(move.move[i].y));

yield return new WaitForSeconds(1f);

}

yield return null;

isMove = true;

}

查看更多主题的豆瓣日记和相册

自嘲的快乐
作者自嘲的快乐
14日记 1相册

全部回应 0 条

添加回应

自嘲的快乐的热门日记

值得一读

    豆瓣
    我们的精神角落
    免费下载 iOS / Android 版客户端