代码编织梦想


俗话说,好记性不如烂笔头,对于有了解过寻路算法的同学,对于A星算法应该不陌生;为了巩固下这个算法的理解,所以利用Unity演示了算法的过程;本文的基本构成分为 基本原理+ 算法实现+ Unity演示三个步骤。

A星算法基本原理

什么是寻路算法

寻路算法是在指定地图中,NPC可以根据起始点和目标点,计算出一条比较合理的链接路线(通常需要最短路径);在地图中,路点可以分为两种,一种是普通路点,一种是障碍路点(墙、水、坑等),算法的目的就是要绕过障碍物,使得NPC尽可能的走最短路线到达目标点(targetPoint)。

对于最基本的A星寻路算法,是把一张地图分为一个二维数组,每一个格子代表一个路点;或者如下图如所示,将一张地图分为一个一个的格子,格子为正方形,下方的绿色格子周围有8个相邻的格子;

在这里插入图片描述

算法的思路

对于上述九宫格图,假设最小方格的边长是10,那么从绿色格子出发,到达红色格子的距离为 200 \sqrt{200} 200 ,这里可以简化为14,因为这样可以简化算法的计算难度(浮点数比整数的计算复杂);到达黄色格子的距离为10;
每一个路点都有一个评估值F,其中 F = G + H F = G + H F=G+H,G值是起点移动到指定方格的移动代价,H是指定的方格移动到终点的估算成本,H值的计算方式有如下两种:

方式一:计算横向和纵向移动的距离,不能斜着走;
在这里插入图片描述
方式二:比如该点和目标点为对角顶点组成的举行的边长是a 和 b,那么H值是 m i n ( a , b ) × 14 + a b s ( a − b ) × 10 min(a, b) \times 14 + abs(a - b) \times 10 min(a,b)×14+abs(ab)×10


在这里插入图片描述
本文算法选择的是方式二,H值的计算需要注意的地方是,不需要考虑障碍物,只需考虑起始点和目标点即可。对于F、G、H三个评估值的什么这么命名,我也不清楚,猜测是就和我们平时用来替代临时变量用的i、j、k一样,仅仅是26英文字母中连续的三个而已,方便记忆😎;

这个算法需要两个数组,openList和closeList,openList里面存放的是当前状态可以到达的路点,closeList存放不能到达的路点和已经经过判断的路点;具体步骤如下:

  1. 从当前选中路点a出发,总共有8个路点可能到达,假设可到达的节点为b,如果b是障碍点,则直接加入closeList;如果b在openList中,当且仅当b的G值小于点a的G值时,更新a的G值,并且将路点b的父节点设置为当前a;如果b在closeList中,则跳过该点的判断。
  2. 如果目标点进入了openList,则遍历停止,找到可到达路径,由于每个节点都保存着到达自己的父节点,所以拿到目标点,一直拿到它的父节点就可以找到到达路径;如果openList为空时还没找都目标路点,则不可到达,算法结束;否则进入下一个步骤;
  3. 遍历openList的路点,选出F值最小的那个点,如果有多个最小值,可以选择第一个最小值,也可以选择多个最小值中的最后一个,最后的表现就是到达目标点的最短路径可能有多条;然后把这个点当做选中路点,进行步骤1;

算法实现

这里列出算法用的大部分代码,其中最关键的就是RefreshFind函数和AddOpenlistNode函数,执行的就是算法的关键部分----遍历openList然后不断的进行判断,直到找到目标路点或者openList为空,其中还是有一点地方hardcode了,如果有不理解的地方,可以留言讨论。

脚本1————cconst.cs

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

namespace AStar
{
    public static class cconst
    {
        public static int NormalTile = 0;
        public static int WaterTile = 1;
        public static int DestinationTile = 2;
        public static int MarkTile = 3;
        public static int FindTile = 4;
        public static int LineNum = 20;
        public static int RowLineNum = 16;  // 行数
        public static int ColLineNum = 32;  // 列数
        public static Vector2 startPos = new Vector2(-617, 298);
        public static int targetIdx = LineNum * 12 + 13;
        public static int startIdx = LineNum * 8 + 5;
        public static float itemRate = 1.0f;
        public static float width = 40 * itemRate;
        public static float height = 40 * itemRate;


