2013-02-25 11:07:30 fzhlee 阅读数 4146

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

View the online demo

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

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
                add neighbor to openList
         }
         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()) {
					// not a valid node to process, skip to next neighbor
					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()) {
                    // Not a valid node to process, skip to next neighbor.
                    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


2015-05-07 17:38:27 a3636987 阅读数 4921

学了一段时间的寻路,在网上也学了挺多算法,今天整理了一下,使用到Unity的3D界面中用于寻路,首先是简单的寻路算法,以下是地图:


地图数组:

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))
        {
            // 存储路径点
            path.Add(new Vector3(startX, startY, 0));
            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之迷宫寻路_A*最短路径寻路》

2018-05-26 10:32:26 u012187817 阅读数 405

初步了解了一些寻路算法后,本以为dijstra是比较合适的寻路算法,今天仔细看了关于A星寻路算法的教程和视频后,我认为A星寻路算法很适合战棋游戏。由于我的项目是仿照小小合金的玩法,所以是只需要上下左右寻路的正方形格子地图。

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;
        pointList.Add(temp);
        while (true)
        {
            if (temp.ParentPoint == null)
                break;
            temp = temp.ParentPoint;
            step++;
            pointList.Add(temp);
        }
        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>();
        openList.Add(start);
        //如果开启列表数量不为0
        while (openList.Count > 0)
        {
            //找到开启列表里最小F值的点,将该点移除开启列表,添加进关闭列表
            Point point = FindMinFOfPoint(openList);
            openList.Remove(point);
            closeList.Add(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);
                    openList.Add(surroundPoint);
                }
            }
            
            //如果开启列表为空,跳出循环
            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)
        {
            list.Add(down);
        }
        if (up != null && up.IsObstacle == false)
        {
            list.Add(up);
        }
        if (left != null && left.IsObstacle == false)
        {
            list.Add(left);
        }
        if (right != null && right.IsObstacle == false)
        {
            list.Add(right);
        }
        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;
    }
}

 

 

 

2018-01-19 20:45:13 Htlas 阅读数 1965

非常简陋的版本的GIF图,放在开头。

前言:

再Unity中寻路导航是游戏开发的最基本的需求之一

什么是A*寻路算法:

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

 

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

(起始点周围的八个点)

每个点里面的三个数字分别为:1.左下角是距离起始点的估量代价,记为G。A距离中心点的距离为1的直线距离,B距离中心点的距离为根号2,约1.4,在这里基础单位为10的话,A的起始点估量代价G=10,B的起始点估量代价G=14 。 2.右下角是距离终点的估量代价,记为H,为该点到终点的步数既几步可达终点。3.左上角是综合估量代价,记为F=G+H,起始点估量代价与终点估量代价的和;

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

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

原理:

从中心位置对相邻格子

假设A是起始格子
    OpenList      CloseList
	A
	A1
    ...
	A6
	A7

从中心位置对相邻8个格子进行判断最小代价,将A移除并添加进CloseList中,并对OpenList进行排序
假设最小代价是是A4,将A4放在OpenList表头,并查找A4周围的8个格子,A41-A48
    OpenList      CloseList
	A4	     A
	A1
	...
	A6
	A7
	A41
	A42
	...
	A48
将A4从Open中移除并添加到CloseList中,
对OpenList进行排序,假设A42的最小代价最小
将A42放在Open的表头,并查询A42相邻8个格子
    OpenList      CloseList
	A42	      A
	A1  	      A4
	...
	A6
	A7
	A41
	...
	A48
...........................
    OpenList      CloseList
	A4234	     A
	A1  	     A4
	...          A42
	A6           A423
	A7           A4234
	A41
	...
	A48
最后可能得到的CloseList如上所示,
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()
	{
		gridPrefab = Resources.Load<GameObject> ("Grid");
		//遍历生成格子
		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
		openList.Add (allGrids [startPosX, startPosY]);
		//获取当前要发现的中心格子
		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.Add (allGrids [x, y]);
							}
						}
					}
				}
			}
			//将当前格子移除OpenList
			openList.Remove(currentGrid);
			//放到CloseList里
			closeList.Add(currentGrid);
			//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)) {
			UnityEngine.SceneManagement.SceneManager.LoadScene (0);
		}
	}
}

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;
        }
    }
}

 

