routemap.cpp.svn-base

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

                {
                    RenderQueue::getSingleton().render(pa, pb, ARGB(255, 255, 0, 255));
                    RenderQueue::getSingleton().render(crossPoint + Point2f(-3, 0), crossPoint + Point2f(3, 0), ARGB(255, 255, 225, 255));
                    RenderQueue::getSingleton().render(crossPoint + Point2f(0, -3), crossPoint + Point2f(0, 3), ARGB(255, 255, 225, 255));
                }
                else
                {
                    RenderQueue::getSingleton().render(pa, pb, ARGB(255, 0, 255, 255));
                }
            }
        }
    }
}

#if 0
/* @fn generateMapFromVertices_old
   @note no longer used, just for reference
*/
void RouteMap::generateMapFromVertices_old()
{
    vector<Edge> newlines;
    size_t n = verticesBuffer.size();
    newlines.reserve(n * (n - 1) / 2);
    for (size_t i = 0; i < verticesBuffer.size(); i++)
    {
        for (size_t j = 0; j < i; j++)
        {
            Edge line;
            line.va = i;
            line.vb = j;
            line.len = (verticesBuffer[i] - verticesBuffer[j]).Length();
            newlines.push_back(line);
        }
    }
    sort(newlines.begin(), newlines.end());
    RouteMapObjSpace s(5);
    s.setRange(range);
    size_t numFace = (n - 3) * 2;
    size_t numEdge = n + numFace - 1;
    for (size_t i = 0; i < newlines.size(); i++)
    {
        const Edge &newline = newlines[i];
        RouteMapObjSpace::Node n;
        n.dataType = DT_Edge;
        n.dataId = edges.size();
        edges.push_back(newline); // 暂且先添加进去
        n.boundingBox.leftTop.x = verticesBuffer[newline.va].x;
        n.boundingBox.leftTop.y = verticesBuffer[newline.va].y;
        n.boundingBox.rightBottom.x = verticesBuffer[newline.vb].x;
        n.boundingBox.rightBottom.y = verticesBuffer[newline.vb].y;
        if (n.boundingBox.leftTop.x > n.boundingBox.rightBottom.x)
            swap(n.boundingBox.leftTop.x, n.boundingBox.rightBottom.x);
        if (n.boundingBox.leftTop.y > n.boundingBox.rightBottom.y)
            swap(n.boundingBox.leftTop.y, n.boundingBox.rightBottom.y);
        if (!s.checkCollision(n, *this))
            //if (j == lines.size())
        {
            // 前面暂且添加的,加对了
            s.addEntity(n.dataId, n.dataType, n.boundingBox);
            if (edges.size() >= numEdge)
                break;
        }
        else
        {
            // 前面暂且添加的不对.
            edges.pop_back();
        }
    }
}
#endif

bool RouteMapObjSpace::checkCollision(const Node &n, RouteMap &rmap)
{
    size_t size = entities.size();
    for (size_t i = 0; i < size; ++i)
    {
        if (entities[i].dataType != DT_Edge)
            continue;

        size_t line2 = entities[i].dataId;
        if (rmap.checkCollision(n.dataId, line2))
        {
            return true;
        }
    }

    if (child)
    {
        const Rectf &r = n.boundingBox;

        size_t cid = getChildId(r);
        if (cid < NumSubSpaces)
        {
            return getChild(cid).checkCollision(n, rmap);
        }
        else
        {
            assert(cid == size_t(-1));
            for (cid = 0; cid < NumSubSpaces; cid++)
            {
                if (getChild(cid).isIntersected(r) && getChild(cid).checkCollision(n, rmap))
                    return true;
            }
        }
    }

    return false;
}

void RouteMapObjSpace::cull(MapObjCuller &culler) const
{
    size_t size = entities.size();
    for (size_t i = 0; i < size; ++i)
    {
        const Node &node = entities[i];
        if (culler.filter(node.dataType) && (node.boundingBox & culler.viewer).Visible())
        {
            culler.objects.push_back(node.dataId);
        }
    }
    if (child)
    {
        size_t cid = getChildId(culler.viewer);
        if (cid < NumSubSpaces)
        {
            getChild(cid).cull(culler);
        }
        else
        {
            assert(cid == size_t(-1));
            for (cid = 0; cid < NumSubSpaces; cid++)
            {
                if (getChild(cid).isIntersected(culler.viewer))
                    getChild(cid).cull(culler);
            }
        }
    }
}

void RouteMap::BeginAddLine()
{
    verticesBuffer.clear();
    edges.clear();
    triangles.clear();
    range.leftTop = Point2f(0, 0);
    range.rightBottom = Point2f(0, 0);
}

void RouteMap::EndAddLine()
{
    RouteMapObjSpace s(5);
    s.setRange(range);

    for (size_t i = 0; i < edges.size(); i++)
    {
        const Edge &newline = edges[i];
        RouteMapObjSpace::Node n;
        n.dataType = DT_Edge;
        n.dataId = i;
        n.boundingBox.leftTop.x = verticesBuffer[newline.va].x;
        n.boundingBox.leftTop.y = verticesBuffer[newline.va].y;
        n.boundingBox.rightBottom.x = verticesBuffer[newline.vb].x;
        n.boundingBox.rightBottom.y = verticesBuffer[newline.vb].y;
        if (n.boundingBox.leftTop.x > n.boundingBox.rightBottom.x)
            swap(n.boundingBox.leftTop.x, n.boundingBox.rightBottom.x);
        if (n.boundingBox.leftTop.y > n.boundingBox.rightBottom.y)
            swap(n.boundingBox.leftTop.y, n.boundingBox.rightBottom.y);
        if (!s.checkCollision(n, *this))
        {
            s.addEntity(n.dataId, n.dataType, n.boundingBox);
        }
    }
}

