A* 算法（二维表最短路径）

1：效果如图

2：思路：采用的是广度优先遍历

3：算法代码如下：

调用接口：

        AStar aStar = new AStar();//定义A*类

        aStar.Init(MapTool.mapWidth, MapTool.mapHeight, map);//初始化接口

        List<mapPosition> path = aStar.Path(from, to);//生成最短路径接口

算法代码：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStar
{
    public int witdh;       //二维表宽度
    public int heigh;       //二维表高度

    private bool[,] map;      //二维表 true代表可走  false代表不可走

    private bool[,] mapTemp;
    private bool isSearchOver = false;
    private mapPosition targetPosition;
    /// <summary>
    /// 初始化
    /// </summary>
    /// <param name="witdh">二位表宽度</param>
    /// <param name="heigh">二维表高度</param>
    /// <param name="map">二维地图</param>
    public void Init(int witdh, int heigh, bool[,] map)
    {
        this.witdh = witdh;
        this.heigh = heigh;

        this.map = map;
    }
    /// <summary>
    /// 计算最短路径
    /// </summary>
    /// <param name="from">起点</param>
    /// <param name="to">终点</param>
    /// <returns></returns>
    public List<mapPosition> Path(mapPosition from, mapPosition to)
    {
        this.isSearchOver = false;
        this.mapTemp = new bool[witdh, heigh];
        for(int i=0;i<witdh;i++)
        {
            for(int j=0;j<heigh;j++)
            {
                this.mapTemp[i, j] = this.map[i, j];
            }
        }

        SerachPathList(new List<mapPosition>(){from},to);

        if(isSearchOver)
        {
            List<mapPosition> path = new List<mapPosition>();
            while(true)
            {
                mapPosition position = new mapPosition(targetPosition.x, targetPosition.y);
                path.Add(position);
                if (targetPosition.lastPosition!=null)
                {
                    targetPosition = targetPosition.lastPosition;
                }
                else
                {
                    break;
                }
            }
            return path;
        }
        return null;
    }

    #region A* 广度优先遍历
    private void SerachPathList(List<mapPosition> from, mapPosition to)
    {
        if (!isSearchOver)
        {
            List<mapPosition> mapList = new List<mapPosition>();
            for (int i = 0; i < from.Count; i++)
            {
                if (!isSearchOver)
                {
                    List<mapPosition> list = SerachPath(from[i], to);
                    if(list!=null)
                    for(int j=0;j< list.Count;j++)
                    {
                        mapList.Add(list[j]);
                    }
                    
                }
            }
            if (!isSearchOver  && mapList.Count>0)
            {
                SerachPathList(mapList,to);
            }
        }

    }
    private List<mapPosition> SerachPath(mapPosition from, mapPosition to)
    {
        if(isSearchOver)
        {
            return null;
        }
        if(from.x == to.x&&from.y== to.y)
        {
            this.isSearchOver = true;
            this.targetPosition = from;
            return null;
        }
        //上
        List<mapPosition> nextPathList = new List<mapPosition>();
        mapPosition from_up = new mapPosition(from.x, from.y + 1);
        if (CanMove(from_up))
        {
            this.mapTemp[from_up.x, from_up.y] = false;
            from_up.lastPosition = from;
            nextPathList.Add(from_up);
        }
        //下
        mapPosition from_down = new mapPosition(from.x, from.y - 1);
        if (CanMove(from_down))
        {
            this.mapTemp[from_down.x, from_down.y] = false;
            from_down.lastPosition = from;
            nextPathList.Add(from_down);
        }
        //左
        mapPosition from_left = new mapPosition(from.x - 1, from.y);
        if (CanMove(from_left))
        {
            this.mapTemp[from_left.x, from_left.y] = false;
            from_left.lastPosition = from;
            nextPathList.Add(from_left);
        }
        //右
        mapPosition from_right = new mapPosition(from.x + 1, from.y);
        if (CanMove(from_right))
        {
            this.mapTemp[from_right.x, from_right.y] = false;
            from_right.lastPosition = from;
            nextPathList.Add(from_right);
        }

        return nextPathList;
    }
    #endregion
    private bool CanMove(mapPosition pos)
    {
        if(pos.x<0|| pos.x>=witdh || pos.y<0||pos.y>=heigh || !this.mapTemp[pos.x, pos.y])
        {
            return false;
        }
        else
        {
            return true;
        }
    }
}

public class mapPosition
{
    
    public mapPosition(int x, int y, mapPosition lastPosition = null)
    {
        this.x = x;
        this.y = y;
        this.lastPosition = lastPosition;
    }

    public mapPosition lastPosition = null;
    public int x;
    public int y;
}

 

本人qq：344810449，欢迎探讨研究。

有unity，shader，小程序，软件开发，游戏制作等需求也可以联系本人，非常乐于助人。

如果觉得还不错给博主来个小惊喜，纯属自愿，不强求：