• What is your GameDev Story?

Archived

This topic is now archived and is closed to further replies.

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

Recommended Posts

I''ve read the Gamasutra''s article "Smart Pathfinding" and I''m just asking for a help in this example: {Dijkstra''s Algorithm pseudo code) priority queue Open DijkstraSearch node n, n'', s s.cost = 0 s.parent = null // s is a node for the start push s on Open while Open is not empty pop node n from Open // n has lowest cost in Open if n is a goal node construct path return success for each successor n'' of n newcost = n.cost + cost(n,n'') if n'' is in Open and n''.cost < = newcost continue n''.parent = n n''.cost = newcost if n'' is not yet in Open push n'' on Open return failure // if no path found Implementation (C++):

// Node succesors are as follows: (N - node)

//  0 1 2

//  7 N 3

//  6 5 4

bool CDijkstraSearch::FindPath(CMap *map)
{
FILE *file;

CNode *succesor = NULL;
CNode *temp = NULL;
int NewCost = -100;

Restart(map);   // cleans map (sets all nodes to  STATUS_OPEN

Start->Cost = 0;
Start->pParent = NULL;
Open.Push(Start);

while(!Open.IsEmpty())
{
temp = Open.Pop();

if(temp == Destination)
{
Destination->pParent = temp;
ShowPath();
return true;
}
for (int i=0; i<8; i++) //8 surrounding succesors

{
succesor = GetSuccesor(temp, i, map);

if(succesor!=NULL)
{
if(succesor->Status !=STATUS_VISITED && succesor->X < map->MapSizeX && succesor->Y < map->MapSizeY )
{
if(succesor->X  == Destination->X  && succesor->Y == Destination->Y)
{
Destination->pParent = temp;
ShowPath();
return true;
}

NewCost = temp->Cost + GetCost(temp, succesor);

if(Open.FindNode(succesor))
{
if(succesor->Cost <=NewCost)
{
succesor->pParent = temp;
succesor->Cost = NewCost;
Open.Push(succesor);
}
}
else
{
succesor->pParent = temp;
Open.Push(succesor);
}
}
}
}
fclose(file);
}

return false;
}

My question is : how do I do the GetCost(Node1, Node2) function? Or how basically it calculates the cost of the cost from getting from node1 to node2? Thanks. " Do we need us? "

Share on other sites
Well the simplest answer is using the Manhatten distance, which is the direct distance from node 1 to node 2. i.e. node2 - node1 (where they are both vectors stating the position of the nodes). Other effects can be taken into account, such as the type of terrain connecting the two nodes (mountains cost more to traverse than sport tracks), the other agents around that terrain (the more agents, the harder to walk fast in a straight line), the kind of agents (enemy soldiers or friendly villagers) and so on. You have to build up a heuristic for overall calculation that takes into account all the various aspects you deem important in deciding how good that piece of the path is.
This is more complex if the nodes aren''t just points, i.e. they''re areas of the world, but using common sense you can come up with _a_ heuristic and if it does the job you want then that''s all you need.

Mike

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 9
• Forum Statistics

• Total Topics
634085
• Total Posts
3015407
×