2020-03-15 15:21:59 weixin_42143018 阅读数 408
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

算法流程图

openset = PriorityQueue() // pop out node with least totoal cost (heuriscost + trajcost)
openset.push(start, 0)
closedset = {}
trajcost[start] = 0

while not openset.empty():
      current = openset.top()
      
      if analytic_expantion(current, goal): // using rs path 
         break;
      
      openset.pop()
      closedset.put(current)
      
      for next in kinematic_expantion(current):
          if (checkcollison(next)):
              delete next
              continue
          if find in closedset:
              delete next
              continue
          next.trajcost = current.trajcost +  calc_trajcost(current, next)
          if not find in openset:
             next.heuricost = calc_heuriscost(next, goal)
             next.totalcost = next.trajcost + next.heuriscost
             parent[next] = current
             openset.push(next)
          if find in openset and openset[next].trajcost > next.trajcost:
             openset[next].trajcost = next.trajcost
             openset[next].totalcost =  openset[next].trajcost + openset[next].heuriscost

reconstruct(goal)
delete start
delete goal
2015-08-27 17:34:31 JiaYangDeLuoChong 阅读数 2977
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

http://pan.baidu.com/s/1pJGHpbH有兴趣的同学可以下载下来把玩一番。这是我在完成算法之后,应用到项目之前,制作的一个demo。该demo通过读取xml文件,在空白的立方体表面上创建六个迷宫。其中,蓝色方块代表玩家,黑色方块代表怪物,怪物每三秒寻路一次,并使用红色方块标记路径。玩家可以通过方向键控制蓝色方块,改变它的位置。

声明:这不是A*算法教程!!!这不是A*算法教程!!!
前一段时间,我参与了某游戏项目,负责AI部分。项目提出这样的要求: 游戏场景为一个巨大的立方体。立方体的每一个面都是一个迷宫,而上面都有若干怪物。如果玩家到达立方体的某一个侧面上,该侧面上的怪物会进行寻路,追踪玩家。



该项目采用unity3D游戏引擎,但是我发现unity自带NavMesh组件似乎不能实现一个场景建立多个NavMesh。于是乎,决定采用A*算法,实现不同怪物能够在立方体不同的侧面上寻路。
A*算法简介
A*算法是寻路策略经常使用的算法。
http://www.policyalmanac.org/games/aStarTutorial.htm这里是一个经典A*算法教程。当然还有其他不错的教程,请大家采用自己喜欢的搜索引擎自行查找。
在执行A*算法的过程中存在两个节点表:Open表和Closed表。Open表表示准备拓展的节点的集合。Closed表表示已经拓展完毕的节点的集合。普通搜索算法通过遍历所有解从而去寻找最优解。而A*算法是估计节点代价,选择代价最小的节点去扩展,将可行的邻居节点加入Open表中,尝试性地去寻找最优解。A*算法在估计节点代价时,使用到估价函数。估价函数的表达式为:f(n)=g(n)+h(n)。f(n)表示从开始节点经过节点n到目标节点所需的估计花费,而g(n)表示从开始节点到节点n的实际花费,h(n)表示从节点n到目标节点的估计花费。如果h(n)设计的合理比较接近真实值,算法就会高效地选择出最优解。但是如果盲目追求h(n)的合理设计将很可能会因为考率的因素太多导致算法效率降低。
下图为A*算法的算法流程图。从图中可以看出,拓展节点时需要遍历当前节点的所有临接(邻居)节点。而节点的f(n)、g(n)和h(n)值决定了搜索结果。




f(n)=g(n)+h(n)的计算:
立方体的每一个侧面上的迷宫可以抽象为一个N*N二维数组。根据迷宫的布置,将可通过区域和障碍物分别标识在数组中。
例如某个侧面迷宫想要设计为:



则对应二维矩阵为:

某节点的f(n)值由g(n)和h(n)组成。g(n)表示从起始点到该点的实际花费。为了方便计算,设横向或者竖向行走一步的花费为10,斜着行走一步的花费为14(保证两者之间大概为√2倍关系)。
h(n)的值为当前结点所在网格到终点的欧式距离*10。



