2013-02-25 11:07:30 fzhlee 阅读数 4146
• ###### 深入浅出Unity3D——第一篇

Unity3D基础知识、游戏算法一网打尽。

74787 人正在学习 去看看 何韬

Note that this code has been updated. I have an updated blog post detailing what changed. The full source code is available athttps://github.com/bgrins/javascript-astar

I first implemented the A* algorithm for a research group I was in through school (Computer Graphics and Image Understanding). A* is a best-first, graph search algorithm. Some basic information can be found on the Wikipedia page for A* and the external links contained in it. Please refer to that page for general reference about the algorithm, I will simply explain in my own words how it works and how I got it working.

A* algorithm in JavaScript

### Why JavaScript?

Because it was easy to deploy!

Since I know JavaScript pretty well, and most of the examples you can find are in C, Java or a similar language that you cannot run without downloading source code or executables, I thought it would be a good idea to program it on an html page. This way, people could see what was going on and view the source very easily by using the online demo.

My hope was to build a page that could be extended with other search algorithms by separating the UI code (that generates a graph with walls and animates the path that is determined by an algorithm), and the algorithm that finds the path. Maybe I will get around to plugging in some more algorithms sometime and making it into a little resource for graph search algorithms.

### How?

#### search.html

Just a basic html file that includes jQuery, the excellent JavaScript library, main.css, graph.js, and astar.js. Also, I have a JavaScript block that initializes the page.

#### graph.js

The point of this file is to build the graph, call the search function, and animate the results after the search has returned. It also has an option to show the debugging information created by the search algorithm. I won’t get too into the code here, since it distracts from the search algorithm.

Please take a look at it, be aware that there are some improvements I would make if I was to rewrite this today. There are some performance issues that could be addressed, and It modifies the Array.prototype to add on specific methods (findGraphNode and removeGraphNode) for search algorithms, which may not be ideal for bigger projects. For this little page, I’m not too worried about it, but if I do get around to adding in more algorithms, I will probably improve this code.

#### astar.js

This is the actual implementation of the algorithm. I will do my best to explain what is going on, but feel free to just look at the source of the example, or just download astar.js.

There are three functions that we keep track of for nodes that we look at:

• g(x): The total cost of getting to that node (pretty straightforward). If we reach a node for the first time or reach a node in less time than it currently took, then update the g(x) to the cost to reach this node.
• h(x): The estimated time to reach the finish from the current node. This is also called a heuristic. We online need to update this if it is not set already, since the distance to the finish will not change even if the path we took to arrive at a node changes. Note: There are many different ways to guess how far you are from the end, I use the Manhattan distance in this implementation.
• f(x): Simply g(x) + h(x). The lower the f(x), the better. Think about it like this: the best node is one that takes the least total amount of time to arrive at and to get to the end. So, a node that took only 1 step to arrive at and 5 to get to the end is more ideal than one that took 10 to arrive and and only 1 to get to the end.

Here is some high level pseudocode of what is happening in the algorithm. Also see the Wikipedia pseudocode for another example.

```  push startNode onto openList
while(openList is not empty) {
currentNode = find lowest f in openList
if currentNode is final, return the successful path
push currentNode onto closedList and remove from openList
foreach neighbor of currentNode {
if neighbor is not in openList {
save g, h, and f then save the current parent
}
if neighbor is in openList but the current g is better than previous g {
save g and f, then save the current parent
}
}
```

Here is the JavaScript for the list implementation:

```var astar = {
init: function(grid) {
for(var x = 0; x < grid.length; x++) {
for(var y = 0; y < grid[x].length; y++) {
grid[x][y].f = 0;
grid[x][y].g = 0;
grid[x][y].h = 0;
grid[x][y].debug = "";
grid[x][y].parent = null;
}
}
},
search: function(grid, start, end) {
astar.init(grid);

var openList   = [];
var closedList = [];
openList.push(start);

while(openList.length > 0) {

// Grab the lowest f(x) to process next
var lowInd = 0;
for(var i=0; i<openList.length; i++) {
if(openList[i].f < openList[lowInd].f) { lowInd = i; }
}
var currentNode = openList[lowInd];

// End case -- result has been found, return the traced path
if(currentNode.pos == end.pos) {
var curr = currentNode;
var ret = [];
while(curr.parent) {
ret.push(curr);
curr = curr.parent;
}
return ret.reverse();
}

// Normal case -- move currentNode from open to closed, process each of its neighbors
openList.removeGraphNode(currentNode);
closedList.push(currentNode);
var neighbors = astar.neighbors(grid, currentNode);

for(var i=0; i<neighbors.length;i++) {
var neighbor = neighbors[i];
if(closedList.findGraphNode(neighbor) || neighbor.isWall()) {
continue;
}

// g score is the shortest distance from start to current node, we need to check if
//	 the path we have arrived at this neighbor is the shortest one we have seen yet
var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
var gScoreIsBest = false;

if(!openList.findGraphNode(neighbor)) {
// This the the first time we have arrived at this node, it must be the best
// Also, we need to take the h (heuristic) score since we haven't done so yet

gScoreIsBest = true;
neighbor.h = astar.heuristic(neighbor.pos, end.pos);
openList.push(neighbor);
}
else if(gScore < neighbor.g) {
// We have already seen the node, but last time it had a worse g (distance from start)
gScoreIsBest = true;
}

if(gScoreIsBest) {
// Found an optimal (so far) path to this node.	 Store info on how we got here and
//	just how good it really is...
neighbor.parent = currentNode;
neighbor.g = gScore;
neighbor.f = neighbor.g + neighbor.h;
neighbor.debug = "F: " + neighbor.f + "<br />G: " + neighbor.g + "<br />H: " + neighbor.h;
}
}
}

// No result was found -- empty array signifies failure to find path
return [];
},
heuristic: function(pos0, pos1) {
// This is the Manhattan distance
var d1 = Math.abs (pos1.x - pos0.x);
var d2 = Math.abs (pos1.y - pos0.y);
return d1 + d2;
},
neighbors: function(grid, node) {
var ret = [];
var x = node.pos.x;
var y = node.pos.y;

if(grid[x-1] && grid[x-1][y]) {
ret.push(grid[x-1][y]);
}
if(grid[x+1] && grid[x+1][y]) {
ret.push(grid[x+1][y]);
}
if(grid[x][y-1] && grid[x][y-1]) {
ret.push(grid[x][y-1]);
}
if(grid[x][y+1] && grid[x][y+1]) {
ret.push(grid[x][y+1]);
}
return ret;
}
};```

