迷宫算法的unity demo实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了迷宫算法的unity demo实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

思考

在之前博客提及过A*寻路算法，同时想实现生成迷宫算法，所以有了这次主题。

参考链接：有关迷宫的生成算法和解密算法_迷宫求解摸墙算法-CSDN博客

算法

Prim生成迷宫算法

我们采用prim算法来生成迷宫：

让迷宫全是墙.
选一个单元格作为迷宫的通路，然后把它的邻墙放入列表
当列表里还有墙时
1. 从列表里随机选一个墙，如果这面墙分隔的两个单元格只有一个单元格被访问过
  1. 那就从列表里移除这面墙，即把墙打通，让未访问的单元格成为迷宫的通路
  2. 把这个格子的墙加入列表
2. 如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙

所以第一步是要让所有格子周围都生成墙，保留第一个格子的左边和最后一个格子的右边不生成墙（即当作是迷宫的通路）。

A*寻路算法

通过以下流程求出路径：

把起点加入 open list 。
重复如下过程：
1. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。
2. 把这个节点移到 close list 。
3. 对当前方格的 8 个相邻方格的每一个方格？
  - 如果它是不可抵达的或者它在 close list 中，忽略它。
  - 如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。
  - 如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。
4. 停止，当你
  - 把终点加入到了 open list 中，此时路径已经找到了，或者
  - 查找终点失败，并且 open list 是空的，此时没有路径。
保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

步骤

生成方块格子

首先生成一系列格子，让它们作为一个背景模板，并管理这些格子。

代码

GridController

public class GridController : MonoBehaviour
{
    private GameObject[,] m_arrGrid = null; //管理每个格子gameObject的数组
    private const int m_iRowCount = 15; //格子行数
    private const int m_iColCount = 20; //格子列数
    private void Awake()
    {
        if (m_arrGrid == null)
        {
            //创建一个10行20列的迷宫型
            m_arrGrid = new GameObject[m_iRowCount, m_iColCount];
        }
        //遍历创建格子
        for(int i = 0; i < m_iRowCount; i++)
        {
            for(int j = 0; j < m_iColCount; j++)
            {
                GameObject grid = Instantiate(Resources.Load<GameObject>("Prefab/Grid"),transform);
                m_arrGrid[i, j] = grid;
            }
        }
    }
    void Start()
    {
        //每个格子显示出场特效
        for (int i = 0; i < m_iRowCount; i++)
        {
            for (int j = 0; j < m_iColCount; j++)
            {
                m_arrGrid[i, j].transform.localScale = Vector3.zero;
                m_arrGrid[i, j].transform.DOScale(Vector3.one, 1.0f);
            }
        }
        Invoke("CreateAllLines", 2.0f);
    }
}

效果

maze_1

所有方块周围生成墙

为了后期能更好管理每个grid的属性，包括后期这个grid周围有几面墙、grid是否被访问过等等，于是就另外写了一个类，绑定到每一个gameobject上。

代码

GridController

//生成所有墙,留一个左上角起点和右下角终点
public void CreateAllLines()
{
    for (int i = 0; i < m_iRowCount; i++)
    {
        for (int j = 0; j < m_iColCount; j++)
        {
            if (i != 0 || j != 0)
            {
                m_arrGridMono[i, j].CreateLine(Grid.LEFT);
            }
            if (i != m_iRowCount - 1 || j != m_iColCount - 1)
            {
                m_arrGridMono[i, j].CreateLine(Grid.RIGHT);
            }
            m_arrGridMono[i, j].CreateLine(Grid.UP);
            m_arrGridMono[i, j].CreateLine(Grid.DOWN);
        }
    }
    Invoke("ClearSomeLines", 2.0f);
}

Grid

public class Grid : MonoBehaviour
{
    //四个方向所代表的数值
    public const int LEFT = 0;
    public const int UP = 1;
    public const int RIGHT = 2;
    public const int DOWN = 3;

    //格子一半长度
    public const int HALF_SIZE = 16;

    //墙要放置的地方
    public static Vector2[] m_linePosition = null; 

    //四个方向是否被堵死
    private bool[] m_arrIsWayPass = {false,false,false,false};

    //四个方向的墙的gameObject
    private GameObject[] m_arrLine = { null, null, null, null };

    private void Awake()
    {
        if(m_linePosition == null)
        {
            m_linePosition = new Vector2[4];
            m_linePosition[LEFT] = Vector2.left * HALF_SIZE;
            m_linePosition[RIGHT] = Vector2.right * HALF_SIZE;
            m_linePosition[UP] = Vector2.up * HALF_SIZE;
            m_linePosition[DOWN] = Vector2.down * HALF_SIZE;
        }
    }


