A Star寻路简易原理

首先说下简单的原理


image.png

如图所示简易地图, 其中绿色方块的是起点 (用 A 表示), 中间蓝色的是障碍物, 红色的方块 (用 B 表示) 是目的地. 为了可以用一个二维数组来表示地图, 我们将地图划分成一个个的小方块.
二维数组在游戏中的应用是很多的, 比如贪吃蛇和俄罗斯方块基本原理就是移动方块而已. 而大型 游戏的地图, 则是将各种"地貌"铺在这样的小方块上.

寻路步骤
1. 从起点 A 开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格 的列表.   
2. 寻找起点 A 周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为 A.      
3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再 次检查的方格
image.png

图中浅绿色描边的方块表示已经加入 "开启列表" 等待检查. 淡蓝色描边的起点 A 表示已经放入 "关闭列表" , 它不需要再执行检查.
从 "开启列表" 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算.

F = G + H             
G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).          
H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以 上下左右移动). 
image.png

我们假设横向移动一个格子的耗费为 10, 为了便于计算, 沿斜方向移动一个格子耗费是 14. 为了 更直观的展示如何运算 FGH, 图中方块的左上角数字表示 F, 左下角表示 G, 右下角表示 H. 看看是否 跟你心里想的结果一样?
从 "开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块), 然后对它进行如下处 理:

4. 把它从 "开启列表" 中删除, 并放到 "关闭列表" 中. 
5. 检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑) 的方格. 如果这
些方格 还不在 "开启列表" 里的话, 将它们加入 "开启列表", 计算这些方格的 G, H 和 F 值
各是多少, 并设置 它们的 "父方格" 为 C.      
6. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过 C 的路
径) 到 达它的话, G 值是否会更低一些, 如果新的 G 值更低, 那就把它的 "父方格" 改为目前
选中的方格 C, 然 后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, 
H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为
它需要更远的路, 这时我们什么也不做. 
image.png

如图, 我们选中了 C 因为它的 F 值最小, 我们把它从 "开启列表" 中删除, 并把它加入 "关闭列 表". 它右边上下三个都是墙, 所以不考虑它们. 它左边是起始方块, 已经加入到 "关闭列表" 了, 也不考 虑. 所以它周围的候选方块就只剩下 4 个. 让我们来看看 C 下面的那个格子, 它目前的 G 是 14, 如 果通过 C 到达它的话, G 将会是 10 + 10, 这比 14 要大, 因此我们什么也不做. 然后我们继续从 "开启列表" 中找出 F 值最小的, 但我们发现 C 上面的和下面的同时为 54, 这 时怎么办呢? 这时随便取哪一个都行, 比如我们选择了 C 下面的那个方块 D.


image.png

D 右边已经右上方的都是墙, 所以不考虑, 但为什么右下角的没有被加进 "开启列表" 呢? 因为如 果 C 下面的那块也不可以走, 想要到达 C 右下角的方块就需要从 "方块的角" 走了, 在程序中设置是 否允许这样走. (图中的示例不允许这样走)
image.png
就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表". 再继续找出它周围可以到达的方块, 如此循环下去...
那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经 被找到.
如何找回路径
image.png

如上图所示, 除了起始方块, 每一个曾经或者现在还在 "开启列表" 里的方块, 它都有一个 "父方 块", 通过 "父方块" 可以索引到最初的 "起始方块", 这就是路径.

代码实现
public class Point
{
    public Point ParentPoint { get; set; }
    public float F { get; set; }
    public float G { get; set; }
    public float H { get; set; }

    public int X { get; set; }
    public int Y { get; set; }

    public bool IsWall { get; set; }
    public Point(int x, int y, Point parent = null)
    {
        this.X = x;
        this.Y = y;
        this.ParentPoint = parent;
        IsWall = false;

    }
 
