routemap.cpp.svn-base

坦克大战游戏完整全套源代码

        boundingBox.rightBottom.x = max(p.x, boundingBox.rightBottom.x);
        boundingBox.rightBottom.y = max(p.y, boundingBox.rightBottom.y);
    }
    if (!boundingBox.Visible())
    {
        boundingBox.rightBottom += Point2f(0.1f, 0.1f);
    }
    return boundingBox;
}

Rectf RouteMap::getBoundingBox(const Polygon &p) const
{
    Rectf boundingBox(FLT_MAX, -FLT_MAX, FLT_MAX, -FLT_MAX);
    for (size_t i = 0; i < p.vertices.size(); ++i)
    {
        assert(p.vertices[i] < verticesBuffer.size());
        const Point2f &pt = verticesBuffer[p.vertices[i]];
        boundingBox.leftTop.x = min(pt.x, boundingBox.leftTop.x);
        boundingBox.leftTop.y = min(pt.y, boundingBox.leftTop.y);
        boundingBox.rightBottom.x = max(pt.x, boundingBox.rightBottom.x);
        boundingBox.rightBottom.y = max(pt.y, boundingBox.rightBottom.y);
    }
    if (!boundingBox.Visible())
    {
        boundingBox.rightBottom += Point2f(0.1f, 0.1f);
    }
    return boundingBox;
}

void RouteMap::FindPath(list<Point2f> &result, const Point2f &from, const Point2f &to) const
{
    RouteMapTriangleDistanceCompare cmp(*this);
    cmp.filterDataType = DT_RouteTriangle;
    size_t idFrom = space.getClosestEntity(from, cmp);
    cmp.resetDistance();
    size_t idTo = space.getClosestEntity(to, cmp);
    if (idFrom < triangles.size() && idTo < triangles.size())
    {
        vector<size_t> nodes;
        if (aStarSearch(nodes, idFrom, idTo))
        {
            result.push_back(from);//getCenter(triangles[idFrom]));
            size_t size = nodes.size();
            for (size_t i = 0; i < size; i++)
                result.push_back(getCenter(triangles[nodes[size - 1 - i]]));
            result.push_back(to);//getCenter(triangles[idTo]));
        }
    }
}

void RouteMap::setRange(const Rectf &range)
{
    this->range = range;
    space.clear();
    space.setRange(range);
}
void RouteMap::randomVertices(const Rectf &range)
{
    verticesBuffer.clear();
    {
        size_t n = 2000;
        verticesBuffer.reserve(n);
        float width = range.GetWidth();
        float height = range.GetHeight();
        for (size_t i = 0; i < n - 4; i++)
        {
            verticesBuffer.push_back(range.leftTop + Point2f(width * rand() / RAND_MAX, height * rand() / RAND_MAX));
        }

        verticesBuffer.push_back(range.leftTop + Point2f(width * 0, height * 0));
        verticesBuffer.push_back(range.leftTop + Point2f(width * 0, height * 1));
        verticesBuffer.push_back(range.leftTop + Point2f(width * 1, height * 0));
        verticesBuffer.push_back(range.leftTop + Point2f(width * 1, height * 1));
    }
    generateMapFromVertices();
}

void RouteMap::addPolygon(const vector<Point2f> &polygonVertices)
{
    Polygon polygon;
    size_t base = verticesBuffer.size();
    Rectf boundingBox(FLT_MAX, -FLT_MAX, FLT_MAX, -FLT_MAX);
    for (size_t i = 0; i < polygonVertices.size(); ++i)
    {
        const Point2f &p = polygonVertices[i];
        boundingBox.leftTop.x = min(p.x, boundingBox.leftTop.x);
        boundingBox.leftTop.y = min(p.y, boundingBox.leftTop.y);
        boundingBox.rightBottom.x = max(p.x, boundingBox.rightBottom.x);
        boundingBox.rightBottom.y = max(p.y, boundingBox.rightBottom.y);

        verticesBuffer.push_back(polygonVertices[i]);
        polygon.vertices.push_back(base + i);
    }
    if (!boundingBox.Visible())
    {
        boundingBox.rightBottom += Point2f(0.1f, 0.1f);
    }
    space.addEntity(polygons.size(), DT_Poly, boundingBox);
    polygons.push_back(polygon);
}

