airrpathfind.cpp

RPG3D演示 国外著名3D引擎 鬼火 这是一个开发团队做的演示 有完整源代码

#include "irrlicht.h"
#include "Airrpathfind.h"

// Copyright (C) 2005 Cestmir "CZestmyr" Houska
// This file is using some classes from "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in Irrlicht.h

using namespace irr;

/****************
/   PathNode    /
****************/

// constructor
PathNode::PathNode(core::vector3df& pos)
: position(pos), list(PIL_NONE){}

// returns the distance from another PathNode
u32 PathNode::distance(PathNode* other)
{
    return (u32)(position.getDistanceFrom(other->position));
}

// returns overestimated distance to a PathNode. It is used by the 
// pathfinding algorithm to explore those PathNodes first, that are more
// likely to lead to the goal.
u32 PathNode::Hdist(PathNode* other)
{
    return (u32)(position.getDistanceFrom(other->position) * 1.2f);
}

// adds the other PathNode to the list of the neighbours
void PathNode::setNeighbour(PathNode* other)
{
    neighbours.push_back(other);
}

// removes the other PathNode from the list of the neighbours
void PathNode::removeNeighbour(PathNode* other)
{
    core::list<PathNode*>::Iterator iter = neighbours.begin();

    while (iter != neighbours.end()){
        if (*iter == other) iter = neighbours.erase(iter);
        else iter++;
    }
}

// checks, whether the other PathNode is a neighbour of this node
bool PathNode::isNeighbour(PathNode* other)
{
    core::list<PathNode*>::Iterator iter = neighbours.begin();

    while (iter != neighbours.end()){
        if (*iter == other) return true;
        iter++;
    }
    
    return false;
}

// draws the node with the given driver, using the given color
void PathNode::draw(video::IVideoDriver* driver, video::SColor& color)
{
    video::S3DVertex NodeMeshVertices[4];

    NodeMeshVertices[0] = video::S3DVertex(0,2,0, 0,1,0,color,0,1);
    NodeMeshVertices[1] = video::S3DVertex(2,-2,-2, 1,0,-1,color,0,1);
    NodeMeshVertices[2] = video::S3DVertex(0,-2,2, 0,0,1,color,0,1);
    NodeMeshVertices[3] = video::S3DVertex(-2,-2,-2, -1,0,-1,color,0,1);

    u16 indices[] = { 0,2,3, 2,1,3, 1,0,3, 2,0,1 };

    core::matrix4 translation;

    translation.makeIdentity();
    translation.setTranslation(position);

    driver->setTransform(video::ETS_WORLD, translation);
    driver->drawIndexedTriangleList(&NodeMeshVertices[0], 4, &indices[0], 4);

    core::list<PathNode*>::Iterator iter = neighbours.begin();
    while (iter != neighbours.end()){
        driver->setTransform(video::ETS_WORLD, core::matrix4());
        driver->draw3DLine(position, (*iter)->position, video::SColor(255,255,255,0));
        iter++;
    }
}

/*********
/  path  /
*********/

// constructor
path::path(): core::list<PathNode*>(){}

// Copy constructor
path::path(path& other): core::list<PathNode*>()
{
    clear();
    core::list<PathNode*>::Iterator iter = other.begin();
    while (iter != other.end())
    {
        push_back(*iter);
        iter++;
    }
}

// = operator
path& path::operator=(path& other)
{
    if (&other == this) return *this;
    clear();
    core::list<PathNode*>::Iterator iter = other.begin();
    while (iter != other.end())
    {
        push_back(*iter);
        iter++;
    }
    return *this;
}

// checks, whether the path contains the searched node
bool path::contains(PathNode* searchedNode)
{
    core::list<PathNode*>::Iterator iter = begin();

    while (iter != end()){
        if (*iter == searchedNode) return true;
        iter++;
    }

    return false;
}

/*****************
/     Network    /
*****************/

