a* on 3d enviroment

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

Recommended Posts

Hello, I'm trying to implement A-Star Pahtfinding on 3D enviroment (triangles). I have a set of triangles (a triangle represents a NODE) with connections between them (neighbours) all setup and ok. Now, to make it more faster i've created a NxN matrice in wich i have precalculated distances between center's of the triangles (distances between nodes, i.e cost) and stored these distance in this "matrice" i've mentioned. (it is the 3d distance between two 3D points). Here is this function wich precalculates all the distances between nodes: (all working ok until now...)
void CAStarSearch::PrecalculateMatrix()
{
// get number of nodes from list
int counter = Oct.m_NavNodeList.size();

// allocate "NxN" grid of floats.
this->matrix = (float **)malloc(sizeof(float) * counter );
for(WORD x = 0; x<counter; x++)
{
matrix[x] = (float *)malloc(sizeof(float) * counter );
Oct.m_NavNodeList[x].m_ID = x;
}

// loop thru this grid of float's.
// for every column
for(WORD b=0; b<counter; b++)
{
// for every row
for(WORD a=0; a<counter; a++)
{

// if a==b this means that distance between nodes is zero (i.e same node).
// else the "matrix" will be filled with distances between nodes.
if(a == b) matrix[a] = 0;
else
// compute distance between nodes
matrix[a] = Oct.m_NavNodeList[a].m_Center.GetDistance( Oct.m_NavNodeList.m_Center );

}
}

// DisplayMatrix();
}


OK, now after that i'm trying to do 3d Pathfinding like so: (i've commented the lines to be more readable) 1) getting the G value (cost from ENTRY to current NODE):
float CAStarSearch::GetG(CNavNode* last_closednode, CNavNode *node)
{
// return distance from last_closednode to node ( and cumulate this in "ClosedListG" variabile. )
return ClosedListG += this->GetMatrixValue( last_closednode, node);
}


NOTE: i keep track and store in a global "ClosedListG" variable the SUM of distances starting grom ENTRY to current NODE. (ClosedListG = the distance from ENTRY to current node ) 2) getting the H value (cost from current NODE to EXIT node):
float CAStarSearch::GetH(CNavNode* current_opennode, CNavNode *target)
{
// return distance between current_opennode and target node.
return this->GetMatrixValue( current_opennode, target);
}


NOTE: this also just returns distance from "current_opennode" to "target" node looking up in "matrix" table . 3) given a (open) list of nodes , select the one with lowest cost "F" , assuming that all nodes in this list have F, G and H values calculated already:
CNavNode* CAStarSearch::GetLowestF(CNavNode *target)
{
list<CNavNode*>::iterator next = m_OpenList.begin();
// select first node on open.
CNavNode* SelectedNode = *next;

// loop thru all nodes in OPEN list.
for(list<CNavNode*>::iterator it = m_OpenList.begin(); it!=m_OpenList.end(); ++it)
{
// chosen = current item in open.
CNavNode* chosen = *it;

// get lowest value here.
if( chosen->m_F < SelectedNode->m_F)
{
// select this one because it has a LOW value than previous one.
SelectedNode = chosen;
}
}

return SelectedNode;
}


