NavPath Class Reference

#include <navpath.h>

Public Member Functions
bool	isAbsolute () const
bool	isEvaluated () const
bool	isComplete () const
bool	isCurrentDependant () const
bool	isTargetDependant () const
std::string	getDescription () const
void	setVisible (bool vis)
void	setColor (GFXColor col)
void	setName (std::string n)
bool	getVisible () const
GFXColor	getColor () const
std::string	getName () const
bool	setSourceNode (PathNode *node)
bool	setDestinationNode (PathNode *node)
PathNode *	getSourceNode ()
PathNode *	getDestinationNode ()
const PathNode *	getSourceNode () const
const PathNode *	getDestinationNode () const
unsigned	getAbsoluteSource () const
unsigned	getAbsoluteDestination () const
const std::list< unsigned > *	getAllPoints () const
std::list< unsigned > *	getAllPoints ()
void	addDependant (NavPath *dependant)
void	removeDependant (NavPath *dependant)
const std::set< NavPath * > *	getDependants () const
std::set< NavPath * > *	getDependants ()
std::vector< NavPath * >	getRequiredPaths () const
bool	checkForCycles () const
bool	evaluate ()
void	removeOldPath ()
void	addNewPath ()
bool	update ()
bool	isNeighborPath (unsigned system, unsigned neighbor)
	NavPath ()
	~NavPath ()

Protected Attributes
bool	visible
std::string	name
GFXColor	color
PathNode *	source
PathNode *	destination
std::list< unsigned >	path
std::map< unsigned, std::pair < unsigned, unsigned > >	pathNeighbors
std::set< NavPath * >	dependants
TopoColor	topoColor
unsigned	topoTime
bool	updated

Friends
class	PathManager

Detailed Description

Definition at line 47 of file navpath.h.

Constructor & Destructor Documentation

NavPath::NavPath

(

)

Definition at line 503 of file navpath.cpp.

References color, destination, name, source, and visible.

{
    name        = "New Path";
    visible     = true;
    color       = GFXColor( 1, 0, 0 );
    source      = NULL;
    destination = NULL;
}

NavPath::~NavPath

(

)

Definition at line 512 of file navpath.cpp.

References destination, getDependants(), PathNode::getRequiredPath(), i, removeDependant(), removeOldPath(), and source.

{
    removeOldPath();
    if (source) {
        if ( source->getRequiredPath() )
            source->getRequiredPath()->removeDependant( this );
        delete source;
        source = NULL;
    }
    if (destination) {
        if ( destination->getRequiredPath() )
            destination->getRequiredPath()->removeDependant( this );
        delete source;
        source = NULL;
    }
    set< NavPath* > *depList = getDependants();
    for (std::set< NavPath* >::iterator i = depList->begin(); i != depList->end(); ++i) {
        if ( (*i)->source->getRequiredPath() == this ) {
            delete (*i)->source;
            (*i)->source = NULL;
        }
        if ( (*i)->destination->getRequiredPath() == this ) {
            delete (*i)->destination;
            (*i)->destination = NULL;
        }
    }
}

Member Function Documentation

void NavPath::addDependant

(

NavPath *

dependant)

Definition at line 230 of file navpath.cpp.

References dependants.

Referenced by setDestinationNode(), and setSourceNode().

{
    if (dependant == NULL)
        return;
    dependants.insert( dependant );
}

void NavPath::addNewPath

(

)

Definition at line 458 of file navpath.cpp.

References _Universe, Universe::AccessCockpit(), Cockpit::AccessNavSystem(), i, path, and pathNeighbors.

Referenced by update().

{
    NavigationSystem::CachedSystemIterator &systemIter = _Universe->AccessCockpit()->AccessNavSystem()->systemIter;

    int i;
    unsigned system;
    //Inscribe new path
    //*************************

    list< unsigned >::iterator aux;
    for (list< unsigned >::iterator iter = path.begin(); iter != path.end(); ++iter) {
        if ( (*iter) != path.front() )
            pathNeighbors[(*iter)].first = ( *--(aux = iter) );
        if ( (*iter) != path.back() )
            pathNeighbors[(*iter)].second = ( *++(aux = iter) );
        systemIter[*iter].part_of_path = true;
        systemIter[*iter].paths.insert( this );
    }
}