// constructor
Network::Network(video::IVideoDriver* driv, ITimer* tim, bool createLogFile)
: state(0), log(createLogFile), driver(driv), selectedNode(NULL), startNode(NULL),
endNode(NULL), timer(tim)
{}

// destructor
Network::~Network()
{
    core::list<PathNode*>::Iterator iter = nodes.begin();

    while (iter != nodes.end()){
        delete (*iter);
        iter++;
    }
}

// draws the node, for testing and editiong purposes
void Network::draw()
{
    video::SMaterial material;
    material.Lighting = false;
    video::SColor color;

    core::list<PathNode*>::Iterator iter = nodes.begin();

    while (iter != nodes.end()){
        if (*iter == selectedNode) color = video::SColor(255,0,64,128);
        else if (*iter == startNode || *iter == endNode || pathSegments.contains(*iter))
            color = video::SColor(255,0,128,64);
        else color = video::SColor(255,255,255,128);
        driver->setMaterial(material);
        (*iter)->draw(driver, color);
        iter++;
    }
}

// returns pointer to the node, that is nearest to the given point
PathNode* Network::nearestNodePointer(core::vector3df pos)
{
    u32 dist = 32000;

    core::list<PathNode*>::Iterator ret = nodes.begin();
    core::list<PathNode*>::Iterator iter = nodes.begin();

    while (iter != nodes.end()){
        u32 d = (u32)pos.getDistanceFrom((*iter)->position);
        if (d < dist) {dist = d; ret = iter;}
        iter++;
    }
    return *ret;
}
// adds a node to this network at the given point
void Network::addNode(core::vector3df pos)
{
    PathNode* node = new PathNode(pos);
    nodes.push_back(node);
}

// adds two-way connection between two nodes
void Network::addConnection(PathNode* a, PathNode* b)
{
    if (a == b) return;
    if (connectionExists(a,b)){       //This method not only adds, but also deletes connections
        a->removeNeighbour(b);
        b->removeNeighbour(a);
        return;
    }

    a->setNeighbour(b);
    b->setNeighbour(a);
    return;
}

// adds one-way connection between two nodes
void Network::addOneWayConnection(PathNode* from, PathNode* to)
{
    if (connectionExists(from,to)){       //This method not only adds, but also deletes connections
        from->removeNeighbour(to);
        to->removeNeighbour(from);
        return;
    }

    from->setNeighbour(to);
    return;
}

// removes node from net with all its connections
void Network::removeNodeFromNet(PathNode* a)
{
    core::list<PathNode*>::Iterator iter = nodes.begin();
    core::list<PathNode*>::Iterator toErase;

    while (iter != nodes.end()){
        if (*iter == a) toErase = iter;
        else (*iter)->removeNeighbour(a);
        iter++;
    }

    nodes.erase(toErase);
    delete a;
}

// checks, whether there is any connection between two nodes
bool Network::connectionExists(PathNode* a, PathNode* b)
{
    if (a->isNeighbour(b) || b->isNeighbour(a)) return true;
    else return false;
}

// selects a node for purpose of making a two-way connection
void Network::selectNode(core::vector3df pos)
{
    if (selectedNode == NULL)
    selectedNode = nearestNodePointer(pos);
    else {
        PathNode* helper = nearestNodePointer(pos);
        addConnection(helper, selectedNode);
        selectedNode = NULL;
    }
}

// selects first and then a second node in order to find a path between
// them. Also stores this path to the pathSegments member.
// Returns true in case of success, else returns false
bool Network::findPath(core::vector3df fromOrTo)
{
    if (state == 0) {startNode = nearestNodePointer(fromOrTo); state = 1; return false;}

    // The state flag can now only be 1
    endNode = nearestNodePointer(fromOrTo);

    ofstream soubor;
    u32 timeStats;
    if (log)
    {
        soubor.open("log.txt");
        timeStats = timer->getTime();
        soubor << "Node Number: " << nodes.getSize() << ::endl;
        soubor << "Starting pathfinding..." << ::endl;
        soubor << "Reseting open and closed lists..." << ::endl;
    }