        public static int SlideDis = 14;
        public static int UnSlideDis = 10;

        public static int slideValNum = 4;
        public static List<Vector2> UnSlideDisVal = new List<Vector2> { new Vector2(-1, 0), new Vector2(0, 1), new Vector2(1, 0), new Vector2(0, -1) };
        public static List<Vector2> SlideDisVal = new List<Vector2> { new Vector2(-1, -1), new Vector2(-1, 1), new Vector2(1, 1), new Vector2(1, -1) };
    }
}




脚本2————AStar.cs

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


namespace AStar
{

    public class GObject
    {
        public GameObject gameobject;
        int objType;

        GameObject fValText;
        GameObject gValText;
        GameObject hValText;

        GameObject textPanel;

        public GObject(GameObject _gameobject, int _type) 
        {
            gameobject = _gameobject; 
            objType = _type;
            textPanel = _gameobject.transform.Find("Panel").gameObject;
            fValText = textPanel.transform.Find("FText").gameObject;
            gValText = textPanel.transform.Find("GText").gameObject;
            hValText = textPanel.transform.Find("HText").gameObject;

            textPanel.SetActive(false);
 
        }
        public bool IsObstacle
        {
            get { return objType == cconst.WaterTile;  }
        }

        public void UpdateDis(int g, int h)
        {
            textPanel.SetActive(true);

            gValText.GetComponent<Text>().text = g.ToString();
            hValText.GetComponent<Text>().text = h.ToString();
            int f = g + h;
            fValText.GetComponent<Text>().text = f.ToString();
        }
    }


    public class Node
    {
        public Node parent;
        public GObject gameobject;
        int idx = 0;

        public Node(GObject obj, int _idx) { gameobject = obj; idx = _idx; }
        int g = 0;
        int h = 0;

        public int Idx
        {
            get { return idx; }
        }

        public int F
        {
            get { return G + H; }
        }

        public int G
        {
            get { return g; }
            set { g = value; }
        }


        public int H
        {
            get { return h; }
            set { h = value;}
        }

        public int xIdx
        {
            get { return idx / cconst.ColLineNum; }
        }

        public int yIdx
        {
            get { return idx % cconst.ColLineNum; }
        }

        public void UpdateGVal(int gVal)
        {
            if(gVal < G)
            {
                G = gVal;
            }
        }

        public void UpdateLocalPosition()
        {
            int rowIdx = xIdx;
            int colIdx = yIdx;

            float posX = cconst.startPos.x + colIdx * cconst.width;
            float posY = cconst.startPos.y - rowIdx * cconst.height;
            gameobject.gameobject.transform.localPosition = new Vector2(posX, posY);
        }

        public void UpdateDescDis()
        {
            gameobject.UpdateDis(G, H);
        }

        public void UpdateDescDis(Node node)
        {
            G = node.G;
            H = node.H;
            gameobject.UpdateDis(G, H);
        }

        public void SetParrent(Node node)
        {
            parent = node;
        }

        public void SetVisible(bool visible)
        {
            gameobject.gameobject.SetActive(visible);
        }
    }

    public class AStarTest : MonoBehaviour
    {

        // Start is called before the first frame update
        public List<int> map;
        public Dictionary<int, string> mapTypeDic;
        public Dictionary<int, GObject> mapTypeObjDic;
        public Dictionary<int, GObject> idxObjDic;
        GameObject normalTile;
        GameObject waterTile;
        GameObject destinationTile;
        GameObject markTile;
        GameObject findTile;
        public int startIdx;
        public int targetIdx;
        public List<int> battleList;

        public List<Node> openList;
        public Dictionary<int, Node> openListIdxDic;
        public List<Node> closeList;
        public Dictionary<int, Node> closeListIdxDic;

        public List< GameObject> totalObjList;

        Node targetNode;
        Node markTargetNode;
        public List<Node> markNodeList;

        public Coroutine curCoroutine;



