Is this fast?

[jesper]

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;
}

 

[Dietmar Kuehl]

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.

 

[jesper]

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.

 

[Dietmar Kuehl]

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

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:riority_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.