4) the A-Star seach function now:
void CAStarSearch::void CAStarSearch::FindPath(CVector3 *Start, CVector3 *Target)
{
// get current NODE for entry, result is stored in "entry" variable (entry = start position in nodes list)
CNavNode entry;
bool foundEntry = false;
Oct.FindNode(*Start, Oct.m_pRoot , entry , foundEntry );

// get current NODE for exit, result is stored in "exit" variable (exit = goal in nodes list)
CNavNode exit;
bool foundExit = false;
Oct.FindNode(*Target, Oct.m_pRoot , exit , foundExit );

// GetMatrixValue returns distance between 2 nodes. (all values have been precalculaded before
// entering this function - and stored in a "N x N" grid (of floats).
if(this->GetMatrixValue(&entry,&exit)==0) return;

// clear CLOSED list and OPEN list.
m_ClosedList.clear();
m_OpenList.clear();
// ClosedListG = path from ENTRY point to CURRENT node.
// (it is the G value from A-star, and represents distance from ENTRY point node to CURRENT node.
// For now ClosedListG is 0 ( it's value is computed and kept track in GetG() function )
this->ClosedListG = 0;

// add ENTRY yo CLOSED list.
m_ClosedList.push_back(&entry);

// add ENTRY's CONNECTIONS to OPEN list.
for(BYTE c=0; c<entry.m_NoConnections; c++)
{
entry.pConnection[c]->m_G = GetG(&entry, entry.pConnection[c]);
entry.pConnection[c]->m_H = GetH(entry.pConnection[c], &exit);
entry.pConnection[c]->m_F = entry.pConnection[c]->m_G + entry.pConnection[c]->m_H;
m_OpenList.push_back(entry.pConnection[c]);
}

// as long as OPEN list is NOT empty (0).
while(!m_OpenList.empty())
{
// select a NODE with lowest F value from OPEN list.
CNavNode *current = this->GetLowestF(&exit);

// have we reached exit (goal node) ??
if(this->GetMatrixValue(current ,&exit)==0) break;
else
{
// add current NODE to CLOSED list.
m_ClosedList.push_back(current);
// remove current NODE from OPEN list.
m_OpenList.remove(current);

// for every CONNECTION in current NODE.
for(BYTE c=0; c<current->m_NoConnections; c++)
{
// does it exist in OPEN list ? if YES -> skip
if(Exist(current->pConnection[c], m_OpenList)) continue;
// does it exist in CLOSED list ? if YES -> skip
if(Exist(current->pConnection[c], m_ClosedList)) continue;

// compute current's CONNECTION's -> F,G,H values.
current->pConnection[c]->m_G = GetG(current, current->pConnection[c]);
current->pConnection[c]->m_H = GetH(current->pConnection[c], &exit);
current->pConnection[c]->m_F = current->pConnection[c]->m_G + current->pConnection[c]->m_H;

// add above selected (low score) node to CLOSED list.
m_OpenList.push_back( current->pConnection[c] );
}
}
}

// used "nodez" variable here - just to display how many nodes were found when reached goal node.
extern int nodez;
nodez = m_ClosedList.size();

// draw all nodes in CLOSED list.
DrawClosedList();

}


NOTE: i call "FindPath" function every frame ! 5) and last function that checks if a node exists in list:
bool CAStarSearch::Exist( CNavNode *test_node, list<CNavNode *>lst )
{
// test if empty list
if(lst.size()==0) return false;
list<CNavNode*>::iterator it = lst.begin();
// loop thru all nodes in "lst"
while(it!=lst.end())
{
// check if equal here , if YES return true.
CNavNode *chosen = *it;
if(chosen == test_node) return true;

it++;
}

return false;
}


PROBLEMS: 1) Search time (from ENTRY to EXIT) is slow (if m_ClosedList has more than 3 to max 50 nodes - the FPS drops from 1400fps to 60fps). Is it because of the STL list functions wich are somekind slowing things down ?? What i'm doing wrong ? 2) Don't know if i'm using the correct algorithm/function for calculating H value (i.e. GetH()) . I just used DISTANCES from a node to another node for calculating this value (and stored them in "matrix" , i.e float distances between nodes). 3) I think i'm doing something wrong in A-Star Search Function because it seems that "m_ClosedList" ends with some nodes that DONT belong to path (this i think is due to the H value i've mentioned above). I know i've posted a lot of code and i appoligise for that !! (i could upload a screenshot but i dont know how...) Thank you , any sugestions will be apreciated. :) [Edited by - redbaseone on December 26, 2009 2:25:19 PM]