        void Start()
        {
            idxObjDic = new Dictionary<int, GObject>();
            mapTypeDic = new Dictionary<int, string> {
                {0, "normalTile" },
                {1, "waterTile" },
                {2, "targetTile" },
                {3, "markTile" },
                {4, "findTile" },
                };






            normalTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.NormalTile]);
            waterTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.WaterTile]);
            destinationTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.DestinationTile]);
            markTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.MarkTile]);
            findTile = Resources.Load<GameObject>("Prefab/" + mapTypeDic[cconst.FindTile]);
            mapTypeObjDic = new Dictionary<int, GObject>
            {
                {cconst.NormalTile,  new GObject(normalTile,cconst.NormalTile)},
                {cconst.WaterTile,  new GObject(waterTile,cconst.WaterTile)},
                {cconst.DestinationTile,  new GObject(destinationTile,cconst.DestinationTile)},
                {cconst.MarkTile,  new GObject(markTile,cconst.MarkTile)},
                {cconst.FindTile,  new GObject(findTile,cconst.FindTile)},
            };

            InitData();
        }

        public void InitData()
        {
            int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;

            startIdx = Random.Range(0, _totalIdx / 2);
            while (battleList.Contains(startIdx))
            {
                startIdx = Random.Range(0, _totalIdx / 2);
            }
            targetIdx = Random.Range(_totalIdx / 2, _totalIdx);
            while (battleList.Contains(targetIdx) || startIdx == targetIdx)
            {
                targetIdx = Random.Range(_totalIdx / 2, _totalIdx);
            }

            totalObjList = new List<GameObject>();

            map = new List<int>();
            for (int i = 0; i < cconst.RowLineNum; ++i)
                for (int j = 0; j < cconst.ColLineNum; ++j)
                {
                    map.Add(cconst.NormalTile);

                }
            map[startIdx] = cconst.MarkTile;
            map[targetIdx] = cconst.DestinationTile;

            battleList = new List<int>();
            int CollineNum = cconst.ColLineNum;
            int startLine = 4;
            for (int i = startLine; i < startLine + 10 && startLine + 10 < cconst.RowLineNum; i++)
            {
                int idx = CollineNum * i + CollineNum / 2;
                map[idx] = cconst.WaterTile;
                battleList.Add(idx);
            }

            InitMapRes();

            // ---------------- A*
            openList = new List<Node>();
            openListIdxDic = new Dictionary<int, Node>();
            closeList = new List<Node>();
            closeListIdxDic = new Dictionary<int, Node>();
            markNodeList = new List<Node>();
            targetNode = new Node(idxObjDic[targetIdx], targetIdx);
            markTargetNode = null;
            InitAStarStart();
            curCoroutine = StartCoroutine(FindNextPoint());
        }

        public IEnumerator FindNextPoint()
        {
            RefreshFind();
            yield return new WaitForSeconds(0.1f);

            if (!openListIdxDic.ContainsKey(targetNode.Idx))
            {
                curCoroutine = StartCoroutine(FindNextPoint());
            }
            else
            {
                markTargetNode = openListIdxDic[targetNode.Idx];
                curCoroutine = StartCoroutine(ShowFindPath(markTargetNode));
                Debug.Log("find the way to the target !!!");
            }
            
        }

        void InitMapRes()
        {
            int _totalIdx = cconst.RowLineNum * cconst.ColLineNum;
            for (int i=0; i< _totalIdx; ++i)
            {
                int rowIdx = i / cconst.ColLineNum;
                int colIdx = i % cconst.ColLineNum;
                var obj = getTypeObject(map[i]).gameobject;
                obj.transform.SetParent(transform);
                idxObjDic[i] = new GObject(obj, map[i]);
                float posX = cconst.startPos.x + colIdx * cconst.width;
                float posY = cconst.startPos.y - rowIdx * cconst.height;
                obj.transform.localPosition = new Vector2(posX, posY);
            }

        }

        void InitAStarStart()
        {
            GObject startObj = idxObjDic[startIdx];
            Node startNode = new Node(startObj, startIdx);
            AddOpenlistNode(startNode);

        }

        void AddOpenlistNode(Node node)
        {
            if(openListIdxDic.ContainsKey(targetNode.Idx))
            {
                Debug.Log("find the way to the target !!!");
                return;
            }

            int xIdx = node.xIdx;
            int yIdx = node.yIdx;
            List<Vector2> curDisVal = new List<Vector2>();
            int curValDis = 0;
            for (int i =0; i<2; i++)
            {
                if(i == 0)
                {
                    curDisVal = cconst.UnSlideDisVal;
                    curValDis = cconst.UnSlideDis;
                }
                else
                {
                    curDisVal = cconst.SlideDisVal;
                    curValDis = cconst.SlideDis;
                }

                for (int j = 0; j < cconst.slideValNum; ++j)
                {
                    var addVal = curDisVal[j];
                    var curXIdx = xIdx + (int)addVal.x;
                    var curYIdx = yIdx + (int)addVal.y;
                    if (curXIdx < 0 || curXIdx >= cconst.RowLineNum || curYIdx < 0 || curYIdx >= cconst.ColLineNum) continue;
                    int cur_Idx = curXIdx * cconst.ColLineNum + curYIdx;
                    if (closeListIdxDic.ContainsKey(cur_Idx)) continue;
                    Node curNode = null;
                    if (openListIdxDic.ContainsKey(cur_Idx))
                    {
                        curNode = openListIdxDic[cur_Idx];
                        int cur_G = node.G + curValDis;
                        if (curNode.G > cur_G)
                        {
                            curNode.SetParrent(node);
                            curNode.UpdateGVal(cur_G);
                        }
                        
                    }
                    else
                    {
                        GObject gobject = getTypeObject(cconst.FindTile);
                        float posX = cconst.startPos.x + curYIdx * cconst.width;
                        float posY = cconst.startPos.y - curXIdx * cconst.height;
                        gobject.gameobject.transform.localPosition = new Vector2(posX, posY);
                        curNode = new Node(gobject, cur_Idx);
                        if (idxObjDic[curXIdx * cconst.ColLineNum + curYIdx].IsObstacle)
                        {
                            closeListIdxDic[cur_Idx] = curNode;
                            //openList.Add(curNode);
                            curNode.gameobject.gameobject.SetActive(false);
                            return;
                        }
                        curNode.SetParrent(node);
                        openList.Add(curNode);
                        openListIdxDic[cur_Idx] = curNode;
                        curNode.G = node.G + curValDis;
                        SetHVal(curNode);
                    }
                    Debug.Log($"the G val is {curNode.G}");
                    curNode.UpdateDescDis();
                }
            }
            closeListIdxDic[node.Idx] = node;
            closeList.Add(node);

        }


        // Update is called once per frame
        void Update()
        {
            if(Input.GetKeyDown(KeyCode.A))
            {
                StopCoroutine(curCoroutine);
                foreach(var obj in totalObjList)
                {
                    Destroy(obj);
                }
                InitData();
            }
            else if (Input.GetKeyDown(KeyCode.B))
            {
                StopCoroutine(curCoroutine);
                foreach (var obj in totalObjList)
                {
                    Destroy(obj);
                }
            }
        }

        void RefreshFind()
        {
            
            
            Node findNode = null;
            int tmpMax = int.MaxValue;
            if(openList.Count == 0)
            {
                Debug.Log("can not find the way to the target !!!");
                return;
            }

            foreach(var node in openList)
            {
                Debug.Log($"idx = {node.Idx}, G = {node.G}, H = {node.H}, F = {node.F}");
                if (node.F < tmpMax)
                {
                    tmpMax = node.F;
                    findNode = node;
                }
            }
            if (findNode == null) return;
            GObject gobject = getTypeObject(cconst.MarkTile);
            Node curNode = new Node(gobject, findNode.Idx);
            curNode.UpdateLocalPosition();
            curNode.UpdateDescDis(findNode);
            markNodeList.Add(curNode);
            openList.Remove(findNode);
            AddOpenlistNode(findNode);
        }

        IEnumerator ShowFindPath(Node targetNode)
        {
            foreach(var _node in markNodeList)
            {
                _node.SetVisible(false);
            }
            Node temp_node = targetNode;
            while(temp_node != null)
            {
                GObject gobject = getTypeObject(cconst.MarkTile);
                Node curNode = new Node(gobject, temp_node.Idx);
                curNode.UpdateLocalPosition();
                temp_node = temp_node.parent;
                yield return new WaitForSeconds(0.5f);
            }

        }    

        void SetHVal(Node node)
        {
            int xDelVal = Mathf.Abs(node.xIdx - targetNode.xIdx);
            int yDelVal = Mathf.Abs(node.yIdx - targetNode.yIdx);
            node.H =  Mathf.Min(xDelVal, yDelVal) * cconst.SlideDis + Mathf.Abs(xDelVal - yDelVal) * cconst.UnSlideDis;
        }

        GObject getTypeObject(int objType)
        {
            GameObject gameObject = Instantiate(mapTypeObjDic[objType].gameobject);
            gameObject.transform.SetParent(transform);
            totalObjList.Add(gameObject);

            return new GObject(gameObject, objType);
        }
    }
        

}


