unity3d自动寻路算法

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

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


2019-09-17 20:23:13 weixin_44292962 阅读数 242

A*寻路算法(分队自动寻路)


参考:https://www.cnblogs.com/wangweixznu/p/5442164.html

简单描述

在上一次上机的基础下继续进行学习。

操作过程

  1. 建立一个简单的场景,里面包括3条路(用红蓝绿区分)。
    在这里插入图片描述

  2. 设置NavMeshLayer,需要设置Red、Blue和Green三个层。
    在这里插入图片描述在这里插入图片描述

  3. 相应颜色的路, 在Navigation Layer里面选择相应颜色层。

  4. 设置多个不同颜色的AI。
    在这里插入图片描述

  5. 选择蓝色AI,然后找到NavMesh Agent组件里面的NavMesh Walkable选项,这里就是人物能通过的层的选择了。按照刚才层的设计,蓝色的小兵需要勾选Blue层 ,把Red层和Green层取消选择。
    在这里插入图片描述
    其他颜色的AI操作类似。

  6. 检查结果
    在这里插入图片描述

2019-03-08 16:56:52 qq_44238513 阅读数 1227

NavMesh(导航网格)是3D游戏世界中用于实现动态物体自动寻路的一种技术,将游戏中复杂的结构组织关系简化为带有一定信息的网格,在这些网格的基础上通过一系列的计算来实现自动寻路。。导航时,只需要给导航物体挂载导航组建,导航物体便会自行根据目标点来寻找最直接的路线,并沿着该线路到达目标点。

建造一个简单的场景

在这里插入图片描述

选中两个球之外所有的物体,然后在Inspector——Static——Navigation Static

在这里插入图片描述

选中要寻路的物体添加在导航栏选中Component——Navigation——Nav Mesh Agent组件

在这里插入图片描述

在导航栏打开Window——Navigation窗口

在这里插入图片描述

在Navigation窗口里面选择Bake然后再选择右下角的Bake

在这里插入图片描述

上面所有的设置好后上代码,把这个代码组件放到寻路的物体上

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

public class AI : MonoBehaviour {

    public GameObject target;
    private NavMeshAgent navMeshAgent;

	void Start ()
    {
        navMeshAgent = GetComponent<NavMeshAgent>();
        if(navMeshAgent==null)
        {
            navMeshAgent = gameObject.AddComponent<NavMeshAgent>();
        }
	}
	

	void Update ()
    {
            navMeshAgent.SetDestination(target.transform.position);
	}
}

然后把目标拖到代码组件的Target里面

在这里插入图片描述

运行就OK了

2018-03-05 16:43:04 chy_xfn 阅读数 3293

  最近两天刚好有空研究了下游戏中的自动寻路功能,收获颇丰,感觉用相应的算法去解决相应的问题真的非常重要啊!至少比自己想的流水账逻辑流程管用。看来以后得花多点时间研究下算法方面的知识了。
  游戏中的自动寻路,顾名思义就是找路,从地图找到从起点到终点的可行最短路径。既然是从地图找路,那么地图就应该是可数据化的,要不怎么找呢。
  所以自动寻路的有两个重点是分别是地图数据化和搜索算法。
  地图数据化,3D游戏地图有点复杂,还没研究,今天先看看2D游戏的。比如,搞一张九宫格式的地图,那么每个格子至少需要有这样的数据,格子的坐标、是路还是墙(根据具体情况格子还可以拓展其他属性)。然后有了这份数据化的地图后,寻路就变成了从一个格子移动到另一个格子的过程。
  搜索算法,深度优先搜索(DFS)和广度优先搜索(BFS)算法,通常我们说DFS用栈方式实现,BFS用队列方式实现,为什么呢,下面我们来看看。

  1. 队列:起点P,将邻接点A、B、C、D存入队列,标记P为已查找,然后A出队,得邻接点A1、A2、A3、A4, 队列变成B、C、D、A1、A2、A3、A4,继续B出队得新队列C、D、A1、A2、A3、A4、B1、B2、B3、B4…。
  2. 栈:起点P,将邻接点A、B、C、D存入栈,标记P为已查找,然后D出栈,得邻接点D1、D2、D3、D4, 栈变成B、C、D1、D2、D3、D4,继续D4出栈得新栈B、C、D1、D2、D3、d1、d2、d3、d4…。
    邻接点:不考虑斜角方向,有上下左右四个。

      粗糙理解讲下就是队列是从根节点开始,搜索所有子节点,然后搜索所有子节点的所有子节点;而栈是从根节点开始,搜索所有子节点,选择某个子节点搜索所有子节点,找不到则回溯父节点继续操作(参考二叉树辅助图理解)。其实从上面来看,无论是栈还是队列,对某个点都是只能访问一次的,访问后立即出栈或出队。如果没处理好,出现重复访问某个点的话,容易出现死循环。
      运用到游戏中,那么起点就是二叉树的根节点,终点就是某个子节点,自动寻路就是找到从根节点到子节点的一条连接线。根节点每连接一个子节点时就记录下长度,最后根据长度就可以求出最短路径了。

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