图中A为起点,C为终点,B为当前考察的节点。红色折线代表g(n),紫色折线代表h(n)。

按照算法过程,实现出代码没有什么特别大的难处,但是有几个问题需要注意:
关于closed表
程序中并不需要实现closed表,只要逻辑上存在就可以了。
斜着通过的问题:
如图这种情况是不应该发生的。解决起来也很简单,只要在拓展节点D时,判断并排除类似E的临节点就可以了。


C++与C#的“对接”:
我首先在C++中实现了A*算法,生成dll,在C#中调用。为了达到这个目的,在C++中声明函数时,需要
extern "C" int _declspec(dllexport) AStar(…)
在C#中,需要导入之前生成的AStar.dll,并声明该函数;
[DllImport("AStar")]
extern int AStar(…);
这一部分,我主要参考了王宇 warensoft的一篇博客,非常感谢。
http://www.cnblogs.com/warensoft/archive/2011/12/09/warenosoft3d.html。
将A*算法返回的路径应用到unity指导怪物运动的问题:
每次运动之前,怪物需要回到最近方格的中心,这样保证不会因为移动的偏差而卡在角落动弹不得。
拓展改进:
采用最小堆,快速查找open表中F值最小的节点。




2019-07-23 09:53:19 w9503 阅读数 315
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

几个月前开始做那个小游戏时,发现需要用到A寻路,看了很多讲解,终于把A搞懂了。过程描述:

①:通过循环提取Open-List中的值并不断地比较寻找此时列表中代价最低的路径点,将代价最低点移除Open-List,加入Close-List后进入②。持续循环此步骤直到Open-List中的路径点个数为0。

②:判断此路径点是否为寻路终点,若是则计算路径,直接进入④。否则,获得此点周围的非障碍点,进入③。

③:判断周围非障碍点是否已经存在于Open-List中,如果存在,重新计算并更新路径点代价函数值。如若不存在,计算路径点代价函数值后并将路径点储存在Open-List中。后将①中的提取点与此周围非障碍点设为父子关系,方便于最终路径点的提取。

④:得到最终点,依次根据节点的父子关系寻找父节点并存入数列中,直至寻找到初始路径点。数列中所有点的集合,即为寻路路径。