Unity演示

演示样例一

在这里插入图片描述

演示样例二

在这里插入图片描述

演示样例三

在这里插入图片描述

演示样例四

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41841073/article/details/127124494

a星算法(java实现)-爱代码爱编程

一、适用场景 在一张地图中,绘制从起点移动到终点的最优路径,地图中会有障碍物,必须绕开障碍物。 二、算法思路 1. 回溯法得到路径 (如果有路径)采用“结点与结点的父节点”的关系从最终结点回溯到起点,得到路径。 2

a星算法的理解和c#实现-爱代码爱编程

         翻了翻别人写的博客,我看到一个A星算法,只怪自己见识太少,竟然没听过这个算法。网上查了好些资料,自己对这算法理解了些,并用C#实现出来。                      A星算法,也叫A*算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。 如在一张dota地图上,英雄从一个地方走动到地图上另一个点,它选择

a星算法详解_cocoiehl的博客-爱代码爱编程

A* 寻路算法 原文地址: http://www.gamedev.net/reference/articles/article2003.asp 概述 虽然掌握了 A* 算法的人认为它容易,但是对于初学者来说, A* 算法还是很复杂的。 搜索区域(The Search Area) 我们假设某人要从 A 点移动到 B 点,但是这两点之间被一堵墙隔开