bool NavPath::checkForCycles

(

)

const

Definition at line 266 of file navpath.cpp.

References getRequiredPaths(), i, and v.

Referenced by setDestinationNode(), and setSourceNode().

{
    const NavPath    *v;
    vector< NavPath* >neighbors;
    unsigned i;
    deque< const NavPath* >pathStack;
    pathStack.push_back( this );
    bool     cycle = false;
    while (!pathStack.empty() && !cycle) {
        v = pathStack.back();
        pathStack.pop_back();
        neighbors = v->getRequiredPaths();
        for (i = 0; i < neighbors.size(); ++i) {
            if (neighbors[i] == this) {
                cycle = true;
                break;
            }
            pathStack.push_back( neighbors[i] );
        }
    }
    return cycle;
}

bool NavPath::evaluate

(

)

Definition at line 289 of file navpath.cpp.

References _Universe, Universe::AccessCockpit(), Cockpit::AccessNavSystem(), destination, fprintf, VegaConfig::getVariable(), i, index, PathNode::initSearchQueue(), isAbsolute(), isComplete(), PathNode::isDestination(), XMLSupport::parse_int(), path, NavigationSystem::CachedSystemIterator::size(), source, and vs_config.

Referenced by update().

{
    NavigationSystem::CachedSystemIterator &systemIter = _Universe->AccessCockpit()->AccessNavSystem()->systemIter;
    path.clear();
    static size_t max_size = XMLSupport::parse_int( vs_config->getVariable( "graphics", "nav_max_search_size", "16384" ) );
    if ( !isComplete() )
        return false;
    if ( isAbsolute() ) {
        //Using a double-rooted BFS search
        unsigned originIndex = source->initSearchQueue().front();
        unsigned destIndex   = destination->initSearchQueue().front();
        if (originIndex == destIndex) {
            path.push_back( originIndex );
            return true;
        }
        vector< unsigned >prev( systemIter.size() );
        vector< unsigned >visited( systemIter.size(), 0 );
        deque< unsigned > oriFront, destFront;
        bool     found = false;
        unsigned midNode;
        unsigned midNodePrevOri;
        unsigned midNodePrevDest;
        midNodePrevOri = midNodePrevDest = 0; //to shut up a warning about possibly used uninitialized --chuck_starchaser
        bool     oriTurn = true;
        deque< unsigned > *front;
        unsigned visitMark;
        if ( originIndex >= visited.size() || destIndex >= visited.size() ) {
            fprintf( stderr, "(previously) FATAL error with nav system, referencing value too big %d %d with visited size %d\n",
                    (int) originIndex, (int) destIndex, (int) visited.size() );
            return false;
        }
        oriFront.push_back( originIndex );
        visited[originIndex] = 1;
        destFront.push_back( destIndex );
        visited[destIndex]   = 2;
        while (oriFront.size() < max_size && destFront.size() < max_size && !oriFront.empty() && !destFront.empty()
               && !found) {
            //stay within memory bounds in case something goes wrong (it has, unfortunately on occasion)
            if (oriTurn) {
                front     = &oriFront;
                visitMark = 1;
            } else {
                front     = &destFront;
                visitMark = 2;
            }
            unsigned index = front->front();
            front->pop_front();
            for (unsigned adjs = 0; adjs < systemIter[index].GetDestinationSize(); ++adjs) {
                unsigned adjIndex = systemIter[index].GetDestinationIndex( adjs );
                if ( systemIter[adjIndex].isDrawable() ) {
                    if (visited[adjIndex] == 0) {
                        visited[adjIndex] = visitMark;
                        prev[adjIndex]    = index;
                        front->push_back( adjIndex );
                    } else if (visited[adjIndex] != visitMark) {
                        midNode = adjIndex;
                        if (oriTurn) {
                            midNodePrevDest = prev[adjIndex];
                            midNodePrevOri  = index;
                        } else {
                            midNodePrevOri  = prev[adjIndex];
                            midNodePrevDest = index;
                        }
                        found = true;
                        break;
                    }
                }
            }
            oriTurn = !oriTurn;
        }
        if (found) {
            unsigned index = midNodePrevOri;
            while (index != originIndex) {
                path.push_front( index );
                index = prev[index];
                if (path.size() >= max_size) {
                    //this prevents some odd "out of memory" crashes we were getting where there might have been a loop in the path somehow
                    path.clear();
                    found = false;
                    return false;
                }
            }
            path.push_front( originIndex );
            if (destIndex == midNode) {
                path.push_back( destIndex );
            } else {
                path.push_back( midNode );

                unsigned index = midNodePrevDest;
                while (index != destIndex) {
                    path.push_back( index );
                    index = prev[index];
                    if (path.size() >= max_size) {
                        //this prevents some odd "out of memory" crashes we were getting where there might have been a loop in the path somehow
                        path.clear();
                        found = false;
                        return false;
                    }
                }
                path.push_back( destIndex );
            }
        }
        return found;
    } else {
        //Using single-rooted BFS search
        vector< unsigned >prev( systemIter.size() );
        vector< bool >    visited( systemIter.size(), false );
        deque< unsigned > frontier = source->initSearchQueue();
        set< unsigned >   origins;
        bool     found = false;
        unsigned index, destIndex = 0;
        for (unsigned i = 0; i < frontier.size(); ++i) {
            index = frontier.front();
            frontier.pop_front();
            visited[index] = true;
            frontier.push_back( index );
            origins.insert( index );
            if ( destination->isDestination( index ) ) {
                path.push_back( index );
                return true;
            }
        }
        while (frontier.size() < max_size && !frontier.empty() && !found) {
            index = frontier.front();
            frontier.pop_front();
            for (unsigned adjs = 0; adjs < systemIter[index].GetDestinationSize(); ++adjs) {
                unsigned adjIndex = systemIter[index].GetDestinationIndex( adjs );
                if ( !visited[adjIndex] && systemIter[adjIndex].isDrawable() ) {
                    visited[adjIndex] = true;
                    prev[adjIndex]    = index;
                    frontier.push_back( adjIndex );
                    if ( destination->isDestination( adjIndex ) ) {
                        found     = true;
                        destIndex = adjIndex;
                        break;
                    }
                }
            }
        }
        if (found) {
            index = destIndex;
            path.push_front( index );
            do {
                index = prev[index];
                path.push_front( index );
                if (path.size() >= max_size) {
                    //this prevents some odd "out of memory" crashes we were getting where there might have been a loop in the path somehow
                    path.clear();
                    found = false;
                    return false;
                }
            } while ( !origins.count( index ) );             //While the index is not an origin
        }
        return found;
    }
}