代码:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
//传说中的最优寻路方法,A*
public class Navigation : MonoBehaviour
{
    private Vector2 chushiposition;
    public GameObject gametest;
    public GameObject gametestlujing;
    [Range(0.5f, 1f)]
    public float lengthofbox;//我的tilemap每个格子是1所以我设置的是1,这个可以根据实际情况改
    public LayerMask NodeLayer;//选择障碍物所在的层
    public Transform player;//拖上目标对象(被追踪者)
    private Transform startPos;
    public Transform meshOrigin;//格子起点对象
    public class NodeItem
    {//单位格子类
        public bool iswall;
        public Vector2 worldpos;
        public int x, y;
        public int g;
        public int h;
        public int f
        {
            get { return g + h; }
        }
        public NodeItem parentNode;
        public NodeItem(bool iswall, Vector2 worldpos, int x, int y)
        {
            this.iswall = iswall;
            this.worldpos = worldpos;
            this.x = x;
            this.y = y;
        }
    }
    private NodeItem[,] nodeItems;
    private int w, h;
    private void Awake()
    {//初始化所有格子
        chushiposition = this.transform.position;
        w = 40; h = 40;
        nodeItems = new NodeItem[w, h];
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                Vector2 pos = new Vector2(i * lengthofbox, j * lengthofbox) + (Vector2)meshOrigin.position;
                bool iswall = false;
                // bool iswall = Physics2D.BoxCast(pos, new Vector2(lengthofbox-0.5f, lengthofbox-0.5f), 0, new Vector2(0, 0), NodeLayer);
                RaycastHit2D hit = Physics2D.BoxCast(pos, new Vector2(lengthofbox - 0.5f, lengthofbox - 0.5f), 0, new Vector2(0, 0), NodeLayer);
                if (hit)
                {
                    iswall = true;
                    if (hit.collider.gameObject.tag == "Player" || hit.collider.gameObject.tag == "guai")
                    {
                        iswall = false;
                    }
                }
                nodeItems[i, j] = new NodeItem(iswall, pos, i, j);
                //if (nodeItems[i, j].iswall)
                //{
                //    GameObject.Instantiate(gametest, nodeItems[i, j].worldpos,Quaternion.identity);
                //}
            }
        }
    }
    private void Start()
    {
        startPos = this.transform;       
    }
    public NodeItem GetIdem(Vector2 pos)
    {//获取坐标的格子坐标
        int i = Mathf.RoundToInt((pos.x - ((Vector2)meshOrigin.position).x) / lengthofbox);
        int j = Mathf.RoundToInt((pos.y - ((Vector2)meshOrigin.position).y) / lengthofbox);
        i = Mathf.Clamp(i, 0, w - 1);
        j = Mathf.Clamp(j, 0, h - 1);
        return nodeItems[i, j];
    }
    public List<NodeItem> Idemaround(NodeItem node)
    {//获取周围8个格子信息
        List<NodeItem> aroundlist = new List<NodeItem>();
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                if (i != 0 || j != 0)
                {
                    int x = node.x + i;
                    int y = node.y + j;
                    if (x < w && x >= 0 && y < h && y >= 0)
                    {
                        aroundlist.Add(nodeItems[node.x + i, node.y + j]);
                    }
                }
            }
        }
        //  for(int c = 0; c < aroundlist.Count; c++)
        // {
        //     print(aroundlist[c].x + "  " + aroundlist[c].y);
        //  }
        return aroundlist;
    }    private void Update()
    {
        if (Input.GetKeyDown(KeyCode.B))
        {
            findingpath((Vector2)startPos.position, (Vector2)player.position);
        }
    }
    private void findingpath(Vector2 startpos, Vector2 distpos)
    {//寻路
        NodeItem startnode = GetIdem(startpos);
        NodeItem distnode = GetIdem(distpos);
        List<NodeItem> Openlist = new List<NodeItem>();
        HashSet<NodeItem> Closelist = new HashSet<NodeItem>();
        Openlist.Add(startnode);
        while (Openlist.Count > 0)
        {
            NodeItem current = Openlist[0];
            for (int i = 0, max = Openlist.Count; i < max; i++)
            {
                // print(Openlist[i].x + "  " + Openlist[i].y + "  " + Openlist[i].f);
                if (current.f >= Openlist[i].f && current.h > Openlist[i].h)
                {
                    current = Openlist[i];
                }
            }
            Openlist.Remove(current);
            Closelist.Add(current);
            //Openlist.Clear();
            if (current == distnode)
            {
                generatepath(startnode, distnode);
                return;
            }
            foreach (NodeItem item in Idemaround(current))
            {
                if (item.iswall == false)
                {
                    GameObject.Instantiate(gametest, item.worldpos, Quaternion.identity);
                }
                //print(item.x + "  " + item.y + "  " + item.f);
                if (item.iswall || Closelist.Contains(item)) continue;
                int newcost = current.g + getdistance(current, item);
                if (newcost < item.g || !Openlist.Contains(item))
                {
                    item.g = newcost;
                    item.h = getdistance(item, distnode);
                    item.parentNode = current;
                    if (!Openlist.Contains(item))
                    {
                        Openlist.Add(item); 
                    }
                }
            }
        }
        generatepath(startnode, null);
    }
    private void generatepath(NodeItem A, NodeItem B)
    {//生成路径泛型队列
        List<NodeItem> path = new List<NodeItem>();
        if (B != null)
        {
            NodeItem node = B;
            while (node != A)
            {
                path.Add(node);
                node = node.parentNode;
            }
            path.Add(A);
            path.Reverse();
            print(path.Count);
            for(int i = 0; i < path.Count; i++)
            {
                GameObject.Instantiate(gametestlujing, path[i].worldpos, Quaternion.identity);
            }
        }
    }
    private int getdistance(NodeItem curr, NodeItem item)
    {//估算权值,对角线算法
        //int costx = Mathf.Abs(curr.x - item.x);
        //int costy = Mathf.Abs(curr.y - item.y);
        //if (costx > costy)
        //{
        //    return 10 * costx ;
        //}
        //else
        //{
        //    return 10 *costy;
        //}
        //曼哈顿算法
        return Mathf.Abs(curr.x - item.x) * 10 + Mathf.Abs(curr.y - item.y) * 10;
    }
}

