Jump to content
  • Advertisement
Sign in to follow this  
podferio

Iterative Deepening

This topic is 2995 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

I need to add iterative deepening to this A* code:
This code came from the game Bos Wars.

int AStarFindPath(int sx, int sy, int gx, int gy, int gw, int gh,
int tilesizex, int tilesizey, int minrange, int maxrange, char *path, int pathlen, void *data)
{
ProfileBegin("AStarFindPath");

int i;
int j;
int o;
int ex;
int ey;
int eo;
int x;
int y;
int px;
int py;
int shortest;
// int counter;
int new_cost;
int costToGoal;
int path_length;
int ret = PF_FAILED;

AStarGoalX = gx; //GOAL X
AStarGoalY = gy; // GOAL Y

//
// Check for simple cases first
/*
i = AStarFindSimplePath(sx, sy, gx, gy, gw, gh, tilesizex, tilesizey,
minrange, maxrange, path, pathlen, data);
if (i != PF_FAILED) {
ret = i;
goto Cleanup;
}

*/

// Initialize
//
AStarCleanUp();

for (i = 0; i < AStarMapWidth * AStarMapHeight; ++i) {
CostMoveToCache = CacheNotSet;
}

OpenSetSize = 0;
CloseSetSize = 0;
x = sx; // STARTING X
y = sy; // STARTING Y

if (!AStarMarkGoal(gx, gy, gw, gh, tilesizex, tilesizey,
minrange, maxrange, data)) {
// goal is not reachable
ret = PF_UNREACHABLE;
goto Cleanup;
}

eo = y * AStarMapWidth + x;
// it is quite important to start from 1 rather than 0, because we use
// 0 as a way to represent nodes that we have not visited yet.
AStarMatrix[eo].CostFromStart = 1;
// 8 to say we are came from nowhere.
AStarMatrix[eo].Direction = 8;

// place start point in open, it that failed, try another pathfinder
costToGoal = AStarCosts(x, y, gx, gy); // costToGoal = the heuristic ( Root node)
AStarMatrix[eo].CostToGoal = costToGoal; // copy heuristic
if (AStarAddNode(x, y, eo, 1 + costToGoal) == PF_FAILED) {
ret = PF_FAILED;
goto Cleanup;
}
// http://www.gamedev.net/reference/programming/features/astar/page3.asp

AStarAddToClose(OpenSet[0].O); // 1. Add the starting square (or node) to the Close list.
if (AStarMatrix[eo].InGoal) {
ret = PF_REACHED;
goto Cleanup;
}

// counter = AStarMapWidth * AStarMapHeight;


//#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!##!#!#!#!#!#!#!#!#!#!#!#!#!#!#
//////////////////////// MAIN LOOP ////////////////



// A* Algorithm.
// Begin search
//
while (OpenSetSize!=NULL) {
//
// Find the best node of from the open set
// OpenSet = List of Open Nodes
//
shortest = AStarFindMinimum(); //2.a.) FIND THE POSITION OF THE LOWEST F SCRE
x = OpenSet[shortest].X; //
y = OpenSet[shortest].Y; // (x,y) coordinates of shortest F SCORE node
o = OpenSet[shortest].O;

AStarRemoveMinimum(shortest); // 2.b.) Switch it to the closed list

//
// If we have reached the goal, then exit.
if (AStarMatrix[o].InGoal == 1) {
ex = x;
ey = y;
break;
}

#if 0
//
// If we have looked too long, then exit.
//
if (!counter--) {
//
// FIXME: Select a "good" point from the open set.
// Nearest point to goal.
AstarDebugPrint("way too long\n");
ret = PF_FAILED;
goto Cleanup;
}
#endif

//
// Generate successors of this node.

// Node that this node was generated from.
px = x - Heading2X[(int)AStarMatrix[x + AStarMapWidth * y].Direction]; // previous NODE x
py = y - Heading2Y[(int)AStarMatrix[x + AStarMapWidth * y].Direction]; // previous NODE y

// 2.c.)For each of the 8 squares adjacent to this current square …

for (i = 0; i < 8; ++i) {
ex = x + Heading2X; // NODE ADJACENT TO THE CURRENT NODE
ey = y + Heading2Y;

// Don't check the tile we came from, it's not going to be better
// Should reduce load on A*

if (ex == px && ey == py) {
continue;
}
//
// Outside the map or can't be entered.
//
if (ex < 0 || ex + tilesizex - 1 >= AStarMapWidth ||
ey < 0 || ey + tilesizey - 1 >= AStarMapHeight) {
continue;
}

// if the point is "move to"-able and
// if we have not reached this point before,
// or if we have a better path to it, we add it to open set


new_cost = CostMoveTo(ex, ey, data); // Cost to move to the adjacent node
if (new_cost == -1) {
// uncrossable tile
continue;
}
//## 2.c.1 ... if it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.

// Add a cost for walking to make paths more realistic for the user.
new_cost++;
eo = ey * AStarMapWidth + ex;
new_cost += AStarMatrix[o].CostFromStart;


if (AStarMatrix[eo].CostFromStart == 0) { // if G=0 or if current node.
// we are sure the current node has not been already visited
AStarMatrix[eo].CostFromStart = new_cost; // G-score
AStarMatrix[eo].Direction = i; //Direction
costToGoal = AStarCosts(ex, ey, gx, gy); // heuristic ( Current Node to Goal )
AStarMatrix[eo].CostToGoal = costToGoal; // copy heuristic
if (AStarAddNode(ex, ey, eo, AStarMatrix[eo].CostFromStart + costToGoal) == PF_FAILED) { // Calculate F Scores
ret = PF_FAILED;
goto Cleanup;
}
// we add the point to the close set
AStarAddToClose(eo);
} else if (new_cost < AStarMatrix[eo].CostFromStart) {
// Already visited node, but we have here a better path
// I know, it's redundant (but simpler like this)
AStarMatrix[eo].CostFromStart = new_cost; //G-Score
AStarMatrix[eo].Direction = i; // Direction
// this point might be already in the OpenSet

// IF THE NODE WAS FOUND, REPLACE THE OUTDATED NODE
j = AStarFindNode(eo); //find the node in the [OPEN SET] if it cannot find, return -1
if (j == -1) {
costToGoal = AStarCosts(ex, ey, gx, gy); // heuristic ( Current to the goal )
AStarMatrix[eo].CostToGoal = costToGoal; // copy heuristic ***
if (AStarAddNode(ex, ey, eo,
AStarMatrix[eo].CostFromStart + costToGoal) == PF_FAILED) { // Calculate F Scores
ret = PF_FAILED;
goto Cleanup;
}
} else {
costToGoal = AStarCosts(ex, ey, gx, gy); // heuristic ( Current node to the goal )
AStarMatrix[eo].CostToGoal = costToGoal; // Copy Heuristic
AStarReplaceNode(j, AStarMatrix[eo].CostFromStart + costToGoal); //Remove the outdated node and add the new cost
}
// we don't have to add this point to the close set
}
}
if (OpenSetSize <= 0) { // no new nodes generated [ 2.d.2
ret = PF_UNREACHABLE;
goto Cleanup;
}
}
/////////////////////////////////////////////////
///////////////////////////////////////////////// MAIN LOOP END ///////////////////////////////
path_length = AStarSavePath(sx, sy, ex, ey, path, pathlen);// 3.Save the path. Working backwards from the
// target square, go from each square to its
//parent square until you reach the starting square.
//That is your path.

ret = path_length;

Cleanup:
ProfileEnd("AStarFindPath");
return ret;
}
}




But can seem to find any good sources.

Anyone?

Thanks,
James

Share this post


Link to post
Share on other sites
Advertisement
IDA* has a lot more in common with depth-first search than with A*. In fact, the only major difference between IDDFS and IDA* is that it searches out to a particular g+h range (nodes with g+h value no higher than a particular limit), rather than a particular search depth (nodes no further than a particular number of edges from the start node). There's also a minor difference with how the limit is iterated. So I would not suggest starting with A* code and trying to add deepening to that... instead, read about IDDFS first, and then take another look at IDA*. It'll make a lot more sense then.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!