public class CPathFind : MonoBehaviour {
    // 自定义地图,1可行,0障碍
    private const int Row = 8, Col = 9;
    private int[,] MapDataArr = new int[Row, Col]
    {
        {1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 1, 0, 0, 1, 0, 1, 1, 1},
        {1, 1, 1, 1, 1, 0, 0, 1, 1},
        {1, 1, 1, 0, 1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1, 0, 1, 1, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 1, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1},
    };
    // 每个地图点数据化
    private class CMapPoint
    { 
        public int x;
        public int y;
        public int abstacle;
        public bool isFind = false;
        public int moveDis = 0;
        public CMapPoint fatherPoint;

        public CMapPoint(int x, int y, CMapPoint fp = null)
        {
            this.x = x;
            this.y = y;
            fatherPoint = fp;
        }
    }

    public GameObject wBlockPrefab;
    public GameObject bBlockPrefab;
    public GameObject playerPrefab;
    public GameObject blockGroupObj;

    private bool isMove = false;
    private int leastDis = 10000;
    private int findCount = 0;

    private CMapPoint endTargetPoint = new CMapPoint(0, 0);
    private CMapPoint moveTargetPoint = new CMapPoint(0, 0);
    private CMapPoint playerPoint = new CMapPoint(0, 0);

    private List<CMapPoint> MapPointList = new List<CMapPoint>();
    private List<CMapPoint> MovePointList = new List<CMapPoint>();

    private List<CMapPoint> OpenList = new List<CMapPoint>();
    private List<CMapPoint> CloseList = new List<CMapPoint>();

    void Start () {
        CreateMap();
    }

    void Update () {
        PlayerMove();
    }

    void OnDestroy()
    {
        for (int i = 0; i < blockGroupObj.transform.childCount; i++)
        {
            GameObject.Destroy(blockGroupObj.transform.GetChild(i).gameObject);
        }
    }

    void CreateMap()
    {
        for (int r = 0; r < MapDataArr.GetLength(0); r++)
        {
            for (int c = 0; c < MapDataArr.GetLength(1); c++)
            {
                CMapPoint mp = new CMapPoint(c, r) {
                    abstacle = MapDataArr[r, c]
                };
                MapPointList.Add(mp);

                GameObject blockPrefab = null;
                if (MapDataArr[r, c] == 1)
                    blockPrefab = wBlockPrefab;
                else
                    blockPrefab = bBlockPrefab;

                GameObject blockObj = GameObject.Instantiate(blockPrefab, Vector3.zero, Quaternion.identity) as GameObject;
                blockObj.name = r + "," + c;
                blockObj.transform.SetParent(blockGroupObj.transform);
                blockObj.transform.localScale = Vector3.one;
                // 左下角为原点
                blockObj.transform.localPosition = new Vector3(c * 60, r * 60, 0);
                blockObj.SetActive(true);
                blockObj.GetComponent<Button>().onClick.AddListener(delegate() { OnClickMapPoint(blockObj.name); });
            }
        }
    }

    void OnClickMapPoint(string name)
    {
        string[] nameArr = name.Split(',');
        int row = int.Parse(nameArr[0]);
        int col = int.Parse(nameArr[1]);
        Debug.Log("click point x=" +col + ", y=" + row);
        if (IsPass(col, row))
        {
            PathFinding(col, row);
        }
        else
        {
            Debug.Log("障碍点,无法通过!");
        }
    }

    void PlayerMove()
    {
        Vector3 targetPos = new Vector3(moveTargetPoint.x * 60, moveTargetPoint.y * 60, 0);
        float dValue = Vector3.Distance(playerPrefab.transform.localPosition, targetPos);
        if (dValue < 0.1)
        {
            playerPoint = new CMapPoint(moveTargetPoint.x, moveTargetPoint.y);
            GetNextMovePoint();
        }
        isMove = (dValue < 0.1) ? false : true;
        if (isMove)
        {
            playerPrefab.transform.localPosition = Vector3.MoveTowards(playerPrefab.transform.localPosition, targetPos, 2);
            Vector3 targetDir = (targetPos - playerPrefab.transform.localPosition).normalized;
            // 方向有变化,由Y轴指向目标方向
            if (targetDir != Vector3.zero)
            {
                playerPrefab.transform.up = targetDir;
            }
        }
    }