为了方便理解,我和同学画了好久的流程图:在这里插入图片描述这是PartA部分

这是PartA部分

这是PartB部分

这是PartB部分

可能避免不了有错误。hh~

推荐几个厉害的讲解:
https://blog.csdn.net/dengheCSDN/article/details/78778769
https://blog.csdn.net/codingriver/article/details/83186067
https://blog.csdn.net/u012234115/article/details/47152137
这几个很厉害,
我的也有自己的样子在这里插入图片描述

还改进了一个搜索距离大的。

在这里插入图片描述
想要工程的可以私聊我哦!

2016-03-18 21:26:51 liu_if_else 阅读数 5437
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

A星寻路原理:

略,网上可搜到
只简单说下F,G,H值
G:从起点A到当前点B的所耗费的移动距离。
H:此点到终点的移动距离(忽视障碍)。
F:F=G+H,用来寻找最优解。

通过理解A星寻路的原理可以设计出以下流程图:

这里写图片描述

Unity C#脚本实现流程图的代码:

此脚本挂在场景中任意空物体上即可实现效果,在Start()内可调整地图相关参数

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

public class AStar : MonoBehaviour {
    //地图节点类型
    public enum NodeType    
    {
        moveable,   //可移动
        bar,        //障碍物
        boundary,   //边界
        aStarPath   //A星路径
    }

    //A星状态
    public enum AStarState
    {
        free,
        isInOpenList,
        isInCloseList
    }

    //pos<-->node 字典
    private Dictionary<Vector2, Node> PosNodeDict;

    //地图节点
    public class Node   
    {
        public Vector2 pos; 
        public NodeType nodeType;
        public AStarState aStarState;
        public Node[] neighbourNodes;
        public Node parentNode=null;
        public float F=0;
        public float G=0;
        public float H = 0;
    }

