D:/SoftwareEntwicklung/C++/HLC/Tools/SoftPixelEngine/repository/sources/Framework/Tools/spToolPathFinder.hpp

Go to the documentation of this file.

/*
 * Path finder header
 * 
 * This file is part of the "SoftPixel Engine" (Copyright (c) 2008 by Lukas Hermanns)
 * See "SoftPixelEngine.hpp" for license information.
 */

#ifndef __SP_TOOL_PATHFINDER_H__
#define __SP_TOOL_PATHFINDER_H__


#include "Base/spStandard.hpp"

#ifdef SP_COMPILE_WITH_PATHFINDER


#include "Base/spBaseObject.hpp"
#include "Base/spDimension.hpp"

#include <list>
#include <map>


namespace sp
{
namespace tool
{


class PathEdge;

class SP_EXPORT PathNode : public BaseObject
{
    
    public:
        
        PathNode();
        PathNode(const dim::vector3df &Position, void* Data = 0);
        ~PathNode();
        
        /* === Functions === */
        
        void setPosition(const dim::vector3df &Position);
        
        std::list<PathNode*> getNeighbors() const;
        
        /* === Inline functions === */
        
        inline dim::vector3df getPosition() const
        {
            return Position_;
        }
        
        inline const std::list<PathEdge*>& getIncidentEdges() const
        {
            return Edges_;
        }
        
    private:
        
        friend class PathEdge;
        friend class PathGraph;
        
        /* === Structures === */
        
        struct SP_EXPORT SNeighbor
        {
            SNeighbor(PathNode* Predecessor, PathNode* Neighbor);
            ~SNeighbor();
            
            /* Members */
            PathNode* Node;
            f32 Distance;
        };
        
        /* === Functions === */
        
        void addEdge(PathEdge* Edge);
        void removeEdge(PathEdge* Edge);
        void updateNeighbors();
        
        /* === Inline functions === */
        
        inline f32 getMinWayCosts() const
        {
            return WayCosts_ + DirectDistance_;
        }
        
        /* === Members === */
        
        dim::vector3df Position_;
        
        f32 WayCosts_;
        f32 DirectDistance_;
        
        std::list<PathEdge*> Edges_;
        std::list<SNeighbor> Neighbors_;
        
        PathNode* Predecessor_;
        
};


class SP_EXPORT PathEdge : public BaseObject
{
    
    public:
        
        PathEdge();
        PathEdge(PathNode* From, PathNode* To, bool Adjusted = false);
        ~PathEdge();
        
        /* === Functions === */
        
        inline PathNode* getFrom() const
        {
            return From_;
        }
        inline PathNode* getTo() const
        {
            return To_;
        }
        
        inline bool getAdjusted() const
        {
            return Adjusted_;
        }
        
        inline f32 getDistance() const
        {
            return Distance_;
        }
        
    private:
        
        friend class PathNode;
        friend class PathGraph;
        
        /* === Functions === */
        
        void updateNodePosition(PathNode* Node);
        
        /* === Members === */
        
        PathNode* From_;
        PathNode* To_;
        
        f32 Distance_;
        bool Adjusted_;
        
};


class SP_EXPORT PathGraph
{
    
    public:
        
        PathGraph();
        virtual ~PathGraph();
        
        /* === Functions === */
        
        PathNode* addNode(const dim::vector3df &Position, void* Data = 0);
        
        void removeNode(PathNode* Node);
        
        void clearNodeList();
        
        PathEdge* addEdge(PathNode* From, PathNode* To, bool Adjusted = false);
        
        void removeEdge(PathEdge* Edge);
        
        void clearEdgeList();
        
        void createGrid(
            const dim::vector3df &From, const dim::vector3df &To, const dim::vector3di &Steps,
            const std::vector<bool> &Bitmap = std::vector<bool>(), bool DiagonalEdges = true
        );
        
        virtual std::list<PathNode*> findPath(PathNode* From, PathNode* To);
        
        virtual bool findPath(PathNode* From, PathNode* To, std::list<PathNode*> &Path);
        
        virtual std::list<PathNode*> findPath(const dim::vector3df &From, const dim::vector3df &To);
        
        virtual bool findPath(const dim::vector3df &From, const dim::vector3df &To, std::list<PathNode*> &Path);
        
        /* === Inline functions === */
        
        inline bool foundPath() const
        {
            return isSolved_;
        }
        
        inline const std::list<PathNode*>& getNodeList() const
        {
            return NodeList_;
        }
        inline const std::list<PathEdge*>& getEdgeList() const
        {
            return EdgeList_;
        }
        
    protected:
        
        /* Functions */
        
        bool nextStep();
        
        PathNode* getNextNode();
        void addNodeToQueue(PathNode* Node, PathNode* Predecessor, const f32 WayCosts);
        
        void constructPath(std::list<PathNode*> &Path, PathNode* NextNode);
        
        /* Members */
        
        std::list<PathNode*> NodeList_;
        std::list<PathEdge*> EdgeList_;
        
        std::list<PathNode*> NodeQueue_;
        std::map<PathNode*, bool> ClosedMap_;
        
        PathNode* StartNode_, * TargetNode_;
        
        bool isSolved_;
        
};


} // /namespace tool

} // /namespace sp


#endif

#endif



// ================================================================================