Share on other sites
Hi, you may want to place your code between the source tags (http://www.gamedev.net/community/forums/faq.asp#tags).

Share on other sites
Quote:
 Original post by leet bixHi, you may want to place your code between the source tags (http://www.gamedev.net/community/forums/faq.asp#tags).

all done. thank you.
please escuse me , im new to this forum. :)

Share on other sites
OK, seems that i've found the solution for PROBLEMS 2) and 3). The heuristic function works just fine!

I've missed that i have to recalculate the F,G,H for all the EXISTING nodes in OPEN list (for a certain step in FindPath - in the while loop).

Here is the function again corrected:

void CAStarSearch::FindPath(CVector3 *Start, CVector3 *Target){	// get current NODE for entry, result is stored in "entry" variable (entry = start position in nodes list)	CNavNode entry;	bool foundEntry = false;	Oct.FindNode(*Start, Oct.m_pRoot , entry , foundEntry );	// get current NODE for exit, result is stored in "exit" variable (exit = goal in nodes list)	CNavNode exit;	bool foundExit = false;	Oct.FindNode(*Target, Oct.m_pRoot , exit , foundExit );	// GetMatrixValue returns distance between 2 nodes. (all values have been precalculaded before 	// entering this function - and stored in a "N x N" grid (of floats).	if(this->GetMatrixValue(&entry,&exit)==0) return;		// clear CLOSED list and OPEN list.	m_ClosedList.clear();	m_OpenList.clear();	// ClosedListG = path from ENTRY point to CURRENT node. 	// (it is the G value from A-star, and represents distance from ENTRY point node to CURRENT node.	// For now ClosedListG is 0 ( it's value is computed and kept track in GetG() function )	this->ClosedListG = 0;	// add ENTRY yo CLOSED list.	m_ClosedList.push_back(&entry);	// add ENTRY's CONNECTIONS to OPEN list.	for(BYTE c=0; c<entry.m_NoConnections; c++)	{		entry.pConnection[c]->m_G = GetG(&entry, entry.pConnection[c], 0);		entry.pConnection[c]->m_H = GetH(entry.pConnection[c], &exit);		entry.pConnection[c]->m_F = entry.pConnection[c]->m_G + entry.pConnection[c]->m_H;		m_OpenList.push_back(entry.pConnection[c]);	}	int i=0;	// as long as OPEN list is NOT empty (0).	while(!m_OpenList.empty())	{		// select a NODE with lowest F value from OPEN list.		CNavNode *current = this->GetLowestF(&exit);						// have we reached exit (goal node) ??		if(this->GetMatrixValue(current ,&exit)==0) break;		else		{			// add current NODE to CLOSED list.			m_ClosedList.push_back(current);			// remove current NODE from OPEN list.			m_OpenList.remove(current);									// ******* FIX *************************************			// recalculate costs for EXISTING nodes in OPEN list.			for(list<CNavNode*>::iterator it = m_OpenList.begin(); it!=m_OpenList.end(); ++it)			{				// chosen = current item in open.				CNavNode* chosen = *it;				chosen->m_G = GetG(current, chosen, current->m_G );				chosen->m_H = GetH(chosen, &exit);				chosen->m_F = chosen->m_G + chosen->m_H;			}			// *************************************************			// for every CONNECTION in current NODE.			for(BYTE c=0; c<current->m_NoConnections; c++)			{				// does it exist in OPEN list ? if YES -> skip 				if(Exist(current->pConnection[c], m_OpenList)) continue;				// does it exist in CLOSED list ? if YES -> skip 				if(Exist(current->pConnection[c], m_ClosedList)) continue;				// compute current's CONNECTION's -> F,G,H values.				current->pConnection[c]->m_G = GetG(current, current->pConnection[c], current->m_G );				current->pConnection[c]->m_H = GetH(current->pConnection[c], &exit);				current->pConnection[c]->m_F = current->pConnection[c]->m_G + current->pConnection[c]->m_H;								// add above selected (low score) node to CLOSED list.				m_OpenList.push_back( current->pConnection[c] );			}					}			}		// used "nodez" variable here - just to display how many nodes were found when reached goal node.	extern int nodez;	nodez = m_ClosedList.size();	// draw all nodes in CLOSED list.	DrawClosedList();}

also, GetG() function modifies (not so much) :

float CAStarSearch::GetG(CNavNode* last_closednode, CNavNode *node, int LastNode_GValue){	// return distance from last_closednode to node ( and cumulate this in "ClosedListG" variabile. )	return this->GetMatrixValue( last_closednode, node)+LastNode_GValue;}

GetG() = takes one more parameter into account "LastNode_GValue" wich represents "last node"'s G Value (last NODE's G-value from CLOSED list).

The path is correctly generated now with the function above corected !!
(If you have any questions i'll gladly answer for how i've done that until now).

correct way:

other pics (some of them with not working algo'):
http://img707.imageshack.us/g/pathfinding2.jpg/

It remains just one problem : How do i make it faster ? STL::list is somekind slowing things down ? What should i do ? Please help ...

Share on other sites
Hi, I don't have the time to read all the code right now, but good job getting it to work! Persistence is important. You my want to consider replacing the std::list open list with a std::priority_queue or by using the heap functions.

Also, why are you running this every frame? Do you really need to? If you have enough memory to store a lookup table between each node do you have twice that much space (you'd be able to store a complete path lookup table if so)?

If you don't already know about it, you may want to take a look at AMD's free performance analyzing tool Code Analyst. It works with Intel CPUs too, but only certain features.

Share on other sites
Quote:
 How do i make it faster ? STL::list is somekind slowing things down ? What should i do ? Please help ...
What compiler/IDE are you using? Are you measuring the performance of a debug build, or a release build?

Also, if you're using Visual Studio and are using a release build, have you added the necessary preprocessor definitions to disable iterator debugging?

I didn't look at the code, but in many cases std::vector can be a faster/better solution than std::list for reasons having to do with cache coherency and how the memory is managed internally. There are quite a few ways A* can be made to run faster, but a good first step is simply to choose appropriate container types.

For what it's worth, I use std::vector along with the standard library's 'heap' functions (make_heap(), etc.) and have gotten good results (although the demands placed on the pathfinding code have been fairly light so far).

In summary:

1. Make sure you're testing with a release build.

2. If you're using Visual Studio, make sure iterator debugging is turned off.

3. Switch from list to vector if possible.

4. Profile to see where the time is being spent (maybe this should be step 3 :)

Share on other sites
Quote:
 Original post by Ken SHi, I don't have the time to read all the code right now, but good job getting it to work! Persistence is important. You my want to consider replacing the std::list open list with a std::priority_queue or by using the heap functions.Also, why are you running this every frame? Do you really need to? If you have enough memory to store a lookup table between each node do you have twice that much space (you'd be able to store a complete path lookup table if so)?If you don't already know about it, you may want to take a look at AMD's free performance analyzing tool Code Analyst. It works with Intel CPUs too, but only certain features.

First of all, please escuse me because my english is not very good. :)

Thank you for replying. Up until now i didn't used std::list so much, but they are useful at least in debug phase and not only for me here in this application. I will take a look to priority_queue and i'll be back with more info.

Regarding function callback - the function must be called at least 5 times per frame (this could speed things up a little). This is used because the "monster" constantly is searching for his "enemy" on the map.

As for memory requirements, i think u are very right.
If let's say i have a NavMesh with 5000 nodes this means i have a matrice wich holds distances between neighbours , and wich occupies: 5000x5000 x sizeof(float) = 5000 x 5000 x 4 = ~ 100MB if i'm not mistaken , wich is A LOT of memory waste !! :)

But, for now i dont have as much nodes in my application, and thank you for observing that and must find a way also for fixing that.
For now im concernig at speed and getting A-Star work right.

Thank you again !

Share on other sites
Quote:
 Original post by Ken SHi, I don't have the time to read all the code right now, but good job getting it to work! Persistence is important. You my want to consider replacing the std::list open list with a std::priority_queue or by using the heap functions.Also, why are you running this every frame? Do you really need to? If you have enough memory to store a lookup table between each node do you have twice that much space (you'd be able to store a complete path lookup table if so)?If you don't already know about it, you may want to take a look at AMD's free performance analyzing tool Code Analyst. It works with Intel CPUs too, but only certain features.

