|
|
Pawn
Captures Wyvern: How Computer Chess Can Improve Your Pathfinding
Listing 2. The Code For The IDA* Algorithm
int IDAStar(position
p, int g) {
/* g = number of steps taken to reach position
*/
/* fmax = determined by ComputeMoves */
int
numOfSuccessors; /* total moves */
int lb; /*
lower bound */
int done; /*
finished search? */
int i; /*
move counter */
int h; /* heuristic distance
to goal */
/*
Use admissible heuristic to estimate distance */
/* to the goal nodes. */
h = EstimateDistanceToGoal(p);
/*
Are we at a goal node? */
if (h == 0) { return TRUE; }
/* Can we make it to the goal node in time?
*/
if (g+h >= fmax) { return FALSE; }
/* Can't cut off search, search all children
*/
numOfSuccessors = GenerateSuccessors(p);
for (i=1; i <= numOfSuccessors; i++) {
done = IDAStar(p.succ[i],
g+1);
if (done == TRUE) { return TRUE; }
}
return FALSE;
}
________________________________________________________