    //地图初始化
    public Node[,] InitMap(int mapHeight,int mapLength)
    {
        Node[,] nodes = new Node[mapHeight, mapLength];
        PosNodeDict = new Dictionary<Vector2, Node>();

        for (int i = 0; i < mapHeight; i++)
        {
            for (int j = 0; j < mapLength; j++)
            {
                nodes[i, j] = new Node();
                //边界判断
                if (i == 0)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else if (j == 0)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else if (i == mapHeight - 1)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else if (j == mapLength - 1)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else
                {
                    nodes[i, j].nodeType = NodeType.moveable;
                    nodes[i, j].pos = new Vector2(j, i);
                }

                //节点加入 坐标<-->节点 字典
                nodes[i, j].aStarState = AStarState.free;
                PosNodeDict.Add(new Vector2(j, i), nodes[i, j]);
             }
        }

        //初始化相邻坐标节点数组
        for (int i=0; i < mapHeight; i++)
        {
            for(int j=0; j < mapLength; j++)
            {
                nodes[i, j].neighbourNodes = new Node[8];
                Vector2 curNeighbVec2;
                //上
                curNeighbVec2 = new Vector2(j, i + 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[0] = PosNodeDict[curNeighbVec2];
                }
                //下
                curNeighbVec2 = new Vector2(j, i - 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[1] = PosNodeDict[curNeighbVec2];
                }
                //左
                curNeighbVec2 = new Vector2(j - 1, i);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[2] = PosNodeDict[curNeighbVec2];
                }
                //右
                curNeighbVec2 = new Vector2(j + 1, i);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[3] = PosNodeDict[curNeighbVec2];
                }
                //左上
                curNeighbVec2 = new Vector2(j - 1, i + 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[4] = PosNodeDict[curNeighbVec2];
                }
                //右上
                curNeighbVec2 = new Vector2(j + 1, i + 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[5] = PosNodeDict[curNeighbVec2];
                }
                //左下
                curNeighbVec2 = new Vector2(j - 1, i - 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[6] = PosNodeDict[curNeighbVec2];
                }
                //右下
                curNeighbVec2 = new Vector2(j + 1, i - 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[7] = PosNodeDict[curNeighbVec2];
                }
            }
        }
        return nodes;
    }

    //设置障碍bar
    public void AddBar(Vector2 barPos)
    {
        if (PosNodeDict.ContainsKey(barPos)){
            print("bar added");
           PosNodeDict[barPos].nodeType = NodeType.bar;
        }
    }

    //地图具象化
    public void InstantiateMap(Node[,] nodes)
    {
        for(int i = 0; i < nodes.GetLength(0); i++)
        {
            for (int j = 0; j < nodes.GetLength(1); j++)
            {
                GameObject curCube = GameObject.CreatePrimitive(PrimitiveType.Cube);
                curCube.transform.position = new Vector3(j, i, 0);
                if (nodes[i, j].nodeType == NodeType.boundary)
                {
                    print("set boundary");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.black);
                }
                else if (nodes[i, j].nodeType == NodeType.bar)
                {
                    print("set bar");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.red);
                }
                else if (nodes[i, j].nodeType == NodeType.aStarPath)
                {
                    print("set path");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.yellow);
                }
            }
        }
    }

    //地图具象化(并对Openlist,Closelist内节点上色)
    public void InstantiateMapBeta(Node[,] nodes){
        for (int i = 0; i < nodes.GetLength(0); i++)
        {
            for (int j = 0; j < nodes.GetLength(1); j++)
            {
                GameObject curCube = GameObject.CreatePrimitive(PrimitiveType.Cube);
                curCube.transform.position = new Vector3(j, i, 0);
                if (nodes[i, j].nodeType == NodeType.boundary)
                {
                    print("set boundary");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.black);
                }
                else if (nodes[i, j].nodeType == NodeType.bar)
                {
                    print("set bar");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.red);
                }
                else if (nodes[i, j].nodeType == NodeType.aStarPath)
                {
                    print("set path");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.yellow);
                }
                else if(OpenList.Contains(nodes[i,j]))
                {
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.green);
                }
                else if(CloseList.Contains(nodes[i,j]))
                {
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.blue);
                }
            }
        }
    }

    //寻路相关
    private List<Node> OpenList;
    private List<Node> CloseList;
    private Vector2 globalEndPos;
    //寻路入口
    public bool PathSearch(Node[,] nodes,Vector2 startPos,Vector2 endPos)
    {
        //校验参数
        if (!PosNodeDict.ContainsKey(startPos) || !(PosNodeDict.ContainsKey(endPos)))
        {
            print("invalid para");
            return false;
        }
        if(PosNodeDict[startPos].nodeType != NodeType.moveable||PosNodeDict[endPos].nodeType!=NodeType.moveable){
            print("invalid para");
            return false;
        }

        OpenList = new List<Node>();
        CloseList = new List<Node>();
        globalEndPos = endPos;
        //算法开始
        //起点为A
        Node A = nodes[(int)startPos.x, (int)startPos.y];
        A.G = 0;
        A.H = Mathf.Abs(globalEndPos.x - A.pos.x) + Mathf.Abs(globalEndPos.y - A.pos.y); //Vector2.Distance(A.pos, globalEndPos);
        A.F = A.G + A.H;
        A.parentNode = null;
        CloseList.Add(A);
        A.aStarState = AStarState.isInCloseList;
        do
        {
            //遍历OpenList,寻找F值最小的节点,设为A
            if (OpenList.Count > 0)
            {
                A = OpenList[0];
            }
            for (int i = 0; i < OpenList.Count; i++)
            {
                if (OpenList[i].F < A.F)
                {
                    A = OpenList[i];
                }
            }

            Node path = AStarSearch(A);

            if (path != null)
            {
                print("path found");
                do
                {
                    path.nodeType = NodeType.aStarPath;
                    if (path.parentNode == null)
                    {
                        path = null;
                    }
                    else
                    {
                        path = path.parentNode;
                    }
                } while (path!= null);
                return true;
            }
            OpenList.Remove(A);
            CloseList.Add(A);
            A.aStarState = AStarState.isInCloseList;
        //OpenList是否还有节点
        } while (OpenList.Count > 0);
        //无到达目的地的路径
        print("path not found");
        return false;
    }

    public Node AStarSearch(Node A)
    {
        //遍历A的周边节点,当前处理节点为B
        Node B;
        for (int i = 0; i < A.neighbourNodes.Length; i++)
        {
            if (A.neighbourNodes[i] == null)
            {
                continue;
            }

            B = A.neighbourNodes[i];
            //是否是可移动节点
            if (B.nodeType != NodeType.moveable)
            {
                continue;
            }
            //是否在开放列表中
            if (B.aStarState == AStarState.isInOpenList)
            {
                //A到B的G值+A.G>B.G
                float curG = Vector2.Distance(A.pos, B.pos);
                if (B.G > curG + A.G)
                {
                    //更新B的父节点为A,并相应更新B.G,B.H
                    B.parentNode = A;
                    B.G = curG + A.G;
                    B.F = B.G + B.H;
                }
                continue;
            }
            else if(B.aStarState==AStarState.free)
            {
                //更新B的父节点为A,并相应更新B.G; 计算B.F,B.H; B加入OpenList
                B.parentNode = A;
                B.G = Vector2.Distance(A.pos,B.pos)+A.G;
                B.H = Mathf.Abs(globalEndPos.x - B.pos.x) + Mathf.Abs(globalEndPos.y - B.pos.y); //Vector2.Distance(B.pos, globalEndPos);
                B.F = B.G + B.H;
                OpenList.Add(B);
                B.aStarState = AStarState.isInOpenList;
                //B.F==0
                if (B.H <Mathf.Epsilon)
                {
                    //B的所有父节点既是路径
                    return B;
                }
                else
                {
                    //继续遍历
                    continue;
                }
            }
            else
            {
                continue;
            }
        }
        return null;
    }

    //程序入口
    // Use this for initialization
    void Start () {
        Node[,] nodes = InitMap(100, 100);

        AddBar(new Vector2(2, 2));
        AddBar(new Vector2(2, 3));
        AddBar(new Vector2(3, 2));
        AddBar(new Vector2(3, 3));
        AddBar(new Vector2(4, 4));
        AddBar(new Vector2(3, 4));
        AddBar(new Vector2(4, 3));
        AddBar(new Vector2(4, 5));
        AddBar(new Vector2(5, 4));
        AddBar(new Vector2(4, 6));
        AddBar(new Vector2(4, 7));
        AddBar(new Vector2(1, 7));
        AddBar(new Vector2(2, 7));
        AddBar(new Vector2(3, 7));

        PathSearch(nodes, new Vector2(3, 1), new Vector2(2,12));

        InstantiateMapBeta(nodes);
    }
}