And here is a faster implementation, using a Binary Heap instead of a list. This is a lot faster and also includes the option to search diagonally – 8 directional movement. Head over to the astar graph search project page to get the latest version of the code!

```var astar = {
init: function(grid) {
for(var x = 0, xl = grid.length; x < xl; x++) {
for(var y = 0, yl = grid[x].length; y < yl; y++) {
var node = grid[x][y];
node.f = 0;
node.g = 0;
node.h = 0;
node.cost = 1;
node.visited = false;
node.closed = false;
node.parent = null;
}
}
},
heap: function() {
return new BinaryHeap(function(node) {
return node.f;
});
},
search: function(grid, start, end, diagonal, heuristic) {
astar.init(grid);
heuristic = heuristic || astar.manhattan;
diagonal = !!diagonal;

var openHeap = astar.heap();

openHeap.push(start);

while(openHeap.size() > 0) {

// Grab the lowest f(x) to process next.  Heap keeps this sorted for us.
var currentNode = openHeap.pop();

// End case -- result has been found, return the traced path.
if(currentNode === end) {
var curr = currentNode;
var ret = [];
while(curr.parent) {
ret.push(curr);
curr = curr.parent;
}
return ret.reverse();
}

// Normal case -- move currentNode from open to closed, process each of its neighbors.
currentNode.closed = true;

// Find all neighbors for the current node. Optionally find diagonal neighbors as well (false by default).
var neighbors = astar.neighbors(grid, currentNode, diagonal);

for(var i=0, il = neighbors.length; i < il; i++) {
var neighbor = neighbors[i];

if(neighbor.closed || neighbor.isWall()) {
continue;
}

// The g score is the shortest distance from start to current node.
// We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
var gScore = currentNode.g + neighbor.cost;
var beenVisited = neighbor.visited;

if(!beenVisited || gScore < neighbor.g) {

// Found an optimal (so far) path to this node.  Take score for node to see how good it is.
neighbor.visited = true;
neighbor.parent = currentNode;
neighbor.h = neighbor.h || heuristic(neighbor.pos, end.pos);
neighbor.g = gScore;
neighbor.f = neighbor.g + neighbor.h;

if (!beenVisited) {
// Pushing to heap will put it in proper place based on the 'f' value.
openHeap.push(neighbor);
}
else {
// Already seen the node, but since it has been rescored we need to reorder it in the heap
openHeap.rescoreElement(neighbor);
}
}
}
}

// No result was found - empty array signifies failure to find path.
return [];
},
manhattan: function(pos0, pos1) {
// See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

var d1 = Math.abs (pos1.x - pos0.x);
var d2 = Math.abs (pos1.y - pos0.y);
return d1 + d2;
},
neighbors: function(grid, node, diagonals) {
var ret = [];
var x = node.x;
var y = node.y;

// West
if(grid[x-1] && grid[x-1][y]) {
ret.push(grid[x-1][y]);
}

// East
if(grid[x+1] && grid[x+1][y]) {
ret.push(grid[x+1][y]);
}

// South
if(grid[x] && grid[x][y-1]) {
ret.push(grid[x][y-1]);
}

// North
if(grid[x] && grid[x][y+1]) {
ret.push(grid[x][y+1]);
}

if (diagonals) {

// Southwest
if(grid[x-1] && grid[x-1][y-1]) {
ret.push(grid[x-1][y-1]);
}

// Southeast
if(grid[x+1] && grid[x+1][y-1]) {
ret.push(grid[x+1][y-1]);
}

// Northwest
if(grid[x-1] && grid[x-1][y+1]) {
ret.push(grid[x-1][y+1]);
}

// Northeast
if(grid[x+1] && grid[x+1][y+1]) {
ret.push(grid[x+1][y+1]);
}

}

return ret;
}
};```

### Conclusion

This A* search implementation could be used as a component to larger system (like a game – maybe tower defense or puzzle), or just for learning purposes. I have done my best to make the code understandable and to present the concepts in a way that would help someone who has never seen the algorithm before, or someone who is not very familiar with JavaScript.

Feel free to view the demo, or download graph.js and astar.js to mess around with it. Check out the javascript-astar project page on Github for the latest version

unity3d自动寻路算法 相关内容

2015-05-07 17:38:27 a3636987 阅读数 4921
• ###### 深入浅出Unity3D——第一篇

