Is this fast?

Discussion in 'C++' started by jesper@alphacash.se, Feb 14, 2006.

  1. Guest

    I would like some feedback on this.
    A while back I was trying my hand at some pathfinding for a small game
    I was making.
    I did not know anything about it so I read some stuff and came up with
    the code below.
    I was at the time quite satisfied with it, but reading stuff here has
    made me doubt it.
    Is this implementation valid?
    Is this implementation fast?
    The member TNode * Spread[LevelSize][LevelSize]; I put it in there to
    make accessing
    the open and closed lists faster, doubles the memory requirement of the
    object is there
    another way that is better memory-wize without being slower? (faster is
    ok though :) )
    TBinaryHeap, can it be replaced with an stl container? Is that faster?

    In general, oppinions and suggestions are welcome, infact they are the
    entire point of this post.
    BTW, I snipped this out of context a bit, so I'm afraid that the
    main program isn't all that exciting.


    //-- Begin Code --
    #include <math>
    #include <stdlib.h>
    #include <iostream>
    // I dont know if #include <string> (<strings>??)is needed. My compiler
    finds all the stuff
    // and compiles this just fine.

    typedef int(*ASUtilFunction)(int, int, void *);
    const int LevelSize=100;
    struct tDelta
    {
    int dx,dy;
    };
    tDelta
    Direction[]={{0,-1},{1,0},{0,1},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}};




    class TNode
    {
    public:
    float f;
    float c;
    int x;
    int y;
    unsigned int heappos;
    bool open;
    bool closed;
    TNode* next;
    TNode* parent;
    inline bool operator<(TNode &a){return f<a.f;}
    inline bool operator==(TNode &a){return (x==a.x)&&(y==a.y);}
    inline TNode(float iF=10){f=iF;heappos=-1;}
    };

    class TBinaryHeap
    {
    private:
    TNode * Heap[LevelSize*LevelSize];
    unsigned int insertpoint;
    bool valid;

    public:
    inline void Push(TNode* tmp)
    {
    unsigned int pos=insertpoint;
    unsigned int parentpos;
    TNode* swap;
    Heap[pos]=tmp;
    while (pos>1)
    {
    parentpos=pos>>1;
    if(*(Heap[pos])<*(Heap[parentpos]))
    {
    swap=Heap[parentpos];
    Heap[parentpos]=Heap[pos];
    Heap[parentpos]->heappos=parentpos;
    Heap[pos]=swap;
    Heap[pos]->heappos=pos;
    pos=parentpos;
    }
    else
    break;
    }
    tmp->heappos=pos;
    insertpoint++;

    }
    inline TNode* Pop()
    {
    if (insertpoint==1) return NULL;
    unsigned int pos=insertpoint;
    unsigned int child1;
    unsigned int child2;
    TNode* swap;
    TNode* ret=Heap[1];
    Heap[1]=Heap[insertpoint-1];
    insertpoint--;
    pos=1;
    unsigned int newpos;

    do
    {
    newpos=pos;
    child1=pos<<1;
    child2=child1+1;
    if (child2<insertpoint-1)
    {
    if(*(Heap[child1])<*(Heap[pos])) {newpos=child1;}
    if(*(Heap[child2])<*(Heap[newpos])) {newpos=child2;}
    }
    else
    if (child1<insertpoint-1)
    {
    if(*(Heap[child1])<*(Heap[pos])) {newpos=child1;}
    }
    if(pos!=newpos)
    {
    swap=Heap[pos];
    Heap[pos]=Heap[newpos];
    Heap[pos]->heappos=pos;
    Heap[newpos]=swap;
    Heap[newpos]->heappos=newpos;
    pos=newpos;
    }
    else
    break;
    }while(true);
    return ret;
    }
    inline bool Validate(unsigned int pos)
    {
    if ((pos<<1)+1<insertpoint-1)
    {
    if (!Validate(pos<<1)) return false;
    if (!Validate(1+(pos<<1))) return false;
    return
    ((*(Heap[pos])<*(Heap[pos<<1]))&&(*(Heap[pos])<*(Heap[(pos<<1)+1])));
    }else
    if ((pos<<1)+1<insertpoint-1)
    {
    if (!Validate(pos<<1)) return false;
    return *(Heap[pos])<*(Heap[pos<<1]);
    }
    return true;
    }
    inline TBinaryHeap(){insertpoint=1;}
    inline void LowerPosition(int pos)
    {
    unsigned int parentpos;
    TNode* swap;
    while (pos>1)
    {
    parentpos=pos>>1;
    if(*(Heap[pos])<*(Heap[parentpos]))
    {
    swap=Heap[parentpos];
    Heap[parentpos]=Heap[pos];
    Heap[parentpos]->heappos=parentpos;
    Heap[pos]=swap;
    Heap[pos]->heappos=pos;
    pos=parentpos;
    }
    else
    break;
    }
    }
    inline void Empty()
    {
    insertpoint=1;
    }
    };



    class TAStar
    {
    private:
    TNode * Spread[LevelSize][LevelSize];
    TNode * FirstNodeToClear;
    TBinaryHeap Heap;

    int GoalX;
    int GoalY;
    void * data;
    TNode *Path;
    ASUtilFunction UtilCost;
    ASUtilFunction UtilValid;
    inline bool isopen(int x,int y){return
    (Spread[x][y]!=NULL)&&(Spread[x][y]->open);}
    inline bool isclosed(int x,int y){return
    (Spread[x][y]!=NULL)&&(Spread[x][y]->closed);}
    inline TNode* getnode(int x,int y){return Spread[x][y];}
    inline TNode* getbest(){return Heap.Pop();}
    inline bool doopen(int x,int y,float c)
    {
    if(!UtilValid(x,y,data)) return false;
    float
    nf=c+UtilCost(x,y,data)*sqrt(((GoalX-x)*(GoalX-x))+((GoalY-y)*(GoalY-y)));
    if(isopen(x,y))
    {
    if(Spread[x][y]->f<=nf)
    return false;
    Spread[x][y]->f=nf;
    Spread[x][y]->c=c;
    Heap.LowerPosition(Spread[x][y]->heappos);
    return true;
    }
    if(isclosed(x,y))
    {
    if(Spread[x][y]->f<=nf)
    return false;

    Spread[x][y]->f=nf;
    Spread[x][y]->c=c;
    Spread[x][y]->closed=false;
    Spread[x][y]->open=true;
    Heap.Push(Spread[x][y]);
    return true;
    }
    if(!Spread[x][y]) Spread[x][y]=new TNode;
    Spread[x][y]->open=true;
    Spread[x][y]->x=x;
    Spread[x][y]->y=y;
    Spread[x][y]->f=nf;
    Spread[x][y]->c=c;
    Heap.Push(Spread[x][y]);
    Spread[x][y]->next=FirstNodeToClear;
    FirstNodeToClear=Spread[x][y];
    return true;
    }
    inline void expand(int x,int y,float c)
    {
    for (int d=0;d<4;d++)
    {
    if(doopen(x+Direction[d].dx,y+Direction[d].dy,c))
    {

    Spread[x+Direction[d].dx][y+Direction[d].dy]->parent=Spread[x][y];
    }
    }
    for (int d=4;d<8;d++)
    {
    if(doopen(x+Direction[d].dx,y+Direction[d].dy,c+0.4))
    {

    Spread[x+Direction[d].dx][y+Direction[d].dy]->parent=Spread[x][y];
    }
    }
    }
    inline void doclose(int x,int y)
    {
    if(!isopen(x,y)) return;
    Spread[x][y]->open=false;
    Spread[x][y]->closed=true;
    }
    inline void ClearNodes()
    {
    while(FirstNodeToClear)
    {
    FirstNodeToClear->open=false;
    FirstNodeToClear->closed=false;
    FirstNodeToClear=FirstNodeToClear->next;
    }
    Heap.Empty();
    }
    public:
    inline TAStar(){data=NULL;for(int x=0;x<LevelSize;x++)for(int
    y=0;y<LevelSize;y++)Spread[x][y]=NULL;}
    inline void SetData(void * d){data=d;}
    inline void SetValid(ASUtilFunction d){UtilValid=d;}
    inline void SetCost(ASUtilFunction d){UtilCost=d;}
    inline bool FindPath(int sx,int sy,int gx,int gy)
    {
    if(!data) return false;
    ClearNodes();
    GoalX=gx;GoalY=gy;
    doopen(sx,sy,0);
    Spread[sx][sy]->parent=NULL;
    while ((Path=Heap.Pop())!=0)
    {
    if((Path->x==gx)&&(Path->y==gy)) break;
    expand(Path->x,Path->y,Path->c+1);
    doclose(Path->x,Path->y);
    }
    if (!Path) return false;
    return true;
    }
    inline TNode* GetPath(){return Path;}
    inline TNode* GetSearchList(){return FirstNodeToClear;}
    };



    int dummyCost(int x,int y, void *data)
    {
    return 1;
    }
    int dummyValid(int x,int y, void *data)
    {
    bool Edge =(x<1)||(x>=LevelSize)||(y<1)||(y>=LevelSize);
    if(!Edge)
    return (((bool*)data)[x+y*LevelSize])?1:0;
    return 0;
    }

    int main(int argc,char ** argv)
    {
    TAStar as;
    int startx=0;
    int starty=0;
    int goalx=0;
    int goaly=0;
    bool * Map=new bool[LevelSize*LevelSize];
    randomize();
    for(int i=0;i<LevelSize*LevelSize;i++)
    Map= (random(10)!=0);


    as.SetData(Map);
    as.SetValid(dummyValid);
    as.SetCost(dummyCost);
    do
    {

    while(!dummyValid(startx=random(LevelSize),starty=random(LevelSize),(void*)Map));

    while(!dummyValid(goalx=random(LevelSize),goaly=random(LevelSize),(void*)Map));
    as.FindPath(startx,starty,goalx,goaly);

    TNode * BeginingOfPath=as.GetPath();
    std::string PathString;
    char itoa_Buf[4];
    while(BeginingOfPath)
    {
    PathString+='(';
    PathString+=itoa(BeginingOfPath->x,itoa_Buf,10);
    PathString+=',';
    PathString+=itoa(BeginingOfPath->y,itoa_Buf,10);
    PathString+=')';
    BeginingOfPath=BeginingOfPath->parent;
    }

    std::cout<<PathString<<"\r\n";

    }while (true);

    return 0;
    }
    , Feb 14, 2006
    #1
    1. Advertising

  2. wrote:
    > A while back I was trying my hand at some pathfinding for a small game
    > I was making.


    What kind of path are you seeking? From your use of a heap I assume
    you are looking for some kind of shortest path search in some form
    of a graph. However, for a shortest path you should not need a
    heap which supports changing of a node's priority. Well, for a
    vanilla formulation of Dijkstra's algorithm you do but this is not
    how to implement it unless your graph is rather dense: just stick
    the edge instead of the node into the priority queue and test
    whether your node was visited.

    The tricky part of changing a node's priority is that this means
    that you need to support some form of node based priority queue
    where you can store some handle to the node in the priority queue
    and use this later when needed. This is a distinct disadvantage
    compared to a much faster array based priority queue which does,
    however, not allow [easily and efficiently] dealing with node
    handles. I have implemented various priority queues in the past
    (in particular d-heaps and Fibonacci-heaps) and measured a factor
    of 10 between using an array based d-heap instead of a node based
    heap (e.g. the Fibonacci-heap and a node based variation of a
    d-heap). Also, the optimal "d" for a d-heap is typically not 2
    but rather something like 5 (this depends on the application and
    the relative cost of moving vs. comparing elements, of course;
    using a general d-heap allows for profiling different values of
    "d").

    > Is this implementation valid?


    Dunno. It is too big for me to quickly glance at it and determine
    whether the code does what it should especially as there is no
    statement what the code should do in detail.

    > Is this implementation fast?


    Dunno.

    > The member TNode * Spread[LevelSize][LevelSize]; I put it in
    > there to make accessing the open and closed lists faster,


    What is this good for? Maybe you should provide some details on
    what kind of paths you are seeking. Typical graph search algorithms
    require O(n) (where n is the number of nodes) memory with a rather
    small constant (e.g. 1/8th of a byte for each node because all what
    is really needed is a bit to mark whether a node was visited;
    whether this extreme is really useful is a different question, though,
    because extracting a bit is possibly more expansive than wasting some
    memory).

    > doubles the memory requirement of the object is there
    > another way that is better memory-wize without being slower?


    Do you have a memory constraint? Well, of course, you don't have
    infinite memory. The question is essentially whether
    'sizeof(TNode*) * LevelSize * LevelSize' is a substantial fraction
    of your overall memory and whether you have alternatives for using
    it. In general you can normally trade memory for speed. Of course,
    the more compact your working set is, the faster your code will be
    on modern processors (because more of the data you need fits into
    a suitable cache).

    > TBinaryHeap, can it be replaced with an stl container? Is that
    > faster?


    Replacing your heap with a version not supporting changes of the
    priority will definitely make the heap *much* faster. However, it
    also requires a change of in the algorithm to traverse the graph.

    As I said, I hadn't a too close look at your code. However:

    > float
    > nf=c+UtilCost(x,y,data)*sqrt(((GoalX-x)*(GoalX-x))+((GoalY-y)*(GoalY-y)));


    Typically, only the relative costs really matter. Thus, you may
    not need to use 'sqrt()' at all. I haven't looked at your use of
    the cost in detail but often you don't really necessary. Also, you
    seem to be moving through some form of a plain. In this case you
    might be able to immediately remove branches if the detour taken
    becomes too large. Of course, this depends on the topology of your
    graph. Depending on your cost functions you might be able to come
    up easily with an upper limit of the distance from your start to
    your target (e.g. by using Breadth First Search before employing
    are more advanced search) and ignore everything which would yield
    a longer path. This essentially limits the number of elements in
    your heap and thus the number of elements you need to process.
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.eai-systems.com> - Efficient Artificial Intelligence
    Dietmar Kuehl, Feb 15, 2006
    #2
    1. Advertising

  3. Guest

    Thank you for taking your time.
    I wrote this routine to find a path from point a to point b, for
    "monsters" in a mazelike gaming level. (Very much like Nethack if that
    is familiar)
    The Idea was to use the same algorithm for all pathfinding tasks in the
    game. It's some time since I touched the code but I intend to return to
    it
    soon. It's kind of like a love child :).
    I built it so that the AI could explore diffrent "Gain" values from
    taking diffrent routes.
    In effect making a certain detour worth the longer trip. This is why I
    needed to be able to change priorty. Or so I thought when
    I did it.

    Spread[LevelSize][LevelSize] I put in there to simplify checking if a
    node is on the open-list or closed-list. I don't have to traverse
    collections to find if a node is present. I can't remember why I put
    the sqrt in there (in any case a lookup table would have been faster,
    go figure). I'll take it out and test the game and see if something
    breaks ;-)

    You mention a "static" heap being much faster. I would like to learn
    (in general terms) how this is done, it sounds very intriguing. (I
    can't spell, *sigh*)
    At the moment the bintree is the fastest I know how to do.
    , Feb 15, 2006
    #3
  4. wrote:
    > I wrote this routine to find a path from point a to point b, for
    > "monsters" in a mazelike gaming level. (Very much like Nethack if that
    > is familiar)


    I ascended this year already :)

    > The Idea was to use the same algorithm for all pathfinding tasks in the
    > game.


    My idea would be more ambitious: use the same algorithm for all
    path-finding tasks (note the omission of the phrase "in the game").
    Effectively, this is what the BGL (Boost Graph Library; see
    <http://www.boost.org/>) is all about.

    > I built it so that the AI could explore diffrent "Gain" values from
    > taking diffrent routes.
    > In effect making a certain detour worth the longer trip.


    OK. I will assume that your maze consists of corridors and rooms.
    This can easily be modelled by a graph: each position represents
    a node and two nodes are adjacent, i.e. connected by an edge, if
    it is possible to move from on position to the other in one step.
    Each edge then become a weight representing the cost to move along
    this edge (note, that to use Dijkstra's algorithm it is necessary
    that all costs are positive; if you have negative costs for edges
    your problem would become real hard).

    This model can possibly refined to e.g. replace all nodes along a
    corridor by just one edge (in which case special treatment becomes
    necessary if the source and/or the target are somewhere within a
    corridor; of course, the special case of moving along a corridor
    towards a known end of the corridor is not really that complex to
    handle...): for the immediate decision, it is entirely sufficient
    to determine the next step and the details of corridors somewhere
    down the road are likely to be irrelevant. If the paths stay stable
    this could even be extended to rooms which are somewhat more
    complex to handle: a room could be replaced by its entrances which
    are each connected to all other entrances with an edge weight with
    the shortest path.

    Of course, this could even be taken one step further: if the paths
    have the same costs for all monsters (or if the costs just differ
    by a factor), it would be possible to create a data structure
    presenting the next step towards an arbitrary target for each node
    in the graph. This is what "all-pair shortest paths" algorithms
    determine. However, this algorithm has a higher complexity and it
    thus makes sense to create a compressed representation first.

    > This is why I needed to be able to change priorty.


    I'm not sure whether I have understood this objective...

    > Spread[LevelSize][LevelSize] I put in there to simplify checking if a
    > node is on the open-list or closed-list.


    Are these used to represent whether a node was visited? I'm unaware
    of the use of terms "open-list" and "closed-list" in this context.
    I'd just call this a label where each label could, of course,
    represent the appropriate direction to take. Efficient access to
    such a label is, of course, essential.

    > You mention a "static" heap being much faster.


    Did I...? Oh, you mean a priority queue where the priorities don't
    change. Yes, this is much faster because all you need to maintain
    is essentially an array of pointers which are just moved
    appropriately. The movements are identical to those you use in your
    implementation (which is just a d-heap with d == 2; d is the number
    of children each node has). However, you don't maintain the position
    of the object within the heap, i.e. you have no efficient access to
    a specific element (and hence you cannot change its priority
    efficiently). The 'std::priority_queue' is a class template which
    is implemented that way also using d == 2. I made a collection of
    several heap data structures available in the past which included
    a d-heap where d was a template parameter. This collection also
    includes the Fibonacci-heap I mentioned which performs better when
    you need to reduce the priority.

    > At the moment the bintree is the fastest I know how to do.


    Array-based d-heaps are the fastest approach for dynamic maintenance
    of priorities if you don't need to change priorities. However, I
    found that d > 2 is typically better. Of course, the bigger your
    objects, the bigger the d which is optimal: when increasing d you
    trade the number of comparisons against the number of moves. When
    you need to change the priority, Fibonacci-heaps are better because
    they will reduce the overall number of operations, at least when
    the heap is used reasonably often: the have amortized constant costs
    for changing the priority (if I remember correctly) e.g. when using
    them with Dijkstra's algorithm.
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.eai-systems.com> - Efficient Artificial Intelligence
    Dietmar Kuehl, Feb 15, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Divyang M
    Replies:
    4
    Views:
    2,180
    Jim Lewis
    May 19, 2005
  2. Replies:
    13
    Views:
    5,063
    Weng Tianxiang
    Jun 11, 2005
  3. Replies:
    0
    Views:
    643
  4. Michele Simionato

    Python is darn fast (was: How fast is Python)

    Michele Simionato, Aug 23, 2003, in forum: Python
    Replies:
    13
    Views:
    546
  5. Juha Nieminen
    Replies:
    22
    Views:
    987
    Kai-Uwe Bux
    Oct 12, 2007
Loading...

Share This Page