[Unity] A |
您所在的位置：网站首页 › a星算法伪代码 › [Unity] A |
[Unity] A
|
在游戏中，有一个很常见地需求，就是要让一个角色从A点走向B点，我们期望是让角色走最少的路。嗯，大家可能会说，直线就是最短的。没错，但大多数时候，A到B中间都会出现一些角色无法穿越的东西，比如墙、坑等障碍物。这个时候怎么办呢？ 是的，我们需要有一个算法来解决这个问题，算法的目标就是计算出两点之间的最短路径，而且要能避开障碍物。
百度百科： A*搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。 简化搜索区域
要实现寻路，第一步我们要把场景简化出一个易于控制的搜索区域。 怎么处理要根据游戏来决定了。例如，我们可以将搜索区域划分成像素点，但是这样的划分粒度对于一般的游戏来说太高了（没必要）。 作为代替，我们使用格子（一个正方形）作为寻路算法的单元。其他的形状类型也是可能的（比如三角形或者六边形），但是正方形是最简单并且最常用的。 比如地图的长是w=2000像索，宽是h=2000像索，那么我们这个搜索区域可以是二维数组 map[w, h], 包含有400000个正方形，这实在太多了，而且很多时候地图还会更大。 现在让我们基于目前的区域，把区域划分成多个格子来代表搜索空间（在这个简单的例子中，20*20个格子 = 400 个格子， 每个格式代表了100像索）：
既然我们创建了一个简单的搜索区域，我们来讨论下A星算法的工作原理吧。 我们需要两个列表 (Open和Closed列表)： 一个记录下所有被考虑来寻找最短路径的格子（称为open 列表） 一个记录下不会再被考虑的格子（成为closed列表）首先在closed列表中添加当前位置（我们把这个开始点称为点 “A”）。然后，把所有与它当前位置相邻的可通行格子添加到open列表中。
现在我们要从A出发到B点。 在寻路过程中，角色总是不停从一个格子移动到另一个相邻的格子，如果单纯从距离上讲，移动到与自身斜对角的格子走的距离要长一些，而移动到与自身水平或垂直方面平行的格子，则要近一些。 为了描述这种区别，先引入二个概念：
节点(Node)：每个格子都可以称为节点。 代价(Cost)：描述角色移动到某个节点时所走的距离（或难易程度）。
如上图，如果每水平或垂直方向移动相邻一个节点所花的代价记为1，则相邻对角节点的代码为1.4(即2的平方根--勾股定理)
通常寻路过程中的代价用f,g,h来表示
g代表(从指定节点到相邻)节点本身的代价--即上图中的1或1.4
h代表从指定节点到目标节点（根据不同的估价公式--后面会解释估价公式）估算出来的代价。 而 f = g + h 表示节点的总代价 /// /// 寻路节点 /// public class NodeItem { // 是否是障碍物 public bool isWall; // 位置 public Vector3 pos; // 格子坐标 public int x, y; // 与起点的长度 public int gCost; // 与目标点的长度 public int hCost; // 总的路径长度 public int fCost { get {return gCost + hCost; } } // 父节点 public NodeItem parent; public NodeItem(bool isWall, Vector3 pos, int x, int y) { this.isWall = isWall; this.pos = pos; this.x = x; this.y = y; } }
注意：这里有二个新的东东 isWall 和 parent。 通常障碍物本身也可以看成是由若干个不可通过的节点所组成，所以 isWall 是用来标记该节点是否为障碍物(节点)。 另外：在考查从一个节点移动到另一个节点时，总是拿自身节点周围的8个相邻节点来说事儿，相对于周边的节点来讲，自身节点称为它们的父节点(parent). 前面一直在提“网格，网格”，干脆把它也封装成类Grid.cs using UnityEngine; using System.Collections; using System.Collections.Generic; public class Grid : MonoBehaviour { public GameObject NodeWall; public GameObject Node; // 节点半径 public float NodeRadius = 0.5f; // 过滤墙体所在的层 public LayerMask WhatLayer; // 玩家 public Transform player; // 目标 public Transform destPos; /// /// 寻路节点 /// public class NodeItem { // 是否是障碍物 public bool isWall; // 位置 public Vector3 pos; // 格子坐标 public int x, y; // 与起点的长度 public int gCost; // 与目标点的长度 public int hCost; // 总的路径长度 public int fCost { get {return gCost + hCost; } } // 父节点 public NodeItem parent; public NodeItem(bool isWall, Vector3 pos, int x, int y) { this.isWall = isWall; this.pos = pos; this.x = x; this.y = y; } } private NodeItem[,] grid; private int w, h; private GameObject WallRange, PathRange; private List pathObj = new List (); void Awake() { // 初始化格子 w = Mathf.RoundToInt(transform.localScale.x * 2); h = Mathf.RoundToInt(transform.localScale.y * 2); grid = new NodeItem[w, h]; WallRange = new GameObject ("WallRange"); PathRange = new GameObject ("PathRange"); // 将墙的信息写入格子中 for (int x = 0; x < w; x++) { for (int y = 0; y < h; y++) { Vector3 pos = new Vector3 (x*0.5f, y*0.5f, -0.25f); // 通过节点中心发射圆形射线，检测当前位置是否可以行走 bool isWall = Physics.CheckSphere (pos, NodeRadius, WhatLayer); // 构建一个节点 grid[x, y] = new NodeItem (isWall, pos, x, y); // 如果是墙体，则画出不可行走的区域 if (isWall) { GameObject obj = GameObject.Instantiate (NodeWall, pos, Quaternion.identity) as GameObject; obj.transform.SetParent (WallRange.transform); } } } } // 根据坐标获得一个节点 public NodeItem getItem(Vector3 position) { int x = Mathf.RoundToInt (position.x) * 2; int y = Mathf.RoundToInt (position.y) * 2; x = Mathf.Clamp (x, 0, w - 1); y = Mathf.Clamp (y, 0, h - 1); return grid [x, y]; } // 取得周围的节点 public List getNeibourhood(NodeItem node) { List list = new List (); for (int i = -1; i = 0) list.Add (grid [x, y]); } } return list; } // 更新路径 public void updatePath(List lines) { int curListSize = pathObj.Count; for (int i = 0, max = lines.Count; i < max; i++) { if (i cntY) { return 14 * cntY + 10 * (cntX - cntY); } else { return 14 * cntX + 10 * (cntY - cntX); } }
好吧，下面直接贴出全部的寻路算法 FindPath.cs: using UnityEngine; using System.Collections; using System.Collections.Generic; public class FindPath : MonoBehaviour { private Grid grid; // Use this for initialization void Start () { grid = GetComponent (); } // Update is called once per frame void Update () { FindingPath (grid.player.position, grid.destPos.position); } // A*寻路 void FindingPath(Vector3 s, Vector3 e) { Grid.NodeItem startNode = grid.getItem (s); Grid.NodeItem endNode = grid.getItem (e); List openSet = new List (); HashSet closeSet = new HashSet (); openSet.Add (startNode); while (openSet.Count > 0) { Grid.NodeItem curNode = openSet [0]; for (int i = 0, max = openSet.Count; i < max; i++) { if (openSet [i].fCost |
【本文地址】
今日新闻 |
推荐新闻 |