First of all, please escuse me because my english is not very good. :)

Thank you for replying. Up until now i didn't used std::list so much, but they are useful at least in debug phase and not only for me here in this application. I will take a look to priority_queue and i'll be back with more info.

Regarding function callback - the function must be called at least 5 times per frame (this could speed things up a little). This is used because the "monster" constantly is searching for his "enemy" on the map.

As for memory requirements, i think u are very right.
If let's say i have a NavMesh with 5000 nodes this means i have a matrice wich holds distances between neighbours , and wich occupies: 5000x5000 x sizeof(float) = 5000 x 5000 x 4 = ~ 100MB if i'm not mistaken , wich is A LOT of memory waste !! :)

But, for now i dont have as much nodes in my application, and thank you for observing that and must find a way also for fixing that.
For now im concernig at speed and getting A-Star work right.

Thank you again !

Share on other sites
Quote:
 Original post by jykIn summary:1. Make sure you're testing with a release build.2. If you're using Visual Studio, make sure iterator debugging is turned off.3. Switch from list to vector if possible.4. Profile to see where the time is being spent (maybe this should be step 3 :)

Thank you for reply ! :)
I will run a benchmark now to see where the bottlenecks are ... :)
Im using MSVC , debug build, preprocessor definitions to disable iterator debugging are ENABLED . will turn this off and see what results will came up.