Unity3D基础知识、游戏算法一网打尽。

74787 人正在学习 去看看 何韬

```using UnityEngine;
using System.Collections;

public static class MapsArray {

public static int[,] MazeItem = new int[15, 10]   //初始化迷宫
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,0,0,1,1},
{1,0,0,1,1,0,1,0,1,1},
{1,0,0,0,0,0,1,0,1,1},
{1,1,0,1,0,1,1,0,1,1},
{1,1,0,1,0,0,0,0,1,1},
{1,0,0,0,1,1,1,0,1,1},
{1,1,0,0,0,0,0,0,1,1},
{1,1,0,1,1,1,0,0,0,1},
{1,1,0,0,1,1,1,0,1,1},
{1,1,1,0,0,0,0,0,1,1},
{1,1,1,1,0,0,1,0,1,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
}
```

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

public class TestPathing : MonoBehaviour {

private int[,] MazeItem;   //初始化迷宫

private GameObject npc;             // npc
private List<Vector3> path;         // 路径
private Vector3 target = Vector3.zero;
private float speed = 4;            // npc移动速度
private int n = 0;                  // 当前已经移动的路点
private const int xStart = 1;
private const int yStart = 1;
private const int xEnd = 8;
private const int yEnd = 8;
void Start () {
MazeItem = MapsArray.MazeItem;  // 初始化迷宫数组
path = new List<Vector3> ();
StartCoroutine (CreateMap());
}

void Update()
{
if (target != Vector3.zero)
{
if (path.Count > 0)
{
npc.transform.position = Vector3.MoveTowards(npc.transform.position, target, Time.deltaTime * speed);
if (npc.transform.position == target)
{
target = GetTarget();
}
}
}
}

// 创建地图
IEnumerator CreateMap () {
// 地图全局
GameObject cube = GameObject.CreatePrimitive(PrimitiveType.Cube);
yield return cube;
for (int i = 0; i < MazeItem.GetLength(0); i++) {
for (int j = 0; j < MazeItem.GetLength(1); j++) {
if(MazeItem[i, j] == 1) {
Instantiate(cube, new Vector3(i, j, 0), Quaternion.identity);
}
}
}

// 起始点标记
GameObject start = Instantiate(cube, new Vector3(xStart, yStart, 0), Quaternion.identity) as GameObject;
start.transform.localScale = Vector3.one * 0.3f;
start.renderer.material.color = Color.grey;
GameObject end = Instantiate(cube, new Vector3(xEnd, yEnd, 0), Quaternion.identity) as GameObject;
end.transform.localScale = Vector3.one * 0.3f;
end.renderer.material.color = Color.blue;
yield return new WaitForEndOfFrame();
StartCoroutine(CreateNPC());

}

// 创建NPC
IEnumerator CreateNPC()
{
GameObject npc_Prefab = GameObject.CreatePrimitive(PrimitiveType.Sphere);
yield return npc_Prefab;
if (MazeItem[1, 1] == 0)
{
npc = Instantiate(npc_Prefab, new Vector3(1, 1, 0), Quaternion.identity) as GameObject;
npc.renderer.material.color = Color.green;
target = npc.transform.position;        // 设置初始点
}
yield return new WaitForEndOfFrame();
StartCoroutine(Pathing());

}

// 开始寻路
IEnumerator Pathing() {
if (GoPathing(xStart, yStart, xEnd, yEnd))
{
print("有路！！！");
}
else
{
print("没路！！！");
}
yield return new WaitForEndOfFrame();
}

bool GoPathing(int startX, int startY, int endX, int endY)
{
if (startX < 0 || startX >= MazeItem.GetLength(0) || startY < 0 || startY >= MazeItem.GetLength(1) || MazeItem[startX, startY] == 1)
return false;
MazeItem[startX, startY] = 1;// 防止重复走
if ((startX == endX && startY == endY) ||
GoPathing(startX - 1, startY, endX, endY) || GoPathing(startX + 1, startY, endX, endY) ||
GoPathing(startX, startY - 1, endX, endY) || GoPathing(startX, startY + 1, endX, endY))
{
// 存储路径点
print("X:" + startX + "Y:" + startY);
return true;
}
else
{
return false;
}
}

// 获取路径
Vector3 GetTarget()
{
Vector3 point = npc.transform.position;
if (path.Count > 0 && n < path.Count)
{
point = path[path.Count - n - 1];
n++;
}
return point;
}
}
```

unity3d自动寻路算法 相关内容

2018-05-26 10:32:26 u012187817 阅读数 405
• ###### 深入浅出Unity3D——第一篇

Unity3D基础知识、游戏算法一网打尽。

74787 人正在学习 去看看 何韬

A星寻路的原理和教程我就不班门弄斧了，百度前几个都是大神写的。对着前辈的教程，我简单修改了一部分代码后做了一个简单的demo，又花了一个晚上将跑通的demo的脚本移植到项目了，在博客里就只贴出demo里的脚本了，作为我的学习记录。

Point类，存储着每一个点的各种属性，父点、F、G、H值，x、z坐标

``````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 Z { get; set; }

public bool IsObstacle { get; set; }
public Point(int x, int z, Point parent = null)
{
this.X = x;
this.Z = z;
this.ParentPoint = parent;
}
public void UpdateParent(Point parent,float g)
{
this.ParentPoint = parent;
this.G = g;
F = G + H;
}
}``````

AStar类，根据需要能得到移动路径点列表、移动所需要的步数、障碍物（不能走的格子）

``````public class AStar : MonoBehaviour {
private const int mapWith = 5;
private const int mapHeight = 5;
private Point[,] map;
Point start;
Point end;
public GameObject player;
List<Point> pointList = new List<Point>();
Vector3 targetPos;
int step;
void Update () {
if (pointList.Count == 0)
return;
Move();
}
void InitPath(int row,int column)
{
map = new Point[row, column];
InitMap();
start = map[0, 0];//起始坐标
end = map[1, 2];//目标点坐标
FindPath(start, end);
SetPathByParent(start, end);
}
//移动方法
void Move()
{
for (int i = pointList.Count; i > 0; i--)
{
Vector3 pointPos = new Vector3(pointList[i - 1].X, player.transform.position.y, pointList[i - 1].Z);
if (player.transform.position == pointPos)
{
pointList.Remove(pointList[i - 1]);
break;
}
if (i == pointList.Count)
{
targetPos = pointPos;
break;
}
}
player.transform.position = Vector3.MoveTowards(player.transform.position, targetPos, 1 * Time.deltaTime);
}
//将通过父点，将路径点添加进列表
private void SetPathByParent(Point start, Point end)
{
Point temp = end;
while (true)
{
if (temp.ParentPoint == null)
break;
temp = temp.ParentPoint;
step++;
}
Debug.Log(step);
}
//点过滤方法，关闭列表里存在的点——其本身，在周围能走的点列表里移除该点
private void PointsFilter(List<Point> src, List<Point> closeList)
{
foreach (Point p in closeList)
{
if (src.IndexOf(p) > -1)
{
src.Remove(p);
}
}
}
//初始化格子坐标和属性
private void InitMap()
{
for (int x = 0; x < mapWith; x++)
{
for (int z = 0; z < mapHeight; z++)
{
map[x, z] = new Point(x, z);
}
}
//设置某点为障碍物
map[0, 1].IsObstacle = true;
}
//寻找路径方法，传入起始点和结束点，
private void FindPath(Point start, Point end)
{
//声明开启列表和结束列表，将起始点添加进开启列表
List<Point> openList = new List<Point>();
List<Point> closeList = new List<Point>();
//如果开启列表数量不为0
while (openList.Count > 0)
{
//找到开启列表里最小F值的点，将该点移除开启列表，添加进关闭列表
Point point = FindMinFOfPoint(openList);
openList.Remove(point);
//得到该点的周围的点，并将关闭列表里最小F值的点从中移除
List<Point> surroundPoints = GetSurroundPoints(point);
PointsFilter(surroundPoints, closeList);
//遍历周围能走的点列表，第一次循环结束后，开启列表里最小F值的点为所以周围的点的父点，并且周围的点都添加进了开启列表
foreach (Point surroundPoint in surroundPoints)
{
//如果周围的点在开启列表里，计算当前遍历到的周围的点的G值
if (openList.IndexOf(surroundPoint) > -1)
{
float nowG = CalcG(surroundPoint, point);
if (nowG < surroundPoint.G)
{
surroundPoint.UpdateParent(point, nowG);
}
}
//不在开启列表里，将当前点设为周围能走的点的父点，计算周围点的F、H、G值，将其添加进开启列表
else
{
surroundPoint.ParentPoint = point;
CalcF(surroundPoint, end);
}
}

//如果开启列表为空，跳出循环
if (openList.IndexOf(end) > -1)
{
break;
}
}
}
//得到周围点方法
private List<Point> GetSurroundPoints(Point point)
{
//默认点有四个方向，上下左右四个点，由地图大小判断四个点是否存在
Point up = null, down = null, left = null, right = null;
//Point lu = null, ru = null, ld = null, rd = null;
if (point.Z < mapHeight - 1)
{
up = map[point.X, point.Z + 1];
}
if (point.Z > 0)
{
down = map[point.X, point.Z - 1];
}
if (point.X > 0)
{
left = map[point.X - 1, point.Z];
}
if (point.X < mapWith - 1)
{
right = map[point.X + 1, point.Z];
}
//判断上下左右点是否为障碍物点，返回存储能走的点的list
List<Point> list = new List<Point>();
if (down != null && down.IsObstacle == false)
{
}
if (up != null && up.IsObstacle == false)
{
}
if (left != null && left.IsObstacle == false)
{
}
if (right != null && right.IsObstacle == false)
{
}
return list;
}
//在开启列表里寻找最小F值的点，并返回该点
private Point FindMinFOfPoint(List<Point> openList)
{
//初始化f值为最大值，遍历开启列表，判断开启列表里F值最小的点，即为最合适的点
float f = float.MaxValue;
Point temp = null;
foreach (Point p in openList)
{
if (p.F < f)
{
temp = p;
f = p.F;
}
}
return temp;
}
//返回由父点计算得到的当前点的G值
private float CalcG(Point now, Point parent)
{
return Vector2.Distance(new Vector2(now.X, now.Z), new Vector2(parent.X, parent.Z))+parent.G;
}
//计算F值，传入当前点和结束点
private void CalcF(Point now,Point end)
{
//得到当前点和结束点的x、z两坐标值之差的绝对值之和为h值，g初始化为0
float h = Mathf.Abs(end.X-now.X) + Mathf.Abs(end.Z-now.Z);
float g = 0;
//如果当前点没有父点，说明为起始点，g值为0
if (now.ParentPoint == null)
g = 0;
//如果有父点，则计算当前点到父点的距离加上父点的g值就为当前点的g值
else
g = Vector2.Distance(new Vector2(now.X, now.Z), new Vector2(now.ParentPoint.X, now.ParentPoint.Z))+ now.ParentPoint.G;
float f = g + h;
now.F = f;
now.G = g;
now.H = h;
}
}
``````

unity3d自动寻路算法 相关内容

2018-01-19 20:45:13 Htlas 阅读数 1965
• ###### 深入浅出Unity3D——第一篇

Unity3D基础知识、游戏算法一网打尽。

74787 人正在学习 去看看 何韬

A*算法呢，*是什么呢，以一个网格为中心点，他周围八个方向的网格就是*，

• A寻路算法的估量代价*
在A*算法中核心的寻路依据就是估量代价，在A*中通常用 F 表示。F = G + H
其中G表示当前点到起始点的估量代价，H表示当前点到终点的代价。

（起始点周围的八个点）

(网图，其中一些估量代价是错的，仅供参考，侵删)

A*算法的核心是两个集合分别为开放列表与关闭列表：Open List，CloseList

``````从中心位置对相邻格子

OpenList      CloseList
A
A1
...
A6
A7

OpenList      CloseList
A4	     A
A1
...
A6
A7
A41
A42
...
A48

OpenList      CloseList
A42	      A
A1  	      A4
...
A6
A7
A41
...
A48
...........................
OpenList      CloseList
A4234	     A
A1  	     A4
...          A42
A6           A423
A7           A4234
A41
...
A48

A4->A4234就是A*算法得到的最短路径``````

1.把起始格添加到开启列表。
2.重复如下的工作：
a) 寻找开启列表中估量代价F值最低的格子。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的8格中的每一个进行如下操作
* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。
* 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
d) 停止，当你
* 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者
* 没有找到目标格，开启列表已经空了。这时候，路径不存在。
3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。

1.AStarController

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

public class AStarController : MonoBehaviour {

//起点坐标
public int startPosX, startPosY;
//终点坐标
public int endPosX, endPosY;
//障碍物比率
public int obstacleRate;

private GameObject gridPrefab;

private List<Grid> openList;
private List<Grid> closeList;
//结果栈
private Stack<Grid> result;

//所有格子数组
private Grid[,] allGrids = null;

void Awake()
{
result = new Stack<Grid> ();
openList = new List<Grid> ();
closeList = new List<Grid> ();
//设置数组长度
allGrids = new Grid[(int)(transform.localScale.x
* 20),(int)(transform.localScale.z * 20)];
}

void Start()
{
//遍历生成格子
for (int i = 0; i < transform.localScale.x * 20; i++) {
for (int j = 0; j < transform.localScale.z * 20; j++) {
//生成
Grid currentGrid = Instantiate (gridPrefab).
GetComponent<Grid>();
//计算偏移量
Vector2 offset = new Vector2 (-4.7f * transform.
localScale.x,-4.7f * transform.localScale.z);
//设置方块的世界坐标
currentGrid.transform.position = new Vector3 (
offset.x + i * 0.5f, 0, offset.y + j * 0.5f);
//设置格子坐标
currentGrid.x = i;
currentGrid.y = j;
//存储起来
allGrids[i,j] = currentGrid;
//随机障碍物
int r = Random.Range(1,101);
if (r <= obstacleRate) {
currentGrid.MyGridType = GridType.Obstacle;
}
}
}
//设置起点和终点
allGrids[startPosX,startPosY].MyGridType = GridType.Start;
allGrids [endPosX, endPosY].MyGridType = GridType.End;

//调用AStar计算
AStarCount();
}
/// <summary>
/// A*计算
/// </summary>
void AStarCount()
{
//将起点放置到OpenList
//获取当前要发现的中心格子
Grid currentGrid = openList[0];
//循环递归
//开启列表中有对象&&当前的中心不是终点
while (openList.Count > 0 &&
currentGrid.MyGridType != GridType.End) {
//重新排序
openList.Sort();
//获取新的中心格子
currentGrid = openList[0];
//判断最新的格子是否是终点
if (currentGrid.MyGridType == GridType.End) {
///TODO:生成结果
GetParent(currentGrid);
return;
}
//上下左右，左上右上左下右下
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i != 0 || j != 0) {
//获取新格子的格子坐标
int x = currentGrid.x + i;
int y = currentGrid.y + j;
//判断格子坐标合法
//前四个条件判断坐标的合法性
//新格子不能是障碍物
//新格子没有被遍历过
if (x > 0 && y > 0 && x < allGrids.GetLength (0)
&& y < allGrids.GetLength (1) &&
allGrids [x, y].MyGridType != GridType.Obstacle &&
!closeList.Contains (allGrids [x, y])) {
//计算G值
int g = (int)(currentGrid.G +
Mathf.Sqrt(Mathf.Abs(i) + Mathf.Abs(j))*10);
//判断新格子是否被遍历过
//如果被遍历过，判断当前G值是否比之前的更小
if (allGrids [x, y].G == 0 || g < allGrids [x, y].G) {
//更新G值
allGrids[x,y].G = g;
//更新父格子
allGrids[x,y].parent = currentGrid;
}
//计算H
allGrids[x,y].H = (Mathf.Abs(x - endPosX) + Mathf.Abs(y- endPosY)) * 10;
//计算F
allGrids[x,y].F = allGrids[x,y].G + allGrids[x,y].H;
//加入到开启列表
if (!openList.Contains (allGrids [x, y])) {
Debug.Log (1);
}
}
}
}
}
//将当前格子移除OpenList
openList.Remove(currentGrid);
//放到CloseList里
//OpenList空了
if (openList.Count == 0) {
Debug.Log ("Can Not Arrave！！！");
}
}
}

private void GetParent(Grid current)
{
//进栈
result.Push (current);
//判断是否继续递归
if (current.parent != null) {
GetParent (current.parent);
} else {
//展示结果
StartCoroutine (ShowResult ());
}
}

IEnumerator ShowResult()
{
//获取总长度
int resultCount = result.Count;
while (result.Count > 0) {
yield return new WaitForSeconds(0.1f);
//出栈
Grid currentResultGrid = result.Pop();
//计算比例
float scale = (resultCount - result.Count)/(float)resultCount;
//上色
Color currentC = Color.Lerp(Color.red,Color.green,scale);
currentResultGrid.SetColor(currentC);
}
}

void Update()
{
if (Input.GetKeyDown (KeyCode.Space)) {
}
}
}``````

2.GridController

``````using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;
public enum GridType {
//正常类型
Normal,
//障碍物类型
Obstacle,
//起点类型
Start,
//终点类型
End
}

public class GridController : MonoBehaviour,IComparable {
//坐标
public int x ,y;
//FGH
public int F, G, H;
//坐标
public GridController parent;
//格子类型
private GridType gridType;
public GridType myGridType {
get {
return gridType;
}
set {
gridType = value;
//设置显示颜色
Color tempColor = Color.white;
switch (gridType) {
case GridType.Start:
tempColor = Color.red;
break;
case GridType.End:
tempColor = Color.green;
break;
case GridType.Obstacle:
tempColor = Color.blue;
break;
default:
break;
}
SetColor(tempColor);
}

}

private MeshRenderer meshRenderer;

private void Awake() {
meshRenderer = GetComponent<MeshRenderer>();
}

public void SetColor(Color c) {
meshRenderer.material.color = c;
}

public int CompareTo(object obj) {
GridController target = obj as GridController;
if (F < target.F) {
return -1;
}else if (F > target.F) {
return 1;
}else {
return 0;
}
}
}
``````

unity3d自动寻路算法 相关内容

2013-12-27 23:54:35 aisajiajiao 阅读数 15437
• ###### 深入浅出Unity3D——第一篇

Unity3D基础知识、游戏算法一网打尽。

74787 人正在学习 去看看 何韬

#### A*算法复习

1. 首先,从开始节点开始,将开始节点放入开放列表中.
2. 只要开放列表中有节点,我们将进行一下过程.
3. 从开放列表中选择第一个节点并将其作为当前节点(我们将在代码结束时提到它,这假定我们已经对开放列表排好序且第一个节点有最小代价值).
4. 获得这个当前节点的邻近节点,它们不是障碍物,像一堵墙或者不能穿越的峡谷一样.
5. 对于每一个邻近节点,检查该邻近节点是否已在关闭列表中.如果不在,我们将为这个邻近节点计算所有代价值(F),计算时使用下面公式:F = G + H,在前面的式子中,G是从上一个节点到这个节点的代价总和,H是从当前节点到目的节点的代价总和.
6. 将代价数据存储在邻近节点中,并且将当前节点保存为该邻近节点的父节点.之后我们将使用这个父节点数据来追踪实际路径.
7. 将邻近节点存储在开放列表中.根据到他目标节点的代价总和,以升序排列开放列表.
8. 如果没有邻近节点需要处理,将当前节点放入关闭列表并将其从开放列表中移除.
9. 返回第二步

#### Node

Node类将处理代表我们地图的2D格子中其中的每个格子对象,一下是Node.cs文件.
```using UnityEngine;
using System.Collections;
using System;