unsigned NavPath::getAbsoluteDestination

(

)

const

Definition at line 215 of file navpath.cpp.

References path.

Referenced by ChainPathNode::initSearchQueue(), and ChainPathNode::isDestination().

{
    return path.back();
}

unsigned NavPath::getAbsoluteSource

(

)

const

Definition at line 210 of file navpath.cpp.

References path.

Referenced by ChainPathNode::initSearchQueue(), and ChainPathNode::isDestination().

{
    return path.front();
}

const std::list< unsigned > * NavPath::getAllPoints

(

)

const

Definition at line 220 of file navpath.cpp.

References path.

Referenced by ChainPathNode::initSearchQueue(), and ChainPathNode::isDestination().

{
    return &path;
}

std::list< unsigned > * NavPath::getAllPoints

(

)

Definition at line 225 of file navpath.cpp.

References path.

{
    return &path;
}

GFXColor NavPath::getColor

(

)

const

Definition at line 148 of file navpath.cpp.

References color.

{
    return color;
}

const std::set< NavPath * > * NavPath::getDependants

(

)

const

Definition at line 244 of file navpath.cpp.

References dependants.

Referenced by PathManager::dfsVisit(), PathManager::updateDependants(), and ~NavPath().

{
    return &dependants;
}

std::set< NavPath * > * NavPath::getDependants

