Archived

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

Path Find algorithm help please.!!

This topic is 5669 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

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? "

Ionware Productions - Games and Game Tools Development

Share this post


Link to post
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

Share this post


Link to post
Share on other sites