效果图:

红色方块为障碍物,黑色方块为边界,灰色方块为空地,绿色方块为OpenList内节点,蓝色方块为CloseList内节点,黄色方块为路径。

这里写图片描述

这里写图片描述

这里写图片描述
————————————————————————————————
维护日志:
2017-8-31:更改标题,文章分类。
2018-8-2:Review,重写了代码,流程图,并更新了效果图。

2016-09-22 22:31:50 NeverMore_Mr 阅读数 0
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

A*算法理解

A*算法目的在于找到一条能够到达目的地的最短路线,其核心思想是广度优先搜索,以当前格子为中心,遍历周围的格子,通过计算每个格子到达目标点的距离,找出一条能够到达且消耗最小的路径。A*算法中的公式很简单:F =G+H,我是这样理解的:
如图,假设角色需要从A点移动到B点。G代表从A点移动到自身相邻的八个点(A1到A8)所消耗的体力值,因为正方向比斜方向移动的距离短,所以正方向消耗10点体力(A到A5),斜方向消耗14点体力(A到A3);H代表从当前点到终点的横纵坐标之差的绝对值,即曼哈顿距离(从A到B为40,从A5到B为30)。也可以这样理解:G为单次行走消耗的体力值,H表示到达终点还将需要消耗的体力值。当某个点受到阻挡时,需返回到之前的点重新计算。这样一来,地图上每一个格子所代表的点到达终点需要消耗的体力值都被量化,下一步我们要做的事情就是找到一条消耗体力值F最小的路径。
A*示意图