Share on other sites
Quote:
 I will run a benchmark now to see where the bottlenecks are ... :)Im using MSVC , debug build, preprocessor definitions to disable iterator debugging are ENABLED . will turn this off and see what results will came up.
Just to be clear, you should try benchmarking using *release* build, and with iterator debugging *disabled*. To disable iterator debugging, you need to add two preprocessor definitions at the project level; if I'm not mistaken, the definitions you need to add are _SCL_SECURE=0 and _HAS_ITERATOR_DEBUGGING=0.

Maybe that's what you intend, or are already doing - I guess 'preprocessor definitions to disable iterator debugger are ENABLED' is the same as iterator debugging being disabled :)

Anyway, before jumping to any conclusions about performance, make sure you're in release mode and that iterator debugging is off; then, if the performance is still not satisfactory, profile to determine where the bottlenecks are.

Share on other sites
If you haven't already implemented a simpler algorithm, like Dijkstra's algorithm, I'd recommend doing that first. A* is a complex algorithm so it can really help to have a good understanding of the more basic algorithms.

You might also want to look into the fringe search algorithm. It's simpler than A* and can perform almost as well (or better); in fact, it will probably perform better than your current A* implementation because A* requires a bunch of optimizations to perform well.

One big A* optimization is to avoid scanning the open and closed lists to determine if a node is on them. You can keep track of which list the node is on within the node itself (only takes a few bits of memory per node, just be sure to clear this out between searches).

Share on other sites
thanks for all your replies !!!
ill do some testing as soon as possible and return.
you gave me some starting points and i appreciate that ! :)

Share on other sites
Well , seems that iterating thru' list (used CodeAnalyst) eats lot of time in my app., when debug mode is on.

After that, I've made the test with _SCL_SECURE=0 and _HAS_ITERATOR_DEBUGGING=0 as you suggested, application being build on RELEASE mode.
The restult was that the FPS rised up from 140fps to 520fps. That's almost 4 times faster.

(still, loosing ~ 800 - 900fps on the fly...maybe priority queue will help next)
Note that, i have not YET implemeted priority queue. :)

Many thanks again, and i'll return with more results, giving a try to fringe search algorithm and/or priority queue in last instance...and i'll post code later.

Share on other sites
fps is not a linear measure of performance. A drop from 1000 to 500 fps is approximately the same as a drop from 500 to 333 fps, or 111 to 100 fps, or 60 to 56 fps. In each of these examples, the difference in run time is about 1 millisecond.

1400 fps = .7 ms
520 fps = 1.9 ms
140 fps = 7 ms

That 900 fps you're losing is caused by approximately 1.2 ms of processing. If you made your algorithm 4 times faster, you would get approximately 1000 fps. Except that the 1400 fps number was from debug mode, so it doesn't really mean anything...

So anyway...it's better to time your code than use your fps counter.

And measuring performance in debug mode is meaningless. Complex but highly optimizable code, like STL containers, will tend to run very slowly in debug mode but very quickly in release mode.

Share on other sites

If your number of nodes (triangles) gets very large then your NxN table will get huge. Having their distance from target value probably does speed things up a little though simpler distance tests like larger of the X and Y deltas can often work alsmost as well.

Also since you have a NxN table anyway (and if your node count isnt too large) you could precalculate all paths once offline (using brute a force method) and simply have the table contain the next node to move to going towards the desired target.

Director[currentnode][targetnode]

That would speed things up alot because now you dont even have to do A* at runtime.