(

)

Definition at line 249 of file navpath.cpp.

References dependants.

{
    return &dependants;
}

string NavPath::getDescription

(

)

const

Definition at line 99 of file navpath.cpp.

References destination, PathNode::getDescription(), getName(), getVisible(), isComplete(), isEvaluated(), and source.

Referenced by NavComputer::updateDescription().

{
    string temp;

    temp  = getName();
    temp += "#n#";
    temp += "----------#n#";
    temp += "Visible: ";
    temp += (getVisible() ? "True" : "False");
    temp += "#n#";
    if (source) {
        temp += "Source:#n#";
        temp += source->getDescription();
        temp += "#n#";
    }
    if (destination) {
        temp += "Destination:#n#";
        temp += destination->getDescription();
        temp += "#n#";
    }
    if (!source || !destination)
        temp += "#n#INCOMPLETE#n#";
    else if ( !isComplete() )
        temp += "#n#PATH CHAIN IS UNSOLVED BEFORE THIS POINT#n#";
    else if ( !isEvaluated() )
        temp += "#n#PATH NOT FOUND#n#";
    return temp;
}

PathNode* NavPath::getDestinationNode ( )

inline

Definition at line 74 of file navpath.h.

References destination.

    {
        return destination;
    }

const PathNode* NavPath::getDestinationNode ( ) const

inline

Definition at line 82 of file navpath.h.

References destination.

    {
        return destination;
    }

string NavPath::getName

(

)

const

Definition at line 153 of file navpath.cpp.

References name.

Referenced by getDescription(), and ChainPathNode::getDescription().

{
    return name;
}

std::vector< NavPath * > NavPath::getRequiredPaths

(

)

const

Definition at line 254 of file navpath.cpp.

References destination, PathNode::getRequiredPath(), and source.

Referenced by checkForCycles().

{
    std::vector< NavPath* >temp;
    if (source)
        if ( source->getRequiredPath() )
            temp.push_back( source->getRequiredPath() );
    if (destination)
        if ( destination->getRequiredPath() )
            temp.push_back( destination->getRequiredPath() );
    return temp;
}

PathNode* NavPath::getSourceNode ( )

inline

Definition at line 70 of file navpath.h.

References source.

    {
        return source;
    }

const PathNode* NavPath::getSourceNode ( ) const

inline

Definition at line 78 of file navpath.h.

References source.

    {
        return source;
    }

bool NavPath::getVisible

(

)

const

Definition at line 143 of file navpath.cpp.

References visible.

Referenced by NavComputer::actionShowPath(), and getDescription().

{
    return visible;
}

bool NavPath::isAbsolute

(

)

const

Definition at line 55 of file navpath.cpp.

References destination, PathNode::isAbsolute(), isComplete(), and source.

Referenced by evaluate().

{
    if ( !isComplete() )
        return false;
    if ( !source->isAbsolute() || !destination->isAbsolute() )
        return false;
    return true;
}

bool NavPath::isComplete

(

)

const

Definition at line 64 of file navpath.cpp.

References destination, PathNode::getRequiredPath(), isEvaluated(), and source.

Referenced by evaluate(), getDescription(), and isAbsolute().

{
    if (!source || !destination)
        return false;
    if ( source->getRequiredPath() )
        if ( !source->getRequiredPath()->isEvaluated() )
            return false;
    if ( destination->getRequiredPath() )
        if ( !destination->getRequiredPath()->isEvaluated() )
            return false;
    return true;
}

