Need help optimizing nodegraph

hi community,



i have a problem, and i might need a good idea here.

i've implemented an improved-for-my-landscape-a* algorithm. to enable the bots to walk between obstacles, i've increased the resolution of the nodes. every ground quad (ok, 2 triangles) is prepresented by 4 nodes. if there is anything in the bounding box around the node, the node is marked as unwalkable (in my case i simply grid[x][y] = null it).

i'd like to increase the resolution even move, to about 16 nodes per ground quad. this would kill both the performance and the vm itself during startup except for 64 bit machines with lots of ram.



since my landscape is made out of wide open areas with some small blocked spots, i thought i could replace a "walkable node cluster" of lets say 9, 16 or 25 (or even more) by a single node, but how to do it? which condition(s) must be met to replace 9 nodes with one without accidently destroying an important part of the graph?

Why must be the node-graph based on a regular grid? It doesn't. If you place nodes (randomly) and they are walkable, they will do the job nevertheless. A* works on a list of nodes instead of grid too. So, instead of zilion possible nodes, you can have nodes only where they are necessary. On large open terrain either make the nodes a quad-tree or just place nodes on important spots, and collect them into a list, or a combination of the two.



For managing nodes i had several strategies. It is safe to join two adjacent smaller nodes into a bigger one, if from any point inside first node, any point in the nodes connected to second node can be reached, and vice versa. It is like a visibility test, but considering if the terrain is not too steep, and is still walkable. If you have unreachable parts, or parts where the bots don't go, unused nodes can be selected by simulating routes (or just playing the game, and collecting usage data). If the simulation gives that some nodes are never used, they can be removed, so there will be less nodes to manage, and also less nodes which A* needs to check.



Hope this helps.

If you use a grid, you can start at a node, and then expand a square from that node. Assume you're walking grid points from left/bottom, then take next unexamined grid point, grow a square up/right from that until you hit something unwalkable, and use the largest walkable square you found for that node. Repeat until all nodes are covered. Note that a square larger than 1:1 will have more neighbor squares, so the connectivity becomes harder (and cost may vary).

have you read some of the gamasutra articles - there is a good one on paths



follow http://www.gamasutra.com/features/20010322/terrano_01.htm then you should find it from a link

small explanation on how one path engine in Java does it(jkilavuz):



http://www.jkilavuz.com/doc/tutorial/tutorial.html

the name is so funny i almost want to use it  XD

but too late. my pathfinder works fine

HamsterofDeath said:

my solution was to optimize the algorithm (binary heap o/ instead of sorted list and a few other things) so that it only takes < 1 seconds to find a path instead of 6-8 and to notice there is no need to increase the node resolution any further. ;)


Share with us, what else did you change besides using binary heap.. i am interested :)
Or were other bits too small and insignificant?

i could achive a little speedup by using precalculated values instead of calculating the path cost from node to node each time. for the grid, i'm using a simple

if myX!=otherX && myY!=otherY return 14andsoon (10000*squareroot of 2) else return 10000;



also, i use arrays instead of lists where possible -> faster read & write access

You are not calling this line very often are you? That squareroot scares me :slight_smile:



Anyways… yes, I am using arrays also, only ints everywhere, no floats, work squared…



Btw whats the number of nodes you can path through with relatively decent time? I am trying to think of what size of map to go for. Also - do you use different path precision for different parts of the map or is it uniform?

The sqrt of 2 is something he is probably precalculating. :slight_smile:

i totally went all out and precalculated the value of 10000*Math.sqrt(2) and stored it into an integer

Are you using the pathfinder for all of the enemy bots in game? if so, how often do you run each bots path finding algorithm and how are you limiting it?



Also, are you limiting the distance that can be set as the destination?

there are no limits, but in most cases the enemies can see the player and reach him directly or almost directly so i can skip most of the pathfinding stuff.

I meant more along the lines of, if a bot is on the other side of the map, are they still running pathfinder algorithms or does your bot setup have LOD dithering for the pathfinding?