public class Node : IComparable {
public float nodeTotalCost;
public float estimatedCost;
public bool bObstacle;
public Node parent;
public Vector3 position;

public Node() {
this.estimatedCost = 0.0f;
this.nodeTotalCost = 1.0f;
this.bObstacle = false;
this.parent = null;
}

public Node(Vector3 pos) {
this.estimatedCost = 0.0f;
this.nodeTotalCost = 1.0f;
this.bObstacle = false;
this.parent = null;
this.position = pos;
}

public void MarkAsObstacle() {
this.bObstacle = true;
}```
Node类有其属性,比如代价值(G和H),标识其是否是障碍物的标记,和其位置和父节点. nodeTotalCost是G,它是从开始节点到当前节点的代价值,estimatedCost是H,它是从当前节点到目标节点的估计值.我们也有两个简单的构造方法和一个包装方法来设置该节点是否为障碍物.之后我们实现如下面代码所示的CompareTo方法:
```	public int CompareTo(object obj)
{
Node node = (Node) obj;
//Negative value means object comes before this in the sort order.
if (this.estimatedCost < node.estimatedCost)
return -1;
//Positive value means object comes after this in the sort order.
if (this.estimatedCost > node.estimatedCost)
return 1;
return 0;
}
}```

#### PriorityQueue

PriorityQueue是一个简短的类,使得ArrayList处理节点变得容易些,PriorityQueue.cs展示如下:
```using UnityEngine;
using System.Collections;
public class PriorityQueue {
private ArrayList nodes = new ArrayList();

public int Length {
get { return this.nodes.Count; }
}

public bool Contains(object node) {
return this.nodes.Contains(node);
}

public Node First() {
if (this.nodes.Count > 0) {
return (Node)this.nodes[0];
}
return null;
}

public void Push(Node node) {
this.nodes.Sort();
}

public void Remove(Node node) {
this.nodes.Remove(node);
//Ensure the list is sorted
this.nodes.Sort();
}
}```

#### GridManager

GridManager类处理所有代表地图的格子的属性.我们将GridManager设置单例,因为我们只需要一个对象来表示地图.GridManager.cs代码如下:
```using UnityEngine;
using System.Collections;
public class GridManager : MonoBehaviour {
private static GridManager s_Instance = null;
public static GridManager instance {
get {
if (s_Instance == null) {
s_Instance = FindObjectOfType(typeof(GridManager))
as GridManager;
if (s_Instance == null)
Debug.Log("Could not locate a GridManager " +
"object. \n You have to have exactly " +
"one GridManager in the scene.");
}
return s_Instance;
}
}```

```public int numOfRows;
public int numOfColumns;
public float gridCellSize;
public bool showGrid = true;
public bool showObstacleBlocks = true;
private Vector3 origin = new Vector3();
private GameObject[] obstacleList;
public Node[,] nodes { get; set; }
public Vector3 Origin {
get { return origin; }
}```

```	void Awake() {
obstacleList = GameObject.FindGameObjectsWithTag("Obstacle");
CalculateObstacles();
}
// Find all the obstacles on the map
void CalculateObstacles() {
nodes = new Node[numOfColumns, numOfRows];
int index = 0;
for (int i = 0; i < numOfColumns; i++) {
for (int j = 0; j < numOfRows; j++) {
Vector3 cellPos = GetGridCellCenter(index);
Node node = new Node(cellPos);
nodes[i, j] = node;
index++;
}
}
if (obstacleList != null && obstacleList.Length > 0) {
//For each obstacle found on the map, record it in our list
foreach (GameObject data in obstacleList) {
int indexCell = GetGridIndex(data.transform.position);
int col = GetColumn(indexCell);
int row = GetRow(indexCell);
nodes[row, col].MarkAsObstacle();
}
}
}```

GridManager有一些辅助方法来遍历格子并得到对应格子的对局.以下是其中一些函数(附有简短说明以阐述它们的是做什么的).实现很简单,所以我们不会过多探究其细节.
GetGridCellCenter方法从格子索引中返回世界坐标系中的格子位置,代码如下:
```	public Vector3 GetGridCellCenter(int index) {
Vector3 cellPosition = GetGridCellPosition(index);
cellPosition.x += (gridCellSize / 2.0f);
cellPosition.z += (gridCellSize / 2.0f);
return cellPosition;
}
public Vector3 GetGridCellPosition(int index) {
int row = GetRow(index);
int col = GetColumn(index);
float xPosInGrid = col * gridCellSize;
float zPosInGrid = row * gridCellSize;
return Origin + new Vector3(xPosInGrid, 0.0f, zPosInGrid);
}```
GetGridIndex方法从给定位置返回格子中的格子索引:
```	public int GetGridIndex(Vector3 pos) {
if (!IsInBounds(pos)) {
return -1;
}
pos -= Origin;
int col = (int)(pos.x / gridCellSize);
int row = (int)(pos.z / gridCellSize);
return (row * numOfColumns + col);
}
public bool IsInBounds(Vector3 pos) {
float width = numOfColumns * gridCellSize;
float height = numOfRows* gridCellSize;
return (pos.x >= Origin.x &&  pos.x <= Origin.x + width &&
pos.x <= Origin.z + height && pos.z >= Origin.z);
}```
GetRow和GetColumn方法分别从给定索引返回格子的行数和列数.
```	public int GetRow(int index) {
int row = index / numOfColumns;
return row;
}
public int GetColumn(int index) {
int col = index % numOfColumns;
return col;
}```

```public void GetNeighbours(Node node, ArrayList neighbors) {
Vector3 neighborPos = node.position;
int neighborIndex = GetGridIndex(neighborPos);
int row = GetRow(neighborIndex);
int column = GetColumn(neighborIndex);
//Bottom
int leftNodeRow = row - 1;
int leftNodeColumn = column;
AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
//Top
leftNodeRow = row + 1;
leftNodeColumn = column;
AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
//Right
leftNodeRow = row;
leftNodeColumn = column + 1;
AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
//Left
leftNodeRow = row;
leftNodeColumn = column - 1;
AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
}

void AssignNeighbour(int row, int column, ArrayList neighbors) {
if (row != -1 && column != -1 &&
row < numOfRows && column < numOfColumns) {
}
}
}```

```void OnDrawGizmos() {
if (showGrid) {
DebugDrawGrid(transform.position, numOfRows, numOfColumns,
gridCellSize, Color.blue);
}
Gizmos.DrawSphere(transform.position, 0.5f);
if (showObstacleBlocks) {
Vector3 cellSize = new Vector3(gridCellSize, 1.0f,
gridCellSize);
if (obstacleList != null && obstacleList.Length > 0) {
foreach (GameObject data in obstacleList) {
Gizmos.DrawCube(GetGridCellCenter(
GetGridIndex(data.transform.position)), cellSize);
}
}
}
}
public void DebugDrawGrid(Vector3 origin, int numRows, int
numCols,float cellSize, Color color) {
float width = (numCols * cellSize);
float height = (numRows * cellSize);
// Draw the horizontal grid lines
for (int i = 0; i < numRows + 1; i++) {
Vector3 startPos = origin + i * cellSize * new Vector3(0.0f,
0.0f, 1.0f);
Vector3 endPos = startPos + width * new Vector3(1.0f, 0.0f,
0.0f);
Debug.DrawLine(startPos, endPos, color);
}
// Draw the vertial grid lines
for (int i = 0; i < numCols + 1; i++) {
Vector3 startPos = origin + i * cellSize * new Vector3(1.0f,
0.0f, 0.0f);
Vector3 endPos = startPos + height * new Vector3(0.0f, 0.0f,
1.0f);
Debug.DrawLine(startPos, endPos, color);
}
}
}```
Gizmos在编辑器场景视图中可以用于绘制可视化的调试并建立辅助.OnDrawGizmos在每一帧都会被引擎调用.所以,如果调试标识showGrid和showObstacleBlocks被勾选我们就是用线条绘制格子使用立方体绘制障碍物.我们就不讲DebugDrawGrid这个简单的方法了.

#### AStar

```using UnityEngine;
using System.Collections;
public class AStar {
public static PriorityQueue closedList, openList;```

```	private static float HeuristicEstimateCost(Node curNode,
Node goalNode) {
Vector3 vecCost = curNode.position - goalNode.position;
return vecCost.magnitude;
}```

```	public static ArrayList FindPath(Node start, Node goal) {
openList = new PriorityQueue();
openList.Push(start);
start.nodeTotalCost = 0.0f;
start.estimatedCost = HeuristicEstimateCost(start, goal);
closedList = new PriorityQueue();
Node node = null;```

```		while (openList.Length != 0) {
node = openList.First();
//Check if the current node is the goal node
if (node.position == goal.position) {
return CalculatePath(node);
}
//Create an ArrayList to store the neighboring nodes
ArrayList neighbours = new ArrayList();
GridManager.instance.GetNeighbours(node, neighbours);
for (int i = 0; i < neighbours.Count; i++) {
Node neighbourNode = (Node)neighbours[i];
if (!closedList.Contains(neighbourNode)) {
float cost = HeuristicEstimateCost(node,
neighbourNode);
float totalCost = node.nodeTotalCost + cost;
float neighbourNodeEstCost = HeuristicEstimateCost(
neighbourNode, goal);
neighbourNode.nodeTotalCost = totalCost;
neighbourNode.parent = node;
neighbourNode.estimatedCost = totalCost +
neighbourNodeEstCost;
if (!openList.Contains(neighbourNode)) {
openList.Push(neighbourNode);
}
}
}
//Push the current node to the closed list
closedList.Push(node);
//and remove it from openList
openList.Remove(node);
}
if (node.position != goal.position) {
return null;
}
return CalculatePath(node);
}```

1. 获得openList的第一个节点.记住每当新节点加入时openList都需要再次排序.所以第一个节点总是有到目的节点最低估计代价值.
2. 检查当前节点是否是目的节点,如果是推出while循环创建path数组.
3. 创建数组列表保存当前正被处理的节点的临近节点.使用GetNeighbours方法来从格子中检索邻接节点.
4. 对于每一个在邻接节点数组中的节点,我们检查它是否已在closedList中.如果不在,计算代价值并使用新的代价值更新节点的属性值,更新节点的父节点并将其放入openList中.
5. 将当前节点压入closedList中并将其从openList中移除.返回第一步.

```	private static ArrayList CalculatePath(Node node) {
ArrayList list = new ArrayList();
while (node != null) {
node = node.parent;
}
list.Reverse();
return list;
}
}```
CalculatePath方法跟踪每个节点的父节点对象并创建数组列表.他返回一个从目的节点到开始节点的ArrayList.由于我们需要从开始节点到目标节点的路径,我们简单调用一下Reverse方法就ok.

#### TestCode Class

```using UnityEngine;
using System.Collections;
public class TestCode : MonoBehaviour {
private Transform startPos, endPos;
public Node startNode { get; set; }
public Node goalNode { get; set; }
public ArrayList pathArray;
GameObject objStartCube, objEndCube;
private float elapsedTime = 0.0f;
//Interval time between pathfinding
public float intervalTime = 1.0f;```

```	void Start () {
objStartCube = GameObject.FindGameObjectWithTag("Start");
objEndCube = GameObject.FindGameObjectWithTag("End");
pathArray = new ArrayList();
FindPath();
}
void Update () {
elapsedTime += Time.deltaTime;
if (elapsedTime >= intervalTime) {
elapsedTime = 0.0f;
FindPath();
}
}```

```	void FindPath() {
startPos = objStartCube.transform;
endPos = objEndCube.transform;
startNode = new Node(GridManager.instance.GetGridCellCenter(
GridManager.instance.GetGridIndex(startPos.position)));
goalNode = new Node(GridManager.instance.GetGridCellCenter(
GridManager.instance.GetGridIndex(endPos.position)));
pathArray = AStar.FindPath(startNode, goalNode);
}```

```	void OnDrawGizmos() {
if (pathArray == null)
return;
if (pathArray.Count > 0) {
int index = 1;
foreach (Node node in pathArray) {
if (index < pathArray.Count) {
Node nextNode = (Node)pathArray[index];
Debug.DrawLine(node.position, nextNode.position,
Color.green);
index++;
}
}
}
}
}```

#### Scene setup

Sample test scene

Scene hierarchy

Obstacle nodes

Start node

End node

GridManager script

### 总结

unity3d自动寻路算法 相关内容