Hey, i have run into a bit of a preformance issue with my calculation of the adjacency node generation, to set them up in my code for about 4096 nodes it takes about 10 seconds, each node can have a maximum of 9 other nodes as an adjacency, eg, left, diagional upper left, up ect ect. I have set it up as a multi dimensional array of my definition of a Node. the map is broken up to [64][64]. there are walls in the map and i have it to only place adjacenceys at positions that arnt walls. I have two for loops for setting the nodes, one for 1st off reading in the map layout and flagging "sectors" as walls or free space, this is a fast process, in the next for loop based off this data i search for adjacent nodes, here is an extract showing what i'm doing.:

for( int y = 0; y < 64; y ++ )
{
    for( int x = 0; x < 64; x ++ )
    {
       //! Automaticly Add Adjaccent Nodes !//
       if(! mAStar->maplvl[x - 1] [y].isWall )
       {	
	   std::stringstream msgNode2;
           getLogSys()->log( msgNode2 );
           //! Get The Node at this offset from current Node !//
	   adjacentNode = mAStar->getNearestNode( mapPosition );
	   mAStar->setAdjacentNode( NodeID, adjacentNode );
       }
......

for each direction comming off that node is a if statement like the one above, where x and y are the current position of the node, and - 1 is the offset from the current node this all works great. but is slow :( getNearestNode is a basic function getting the closest node to any vector3 specified, setAdjacentNode is getting the nodeID and adding the adjacent nodes to a vector list. now in theory off a map with no walls, 64 * 64 = 4096 * the number of possibel adjacencies per node (9) that gives us 36864 calculations it needs to compute. somehow this is taking around 10-15 seconds to calculate. I think the reason for this slow preformance is that every time the if statement as the one above is entered it searches through everysingle node on the list until it gets to the node that it wants, like the one above it, if this is true; i need to as i go along calculating the adjancies i need to omit nodes from the list to search for adjacncies, like i mean if it were up to node 2500, we dont need to search for the node at the start; 1. so as i search for nodes i am constantly making the list smaller. Just posting here to get some advice on this matter and does my theory in the above paragraph sound accurate for the preformance problem?. cheerz & thankz 4 reading. [Edited by - Twinsen2 on July 26, 2006 8:32:41 AM]

Profile your code to find the part that is taking most of the time, then work on optimizing that section of code (either by speeding it up or removing the need for it).

I would guess one slowdown is constructing a stringstream 4096 * 8 = 32768 times and then logging an equal number of times. Also, why do you say you can have up to 9 adjecent nodes? In a square grid, each square only has 8 neighbors, and it doesn't seem useful for a square to be considered adjecent to itself.

Really, though, why do you need separate adjecancy information if your map is tile-based? Couldn't you just do something like
if(Map[Tile.X-1][Tile.Y-1] != Wall) {OpenList.insert(Coordinate(Tile.X-1, Tile.Y-1));}
Inside your A* search? It'd not only allow you to entirely skip your setup loop, but it would also eliminate a ton of data and probably improve cache coherency, resulting in a significant speedup.

Thankz for ur help man, i indeed removed the logging system & slowly but surely tested the preformance of each line of code and thankfully i found the slow down, in the function call getNearestNode, it searches through the list of every node for a close one and then preforms some distance calculations, this was the culprit, stupid thou, because i knew were every node was so i didnt have to search for the nearest node, i just put in the nodes position automaticlly and the initalization of the map was near instant.
Sorry for the above, i did infact mean 8 possible adjacent nodes not 9.

I took ur advice and modified the a* implementation for all this to be done in the a* setup and add them to the open list.

end result a massive speed improvment & a more better structured code layout, thier is no longer any noticable lag of initalization :D :D/
thankz once again.

A question;

How do you know where the nodes are, without performing a distance check?

My thought would be to use a quadtree, that is aware of nearby pathfinding nodes - and choose from these.

Quote: Original post by Rasmadrak
How do you know where the nodes are, without performing a distance check?

The original poster appears to be using a simple grid map. The distance and position is implied by the structure.