Unity系列研究

Unity-基于路径点寻路算法的研究(二)检测障碍

在上一篇文章基于路径点寻路算法的研究(一)中介绍了基于路径点寻路的基本思路,接下来我将介绍如何去检测AI与目标点之间是否有障碍物。

我们还是先来看上一篇文章中的这张图

20160811143547

在上图中,假设蓝色点所连接的线段表示障碍(这里可以理解为蓝色的点所连接的线段为墙),这样的话R点和Q点之间就被线段DE和线段HG挡住了。所以想要判断两个点(R,Q)之间是否有障碍,只需要判断这两个点所构成的线段RQ是否与障碍线段(蓝色点所构成的线段)相交就行了。

接下来就来解决如何判断两个线段是否相交

20160812140019

上图中有四条线段(A,B) (C,D) (E,F) (GH)

我们可以发现在两个相交线段(A,B)和(C,D)中,线段(A,B)的两个端点A,B分别在线段(C,D)的两侧,同时线段(C,D)的端点C,D分别在线段(A,B)的两侧。

而在两个不相交线段(E,F)和(G,H)中,线段(G,H)的两个端点G,H分别在线段(E,F)的两侧,线段(E,F)的两个端点E,F不在线段(G,H)的两侧。

也就是说如果两个线段相交,那么这两条线段的端点分别在另一条线段的两侧

当然了,判断两个线段是否有很多方法,在这里我就使用上述方法。

而要计算两个点是否在一条线段的两边,数学上也是有相关定理的 对于直线方程y=f(x)以及另外2个点(x1,y1)(x2,y2),如果(y1-f(x1))*(y2-f(x2))<=0,那么(x1,y1)和(x2,y2)位于直线y=f(x)的两边(包含某个点位于直线上)

好了,接下来我们就来看代码吧

    //存放所有障碍线段的直线方程
    private static List<Dictionary<string, float>> VertextsEquation = new List<Dictionary<string, float>>();
    ///<summary>
    /// 判断一条线段是否与多边形相交
    /// 如果该线段的两个端点都在在多边形内 则该线段不与多边形相交
    /// </summary>
    /// <param name="_line"></param>
    /// <param name="_vertexs"></param>
    /// <returns></returns>
    public static bool PolygonLineIsCross(List<Vector3> _line, List<Vector3> _vertexs)
    {
        int index = 1;
        if (VertextsEquation.Count == 0)
        {
            for (int i = 0; i < _vertexs.Count; i++)
            {

                if (i == _vertexs.Count - 1)
                {
                    index = -i;
                }
                //计算多边形一条边的直线方程
                Vector3 _vecNor = (_vertexs[i + index] - _vertexs[i]).normalized;
                float vertexs_k = 0;
                float vertexs_b = 0;
                
                //直线方程为常量时 (这里用K=0表示直线方程为常量)
                if (_vecNor.x == 0)
                {
                }
                else {
                    vertexs_k = _vecNor.z / _vecNor.x;
                    vertexs_b = _vertexs[i].z - vertexs_k * _vertexs[i].x;
                }
                
                Dictionary<string, float> k_b = new Dictionary<string, float>();
                k_b.Add("k", vertexs_k);
                k_b.Add("b", vertexs_b);
                VertextsEquation.Add(k_b);
            }
        }
        index = 1;
        //得到该线段的直线方程
        Vector3 vecNor = (_line[0] - _line[1]).normalized;
        float line_k = vecNor.z / vecNor.x;
        float line_b = _line[0].z - line_k * _line[0].x;

        for (int i = 0; i < _vertexs.Count; i++)
        {
            if (i == _vertexs.Count - 1) {
                index = -i;
            }

            if ((_vertexs[i].z - (line_k * _vertexs[i].x + line_b)) * (_vertexs[i + index].z - (line_k * _vertexs[i + index].x + line_b)) <= 0)
            {
                //当直线方程为常量时
                if (VertextsEquation[i]["k"] == 0)
                {

                    if ((_line[0].x - _vertexs[i].x) * (_line[1].x - _vertexs[i].x) <= 0)
                    {
                        return true;
                    }
                }
                else if ((_line[0].z - (VertextsEquation[i]["k"] * _line[0].x + VertextsEquation[i]["b"])) * (_line[1].z - (VertextsEquation[i]["k"] * _line[1].x + VertextsEquation[i]["b"])) <= 0)
                {
                    return true;
                }
            }
            
        }

        return false;

    }

在PolygonlineIsCross方法的两个参数中_line 为线段两端点的集合,_vertexs是所有障碍线段端点的集合。

因为PolygonlineIsCross方法会被经常调用,而地形的障碍线段往往是固定的,所以这里我先把所有障碍线段的直线方程计算后存到了Dictionary当中,下一次执行PolygonlineIsCross方法时就直接从Dictionary中获取就行,不用重复计算。当然了我们也可以根据是否需要重复计算障碍物直线方程来对PolygonlineIsCross方法进行调整。

这里虽然使用了Vector3类型来表示点,但计算时我忽略了Y轴(Unity的Y轴) 只做了二维平面的计算。

好了,通过上述方法我们就能实现,寻路中的障碍检查了。

(1)

本文由 树莓屋 作者:Berry贝锐 发表,转载请注明来源!

关键词:,

热评文章

发表评论