Unity中模拟A*算法

1.定义格子类

格子代表着二维地图中的坐标点,且每个格子有F、G、H值。因此,格子可以用一个类来表示:

public class Node {
//坐标
public int X, Y;
//记录消耗值
public int F, G, H;
//父节点
public Node Parent;

//自动计算H值,估计值
public void CalculateH(Vector2 end)
{
    this.H = (int)(10 * (Mathf.Abs(end.x - X) + Mathf.Abs(end.y - Y)));
}

//自动计算F值
public void CalculateF()
{
    this.F = G + H;
}

public Node(int x, int y, Node parent = null)
{
    this.X = x;
    this.Y = y;
    this.Parent = parent;           
}

public Node(Vector2 point, Node parent = null)
{
    this.X = (int)point.x;
    this.Y = (int)point.y;
    this.Parent = parent;
}
}

2.生成简易的格子地图

由于格子代表一个个坐标点,因此可以利用txt文档存储地图坐标信息,用0表示起始点,9表示目标点,2表示障碍物,1表示可行走的格子。因此txt中存放数据为:
1111111
1112111
1012191
1112111
1111111
利用StreamReader类加载数据,代码如下:

byte[,] mapData;       //用来接受地图数据
int rowCount;          //地图行数
int colCount;          //地图列数
string mapPath;        //txt文件存放路径

void LoadMapData(string path)
{
    StreamReader sr = new StreamReader(mapPath);
    string content = sr.ReadToEnd();
    string[] rows = content.Split('\n');
    rowCount = rows.Length;
    colCount = rows[0].Trim().Length;
    mapData = new byte[rowCount, colCount];
    for (int i = 0; i < rowCount; i++)
    {
        for (int j = 0; j < colCount; j++)
        {
            mapData[i, j] = byte.Parse(rows[i][j].ToString());
        }
    }
    sr.Close();
    sr.Dispose();
}

加载完地图数据后,在场景中创建出地图(用cube表示格子,因此提前制作好三种cube的预制体)

void CreatMap()
{
    //生成蓝色Cube表示起始点
    GameObject bluePrefab = Resources.Load<GameObject>("BluePrefab");
    //生成红色Cube表示终点
    GameObject redPrefab = Resources.Load<GameObject>("RedPrefab");
    //生成黑色Cube表示障碍物
    GmaObject blackPrefab = Resources.Load<GameObject>("BlackPrefab");
    //生成白色Cube表示普通格子
    GmaObject blackPrefab = Resources.Load<GameObject>("WhitePrefab");

    //for循环遍历mapData中的数据,并根据数值生成相应的Cube
    for (int i = 0; i < rowCount; i++)
    {
        for (int j = 0; j < colCount; j++)
        {
            GameObject grid = null;
            switch ((int)mapData[i, j])
            {                    
                case 0:
                    grid = Instantiate(bluePrefab);
                    break;
                case 1:
                    grid = Instantiate(WhitePrefab);
                    break;
                case 2:
                    grid = Instantiate(blackPrefab);
                    break;
                case 9:
                    grid = Instantiate(redPrefab);
                    break;
            }
            grid.transform.position = GetPosition(i,j);
            grid.transform.SetParent(transform);
            grid.transform.localScale = Vector3.one * 0.8f;
            grid.name = i + "_" + j;
        }        
    }
}

生成后的地图如下:
这里写图片描述

3.实现A*算法

Vector2 start;      //起始点
Vector2 endd;       //终止点

//某点的八个相邻方向
Vector2[] dirs = new Vector[]{Vector2.up,Vector2.down,
Vector2.left,Vector2.right,new Vector2(1,1),new Vector2(1,-1),new Vector2(-1,1),new Vector2(-1,-1)};

List<Node> list = new List<Node>();    //待访问的节点列表
List<Node> visited = new List<Node>(); //已访问的节点列表
Stack<Vector2> path = new Stack<Vector2>();//行走路径