03-0002 python实现a*算法_雯饰太一的博客-爱代码爱编程

Python实现A*算法 1.算法描述2.问题描述3.算法原理4.算法源码5.算法输出6.总结 1.算法描述 A*搜寻算法俗称A星算法,是比较流行的启发式搜索算法之一,被广泛应用于路径优化领域。它的独特之处是

不到一百行python代码简单实现a星算法_看我飞飞飞的博客-爱代码爱编程_a星算法python

为了更好地理解A星算法,自己手撸了一段91行的代码来实现A星算法 可能代码风格不是很好,因为这也就是一上午写出来的,只是简单实现了A星 过两天准备好好改动一下代码使其更易读,再好好备注一下。 #python3.7.3 im

利用unity3d实现a星算法(一)-爱代码爱编程

A星算法 算法分析 Node的属性 gCost 利用currentNode来来计算从起点到currentNode再到neighbourNode的距离=gCost hCost

A星算法理解-爱代码爱编程

A星算法理解 1.选择A星算法的原因 为了进行路径规划算法是不可回避的:启发式搜索算法是比较常规的一类算法就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的,

A*算法解决8数码问题python实现-爱代码爱编程

1.A*的通俗理解 很多游戏特别是rts,rpg类游戏,都需要用到寻路。寻路算法有深度优先搜索(DFS),广度优先搜索(BFS),A星算法等,而A星算法是一种具备启发性策略的算法,效率是几种算法中最高的,因此也成为游戏中最常用的寻路算法。 对于A星算法的具体理解可以参考下面这篇文章,本文着重讲解A星算法,在解决8数码问题的思路以及代码A*算法的通俗理解

