---

---

AI_AStar.h

Go to the documentation of this file.

#ifndef AI_A_STAR_H
#define AI_A_STAR_H

#include "AI_Global.h"
#include "utils/AI_Array.h"


#define GRAPH_INITIAL_SIZE 0
#define GRAPH_GROW_SIZE 8


class AI_AStar
{
//*** Embedded
public:
    class Link;
    class Node;
    class Graph;
    class Session;

    typedef AI_Array<Link*> LinkArray;
    typedef LinkArray::iterator LinkArrayIt;
    typedef AI_Array<Node*> NodeArray;
    typedef NodeArray::iterator NodeArrayIt;

    class Node {
    //*** Attributes
    protected:
        int m_i_index;
        LinkArray m_arr_links;
        void *m_ptr_user_data;

    //*** Methods
    public:
        Node ();

        //*** Building
        void removeLink ( Link *ptr_link );
        void addLink( Link *ptr_link );
        void reset(void);

        //*** Sets
        void set (int i_index);
        void setUserData( void *ptr_data );

        //*** Gets
        void *getUserData( void ) const;
        int getIndex( void ) const;
        LinkArray &getLinks( void );

        //*** Utils
        Link *isLinkedTo( Node *ptr_other );
    };


    class Link {
    //*** Attributes
    protected:
        Node *m_ptr_node1;
        Node *m_ptr_node2;
        float m_f_length;
        float m_f_min_width;
        float m_f_max_width;
        void *m_ptr_user_data;
        Session *m_ptr_session;

    //*** Methods
    public:
        //*** Constructors & destructors
        Link();

        //*** Sets
        void set( Node *ptr_node1, Node *ptr_node2, float f_length, float f_min, float f_max, Session *ptr_session=NULL );
        void setUserData( void *ptr_data );

        //*** Gets
        void *getUserData( void ) const;
        Node *getFirstNode ( void ) const;
        Node *getSecondNode ( void ) const;
        const float getMinWidth ( void ) const;
        const float getMaxWidth ( void ) const;
        const float getLength ( void ) const;
        Node *getOtherNode ( Node *ptr_node );
        Session *getSession( void );

    };


    class Graph {
    protected:
        NodeArray m_arr_nodes;
        LinkArray m_arr_links;
        int m_i_first_node_index;

    public:
        //*** Constructor & Destructor
        Graph();
        ~Graph();

        //*** Building
        Node *addNode ( void *ptr_user_data = NULL );
        Link *addLink ( Node *ptr_node1, Node *ptr_node2, float f_lenght, float f_min, float f_max, Session *ptr_session=NULL );
        void reset( void );
        void clear( void );
        void setBaseNodeIndex( const int i);
        const int getBaseNodeIndex( void ) const;
        const int getLinksNumber( void ) const;
        const int getNodesNumber( void ) const;
        Node *getNode(const int i) const;
        Link *getLink(const int i) const;
    };


    class Informator {
    public:
        virtual float getHeuristic ( Node *ptr_node1, Node *ptr_node2 ) = 0;
    };


    class Session {
        friend AI_AStar;

    //*** Embedded
    private:
        struct PathSegment {
            Node *ptr_node_first;
            Node *ptr_node_second;
        };

        struct PathDirection {
            Node *ptr_node;
            float f_distance;
            float f_guess;

        public:
            PathDirection(void);
            PathDirection(Node *ptr_node, float f_distance, float f_guess);
        };

        typedef AI_Array<PathDirection>::iterator DirectionVectorIt;
    
    //*** Attributes
    private:
        Graph m_graph;
        float m_f_agent_width;
        AI_Array<PathSegment> m_arr_segments;
        AI_Array<PathDirection> m_arr_directions;
        unsigned char *m_ptr_byte_visited;
        int m_i_visited_size;
        float m_f_distance;
        Node *m_ptr_node_actual;
        Node *m_ptr_node_start;
        Node *m_ptr_node_final;
        NodeArray m_arr_way;