bool NavPath::isCurrentDependant

(

)

const

Definition at line 77 of file navpath.cpp.

References destination, PathNode::isCurrentDependant(), and source.

{
    if (source)
        if ( source->isCurrentDependant() )
            return true;
    if (destination)
        if ( destination->isCurrentDependant() )
            return true;
    return false;
}

bool NavPath::isEvaluated ( ) const

inline

Definition at line 51 of file navpath.h.

References path.

Referenced by getDescription(), and isComplete().

    {
        return path.size() != 0;
    }

bool NavPath::isNeighborPath	(	unsigned	system,
		unsigned	neighbor
	)

Definition at line 478 of file navpath.cpp.

References i, path, and pathNeighbors.

{
    map< unsigned, pair< unsigned, unsigned > >::iterator i = pathNeighbors.find( system );
    if ( i == pathNeighbors.end() )
        return false;
    if ( system != path.front() )
        if ( (*i).second.first == neighbor )
            return true;
    if ( system != path.back() )
        if ( (*i).second.second == neighbor )
            return true;
    return false;
}

bool NavPath::isTargetDependant

(

)

const

Definition at line 88 of file navpath.cpp.

References destination, PathNode::isTargetDependant(), and source.

{
    if (source)
        if ( source->isTargetDependant() )
            return true;
    if (destination)
        if ( destination->isTargetDependant() )
            return true;
    return false;
}

void NavPath::removeDependant

(

NavPath *

dependant)

Definition at line 237 of file navpath.cpp.

References dependants.

Referenced by setDestinationNode(), setSourceNode(), and ~NavPath().

{
    if (dependant == NULL)
        return;
    dependants.erase( dependant );
}

void NavPath::removeOldPath

(

)

Definition at line 446 of file navpath.cpp.

References _Universe, Universe::AccessCockpit(), Cockpit::AccessNavSystem(), i, path, and pathNeighbors.

Referenced by update(), and ~NavPath().

{
    NavigationSystem::CachedSystemIterator &systemIter = _Universe->AccessCockpit()->AccessNavSystem()->systemIter;
    //Erase old path
    //*************************
    for (list< unsigned >::iterator i = path.begin(); i != path.end(); ++i)
        if ( systemIter[*i].paths.erase( this ) )         //This erases this path from the list of paths in system
            if ( systemIter[*i].paths.empty() )
                systemIter[*i].part_of_path = false;
    pathNeighbors.clear();
}

void NavPath::setColor

(

GFXColor

col)

Definition at line 133 of file navpath.cpp.

References color.

{
    color = col;
}

bool NavPath::setDestinationNode

(

PathNode *

node)

Definition at line 185 of file navpath.cpp.

References _Universe, Universe::AccessCockpit(), Cockpit::AccessNavSystem(), addDependant(), checkForCycles(), destination, PathNode::getRequiredPath(), NavigationSystem::pathman, removeDependant(), and PathManager::updateSpecificPath().

Referenced by NavComputer::actionDestination(), and NavComputer::init().

{
    if (!node)
        return false;
    PathNode *oldNode = destination;
    destination = node;
    if ( checkForCycles() ) {
        destination = oldNode;
        delete node;
        node = NULL;
        return false;
    } else {
        if (oldNode)
            if ( oldNode->getRequiredPath() )
                oldNode->getRequiredPath()->removeDependant( this );
        if ( node->getRequiredPath() )
            node->getRequiredPath()->addDependant( this );
        if (oldNode)
            delete oldNode;
        oldNode = NULL;
        _Universe->AccessCockpit()->AccessNavSystem()->pathman->updateSpecificPath( this );
        return true;
    }
}

void NavPath::setName

(

std::string

n)

Definition at line 138 of file navpath.cpp.

References name.

Referenced by NavComputer::actionRenameConfirmed(), and NavComputer::init().

{
    name = n;
}

bool NavPath::setSourceNode

(

PathNode *

node)