//A*算法
void AStar()
{
    GetStartAndEnd();
    //创建起始节点进入队列
    Node root = new Node(start);
    list.Add(root);

    //开始检索list中的节点以及周围八个方向的点(广度优先算法)
    while(list.Count>0)
    {
        //先对list中的节点按照F值排序
        list.Sort(NodeSort);
        //取F值最小的节点作为起始节点
        Node node = list[0];
        list.Remove(node);
        visited.Add(node);
        //对节点周围八个方向的点进行遍历
        for(int i=0;i<dirs.Length;i++)
        {
            Vector2 point;
            point.x=node.X+dirs[i].x;
            point.y=node.Y+dirs[i].y;
            //判断该点能否到达
            if(IsOk(point))
            {
                Node n = new Node(point);
                //计算该点的G、H、F值
                n.G = i>3?(node.G+14):(node.G+10);
                n.CalculateH(end);
                n.CalculateF();
                list.Add(n);
                if(point == end)
                {
                    Debug.Log("Find!")
                    Node p = n;
                    //遍历父节点(来时的路径)
                    while(p!=null)
                    {
                        path.Push(new Vector2(p.x,p.y));
                        p = p.parent;
                    }
                    return;
                }
            }
        }
}

//获取起始点和终止点
void GetStartAndEnd()
{
    for(int i=0;i<rowCount;i++)
    {
        for(int j=0;j<colCount;j++)
        {
            //0表示起始点
            if(mapData[i,j]==0)
            {
                start.x = i;
                start.y = j;
            }
            //9表示终止点
            if(mapData[i,j]==9)
            {
                start.x = i;
                start.y = j;
            }
        }
    }
}

//集合中的节点按照F值排序
void NodeSort(Node node1,Node node2)
{
    if (x.F > y.F)
        return 1;
    else if (x.F < y.F)
        return -1;
    else
        return 0;
}

//判断该节点是否能够到达
bool IsOk(Vector2 point)
{
    //越界
    if (point.x < 0 || point.x >= rowCount || point.y < 0 || point.y >= colCount)
    {
        return false;
    }
    //障碍物
    if (mapData[(int)point.x, (int)point.y] == 2)
    {
        return false;
    }
    //节点已访问
    for (int i = 0; i < visited.Count; i++)
    {
        if (visited[i].X == point.x && visited[i].Y == point.y)
        {
            return false;
        }            
    }
    //节点在List中
    for (int i = 0; i < list.Count; i++)
    {
        if (list[i].X == point.x && list[i].Y == point.y)
        {
            return false;
        }
    }
    return true;
}

4.创建角色进行寻路测试

//用于测试的移动角色
Transform player;        //角色
Vector3 target;          //当前移动的目标点
Vector3 moveDir;         //当前移动的方向

void Awake()
{
    mapPath=Application.dataPath+"Map.txt";
    LoadMapData(mapPath);
    CreateMap();
}
void Start()
{
    AStar();
    player = GameObject.CreatePrimitive(PrimitiveType.Capsule).transform;
    player.transform.position = GetPosition(start);
    target = getPosition(path.Peek());
}

void Update()
{
    moveDir = (target - player.position).normalized;
    player.Translate(moveDir*Time.deltaTime);
    if(Vector3.Distance(player.position,target)<0.1f&&path.Count>0)
    {
        path.Pop();
        if(path.Count == 0)
        {
            this.enabled = false;
        }
        else
        {
            target = GetPosition(path.Peek());
        }           
    }       
}
//获取横纵坐标值获取世界坐标
Vector3 GetPosition(int i,int j)
{
    //j控制内层循环,因此关联x轴坐标(表示列数)
    float x = j - colCount * 0.5f;
    //i控制外层循环,因此关联z轴坐标(表示行数)
    float y = rowCount*0.5f - i;
    return new Vector3(x, 0, y);
}
//根据vector2坐标获取世界坐标
Vector3 GetPosition(Vector2 point)
{
    float x = point.y - colCount * 0.5f;
    float y = rowCount * 0.5f - point.x ;
    return new Vector3(x, 0, y);
}

运行结果如下:
这里写图片描述