自制NavMesh2D（三）

Medemus

Navigation

发布于：2020年11月8日

次浏览

图源：https://www.pixiv.net/artworks/85447522

对三角形进行A*寻路

在获得具体路径之前，需要知道走过了哪些三角形，只有知道需要经过哪些三角形才能进行接下来的路径规划，而一般这步操作是由A*算法来进行的。

在常见情况下，A*往往是对二维网格进行操作。

那么如果要在不规则的三角形集合中进行A寻路，看上去似乎有很大不同，但其实本质是一样的，在（二）中，为了支持三角形进行A寻路，为其增添了一些参数，并规定了在三角形中的G与H的计算规则，这样就能按照常规的方法来进行A*寻路的操作了。

首先是要获取终点与终点所在的三角形：

NavTriangle startNavTriangle = null, endNavTriangle = null;

foreach (var triangle in navMeshData)//获取起始三角形与终点三角形
{
    if (startNavTriangle == null)
        if (MUtil.IsPointIn(start, triangle))
            startNavTriangle = triangle;

    if (endNavTriangle == null)
        if (MUtil.IsPointIn(end, triangle))
            endNavTriangle = triangle;

    if(startNavTriangle != null && endNavTriangle != null)
        break;
}

进行A*相关操作：

//A*寻路
bool isFound = false;
int traversalTimes = 1;
List<NavTriangle> openList = new List<NavTriangle>();   //开放列表
List<NavTriangle> closeList = new List<NavTriangle>();
startNavTriangle.traversalTimes = traversalTimes;
openList.Add(startNavTriangle);
Debug.LogWarning("start:" + startNavTriangle.ID);
int tmp = 10000;
while (openList.Count > 0 && tmp > 0)
{
    --tmp;
    NavTriangle curNode;
    curNode = openList[openList.Count - 1];
    openList.Remove(curNode);
    closeList.Add(curNode);

    if (curNode.ID == endNavTriangle.ID)
    {
        isFound = true;
        break;
    }

    for (int i = 0; i < 3; ++i)
    {
        int index = curNode.neighborID[i];
        NavTriangle neighboTriangle;
        if (index < 0)
        {
            continue;
        }
        else
        {
            neighboTriangle = navMeshData[index];
        }

        if (neighboTriangle.groupID == startNavTriangle.groupID)
        {
            if (neighboTriangle.traversalTimes != traversalTimes)//如果没有遍历过
            {
                neighboTriangle.traversalTimes = traversalTimes;
                neighboTriangle.parentID = curNode.ID;//将邻居的父节点设置为当前节点
                neighboTriangle.isOpen = true;
            
                neighboTriangle.CalcHeuristic(end);//计算H
                neighboTriangle.G = curNode.G + curNode.GetCost(neighboTriangle.ID);//计算G
            
                openList.Add(neighboTriangle);//加入openList
                openList.Sort(CompareTriWithFValue);//根据F排序
                neighboTriangle.inWallIndex = curNode.ID;//进入边为cur
            }
            else//如果已在open中
            {
                if (neighboTriangle.isOpen)
                {
                    if (neighboTriangle.G + neighboTriangle.GetCost(curNode.ID) < curNode.G)//如果当前到达邻居的G小于原来的G，则更新该邻居
                    {
                        Debug.Log("change:"+neighboTriangle.ID);
                        curNode.G = neighboTriangle.G + neighboTriangle.GetCost(curNode.ID);
                        curNode.parentID = neighboTriangle.ID;
                        curNode.inWallIndex = neighboTriangle.ID;
                    }
                }
                else
                {
                    neighboTriangle = null;
                    continue;
                }
            }
        }
    }
}//遍历

完成上述操作后即可在closeList中通过每个三角形的父节点获取完整的三角形列表。

测试，绿色点为起点，黄色为终点：

计算路径

在有了三角形后，就可以将其转换为具体的路径了。

通过计算拐点获得路径上的路径点，再将这些路径点连接起来便是所需要的路径了。

所以这一步的关键操作就在于如何获取拐点。NavMesh

设计一个方法，用来获取下一个拐点：