    //在一个方向上生成一面墙
    public void CreateLine(int iDirection)
    {
        GameObject goLine = Instantiate(Resources.Load<GameObject>("Prefab/Line"), transform);
        m_arrLine[iDirection] = goLine;
        m_arrIsWayPass[iDirection] = true;
        goLine.transform.localScale = Vector3.zero;
        goLine.transform.localPosition = m_linePosition[iDirection];
        //如果是左边或者右边的线，要记住把它翻转
        if (iDirection == LEFT || iDirection == RIGHT)
        {
            goLine.transform.localRotation = Quaternion.Euler(Vector3.forward * 90);
        }
        goLine.transform.DOScale(Vector3.one, 1.0f);
    }
}

效果

maze_2

去除一些墙

我们利用prim生成迷宫算法来将一些墙去除。

代码

GridController

//清除一些墙，来生成迷宫
//我们可以维护一个迷宫单元格的列表，而不是边的列表。
//在这个迷宫单元格列表里面存放了未访问的单元格，我们在单元格列表中随机挑选一个单元格，
//如果这个单元格有多面墙联系着已存在的迷宫通路，我们就随机选择一面墙打通。
public void ClearSomeLines()
{
    List<Grid> listGrid = new List<Grid>();

    //以左上角为起点，开始访问
    m_arrGridMono[0, 0].SetVisited(true);

    //先把最左上边的右边第一个，下边第一个加入到list中
    if (m_iColCount > 1)
    {
        listGrid.Add(m_arrGridMono[0, 1]);
    }
    if (m_iRowCount > 1)
    {
        listGrid.Add(m_arrGridMono[1, 0]);
    }

    //循环取list中的随机一个未打通的单元格，与周围打通了的随机一个单元格进行连通，
    //并且将其他没有打通的且未在list中的放入list中
    while (listGrid.Count > 0)
    {
        int iVisitIndex = Random.Range(0, listGrid.Count);
        Grid gridVisit = listGrid[iVisitIndex];
        int iPosRow = gridVisit.GetPosRow();
        int iPosCol = gridVisit.GetPosCol();
        listGrid.RemoveAt(iVisitIndex);
        //存储已经打通了的grid信息，每一个元素代表某个方向的grid脚本
        List<KeyValuePair<int, Grid>> listVisitedGrid = new List<KeyValuePair<int, Grid>>();

        //上判断
        if (iPosRow > 0)
        {
            if (m_arrGridMono[iPosRow - 1, iPosCol].IsVisited())
            {
                listVisitedGrid.Add(new KeyValuePair<int, Grid>(Grid.UP, m_arrGridMono[iPosRow - 1, iPosCol]));
            }
            else if (!listGrid.Contains(m_arrGridMono[iPosRow - 1, iPosCol]))
            {
                listGrid.Add(m_arrGridMono[iPosRow - 1, iPosCol]);
            }
        }

        //下判断
        if (iPosRow < m_iRowCount - 1)
        {
            if (m_arrGridMono[iPosRow + 1, iPosCol].IsVisited())
            {
                listVisitedGrid.Add(new KeyValuePair<int, Grid>(Grid.DOWN, m_arrGridMono[iPosRow + 1, iPosCol]));
            }
            else if (!listGrid.Contains(m_arrGridMono[iPosRow + 1, iPosCol]))
            {
                listGrid.Add(m_arrGridMono[iPosRow + 1, iPosCol]);
            }
        }

        //左判断
        if (iPosCol > 0)
        {
            if (m_arrGridMono[iPosRow, iPosCol - 1].IsVisited())
            {
                listVisitedGrid.Add(new KeyValuePair<int, Grid>(Grid.LEFT, m_arrGridMono[iPosRow, iPosCol - 1]));
            }
            else if (!listGrid.Contains(m_arrGridMono[iPosRow, iPosCol - 1]))
            {
                listGrid.Add(m_arrGridMono[iPosRow, iPosCol - 1]);
            }
        }

        //右判断
        if (iPosCol < m_iColCount - 1)
        {
            if (m_arrGridMono[iPosRow, iPosCol + 1].IsVisited())
            {
                listVisitedGrid.Add(new KeyValuePair<int, Grid>(Grid.RIGHT, m_arrGridMono[iPosRow, iPosCol + 1]));
            }
            else if (!listGrid.Contains(m_arrGridMono[iPosRow, iPosCol + 1]))
            {
                listGrid.Add(m_arrGridMono[iPosRow, iPosCol + 1]);
            }
        }

        //随机在listVisitedGrid中挑选一个，进行双向打通
        int iVisitedIndex = Random.Range(0, listVisitedGrid.Count);
        int iDirection = listVisitedGrid[iVisitedIndex].Key;
        Grid gridVisited = listVisitedGrid[iVisitedIndex].Value;
        gridVisit.DeleteLine(iDirection);
        gridVisited.DeleteLine(Grid.ContraryDirection(iDirection));
        gridVisit.SetVisited(true);
    }
    Invoke("FindWay", 2.0f);
}