    //*** Methods
    protected:
        //*** Sets
        void setNodeVisited( int i );
        void pushDirection( Node *ptr_node, float f_distance, float f_depth );
        void pushSegment( Node *ptr_node1, Node *ptr_node2 );
        void pushWay( Node *ptr_node );

        //*** Gets
        bool isNodeVisited( int i );
        Node *getActualNode( void );
        float getActualDistance( void );
        PathSegment &getBackSegment( void );

        //*** Utils
        bool beginSearch ( void );
        void endSearch ( void );
        bool isFinishReached( void );
        bool moveBestDirection( void );
        void removeBackSegment( void );
    
    public:
        //*** Constructor & destructor
        Session();
        ~Session();

        //*** Build subgraph
        Node *addNode ( void *ptr_user_data );
        Link *addLink ( Node *ptr_node1, Node *ptr_node2, float f_lenght, float f_min, float f_max );
        void reset ( AI_AStar *ptr_astar );

        //*** Find way
        void setMission ( Node *ptr_node_start, Node *ptr_node_final );
        int getWaySize( void );
        Node *getWayNode( int i );

        //*** Sets
        void setAgentWidth( float f_width );
        void setAStar( AI_AStar *ptr_astar );

        //*** Gets
        float getAgentWidth( void );
        Node *getStartNode( void );
        Node *getFinalNode( void );
    };


//*** Attributes
private:
    Informator *m_ptr_informator;
    Graph m_graph;
    

//*** Methods
public:
    AI_AStar(void);
    ~AI_AStar(void);

    //*** Building graph
    Node *addNode ( void *ptr_user_data = NULL );
    Link *addLink ( Node *ptr_node1, Node *ptr_node2, float f_lenght, float f_min, float f_max );
    void clear(void);

    //*** Sets
    void setInformator (Informator *ptr_informator);

    //*** Gets
    int getLinksNumber( void ) const;
    Link *getLink ( int i ) const;
    int getNodesNumber( void ) const;
    Node *getNode ( int i ) const;

    //*** Find way
    bool findWay ( Session &session );
};


inline
void AI_AStar::Node::set (int i_index)
{
    m_i_index = i_index;
}


inline
void AI_AStar::Node::setUserData( void *ptr_data )
{
    m_ptr_user_data = ptr_data;
}


inline
void *AI_AStar::Node::getUserData( void ) const
{
    return m_ptr_user_data;
}


inline
void AI_AStar::Link::set(Node *ptr_node1, Node *ptr_node2, float f_length, float f_min, float f_max, Session *ptr_session)
{
    m_ptr_user_data = NULL;
    m_ptr_node1 = ptr_node1;
    m_ptr_node2 = ptr_node2;
    m_f_length = f_length;
    m_f_min_width = f_min;
    m_f_max_width = f_max;
    m_ptr_session = ptr_session;
}


inline
AI_AStar::Graph::Graph() :
    m_arr_nodes(GRAPH_INITIAL_SIZE, GRAPH_GROW_SIZE, NULL),
    m_arr_links(GRAPH_INITIAL_SIZE, GRAPH_GROW_SIZE, NULL),
    m_i_first_node_index(0)
{
    NodeArrayIt it_n = m_arr_nodes.Begin();
    for (int i=0; i<m_arr_nodes.AllocSize(); i++, it_n++)
        *it_n=NULL;

    LinkArrayIt it_l = m_arr_links.Begin();
    for (int i=0; i<m_arr_links.AllocSize(); i++, it_l++)
        *it_l=NULL;
}


inline
AI_AStar::Graph::~Graph()
{
    clear();
}


inline
void AI_AStar::Graph::setBaseNodeIndex( const int i)
{
    m_i_first_node_index = i;
}


inline
const int AI_AStar::Graph::getBaseNodeIndex( void ) const
{
    return m_i_first_node_index;
}


inline 
const int AI_AStar::Graph::getLinksNumber( void ) const
{
    return m_arr_links.Size();
}


inline 
const int AI_AStar::Graph::getNodesNumber( void ) const
{
    return m_arr_nodes.Size();
}


inline 
AI_AStar::Node *AI_AStar::Graph::getNode(const int i) const
{
    return m_arr_nodes[i];
}


