A star 寻路

大白话说一下几个点：

通俗的来说，其实就是以一个规则来从A点走到B点。
怎么来判断我们走的格子是一个合适的格子？
就是靠一个规则来计算，这个规则就是估价函数。

估价函数：
常用：曼哈顿算法
F = G + H
G：表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).
H：表示从指定的方格移动到终点 B 的预计耗费

G值的计算：
假定：左右上下方向的移动产生的耗费是10
那么在斜方向的移动耗费就是左右上下方向耗费的根号2 倍，就是14咯

H值的计算：
(H 有很多计算方法, 这里我们设定只可以上下左右移动).
就是算是指定格子到终点格子的横方向上的耗费+竖方向上的耗费。

开启列表：就是一个等待检查方格的列表.
关闭列表：存放不需要再次检查的方格的列表

伪代码：
把起始格添加到 “开启列表”
do
{
寻找开启列表中F值最低的格子, 我们称它为当前格.
把它切换到关闭列表.
对当前格相邻的8格中的每一个
if (它不可通过 || 已经在 “关闭列表” 中)
{
什么也不做.
}
if (它不在开启列表中)
{
把它添加进 “开启列表”, 把当前格作为这一格的父节点, 计算这一格的 FGH
}
if (它已经在开启列表中)
{
if (用G值为参考检查新的路径是否更好, 更低的G值意味着更好的路径)
{
把这一格的父节点改成当前格, 并且重新计算这一格的 GF 值.
}
}
} while( 目标格已经在 “开启列表”, 这时候路径被找到)
如果开启列表已经空了, 说明路径不存在.
最后从终点开始, 沿着每一格的父节点移动直到回到起始格, 这就是路径。

地图信息：
1,不可走
0，可走

在Unity里效果如下：

节点：

using UnityEngine;

using System.Collections;

public class Node

{

    public bool canWalk;//是否可以行走

    public Vector3 worldPos;//节点的位置

    public int gridX, gridY;//地形网格的下标

    public int gCost;//离起始点的耗费

    public int hCost;//离目标点的耗费

    public int fCost { get { return gCost + hCost; } }

    public Node parent;//父对象

    public Node(bool _canWalk, Vector3 _pos, int _x, int _y)

    {

        canWalk = _canWalk;

        worldPos = _pos;

        gridX = _x;

        gridY = _y;

    }

}

地图网格：

using UnityEngine;

using System.Collections;

using System.Collections.Generic;

public class Grid : MonoBehaviour

{

    public Node[,] grid;//网格，是Node节点的二维数组

    public Vector2 gridSize;//网格的大小

    public float nodeRadius;//节点的半径

    private float nodeDiameter;//节点的直径

    public LayerMask whatLayer;//是可走层还是不可走层

    public int gridCountX, gridCountY;//每一行、列有几个Node

    public List<List<Node>> AllPath = new List<List<Node>>();//所有人的路径

    void Start()

    {

        nodeDiameter = nodeRadius * ;

        gridCountX = Mathf.RoundToInt(gridSize.x / nodeDiameter);

        gridCountY = Mathf.RoundToInt(gridSize.y / nodeDiameter);

        grid = new Node[gridCountX, gridCountY];

        CreateGrid();

    }

    void CreateGrid()

    {

        //左下角

        Vector3 startPoint = this.transform.position - gridSize.x /  * Vector3.right - gridSize.y /  * Vector3.forward;

        for (int i = ; i < gridCountX; i++)

        {

            for (int j = ; j < gridCountY; j++)

            {

                Vector3 worldPoint = startPoint + Vector3.right * (i * nodeDiameter + nodeRadius) + Vector3.forward * (j * nodeDiameter + nodeRadius);

                bool walkable = !Physics.CheckSphere(worldPoint, nodeRadius *, whatLayer);//检测半径（直径）范围内是否可行走，发射球形射线检测层

                grid[i, j] = new Node(walkable, worldPoint, i, j);

            }

        }

    }

    void OnDrawGizmos()

    {

        //画地形网格边缘

        Gizmos.DrawWireCube(transform.position, new Vector3(gridSize.x, , gridSize.y));

        //画节点Node

        if (grid == null) return;

        foreach (var node in grid)

        {

            Gizmos.color = node.canWalk ? Color.white : Color.red;

            Gizmos.DrawCube(node.worldPos, Vector3.one * (nodeDiameter - .1f));

        }

        //画角色

        /*  Node playerNode = GetFromPositon(player.position);

          if (playerNode != null && playerNode.canWalk)

          {

              Gizmos.color = Color.yellow;

              Gizmos.DrawCube(playerNode.worldPos, Vector3.one * (nodeDiameter - .1f));

          }*/

        //画路径

        //if (path != null)

        //{

        //    foreach (var node in path)

        //    {

        //        Gizmos.color = Color.black;

        //        Gizmos.DrawCube(node.worldPos, Vector3.one * (nodeDiameter - .1f));

        //    }

        //}

        if (AllPath.Count > )

        {

            for (int i = ; i < AllPath.Count; i++)

            {

                if (AllPath[i].Count > )

                {

                    foreach (var node in AllPath[i])

                    {

                        Gizmos.color = Color.black;

                        Gizmos.DrawCube(node.worldPos, Vector3.one * (nodeDiameter - .1f));

                    }

                }

            }

        }

    }

}