bool RouteMap::insidePolygon(const Point2f &p, const Polygon &polygon) const
{
    int size = (int)polygon.vertices.size();
    int i0 = 0, i1 = 0;
    for (;;)
    {
        Point2f N, D;

        const Point2f &p1 = verticesBuffer[polygon.vertices[i1]];
        const Point2f &p0 = verticesBuffer[polygon.vertices[i0]];

        int iDiff = i1 - i0;
        if (iDiff == 1 || (iDiff < 0 && iDiff + size == 1))
        {
            N.x = p1.y - p0.y;
            N.y = p0.x - p1.x;
            D = p - p0;
            return N * D <= 0.0f;
        }

        // bisect the index range
        int iMid;
        if (i0 < i1)
        {
            iMid = (i0 + i1) >> 1;
        }
        else
        {
            iMid = ((i0 + i1 + size) >> 1);
            if (iMid >= size)
            {
                iMid -= size;
            }
        }
        const Point2f &pMid = verticesBuffer[polygon.vertices[iMid]];

        // determine which side of the splitting line contains the point
        N.x = pMid.y - p0.y;
        N.y = p0.x - pMid.x;
        D = p - p0;
        if (N * D > 0.0f)
        {
            // P potentially in <V(i0),V(i0+1),...,V(mid-1),V(mid)>
            i1 = iMid;
        }
        else
        {
            // P potentially in <V(mid),V(mid+1),...,V(i1-1),V(i1)>
            i0 = iMid;
        }
    }
}