inline 
AI_AStar::Link *AI_AStar::Graph::getLink(const int i) const
{
    return m_arr_links[i];
}



inline
AI_AStar::Node::Node () :
    m_ptr_user_data(NULL)
{
}


inline
AI_AStar::Link *AI_AStar::Node::isLinkedTo( Node *ptr_other )
{
    for (LinkArrayIt it=m_arr_links.Begin(); it!=m_arr_links.End(); it++)
    {
        if ( ptr_other==(*it)->getOtherNode ( this ) )
        {
            return (*it);
        }
    }

    return NULL;
}


inline
void AI_AStar::Node::removeLink ( Link *ptr_link )
{
    //*** Iterate backward to increase chance to find link to
    //    be removed first.
    if ( m_arr_links.Size()>0 )
    {
        LinkArrayIt it = m_arr_links.End();
        do {
            it--;

            if (*it==ptr_link)
            {   
                m_arr_links.Erase(it);
                return;
            }
        } while( it!=m_arr_links.Begin() );
    }
}


inline
int AI_AStar::Node::getIndex( void ) const
{
    return m_i_index;
}


inline
AI_AStar::LinkArray &AI_AStar::Node::getLinks( void )
{
    return m_arr_links;
}


inline
void AI_AStar::Node::addLink( Link *ptr_link )
{
    m_arr_links.Append( ptr_link );
}


inline
void AI_AStar::Node::reset(void)
{
    m_arr_links.Reset();
}


inline
AI_AStar::Link::Link() :
    m_ptr_session(NULL),
    m_ptr_node1(NULL),
    m_ptr_node2(NULL),
    m_ptr_user_data(NULL)
{
}


inline
AI_AStar::Node *AI_AStar::Link::getOtherNode ( Node *ptr_node )
{
    if ( m_ptr_node1==ptr_node )
        return m_ptr_node2;
    
    return m_ptr_node1;
}


inline
AI_AStar::Node *AI_AStar::Link::getFirstNode ( void ) const
{
    return m_ptr_node1;
}


inline
AI_AStar::Node *AI_AStar::Link::getSecondNode ( void ) const
{
    return m_ptr_node2;
}


inline
AI_AStar::Session *AI_AStar::Link::getSession( void )
{
    return m_ptr_session;
}


inline
const float AI_AStar::Link::getMinWidth ( void ) const
{
    return m_f_min_width;
}


inline
const float AI_AStar::Link::getMaxWidth ( void ) const
{
    return m_f_max_width;
}


inline
const float AI_AStar::Link::getLength ( void ) const
{
    return m_f_length;
}


inline
void *AI_AStar::Link::getUserData( void ) const
{
    return m_ptr_session;
}


inline
AI_AStar::Session::Session() :
    m_ptr_byte_visited(NULL),
    m_i_visited_size(0),
    m_f_agent_width(0)
{
}


inline
AI_AStar::Session::~Session()
{
    m_graph.reset();

    if (m_ptr_byte_visited)
    {
        delete(m_ptr_byte_visited);
    }
}


inline
AI_AStar::Node *AI_AStar::Session::addNode ( void *ptr_user_data )
{
    return m_graph.addNode( ptr_user_data );
}


inline
AI_AStar::Link *AI_AStar::Session::addLink ( Node *ptr_node1, Node *ptr_node2, float f_lenght, float f_min, float f_max)
{
    return m_graph.addLink( ptr_node1, ptr_node2, f_lenght, f_min, f_max, this );
}


inline
bool AI_AStar::Session::isFinishReached( void )
{
    return (m_ptr_node_actual==m_ptr_node_final);
}


inline
bool AI_AStar::Session::isNodeVisited( int i )
{
    unsigned char c = m_ptr_byte_visited[ i / 8 ];
    if (c & 1<<(i%8))
    {
        return true;
    }
    return false;
}


inline
void AI_AStar::Session::setNodeVisited( int i )
{
    unsigned char &c = m_ptr_byte_visited[ i / 8 ];
    c |= 1<<(i%8);
}