2013-12-27 23:54:35 aisajiajiao 阅读数 15437

这篇文章翻译自Unity 4.x Game AI Programming这本书第七章

在本章中,我们将在Unity3D环境中使用C#实现A*算法.尽管有很多其他算法,像Dijkstra算法,但A*算法以其简单性和有效性而广泛的应用于游戏和交互式应用中.我们之前在第一章AI介绍中短暂的涉及到了该算法.不过现在我们从实现的角度来再次复习该算法.

A*算法复习

在我们进入下一部分实现A*之前,我们再次复习一下A*算法.首先,我们将需要用可遍历的数据结构来表示地图.尽管可能有很多结构可实现,在这个例子中我们将使用2D格子数组.我们稍后将实现GridManager类来处理这个地图信息.我们的类GridManager将记录一系列的Node对象,这些Node对象才是2D格子的主题.所以我们需要实现Node类来处理一些东西,比如节点类型,他是是一个可通行的节点还是障碍物,穿过节点的代价和到达目标节点的代价等等.

我们将用两个变量来存储已经处理过的节点和我们要处理的节点.我们分别称他们为关闭列表和开放列表.我们将在PriorityQueue类里面实现该列表类型.我们现在看看它:

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

这就是我们将在Unity3D中使用C#实现的算法概览.所以,搞起吧.

实现

我们将实现我们之前提到过的基础类比如Node类,GridManager类和PriorityQueue类.我们将在后续的主AStar类里面使用它们.

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;
	}
}
这个方法很重要.我们的Node类继承自ICompare因为我们想要重写这个CompareTo方法.如果你能想起我们在之前算法部分讨论的东西,你会注意到我们需要根据所有预估代价值来排序我们的Node数组.ArrayList类型有个叫Sort.Sort的方法,该方法只是从列表中的对象(在本例中是Node对象)查找对象内部实现的CompareTo方法.所以,我们实现这个方法并根据estimatedCost值来排序Node对象.你可以从以下资源中了解到更多关于.Net framework的该特色.

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.Add(node);
		this.nodes.Sort();
	}
	
	public void Remove(Node node) {
		this.nodes.Remove(node);
		//Ensure the list is sorted
		this.nodes.Sort();
	}
}
上面的代码很好理解.需要注意的一点是从节点的ArrayList添加或者删除节点后我们调用了Sort方法.这将调用Node对象的CompareTo方法,且将使用estimatedCost值来排序节点.

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;
		}
	}
我们在场景中寻找GridManager对象,如果找到我们将其保存在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; }
}
紧接着我们声明所有的变量;我们需要表示我们的地图,像地图行数和列数,每个格子的大小,以及一些布尔值来形象化(visualize)格子与障碍物.此外还要向下面的代码一样保存格子上存在的节点:
	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();
			}
		}
	}
我们查找所有标签为Obstacle的游戏对象(game objects)并将其保存在我们的obstacleList属性中.之后在CalculateObstacles方法中设置我们节点的2D数组.首先,我们创建具有默认属性的普通节点属性.在这之后我们查看obstacleList.将其位置转换成行,列数据(即节点是第几行第几列)并更新对应索引处的节点为障碍物.

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;
	}
另外一个重要的方法是GetNeighbours,它被AStar类用于检索特定节点的邻接点.
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) {
	  Node nodeToAdd = nodes[row, column];
	  if (!nodeToAdd.bObstacle) {
		neighbors.Add(nodeToAdd);
	  }
	}
  }
首先,我们在当前节点的左右上下四个方向检索其邻接节点.之后,在AssignNeighbour方法中,我们检查邻接节点看其是否为障碍物.如果不是我们将其添加neighbours中.紧接着的方法是一个调试辅助方法用于形象化(visualize)格子和障碍物.
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这个简单的方法了.
注意:你可以从Unity3D参考文档了解到更多有关gizmos的资料

AStar

类AStar是将要使用我们目前所实现的类的主类.如果你想复习这的话,你可以返回算法部分.如下面AStar.cs代码所示,我们先声明我们的openList和closedList,它们都是PriorityQueue类型.