Definition at line 158 of file navpath.cpp.

References _Universe, Universe::AccessCockpit(), Cockpit::AccessNavSystem(), addDependant(), checkForCycles(), PathNode::getRequiredPath(), PathNode::isSourceable(), NavigationSystem::pathman, removeDependant(), source, and PathManager::updateSpecificPath().

Referenced by NavComputer::actionSource(), PathManager::addPath(), and NavComputer::init().

{
    if (!node)
        return false;
    if ( !node->isSourceable() )
        return false;
    PathNode *oldNode = source;
    source = node;
    if ( checkForCycles() ) {
        source = oldNode;
        delete node;
        node   = NULL;
        return false;
    } else {
        if (oldNode)
            if ( oldNode->getRequiredPath() )
                oldNode->getRequiredPath()->removeDependant( this );
        if ( node->getRequiredPath() )
            node->getRequiredPath()->addDependant( this );
        if (oldNode)
            delete oldNode;
        oldNode = NULL;
        _Universe->AccessCockpit()->AccessNavSystem()->pathman->updateSpecificPath( this );
        return true;
    }
}

void NavPath::setVisible

(

bool

vis)

Definition at line 128 of file navpath.cpp.

References visible.

Referenced by NavComputer::actionShowPath().

{
    visible = vis;
}

bool NavPath::update

(

)

Definition at line 492 of file navpath.cpp.

References addNewPath(), evaluate(), and removeOldPath().

Referenced by PathManager::updateSpecificPath().

{
    removeOldPath();
    if ( evaluate() ) {
        addNewPath();
        return true;
    } else {
        return false;
    }
}

Friends And Related Function Documentation

friend class PathManager

friend

Definition at line 109 of file navpath.h.

Member Data Documentation

GFXColor NavPath::color

protected

Definition at line 113 of file navpath.h.

Referenced by getColor(), NavPath(), and setColor().

std::set< NavPath* > NavPath::dependants

protected

Definition at line 118 of file navpath.h.

Referenced by addDependant(), getDependants(), and removeDependant().

PathNode* NavPath::destination

protected

Definition at line 115 of file navpath.h.

Referenced by evaluate(), getDescription(), getDestinationNode(), getRequiredPaths(), isAbsolute(), isComplete(), isCurrentDependant(), isTargetDependant(), NavPath(), setDestinationNode(), and ~NavPath().

std::string NavPath::name

protected

Definition at line 112 of file navpath.h.

Referenced by getName(), NavPath(), and setName().

std::list< unsigned > NavPath::path

protected

Definition at line 116 of file navpath.h.

Referenced by addNewPath(), evaluate(), getAbsoluteDestination(), getAbsoluteSource(), getAllPoints(), isEvaluated(), isNeighborPath(), and removeOldPath().

std::map< unsigned, std::pair< unsigned, unsigned > > NavPath::pathNeighbors

protected

Definition at line 117 of file navpath.h.

Referenced by addNewPath(), isNeighborPath(), and removeOldPath().

PathNode* NavPath::source

protected

Definition at line 114 of file navpath.h.

Referenced by evaluate(), getDescription(), getRequiredPaths(), getSourceNode(), isAbsolute(), isComplete(), isCurrentDependant(), isTargetDependant(), NavPath(), setSourceNode(), and ~NavPath().

TopoColor NavPath::topoColor

protected

Definition at line 120 of file navpath.h.

Referenced by PathManager::dfsVisit().

unsigned NavPath::topoTime

protected

Definition at line 121 of file navpath.h.

Referenced by PathManager::dfsVisit().

bool NavPath::updated

protected

Definition at line 122 of file navpath.h.

Referenced by PathManager::updateSpecificPath().

bool NavPath::visible

protected

Definition at line 111 of file navpath.h.

Referenced by getVisible(), NavPath(), and setVisible().

---

The documentation for this class was generated from the following files:

• src/gfx/nav/navpath.h
• src/gfx/nav/navpath.cpp