寻路：

using UnityEngine;

using System.Collections;

using System.Collections.Generic;

public class FindPath

{

    public Grid mapGrid;

    private GameObject npc, target;

    private List<Node> FinalPath = new List<Node>();

    public List<Node> GetFinalPath(GameObject self, GameObject target)

    {

        FindingPath(self.transform.position, target.transform.position);

        return FinalPath;

    }

    public void FindingPath(Vector3 _startPos, Vector3 _endPos)

    {

        //Node startNode = mapGrid.GetFromPositon(_startPos);

        //Node endNode = mapGrid.GetFromPositon(_endPos);

        Node startNode = GetFromPositon(_startPos);

        Node endNode = GetFromPositon(_endPos);

        //开启列表

        List<Node> openSet = new List<Node>();

        //关闭列表

        HashSet<Node> closeSet = new HashSet<Node>();

        openSet.Add(startNode);

        while (openSet.Count > )

        {

            Node currentNode = openSet[];

            for (int i = ; i < openSet.Count; i++)

            {

                if (openSet[i].fCost < currentNode.fCost && openSet[i].hCost < currentNode.hCost)

                {

                    currentNode = openSet[i];

                }

            }

            openSet.Remove(currentNode);

            closeSet.Add(currentNode);

            if (currentNode == endNode)

            {

                GeneratePath(startNode,endNode);

                return;

            }

            foreach (var node in GetNeibourhood(currentNode))

            {

                if (!node.canWalk || closeSet.Contains(node)) continue;

                int newCost = currentNode.gCost + GetNodesDistance(currentNode,node);

                if (newCost < node.gCost || !openSet.Contains(node))

                {

                    node.gCost = newCost;

                    node.hCost = GetNodesDistance(node,endNode);

                    node.parent = currentNode;

                    if (!openSet.Contains(node))

                    {

                        openSet.Add(node);

                    }

                }

            }

        }

    }

    private void GeneratePath(Node startNode,Node endNode)

    {

        List<Node> path = new List<Node>();

        Node temp = endNode;

        while (temp != startNode)

        {

            path.Add(temp);

            temp = temp.parent;

        }

        path.Reverse();

        FinalPath = path;

        mapGrid.AllPath.Add(FinalPath);

    }

    public int GetNodesDistance(Node a, Node b)

    {

        int countX = Mathf.Abs(a.gridX - b.gridX);

        int countY = Mathf.Abs(a.gridY - b.gridY);

        if (countX > countY)

        {

            return  * countY +  * (countX - countY);

        }

        else

        {

            return  * countX +  * (countY - countX);

        }

    }

    //角色在哪个节点之上

    public Node GetFromPositon(Vector3 _PlayerPos)

    {

        float percentX = (_PlayerPos.x + mapGrid.gridSize.x / ) / mapGrid.gridSize.x;

        float percentY = (_PlayerPos.z + mapGrid.gridSize.y / ) / mapGrid.gridSize.y;

        percentX = Mathf.Clamp01(percentX);

        percentY = Mathf.Clamp01(percentY);

        int x = Mathf.RoundToInt((mapGrid.gridCountX - ) * percentX);

        int y = Mathf.RoundToInt((mapGrid.gridCountY - ) * percentY);

        return mapGrid.grid[x, y];

    }

    //获取节点周围的节点

    public List<Node> GetNeibourhood(Node node)

    {

        List<Node> neribourhood = new List<Node>();

        for (int i = -; i <= ; i++)

        {

            for (int j = -; j <= ; j++)

            {

                if (i ==  && j == )

                {

                    continue;

                }

                int tempX = node.gridX + i;

                int tempY = node.gridY + j;

                if (tempX >  && tempY >  && tempX < mapGrid.gridCountX && tempY < mapGrid.gridCountY)

                {

                    neribourhood.Add(mapGrid.grid[tempX, tempY]);

                }

            }

        }

        return neribourhood;

    }

}

还有许多优化的地方：
1.多单位寻路
2.动态障碍

本文固定链接: http://www.shihuanjue.com/?p=103
转载请注明: 乔 2015年09月26日于是幻觉发表

巴特西

A star 寻路

最新文章

热门文章