void RouteMap::addLine(const Point2f &a, const Point2f &b)
{
    range.leftTop.x = min(range.leftTop.x, min(a.x, b.x));
    range.leftTop.y = min(range.leftTop.y, min(a.y, b.y));
    range.rightBottom.x = max(range.rightBottom.x, max(a.x, b.x));
    range.rightBottom.y = max(range.rightBottom.y, max(a.y, b.y));
    verticesBuffer.push_back(a);
    verticesBuffer.push_back(b);
    Edge line;
    line.va = verticesBuffer.size() - 2;
    line.vb = verticesBuffer.size() - 1;
    line.len = (a - b).Length();
    edges.push_back(line);
}
struct DistanceCmp
{
    struct Node
    {
        Node(size_t tid, size_t ptid, float _f) : triangleId(tid), parentTId(ptid), f(_f)
        {
        }
        size_t triangleId;
        size_t parentTId;

        float f;
    };
    DistanceCmp(const RouteMap &_rmap, const Point2f &_target) : rmap(_rmap), target(_target)
    {
    }
    const RouteMap &rmap;
    const Point2f &target;
    bool operator () (const Node &a, const Node &b) const
    {
        assert(a.triangleId < rmap.triangles.size());
        assert(b.triangleId < rmap.triangles.size());
        float da = a.f + (rmap.getCenter(rmap.triangles[a.triangleId]) - target).Length();
        float db = b.f + (rmap.getCenter(rmap.triangles[b.triangleId]) - target).Length();
        return da > db;
    }
};

bool RouteMap::aStarSearch(vector<size_t> &result, size_t from, size_t to) const
{
    assert(from < triangles.size());
    assert(to < triangles.size());
    assert(!triangles[from].block);
    assert(!triangles[to].block);

    const Point2f &target = getCenter(triangles[to]);

    typedef pair<size_t, float> VisitValue; // parent id, minimal distance
    typedef map<size_t, VisitValue> VisitMap;
    VisitMap visit;
    vector<DistanceCmp::Node> heap;
    heap.push_back(DistanceCmp::Node(from, size_t(-1), 0.f));
    visit.insert(pair<size_t, VisitValue>(from, VisitValue(size_t(-1), 0.f)));

    DistanceCmp distanceComparor(*this, target);

    while(!heap.empty())
    {
        pop_heap(heap.begin(), heap.end(), distanceComparor);
        DistanceCmp::Node n = heap.back();
        heap.pop_back();
        if (n.triangleId == to)
            break;

        assert(n.triangleId < triangles.size());
        const Triangle &tri0 = triangles[n.triangleId];
        const Point2f &ctri0 = getCenter(tri0);
        for (int i = 0; i < 3; i++)
        {
            if (tri0.t[i] == size_t(-1))
                continue;

            VisitMap::iterator iv = visit.find(tri0.t[i]);
            const Triangle &tri1 = triangles[tri0.t[i]];
            const Point2f &ctri1 = getCenter(tri1);
            float len = n.f + (ctri1 - ctri0).Length();
            if (iv == visit.end())
            {
                assert(tri0.t[i] != n.triangleId);
                visit.insert(iv, pair<size_t, VisitValue>(tri0.t[i], VisitValue(n.triangleId, len)));
                heap.push_back(DistanceCmp::Node(tri0.t[i], n.triangleId, len));
                push_heap(heap.begin(), heap.end(), distanceComparor);
            }
            else
            {
                if (len < iv->second.second)
                {
                    iv->second.first = n.triangleId;
                    iv->second.second = len;
                    assert(tri0.t[i] != n.triangleId);
                    heap.push_back(DistanceCmp::Node(tri0.t[i], n.triangleId, len));
                    push_heap(heap.begin(), heap.end(), distanceComparor);
                }
            }
        }
    }
    size_t id = to;
    result.clear();

    for(;;)
    {
        if (id == from)
            break;
        VisitMap::iterator ii = visit.find(id);
        if (ii == visit.end())
        {
            result.clear();
            break;
        }
        id = ii->second.first;
        result.push_back(id);
    }
    return id == from;
}

Point2f RouteMap::getCenter(const Triangle &t) const
{
    return (verticesBuffer[t.v[Triangle::PointA]] + verticesBuffer[t.v[Triangle::PointB]] + verticesBuffer[t.v[Triangle::PointC]]) / 3;
}

Rectf RouteMap::getBoundingBox(const Edge &e) const
{
    Rectf boundingBox(FLT_MAX, -FLT_MAX, FLT_MAX, -FLT_MAX);;
    {
        const Point2f &p = verticesBuffer[e.va];
        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);
    }
    {
        const Point2f &p = verticesBuffer[e.vb];
        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);
    }
    if (!boundingBox.Visible())
    {
        boundingBox.rightBottom += Point2f(0.1f, 0.1f);
    }
    return boundingBox;
}

Rectf RouteMap::getBoundingBox(const Triangle &t) const
{
    Rectf boundingBox(FLT_MAX, -FLT_MAX, FLT_MAX, -FLT_MAX);;
    for (int i = Triangle::PointA; i <= Triangle::PointC; i++)
    {
        const Point2f &p = verticesBuffer[t.v[i]];
        boundingBox.leftTop.x = min(p.x, boundingBox.leftTop.x);
        boundingBox.leftTop.y = min(p.y, boundingBox.leftTop.y);