inline
void AI_AStar::Session::setAgentWidth( float f_width )
{
    m_f_agent_width = f_width;
}


inline
float AI_AStar::Session::getAgentWidth( void )
{
    return m_f_agent_width;
}


inline
AI_AStar::Node *AI_AStar::Session::getActualNode( void )
{
    return m_ptr_node_actual;
}


inline
float AI_AStar::Session::getActualDistance( void )
{
    return m_f_distance;
}


inline
void AI_AStar::Session::pushDirection( Node *ptr_node, float f_distance, float f_guess )
{
    PathDirection &dir = m_arr_directions.PushBack();

    dir.ptr_node = ptr_node;
    dir.f_distance = f_distance;
    dir.f_guess = f_guess;
}


inline
void AI_AStar::Session::pushSegment( Node *ptr_node1, Node *ptr_node2 )
{
    PathSegment &segment = m_arr_segments.PushBack();

    segment.ptr_node_first = ptr_node1;
    segment.ptr_node_second = ptr_node2;
}


inline
AI_AStar::Node *AI_AStar::Session::getStartNode( void )
{
    return m_ptr_node_start;
}


inline
AI_AStar::Node *AI_AStar::Session::getFinalNode( void )
{
    return m_ptr_node_final;
}


inline
AI_AStar::Session::PathSegment &AI_AStar::Session::getBackSegment( void )
{
    return m_arr_segments.Back();
}


inline
void AI_AStar::Session::removeBackSegment( void )
{
    m_arr_segments.PopBack();
}


inline
void AI_AStar::Session::pushWay( Node *ptr_node )
{
    m_arr_way.PushBack( ptr_node );
}


inline
int AI_AStar::Session::getWaySize( void )
{
    return m_arr_way.Size();
}


inline
AI_AStar::Node *AI_AStar::Session::getWayNode( int i )
{
    return m_arr_way[getWaySize()-i-1];
}


inline
void AI_AStar::Session::setMission ( Node *ptr_node_start, Node *ptr_node_final )
{
    m_ptr_node_start = ptr_node_start;
    m_ptr_node_final = ptr_node_final;
}


inline
void AI_AStar::Session::reset ( AI_AStar *ptr_astar )
{
    m_graph.reset();
    m_graph.setBaseNodeIndex( ptr_astar->getNodesNumber() );
}


inline
AI_AStar::Session::PathDirection::PathDirection(void) :
    ptr_node(NULL)
{
}


inline
AI_AStar::Session::PathDirection::PathDirection(Node *ptr_node, float f_distance, float f_guess) :
    ptr_node(ptr_node),
    f_distance(f_distance),
    f_guess(f_guess)
{
}


inline
AI_AStar::AI_AStar(void) : 
    m_ptr_informator(NULL)
{
}


inline
AI_AStar::~AI_AStar(void)
{
}


inline
void AI_AStar::clear(void)
{
    m_graph.clear();
}


inline
AI_AStar::Node *AI_AStar::addNode ( void *ptr_user_data )
{
    return m_graph.addNode( ptr_user_data );
}


inline
AI_AStar::Link *AI_AStar::addLink ( Node *ptr_node1, Node *ptr_node2, float f_lenght, float f_min, float f_max)
{
    return m_graph.addLink(ptr_node1, ptr_node2, f_lenght, f_min, f_max);
}


inline
int AI_AStar::getLinksNumber( void ) const
{
    return m_graph.getLinksNumber();
}


inline
AI_AStar::Link *AI_AStar::getLink ( int i ) const
{
    return m_graph.getLink(i);
}


inline
int AI_AStar::getNodesNumber( void ) const
{
    return m_graph.getNodesNumber();
}


inline
AI_AStar::Node *AI_AStar::getNode ( int i ) const
{
    return m_graph.getNode(i);
}


inline
void AI_AStar::setInformator (Informator *ptr_informator)
{
    m_ptr_informator = ptr_informator;
}


#endif

---

InExIn pages are hosted by
InExIn documentation generated by doxygen at Tue Dec 18 12:55:27 2007