效果

maze_3

找到路径

去除之后，通过A*寻路算法破解迷宫。

代码

GridController

//找到迷宫的通路
public void FindWay()
{
    List<Grid> listOpenGrid = new List<Grid>();//待检查的格子
    List<Grid> listCloseGrid = new List<Grid>();//已经检查过的格子

    //把起始点放入openGrid中
    listOpenGrid.Add(m_arrGridMono[0, 0]);
    Grid nowGrid = null; //现在在处理中的格子

    //更新起点的FGH评估值
    m_arrGridMono[0, 0].UpdateValue(m_iRowCount - 1, m_iColCount - 1, null);

    //当终点已加入到了open list或者可以遍历的格子已经为空了，那么就终止查找父节点的循环
    while (listOpenGrid.Count > 0 && !listOpenGrid.Contains(m_arrGridMono[m_iRowCount - 1, m_iColCount - 1]))
    {
        nowGrid = listOpenGrid[0];
        int iNumF = nowGrid.GetNumF();
        //遍历listOpenGrid，查找F值最小的格子，并且把它移到listCloseGrid中
        foreach (Grid openGrid in listOpenGrid)
        {
            if (iNumF >= openGrid.GetNumF())
            {
                nowGrid = openGrid;
                iNumF = nowGrid.GetNumF();
            }
        }
        listOpenGrid.Remove(nowGrid);
        listCloseGrid.Add(nowGrid);
        Grid neighborGrid = null;

        //对当前方格的上下左右四个相邻方格作判断
        //如果它是不可抵达的或者它在close list中，忽略它
        if (!nowGrid.HasLine(Grid.UP))
        {
            neighborGrid = m_arrGridMono[nowGrid.GetPosRow() - 1, nowGrid.GetPosCol()];
            if (!listCloseGrid.Contains(neighborGrid))
            {
                //如果它不在open list中，把它加入open list
                if (!listOpenGrid.Contains(neighborGrid))
                {
                    listOpenGrid.Add(neighborGrid);
                }
                //更新FGH评估值
                neighborGrid.UpdateValue(m_iRowCount - 1, m_iColCount - 1, nowGrid);
            }
        }
        if (!nowGrid.HasLine(Grid.DOWN))
        {
            neighborGrid = m_arrGridMono[nowGrid.GetPosRow() + 1, nowGrid.GetPosCol()];
            if (!listCloseGrid.Contains(neighborGrid))
            {
                if (!listOpenGrid.Contains(neighborGrid))
                {
                    listOpenGrid.Add(neighborGrid);
                }
                neighborGrid.UpdateValue(m_iRowCount - 1, m_iColCount - 1, nowGrid);
            }
        }
        if ((!nowGrid.HasLine(Grid.LEFT)) && nowGrid.GetPosCol() > 0)
        {
            neighborGrid = m_arrGridMono[nowGrid.GetPosRow(), nowGrid.GetPosCol() - 1];
            if (!listCloseGrid.Contains(neighborGrid))
            {
                if (!listOpenGrid.Contains(neighborGrid))
                {
                    listOpenGrid.Add(neighborGrid);
                }
                neighborGrid.UpdateValue(m_iRowCount - 1, m_iColCount - 1, nowGrid);
            }
        }
        if ((!nowGrid.HasLine(Grid.RIGHT)) && nowGrid.GetPosCol() < m_iColCount - 1)
        {
            neighborGrid = m_arrGridMono[nowGrid.GetPosRow(), nowGrid.GetPosCol() + 1];
            if (!listCloseGrid.Contains(neighborGrid))
            {
                if (!listOpenGrid.Contains(neighborGrid))
                {
                    listOpenGrid.Add(neighborGrid);
                }
                neighborGrid.UpdateValue(m_iRowCount - 1, m_iColCount - 1, nowGrid);
            }
        }
    }
    Grid wayGrid = m_arrGridMono[m_iRowCount - 1, m_iColCount - 1];
    while (wayGrid)
    {
        wayGrid.SetGone();
        wayGrid = wayGrid.GetParentGrid();
    }
}

Grid

public class Grid : MonoBehaviour
{
    //四个方向所代表的数值
    public const int LEFT = 0;
    public const int UP = 1;
    public const int RIGHT = 2;
    public const int DOWN = 3;