    void PathFinding(int x, int y)
    {
        leastDis = 10000;
        findCount = 0;
        endTargetPoint.x = x;
        endTargetPoint.y = y;
        endTargetPoint.fatherPoint = null;
        endTargetPoint.moveDis = 10000;
        MovePointList.Clear();

        //ShortestPathDFS();
        ShortestPathBFS();
    }

    void ShortestPathDFS()
    {
        // 传参数moveTargetPoint表示先移动完当前一格
        FindPathByDFS(moveTargetPoint, 0);
        GetLeastPath();
        Debug.Log("DFS Find Count: " + findCount);
    }

    // 使用深度优先搜索(利用堆栈)找出所有可能路线,求出最短路线
    void FindPathByDFS(CMapPoint curPoint, int dis)
    {
        int x = curPoint.x, y = curPoint.y;
        // (dis < leastDis)加这个条件可以优化计算量
        if (IsPass(x, y) && !GetIsFindStatus(curPoint) && dis < leastDis)
        {
            findCount += 1;
            //Debug.Log("find point x=" + x + ", y=" + y);
            if (x == endTargetPoint.x && y == endTargetPoint.y)
            {
                if (dis < leastDis)
                {
                    leastDis = dis;
                    endTargetPoint.fatherPoint = curPoint.fatherPoint;
                    //Debug.Log("end point x="+x + ", y="+y);
                }
                return;
            }
            // 记录已经查找过的点,避免重复查找导致堆栈溢出
            SetIsFindStatus(curPoint, true);
            // 利用递归方式搜索
            FindPathByDFS(new CMapPoint(x + 1, y, curPoint), dis + 1);
            FindPathByDFS(new CMapPoint(x - 1, y, curPoint), dis + 1);
            FindPathByDFS(new CMapPoint(x, y + 1, curPoint), dis + 1);
            FindPathByDFS(new CMapPoint(x, y - 1, curPoint), dis + 1);
            SetIsFindStatus(curPoint, false);
        }
    }

    // 根据终点倒序求出路线所有移动点
    void GetLeastPath()
    {
        CMapPoint mp = endTargetPoint;
        while (mp.fatherPoint != null)
        {
            MovePointList.Add(mp);
            mp = mp.fatherPoint;
        }
        MovePointList.Reverse();
    }

    //-------------------------------------------------------------//
    void ShortestPathBFS()
    {
        FindPathByBFS();
        GetLeastPath();
        Debug.Log("BFS Find Count: " + findCount);
    }

    // 使用广度优先搜索(利用队列),每次从队列取一个点出来,找出其可访问邻接点,直至找到终点
    void FindPathByBFS()
    {
        OpenList.Clear();
        CloseList.Clear();
        ClearMoveDisOfPoint();

        OpenList.Add(moveTargetPoint);
        CMapPoint mp = null;
        while(OpenList.Count > 0)
        {
            mp = OpenList[0];
            OpenList.RemoveAt(0);
            CloseList.Add(mp);
            FindAroundPoint(mp);
            mp = null;
        }
    }