A*:python实现A星寻路算法可视化-爱代码爱编程

A星寻路算法可视化 效果算法流程代码 效果 确定起点终点,画障碍,空格启动 红色是探索过的,绿色是当前可探索的。 算法流程 先介绍几个概念 名词解释open列表可探索的方块closed列表已探索的方块方块分数FF = G + HG从起点到当前点的距离H自己定义的当前点到终点的距离邻接节点本例中指上下左右4个节点我对H的理解是这样的: H

A星算法说明-爱代码爱编程

A*算法说明 文章目录 前言原理说明如何构造 h ( n

A星算法-爱代码爱编程

A星算法 1.简述 A星算法就是试图在地图中找到一条最短路径,但不保证一定存在。 任务 小猫去找青蛙玩(好TM弱智啊~)条件 黑色方块无法通行,每走一个格子小猫消耗的体力都为1。2.如果说你是小猫,你会怎么走? 嗯,毫无疑问 你肯定这么走。。。很简单的对吧,但是你这么走的时候,真的没经过思考?并非如此吧,你要找最短路径是不是直接连线是最快的?但是连

用简单直白的方式讲解A星寻路算法原理-爱代码爱编程

很多游戏特别是rts,rpg类游戏,都需要用到寻路。寻路算法有深度优先搜索(DFS),广度优先搜索(BFS),A星算法等,而A星算法是一种具备启发性策略的算法,效率是几种算法中最高的,因此也成为游戏中最常用的寻路算法。 直入正题: 在游戏设计中,地图可以划分为若干大小相同的方块区域(方格),这些方格就是寻路的基本单元。 在确定了寻路的开始点,结束点的

基于Unity的A星寻路算法(绝对简单完整版本)-爱代码爱编程

前言 在上一篇文章,介绍了网格地图的实现方式,基于该文章,我们来实现一个A星寻路的算法,最终实现的效果为: 项目源码已上传Github:AStarNavigate 在阅读本篇文章,如果你对于里面提到的一些关于网格地图的创建方式的一些地图不了解的话,可以先阅读了解一下下面的这篇文章: 文章链接: Unity 制作一个网格地图生成组件

【无人机】基于A星算法实现三维栅格地图路径规划matlab代码-爱代码爱编程

1 算法介绍 A*搜寻算法俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。(拷自百度百科)是常用搜索算法中,能够以最短时间来求得最短路径的一种启发式搜索算法。兼具广搜和深搜的优点,那么比较起广搜和深搜这些盲目搜索,A*有什么特点呢?A*搜索的效率就在于:以深搜的

浅谈迪杰斯特拉(Dijkstra)算法和A*算法原理及实现-爱代码爱编程

写在前面         最近我在学习一门名叫《智能自主机器人及系统》的课程,虽然跟过去所学的《机器人学》在部分内容上有所重复,但该课程的应用性更强。对于不同的机器人,如差速轮式车、四轮车、四旋翼、仿人机器人的建模进行了深入的探讨(如果有机会我会将其总结发布)。          最近课程进展到了智能机器人的决策与规划。其中规划中最基础的问题是最短路径

我做过的python30道练习题_linmeiyun的博客-爱代码爱编程

练习题 1 成绩等级 要求输出成绩等级A、B、C、D、E, 其中90-100分为A,80-89分为B,70-79分为C,60-69分为D,60分以下为E。 要求: - 用If语句实现; - 输入百分制成绩后要判断该成绩的合理性,对不合理的成绩应输出出错信息。 参考答案:   练习题 2 预判比赛结果 篮球比赛是高分的比赛,领

【算法导论】a*算法(a星算法)-爱代码爱编程

前言 这篇blog是由iOS Tutorial Team的成员  Johann Fradj发表的,他目前是一位全职的资深iOS开发工程师。他是Hot Apps Factory的创始人,该公司开发了App Cooker。目前来看,这是一篇例子最简单的A星寻路算法介绍,我只是在原有的基础上做了一下调整,并且在后面带有我写的c++代码。 原文可以查