    //格子一半长度
    public const int HALF_SIZE = 16;

    //墙要放置的地方
    public static Vector2[] m_linePosition = null;

    private bool m_bIsVisited = false; //是否被访问过，也就是是否已经成为通路了

    //四个方向是否被堵死
    private bool[] m_arrIsWayPass = { false, false, false, false };

    //四个方向的墙的gameObject
    private GameObject[] m_arrLine = { null, null, null, null };

    //格子所在位置
    private int m_iPosRow = 0;
    private int m_iPosCol = 0;

    //自身的图案
    private Image m_imgSelf = null;

    //自身的父节点
    private Grid m_gridParent = null;

    //计算搜索评估值的三个数值
    private int m_F = 0; //总评估值
    private int m_G = 0; //起始点到这个点的代价
    private int m_H = 0; //这个点到终点的预估代价（采用曼哈顿距离直接计算）

    private void Awake()
    {
        if (m_linePosition == null)
        {
            m_linePosition = new Vector2[4];
            m_linePosition[LEFT] = Vector2.left * HALF_SIZE;
            m_linePosition[RIGHT] = Vector2.right * HALF_SIZE;
            m_linePosition[UP] = Vector2.up * HALF_SIZE;
            m_linePosition[DOWN] = Vector2.down * HALF_SIZE;
        }
        m_imgSelf = transform.GetComponent<Image>();
    }

    //计算一个方向的反方向
    public static int ContraryDirection(int iDirection)
    {
        return (iDirection + 2) % 4;
    }

    //在一个方向上生成一面墙
    public void CreateLine(int iDirection)
    {
        GameObject goLine = Instantiate(Resources.Load<GameObject>("Maze/Line"), transform);
        m_arrLine[iDirection] = goLine;
        m_arrIsWayPass[iDirection] = true;
        goLine.transform.localScale = Vector3.zero;
        goLine.transform.localPosition = m_linePosition[iDirection];
        //如果是左边或者右边的线，要记住把它翻转
        if (iDirection == LEFT || iDirection == RIGHT)
        {
            goLine.transform.localRotation = Quaternion.Euler(Vector3.forward * 90);
        }
        goLine.transform.DOScale(Vector3.one, 1.0f);
    }

    //某个方向上是否有墙
    public bool HasLine(int iDirection)
    {
        return m_arrIsWayPass[iDirection];
    }

    //是否被访问过
    public bool IsVisited()
    {
        return m_bIsVisited;
    }

    //修改访问标记
    public void SetVisited(bool bIsVisited)
    {
        m_bIsVisited = bIsVisited;
    }

    //打通墙壁
    public void DeleteLine(int iDirection)
    {
        if (m_arrIsWayPass[iDirection])
        {
            m_arrIsWayPass[iDirection] = false;
            m_arrLine[iDirection].transform.DOScale(Vector3.zero, 1.0f);
        }
    }

    //设置这个格子的位置
    public void SetPos(int iPosRow, int iPosCol)
    {
        m_iPosCol = iPosCol;
        m_iPosRow = iPosRow;
    }

    //获取这个格子所在位置
    public int GetPosRow()
    {
        return m_iPosRow;
    }
    public int GetPosCol()
    {
        return m_iPosCol;
    }

    //设置这个格子被走过
    public void SetGone()
    {
        m_imgSelf.DOColor(Color.green, 1.0f);
    }

    //设置父节点
    public void SetParentGrid(Grid parentGrid)
    {
        m_gridParent = parentGrid;
    }

    //返回父节点
    public Grid GetParentGrid()
    {
        return m_gridParent;
    }

    //返回这个格子到起点的距离
    public int GetNumG()
    {
        return m_G;
    }

    //返回这个格子的评估值
    public int GetNumF()
    {
        return m_F;
    }

    //更新评估值
    public void UpdateValue(int iEndGridPosRow, int iEndGridPosCol, Grid lastGrid)
    {
        m_H = (iEndGridPosRow - m_iPosRow) + (iEndGridPosCol - m_iPosCol);

        if (lastGrid)
        {
            int iLastG = lastGrid.GetNumG();
            if (m_G == 0 || m_G >= iLastG + 1)
            {
                m_G = iLastG + 1;
                m_gridParent = lastGrid;
            }
        }
        m_F = m_H + m_G;
    }
}

效果

maze_4

资源

这篇文章绑定的即是源码资源，为unity资源package，导入package后直接运行即可看到总体效果。https://download.csdn.net/download/weixin_45218342/88741148文章来源地址https://www.toymoban.com/news/detail-802624.html

到了这里，关于迷宫算法的unity demo实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！