    // 从访问点找出其可移动邻接点,记录从起点到该点的最短距离,存储该点到队列
    void FindAroundPoint(CMapPoint fatherPoint)
    {
        int x = fatherPoint.x, y = fatherPoint.y;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                int x1 = 0, y1 = 0;
                if (i == 0)
                {
                    x1 = x + (2 * j - 1);
                    y1 = y;
                }
                else
                {
                    x1 = x;
                    y1 = y + (2 * j - 1);
                }
                findCount += 1;
                //Debug.Log(findCount+ " find point x=" + x1 + ", y=" + y1);
                CMapPoint temp = new CMapPoint(x1, y1, fatherPoint);

                if (IsPass(x1, y1) && !InOpenList(temp) && !InCloseList(temp))
                {
                    //Debug.Log(findCount + " find point x=" + x1 + ", y=" + y1);
                    // 记录和起点之间的距离
                    temp.moveDis = fatherPoint.moveDis + 1;
                    if (x1 == endTargetPoint.x && y1 == endTargetPoint.y && (temp.moveDis < leastDis))
                    {
                        endTargetPoint.fatherPoint = temp.fatherPoint;
                        leastDis = temp.moveDis;
                        continue;
                    }
                    OpenList.Add(temp);
                }
            }
        }
    }

    // 清空所有格子记录的已移动距离
    void ClearMoveDisOfPoint()
    {
        foreach (var p in MapPointList)
        {
            p.moveDis = 0;
        }
    }

    // 设置搜索到某个格子时已移动距离
    void SetMoveDisOfPoint(int x, int y, int dis)
    {
        foreach (var p in MapPointList)
        {
            if (p.x == x && p.y == y)
            {
                p.moveDis = dis;
            }
        }
    }

    bool InOpenList(CMapPoint mp)
    {
        foreach (var p in OpenList)
        {
            if (p.x == mp.x && p.y == mp.y)
            {
                return true;
            }
        }
        return false;
    }

    bool InCloseList(CMapPoint mp)
    {
        foreach (var p in CloseList)
        {
            if (p.x == mp.x && p.y == mp.y)
            {
                return true;
            }
        }
        return false;
    }
    //-------------------------------------------------------------//

    // 获取当前格子查找状态
    bool GetIsFindStatus(CMapPoint mp)
    {
        foreach (var p in MapPointList)
        {
            if (p.x == mp.x && p.y == mp.y)
            {
                return p.isFind;
            }
        }
        return true;
    }

    // 设置当前格子是否已查找过了
    void SetIsFindStatus(CMapPoint mp, bool status)
    { 
        foreach(var p in MapPointList)
        {
            if (p.x == mp.x && p.y == mp.y)
            {
                p.isFind = status;
            }
        }
    }

    // 判断该点是否可通过(非障碍点且在地图内)
    bool IsPass(int x, int y)
    {
        if (0 <= x && x < Col && 0 <= y && y < Row)
        {
            foreach (var p in MapPointList)
            { 
                if (p.x == x && p.y == y)
                {
                    return (p.abstacle == 1);
                }
            }
        }
        return false;
    }

    // 曼哈顿距离
    int ManhattanDistance(int x1, int y1, int x2, int y2)
    {
        return (Mathf.Abs(x1 - x2) + Mathf.Abs(y1 - y2));
    }

    // 获取下一个移动点(每次移动一格)
    void GetNextMovePoint()
    {
        if (MovePointList.Count > 0)
        {
            // 不能直接赋值,注意对象的引用关系
            moveTargetPoint = new CMapPoint(MovePointList[0].x, MovePointList[0].y);
            MovePointList.RemoveAt(0);
            //Debug.Log("next move point x=" + moveTargetPoint.x + ", y=" + moveTargetPoint.y);
        }
    }
}

》》》》戳我下载完整项目》》》》

2017-05-17 17:24:11 yongh701 阅读数 7250

毕竟游戏里面,不能所有物体都要求它按照一条定向的路径移动的,需要给玩家一个操作空间,让玩家点哪,这东西自然而然地去哪里。因此自《【iTween】指定路径位移》(点击打开链接)之后,自动寻路的需求应运而生。不过,Unity3D自带的功能,就能完成这个看起来高大上的功能。下面举一个例子说明这个问题。

如下图,摆了4个cube当作墙,然后摆一个球,当作游戏的主角,鼠标点哪走哪,但关键是不会出现穿墙的情况。


具体做法如下:

一、场景布置

1、如下图所示,没什么好说的。


2、之后先将这个场景保存为Navmesh,然后如下图打开自动寻路设置界面。


如下图所示,在Navigation界面,对所有代表墙的Cube和地板Plane都勾上Navigation Static。表示这些都是寻路的阻碍物。

都设置好再点击Bake。烘培之后就会出现如下图的淡蓝色的,可移动的区域。这是Unity3D自己能计算出来的。


3、给球加上Nav Mesh Agent这个组件,表示它是一个被导航体。里面的半径、速度等,Unity3D给你上这个组件的时候,基本会给你计算好的,如果你是自己导入的3D模型估计需要将半径改到和你的3D模型基本匹配的程度。


4、之后再给Plane上一个plane标签,用于碰撞检测。因为Unity3D中,鼠标点击Plane,需要是在鼠标点击的屏幕像素点,发出一条直线和Unity3D世界中物体碰撞,才能找到准确的点击的。这在《【Unity3D】判断是否鼠标点击物体与血条制作》(点击打开链接)已经说了,这里不再赘述了。毕竟这个plane注定要会被我们一会儿疯狂点击的。


二、脚本设置

给球sphere赋予如下的Navigation.cs:

using UnityEngine;
using System.Collections;

public class Navigation : MonoBehaviour
{
    private NavMeshAgent navMeshAgent;
    void Start()
    {
        navMeshAgent = gameObject.GetComponent<NavMeshAgent>();//初始化navMeshAgent
    }
    void Update()
    {
        if (Input.GetMouseButtonDown(0))//鼠标左键点下  
        {
            Ray mRay = Camera.main.ScreenPointToRay(Input.mousePosition);//住摄像机向鼠标位置发射射线 
            RaycastHit mHit;
            if (Physics.Raycast(mRay, out mHit))//射线检验 
            {
                if (mHit.collider.gameObject.tag == "plane")
                {
                    navMeshAgent.SetDestination(mHit.point);//mHit.point就是射线和plane的相交点,实为碰撞点
                }
            }
        }
    }
}
则能够享受NavMeshAgent带来的Unity3D自动寻路的欢乐~(*^_^*)