void RouteMap::generateMapFromVertices()
{
    edges.clear();
    size_t i;

    numOriginalVertices = verticesBuffer.size();
    //vector<Edge> polyEdges;
    RouteMapObjSpace &tmpSpace = polySpace;
    tmpSpace.clear();
    tmpSpace.setRange(this->range);

    // generate extra vertices from polygons' intersected points
    for (i = 0; i < polygons.size(); i++)
    {
        const Polygon &polygon = polygons[i];
        vector<size_t> result;
        MapObjCuller culler(result);
        culler.dataType = DT_Edge;

        size_t sv;
        Edge e;
        // 对每条边，利用tmpSpace的cull找到与它有可能发生交叉的所有polyEdges的索引号
        e.va = polygon.vertices.back();
        for (sv = 0; sv < polygon.vertices.size(); sv++)
        {
            e.vb = polygon.vertices[sv];
            culler.viewer = getBoundingBox(e);
            tmpSpace.cull(culler);
            // 对这些polyEdges，判断是否与当前polygon的当前边有交点
            for (size_t j = 0; j < result.size(); j++)
            {
                Point2f crossPoint;
                if (LineCrossPoint(e, polyEdges[result[j]], crossPoint)) // 求交点
                {
                    // 若有交点，则该点也需要加入到三角剖分的计算顶点中去
                    verticesBuffer.push_back(crossPoint);
                }
            }
            e.va = e.vb;
        }

        // add polygon's edges to the tmpSpace
        e.va = polygon.vertices.back();
        for (sv = 0; sv < polygon.vertices.size(); sv++)
        {
            e.vb = polygon.vertices[sv];
            tmpSpace.addEntity(polyEdges.size(), DT_Edge, getBoundingBox(e));
            polyEdges.push_back(e);
            e.va = e.vb;
        }
    }

    // convert verticesBuffer to vertexSet
    vertexSet vs;
    for (i = 0; i < verticesBuffer.size(); i++)
    {
        vertex v(verticesBuffer[i].x, verticesBuffer[i].y);
        v.setUserData(i);
        vs.insert(v);
    }

    // call Delaunay methods
    triangleSet ts;
    Delaunay::Triangulate(vs, ts);
    edgeSet es;
    Delaunay::TrianglesToEdges(ts, es);

    int cc = 0;
    // fetch the result of Delaunay
    for (ctIterator cti = ts.begin(); cti != ts.end(); ++cti)
    {
        Triangle t;
        t.v[Triangle::PointA] = cti->GetVertex(0)->getUserData();
        t.v[Triangle::PointB] = cti->GetVertex(1)->getUserData();
        t.v[Triangle::PointC] = cti->GetVertex(2)->getUserData();
        sort(t.v, t.v + 3);

        // add triangle to space
        const Rectf &boundingBox = getBoundingBox(t);
        tmpSpace.addEntity(triangles.size(), DT_Triangle, boundingBox);
        triangles.push_back(t);
    }

    // generate edges, and set triangles' neighbourhood 
    for (cedgeIterator cei = es.begin(); cei != es.end(); ++cei)
    {
        Edge e;
        size_t eid = edges.size();
        e.va = cei->m_pV0->getUserData();
        e.vb = cei->m_pV1->getUserData();
        if (e.va > e.vb)
            swap(e.va, e.vb);
        e.t0 = cei->t0;
        e.t1 = cei->t1;
        if (e.t0 > e.t1)
            swap(e.t0, e.t1);
        assert(e.va < verticesBuffer.size());
        assert(e.vb < verticesBuffer.size());

        // connect 2 triangles
        size_t t0 = e.t0;
        size_t t1 = e.t1;
        if (t0 < triangles.size() && t1 < triangles.size())
        {
            Triangle &tri0 = triangles[t0];
            Triangle &tri1 = triangles[t1];
            //if (tri0.block || tri1.block)
            //    continue;

            // FIXME: what ugly code it is ...
#define SET_NEIGHBOUR_TRIANGLE(tri, t1)                                             \
    if (tri.v[Triangle::PointA] == e.va)                                            \
    {                                                                               \
        assert(tri.v[Triangle::PointB] == e.vb || tri.v[Triangle::PointC] == e.vb); \
        if (tri.v[Triangle::PointB] == e.vb)                                        \
            tri.t[Triangle::EdgeAB] = t1, tri.e[Triangle::EdgeAB] = eid;            \
        else                                                                        \
            tri.t[Triangle::EdgeAC] = t1, tri.e[Triangle::EdgeAC] = eid;            \
    }                                                                               \
    else if (tri.v[Triangle::PointB] == e.va)                                       \
    {                                                                               \
        assert(tri.v[Triangle::PointA] == e.vb || tri.v[Triangle::PointC] == e.vb); \
        if (tri.v[Triangle::PointA] == e.vb)                                        \
            tri.t[Triangle::EdgeAB] = t1, tri.e[Triangle::EdgeAB] = eid;            \
        else                                                                        \
            tri.t[Triangle::EdgeBC] = t1, tri.e[Triangle::EdgeBC] = eid;            \
    }                                                                               \
    else                                                                            \
    {                                                                               \
        assert(tri.v[Triangle::PointC] == e.va);                                    \
        assert(tri.v[Triangle::PointA] == e.vb || tri.v[Triangle::PointB] == e.vb); \
        if (tri.v[Triangle::PointA] == e.vb)                                        \
            tri.t[Triangle::EdgeAC] = t1, tri.e[Triangle::EdgeAC] = eid;            \
        else                                                                        \
            tri.t[Triangle::EdgeBC] = t1, tri.e[Triangle::EdgeBC] = eid;            \
    }

            SET_NEIGHBOUR_TRIANGLE(tri0, t1);
            SET_NEIGHBOUR_TRIANGLE(tri1, t0);
        }
//      space.addEntity(edges.size(), DT_Edge, getBoundingBox(e));
        edges.push_back(e);
    }
#if 1
    // 对每条边检查是否与多边形的边有交叉，若有则需要turn
    vector<size_t> edgeIds(edges.size());
    for (i = 0; i < edges.size(); i++)
        edgeIds[i] = i;
    
    vector<size_t> edgeIds2;
    edgeIds2.reserve(edgeIds.size());
    size_t tryCount = 3; // 最多进行尝试3次无效的剔除
    while(!edgeIds.empty())
    {
        // 过滤edgeIds中的边，把与多边形边相交的边添加到edgeIds2中去
        for (i = 0; i < edgeIds.size(); i++)
        {
            size_t eid = edgeIds[i];
            Edge &e = edges[eid]; // 

            e.failedToTurn = false;

            vector<size_t> result; // id in polyEdges
            MapObjCuller culler(result);
            culler.dataType = DT_Edge;
            culler.viewer = getBoundingBox(e);
            tmpSpace.cull(culler);
            for (size_t j = 0; j < result.size(); j++)
            {
                const Edge &polyEdge = polyEdges[result[j]];
                if (e.va == polyEdge.va || e.va == polyEdge.vb || 
                    e.vb == polyEdge.va || e.vb == polyEdge.vb)
                    continue;

                // 如果一端恰好是该多边形边的切割点，那么也要忽略相交检测