    public void UpdataParent(Point parent, float g) 
    {
        this.ParentPoint = parent;
        this.G = g;
        F = G + H;
    }
}
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStar : MonoBehaviour
{

   const int mapWith = 8;
   const  int mapHeight = 6;
    private Point[,] map = new Point[mapWith, mapHeight];


    // Use this for initialization
    void Start()
    {
        InitMap();
        Point start = map[3, 3];
        Point end = map[7, 3];
        FindPath(start, end);
        ShowPath(start, end);
      
    }
    void Update()
    {

    }
    void InitMap()
    {
        for (int x = 0; x < mapWith; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                map[x, y] = new Point(x, y);
            }
        }
        map[5, 2].IsWall = true;
        map[5, 3].IsWall = true;
        map[5, 4].IsWall = true;
    }
    void ShowPath(Point start,Point end)
    {
        Point temp = end;
        while (true)
        {
            Debug.Log(temp.X + "," + temp.Y);
            Color c = Color.gray;
            if (temp == start) c = Color.green;
            if (temp == end) c = Color.red;
            CreateCube(temp.X,temp.Y,c);

            if (temp.ParentPoint == null) break;
            temp = temp.ParentPoint;
        }
        for (int x = 0; x < mapWith; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                if (map[x, y].IsWall)
                {
                    CreateCube(x,y,Color.blue);
                }
            }
        }
    }

    void CreateCube(int x,int y,Color color)
    {
        GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
        go.transform.position = new Vector3(x,y,0);
        go.GetComponent<MeshRenderer>().material.color = color;
    }
    void FindPath(Point start, Point end)
    {
        List<Point> openList = new List<Point>();
        List<Point> closeList = new List<Point>();
        openList.Add(start);
        while (openList.Count > 0)
        {

            Point point = FindMinFOfPoint(openList);
            openList.Remove(point);
            closeList.Add(point);
            List<Point> SurroundPoints = GetSurroundPoints(point);
            PointsFilter(SurroundPoints,closeList);
            foreach (Point SurroundPoint in SurroundPoints)
            {
                if (openList.IndexOf(SurroundPoint) > -1)
                {
                    float nowG = CalcG(SurroundPoint, point);
                    if (nowG < SurroundPoint.G)
                    {
                        SurroundPoint.UpdataParent(point, nowG);
                    }
                }
                else
                {
                    SurroundPoint.ParentPoint = point;
                    CalcF(SurroundPoint, end);
                    openList.Add(SurroundPoint);
                }

            }
            if (openList.IndexOf(end) > -1)
                break;

        }

       // start.CalcF();

    }
   void PointsFilter(List<Point> src, List<Point> closePoint)
    {
        foreach (Point p in closePoint)
        {
            if (src.IndexOf(p) > -1)
            {
                src.Remove(p);
            }
        }
    }
    List<Point> GetSurroundPoints(Point point)
    {
        Point left=null, up=null, down=null, right=null;
        Point lu = null, ru = null, ld = null, rd = null;
        if (point.Y < mapHeight - 1) up = map[point.X, point.Y + 1];
        if (point.Y > 0) down = map[point.X, point.Y - 1];
        if (point.X > 0) left = map[point.X-1, point.Y];
        if (point.X < mapWith - 1) right = map[point.X + 1, point.Y];
        if(up!=null&&left!=null)
            lu = map[point.X - 1, point.Y+1];
        if (up != null && right != null)
            ru = map[point.X + 1, point.Y + 1];
        if (down != null && left != null)
            ld = map[point.X - 1, point.Y - 1];
        if (down != null && right != null)
            rd = map[point.X + 1, point.Y - 1];
        List<Point> list = new List<Point>();
        if (down != null && down.IsWall == false)
            list.Add(down);
        if (up != null && up.IsWall == false)
            list.Add(up);
        if (left != null && left.IsWall == false)
            list.Add(left);
        if (right != null && right.IsWall == false)
            list.Add(right);
        if(lu!=null&&lu.IsWall==false&&left.IsWall==false&&up.IsWall==false)
            list.Add(lu);
        if (ru != null && ru.IsWall == false && right.IsWall == false && up.IsWall == false)
            list.Add(ru);
        if (ld != null && ld.IsWall == false && left.IsWall == false && down.IsWall == false)
            list.Add(ld);
        if (rd != null && rd.IsWall == false && right.IsWall == false && down.IsWall == false)
            list.Add(rd);
        return list;
    }
    Point FindMinFOfPoint(List<Point> openList)
    {
        float f = float.MaxValue;

        Point temp = null;
        foreach (Point p in openList)
        {
            if (p.F < f)
            {

                temp = p;
                f = p.F;
            }
        }
        return temp;
    }

    float CalcG(Point now,Point parent)
    {
      return  Vector2.Distance(new Vector2(now.X, now.Y), new Vector2(parent.X, parent.Y)) + parent.G;
    }
    public void CalcF(Point now, Point end)
    {
        float h = Mathf.Abs(end.X - now.X) + Mathf.Abs(end.Y - now.Y);
        float g = 0;
        if (now.ParentPoint == null)
        {
            g = 0;
        }
        else
        {
            g = Vector2.Distance(new Vector2(now.X, now.Y), new Vector2(now.ParentPoint.X, now.ParentPoint.Y)) + now.ParentPoint.G;
        }

        float f = g + h;
        now.F = f;
        now.G = g;
        now.H = h;
    }
}

运行后,绿色代表起点,红色代表终点,蓝色是障碍物,灰色就是最短路径了。


image.png

相关插件:A* Pathfinding Project

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,743评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,296评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,285评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,485评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,581评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,821评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,960评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,719评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,186评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,516评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,650评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,329评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,936评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,757评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,991评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,370评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,527评论 2 349

推荐阅读更多精彩内容