using UnityEngine;
using System.Collections;
public class AStar {
	public static PriorityQueue closedList, openList;
接下来我们实现一个叫HeursticEstimatedCost方法来计算两个节点之间的代价值.计算很简单.我们只是通过两个节点的位置向量相减得到方向向量.结果向量的长度便告知了我们从当前节点到目标节点的直线距离.

	private static float HeuristicEstimateCost(Node curNode, 
			Node goalNode) {
		Vector3 vecCost = curNode.position - goalNode.position;
		return vecCost.magnitude;
	}
接下来使我们主要的FindPath方法:

	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) {
			Debug.LogError("Goal Not Found");
			return null;
		}
		return CalculatePath(node);
	}
这代码实现类似于我们之前讨论过的算法,所以如果你对特定的东西不清楚的话可以返回去看看.

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

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

这就是我们的AStar类.我们将在下面的代码里写一个测试脚本来检验所有的这些东西.之后创建一个场景并在其中使用它们.

TestCode Class

代码如TestCode.cs所示,该类使用AStar类找到从开始节点到目的节点的路径.

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;
首先我们创建我们需要引用的变量.pathArray用于保存从AStar的FindPath方法返回的节点数组.

	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();
		}
	}
在Start方法中我们寻找标签(tags)为Start和End的对象并初始化pathArray.如果开始和结束的节点位置变了我们将尝试在每一个我们所设置的intervalTime属性时间间隔里找到我们的新路径.之后我们调用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);
	}
因为我们在AStar类中实现了寻路算法,寻路现在变得简单多了.首先,我们获得开始和结束的游戏对象(game objects).之后,我们使用GridManager的辅助方法创建新的Node对象,使用GetGridIndex来计算它们在格子中对应的行列位置.一旦我们将开始节点和目标节点作为参数调用了AStar.FindPath方法并将返回的数组保存在pathArray属性中.接下我们实现OnDrawGizmos方法来绘制并形象化(draw and visualize)我们找到的路径.

	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++;
				}
			}
		}
	}
}
我们检查了我们的pathArray并使用Debug.DrawLine方法来绘制线条连接起pathArray中的节点.当运行并测试程序时我们就能看到一条绿线从开始节点连接到目标节点,连线形成了一条路径.

Scene setup

我们将要创建一个类似于下面截图所展示的场景:


Sample test scene

我们将有一个平行光,开始以及结束游戏对象,一些障碍物,一个被用作地面的平面实体和两个空的游戏对象,空对象身上放置GridManager和TestAstar脚本.这是我们的场景层级图.


Scene hierarchy

创建一些立方体实体并给他们加上标签Obstacle,当运行我们的寻路算法时我们需要寻找带有该标签的对象.


Obstacle nodes

创建一个立方体实体并加上标签Start


Start node

创建另一个立方体实体并加上标签End


End node

现在创建一个空的游戏对象并将GridManager脚本赋给它.将其名字也设置回GridManager因为在我们的脚本中使用该名称寻找GridManager对象.这里我们可以设置格子的行数和列数和每个格子的大小.


GridManager script

Testing

我们点击Play按钮实打实的看下我们的A*算法.默认情况下,一旦你播放当前场景Unity3D将会切换到Game视图.由于我们的寻路形象化(visualization)代码是为我编辑器视图中的调试绘制而写,你需要切换回Scene视图或者勾选Gizmos来查看找到的路径.


现在在场景中尝试使用编辑器的移动工具移动开始和结束节点.(不是在Game视图中,而是在Scene视图中)


如果从开始节点到目的节点有合法路径,你应该看到路径会对应更新并且是动态实时的更新.如果没有路径,你会在控制窗口中得到一条错误信息.

总结

在本章中,我们学习了如何在Unity3D环境中实现A*寻路算法.我们实现了自己的A*寻路类以及我们自己的格子类,队列类和节点类.我们学习了IComparable接口并重写了CompareTo方法.我们使用调试绘制功能(debug draw functionalities)来呈现我们的网格和路径信息.有了Unity3D的navmesh和navagent功能你可能不必自己实现寻路算法.不管怎么样,他帮助你理解实现背后的基础算法.

在下一章中,我们将查看如何扩展藏在A*背后的思想看看导航网格(navigation meshes).使用导航网格,在崎岖的地形上寻路将变得容易得多.

Unity3D A* 寻路算法

阅读数 2148

没有更多推荐了,返回首页