所需要的相关信息：

public Vector2 GetNextWayPoint(Vector2 way,List<NavTriangle> pathList,Vector2 end,ref int curIndex)
{
    var tri = pathList[curIndex];//当前路径点所在的三角形
    var outLine = tri.GetLineByIndex(tri.outWallIndex);//获取当前三角形的离开边
    int lastIndex1 = curIndex;//当前左侧那条边的所在三角形的index
    int lastIndex2 = curIndex;//当前右侧那条边的所在三角形的index
    Line l1 = new Line(way,outLine.start);//右侧那条边，路径点->离开边的起点
    Line l2 = new Line(way,outLine.end);//左侧那条边，路径点->离开边的终点
    Vector2 targetPoint1, targetPoint2;//下一个离开边的起点和终点（两条边下一个到达的位置）

    ///········
}

开始遍历：

public Vector2 GetNextWayPoint(Vector2 way,List<NavTriangle> pathList,Vector2 end,ref int curIndex)
{
    ///········
    for (int i = curIndex + 1; i < pathList.Count; ++i)//从三角形列表的下一个开始遍历
    {
        tri = pathList[i];
        outLine = tri.GetLineByIndex(tri.outWallIndex);//下一个三角形的离开边
        
        if (i == pathList.Count - 1)
        {
            targetPoint1 = targetPoint2 = end;//如果已经到了最后一个三角形，直接指向终点
        }
        else
        {
            targetPoint1 = outLine.start;
            targetPoint2 = outLine.end;
        }
    ///········
    }
}

遍历时具体的判定：

public Vector2 GetNextWayPoint(Vector2 way,List<NavTriangle> pathList,Vector2 end,ref int curIndex)
{
    ///········
    for (int i = curIndex + 1; i < pathList.Count; ++i)//从三角形列表的下一个开始遍历
    {
    ///········
        if (!MMath.IsEqual(targetPoint1, l1.end))//如果移动到的下一个边的点与当前点一样的话就不需要移动
        {
            if (l2.ClassifyPoint(targetPoint1) == PointSide.LEFT_SIDE)//如果右侧边的目标点在左侧边的左侧（代表漏斗角的度数变成负数）
            {
            //左侧边的当前点就是拐点
                curIndex = lastIndex1;
                Vector2 nextPoint = l2.end;
                
                return nextPoint;
            }else if (l1.ClassifyPoint(targetPoint1) != PointSide.RIGHT_SIDE)//如果右侧边的目标点没有在其右侧（角度没有变大）
            {
            //正常移动
                lastIndex1 = i;
                l1.end = targetPoint1;
            }
        }
        
        if (!MMath.IsEqual(targetPoint2, l2.end))//如果移动到的下一个边的点与当前点一样的话就不需要移动
        {
            /*Debug.DrawLine(l2.start,targetPoint2);*/
            if (l1.ClassifyPoint(targetPoint2) == PointSide.RIGHT_SIDE)//如果左侧边的目标点在右侧边的右侧（代表漏斗角的度数变成负数）
            {
                //右侧边的当前点就是拐点
                Vector2 nextPoint = l1.end;
                curIndex = lastIndex2;
                return nextPoint;
            }else if (l2.ClassifyPoint(targetPoint2) != PointSide.LEFT_SIDE)//如果左侧边的目标点没有在其左侧（角度没有变大）
            {
            //正常移动
                lastIndex2 = i;
                l2.end = targetPoint2;
            }
        }
    }
    Vector2 wayPoint = end;
    curIndex = pathList.Count - 1;
    return wayPoint;
}

通过这样，就能够获取到下一个拐点，然后再将该拐点的所在三角形作为当前三角形，获取下一个拐点（路径点），直到路径点为终点，结束寻找。

var point = start;
wayPoints.Add(point);
int curIndex = 0;
while (!(point == end))//如果获取到的拐点（路径点）不是终点
{
    point = GetNextWayPoint(point, pathList, end, ref curIndex);//获取下一个拐点
    if (point == null)
    {
        return false;
    }
    wayPoints.Add(point);//将获取到的点添加进路径点列表
}