..lesson 1 and 2 together in action..

[Naughty Alien]

..okay, recently i have noted you folks about navigation grid generator used for path search..so today i have finished optimized A-Star algo, using that grid for search. Algo can be easy switch to behave as Djikstra if you want that. Its incredibly fast thanks to navigation grid because loads of parenting and calculations are done during grid generation and stored as a data already so path search algo doesn't waste time on unnecessary calculus..here are some small shots, both in action and connected...so now just text/description left to do..

 

 

 

 

 

..once tutorial description(pdf text) done, somebody owe me coffe and LE T-Shirt

[Pixel Perfect]

Its incredibly fast thanks to navigation grid because loads of parenting and calculations are done during grid generation and stored as a data already so path search algo doesn't waste time on unnecessary calculus

 

Looking good NA. What sort of range of search times are you getting on average in mS?

[Naughty Alien]

..i have tested on my 7600GT low end test rig (5 years old machine), 20 000 nodes and returned path took about 2.1ms

[VeTaL]

Its incredibly fast thanks to navigation grid because loads of parenting and calculations are done during grid generation and stored as a data already so path search algo doesn't waste time on unnecessary calculus..

 

Thats pretty good solution: i worked with the same idea in Gamestudio (just additional information):

http://www.opserver.de/coni_users/web_users/pirvu/aum/aum27/english/aum27/code.html

http://www.opserver.de/coni_users/web_users/pirvu/aum/aum28/english/aum28/code.html

http://www.opserver.de/coni_users/web_users/pirvu/aum/aum29/english/aum29/code.html

http://www.opserver.de/coni_users/web_users/pirvu/aum/aum30/english/aum30/code.html

http://www.opserver.de/coni_users/web_users/pirvu/aum/aum31/english/aum31/code.html

[Pixel Perfect]

..i have tested on my 7600GT low end test rig (5 years old machine), 20 000 nodes and returned path took about 2.1ms

Yeah, that sounds about right. On my system I'm getting sub millisecond response on average with some extending up to 4ms on a 40000 node grid.

 

I've not come accross that series of articles before VeTal, thanks for posting the links. Always interesting looking at how others have designed their systems.

[Naughty Alien]

..tested just now on 8600GT rig, 30 000 nodes..cant get any value..it appears to be under 1 ms, whats excellent

[Sooshi]

Thanks NA, and you too VeTal

[VeTaL]

You're welcome: i have some experience with such algorithms, so i'm glad that i can help

[Pixel Perfect]

I didn't pick up on this earlier NA but I thought you had indicated in a previous post you were running the searches on the GPU yet your speeds seem comparable with mine running on the CPU. Are you not using the GPU then?

[Sooshi]

You're welcome: i have some experience with such algorithms, so i'm glad that i can help

 

Hey VeTal, I have just followed everything in your tutorial, very nice! There are some things I didnt know that I have added to my own workflow, thanks a lot!

 

And I cant wait for your lessons as well NA

[VeTaL]

I'm very glad that you liked them, but they are not mine lessons

This is monthly magazine of 3dgamestudio, called AUM, i also had learned by those tutorials and i found them very usefull, so i decided to share links now

 

Are you not using the GPU then?

If Naughty Alien's algorithm is close to algorithm from tutorials (i think so because of his phrase "calculations are done during grid generation", but i'm not sure), then it doesnt use neither GPU nor CPU during gameplay.

 

Short summary of those tutorials:

1) first, before game launched a special script runs and creates a large matrix, which consists of paths from each node to each node, this matrix saved to file (it can take some time, but no matter for end user).

2) then, when game started, user just requests "how can i get from node A to node X?" and engine looks into matrix and get only one variable from matrix (this is all work of CPU) and answers "matrix says that you can get from node A to node X through node G, H and L".

 

Thats all, but, as i said, i'm not sure that Naughty Alien use the same algorithm, but anyway, its very usefull.

[macklebee]

Looks great NA, cannot wait to see this in action. Appreciate the hard work and detail you have been putting in to all this for the community. Thanks and do you like your coffee with one or two lumps? what size t-shirt?

[Pixel Perfect]

If Naughty Alien's algorithm is close to algorithm from tutorials (i think so because of his phrase "calculations are done during grid generation", but i'm not sure), then it doesnt use neither GPU nor CPU during gameplay.

I think he was just referring to all of the node distance calculations. You can only really use the matrix method you are referring to with static geometry where you effectively pre-calculate all of the node paths and simply read them in ... very fast but useless for dynamic object avoidance. For that the nodes need to be updated in real time and the path finding done on the fly!

 

My system certainly works on that basis although everything that can be precalculated is! I guess we need NA to enlighten us a bit more on how his does! The tutorial will reveal this no doubt

[Naughty Alien]

hi guys...these lessons using CPU only...however, similar algo i have plugged in to GPU trough OpenCL, so in my game actual thing is executed on GPU(calculation and path returned) and its blowing away comparisons i have mentioned here..its just supercomputing fast ..but this lessons Im presenting here, are VERY fast having in mind its CPU..last night i have added new grouping algo over grid so A-star will look for bigger searcheable blocks and cut off what is not important(means cut off larger portions of nodes), so speed up is insane, and its still main CPU..now on my 7600GT rig im getting under 1 ms over 35000 nodes..with such speed is entirely usable in games with no problems at all..eventuall after i release lessons, if people likes it, i may consider lesson of porting thing for GPU execution..will see..T-Shirt+coffe

[macklebee]

sweet... sounds amazing NA. cannot wait to see this... and you bring up a good point, where's the Leadwerks gift shop with coffee mugs, T-shirts, hats, and dog collars? i see a new business possibility

[Naughty Alien]

..hhehe...well..I think Josh had some T-shirts and coffe mugs I dont know whats happen now I hope it they re appear, Tshirt will be something usable actually

[Rick]

I thought navmeshes were the way to go with pathfinding these days?

[Naughty Alien]

..grid generator exposed here works almost identically like navmeshes, only difference is nodes generation itself based on navmesh itself(navmesh use its edges / vertices, while im using nicely balanced nodes)

[Rick]

Yeah, but navmeshes are supposed to be faster right? Since you have less quads than you would waypoints. I would think the bigger your area gets the way worse performance it has with waypoints vs a navmesh. This is good, don't get me wrong, but it seems currently today most games use navmeshes.

[macklebee]

i await your tutorial then rick... oh thats right...

[Rick]

I was just curious as to why he didn't use navmeshes as that seems to be what games are going to these days. I said this is good, was just curious. Seems we can't question anything these days without getting people all bent out of shape.

[Naughty Alien]

Yeah, but navmeshes are supposed to be faster right? Since you have less quads than you would waypoints. I would think the bigger your area gets the way worse performance it has with waypoints vs a navmesh. This is good, don't get me wrong, but it seems currently today most games use navmeshes.

 

..but my grid generator IS actually Navmesh lets see how nav mesh works, right?

 

Basically, a "navigation mesh" is a logical graph of convex regions that defines where a computer-controlled character is allowed to move. Often these regions are a lower-resolution version of the model of the floor on which the game's characters walk. The character can move anywhere inside the physical boundaries defined by the regions, and the accompanying graph can be used with various algorithms, such as the A* algorithm, to solve paths which can, in turn, be used by a AI algorithms to help decide how the character should react to its environment. For example, consider a room that has some obstacles in it as in the image below.

 

 

The navigation mesh for this room might look like the left-most image below. We break up the floor of the room into a set of convex regions that border each other. These regions are organized as a graph, as shown in the right-most image below, which can be used in search algorithms such as A* or Breadth-First to very quickly find ideal paths from one region to any other region. For example, the path that results of a Breadth-First search from A to L would probably be {A, B, C, D, O, F, L}.

 

 

The whole idea here is that we've taken the very complex problem of moving a character across a complex level, and we've reduced it to the generally very simple problem of moving a character in a straight line between two touching convex regions. However, the main problem with navigation meshes is that they're hard to construct. You'll usually build the polgyons manually in a 3D editor, or generate the mesh automaticaly from the game models themselves, and then you still have to build the graph. GRAPH, thats key

 

And thats what grid generator does in tutorial i have exposed, generating graph with nodes over nav mesh instead just convex regions border each other. Why? Because grid generator output will be not just walkable areas but also NON walkable areas obscured by level geometry loaded later and also eventually updated in runtime. All those data are ready to use for search algo with no checking but result path..its fast..very very fast..so, it is actually navmesh, with more data filled in to it, rather than just consider convex regions. Most important, Convex regions connected to each other, may be VERY messy because u cant get always nicely balanced triangulation on custom geometry, there is NO WAY, without loosing edges. and your convex regions in navmesh depend on it (means navigation itself), on other side, my grid generator will 'equalize' entire navmesh area and deliver balanced graph with precalculated data accurately set for exact nav mesh, necessary for very fast search(what raw navmesh convex regions use too anyway)..

 

P.S.

Grid generator also doesnt require any additional work once initiated(only 1 code line) while for raw navmesh you have to manually set some quads. And i still do believe, pivots(grid generator using it) are faster than quads, so performance cant be worse with expansion..

[Rick]

Nice explanation. That's kind of what I was looking for. I still can't understand how using something like A* would be faster with waypoints than navmeshes though. Generally you have less quads in a navmesh than you do waypoints which means less data to go through to find the path.

 

The room you constructed has 15 quads, but it would most likely have way more waypoints, which means more points to check against right? It does seem that navmeshes require additional work like dynamic object avoidance for dynamic scenes and spline movement to make moving look more natural. I would think the spline would still be desired for waypoints, but waypoints does have the benefit of being a build in dynamic scene avoider.

 

Do you think combining navmesh with waypoints would yield even better results? The first check could be just the quads to find the quad path. Then the next check would be only the waypoints within the quad path. That seems like it might help break down very large areas.

 

 

[edit]

Did you mention if the path is returned in one call or can it be spread out over a few cycles to ease the burden on the cpu? I've always read that's how some of the RTS games did this. I remember games like Age of Empires where when you told a unit where to go there was a 1 second animation of the unit saying "OK" before he actually moved. I read somewhere that was to hide the fact that the pathfinding was spread out over a few cycles so as to not have any noticeable fps hit.

[Naughty Alien]

..well.whole point is, that navmesh output is a graph based on convex regions, and its fixed..in my tutorial, principle is SAME, i do generate also grid out of navmesh BUT i control how many grid elements will be spitted out and also even then, graph will be scaled down if not fitting navmesh area properly and balanced properly over entire navmesh area so you cant see concentration points like you can see in original navmesh grid because of unbalanced triangulation, so you need to fill more triangles in order to get it right, and that means more and more graph nodes. At the end navmesh need to use grid search algo and there is no escape from that. So its same. Difference is that my grid system setting for you walkable zones out of box and NON walkable based on actual level(not navmesh) whats very cool. All your a-star need to look is walkability over grid/children(heck, doesnt have to even check parenting because its already in grid generator, what usually a-star NEED to do)..thats why its very fast...if you create on the top of that global node zones,and checking that first, its possible to cut of hundreds and hundreds of nodes just in one pass..its insane speed boost..Grid generator extract for you everything in one line of code, and its all in there, ready to use..and also you can change it on runtime if some physics obstacle appear (thats happen over result path node check)..so for entire grid, all you need is this:

 

GRID:TGrid = TGrid.Create(50, 50, 2, vec3(-50, 10, 50), "navMesh.gmf",, "level.gmf")

 

and u are set..

[Rick]

Difference is that my grid system setting for you walkable zones out of box and NON walkable based on actual level(not navmesh) whats very cool.

 

Is there a way to handle walking weights? For example moving through a swamp type land would be slower than just going around it? Are we able to select an individual waypoint and modify some kind of settings for it? Or maybe but some kind of special meshes in our scene that when the grid is generated it automatically does this, but the mesh would be invisible at game runtime. Just curious on the flexibility this has.

 

In the 3rd picture on your first post, what's the crazy zig zag going on there? I assume the dark blue is the path that was found, and in that 3rd picture it looks like a few straight lines would be desired instead.

 

I guess I still don't get how waypoints would be faster than navmesh when it comes to running A* against it. Less nodes to cycle through should equal faster right? I would think, everything I've read and seen, shows you would have less quads than waypoints. Don't get me wrong I'm interesting in trying to figure out why you say this would be faster than navmesh, but all the literature I've read state that using quad navmesh is the way to go over waypoints, so it'll just take erasing all that for me to understand where you are coming from.

 

 

[EDIT]

NA, I hope you don't take my questions in a negative way. I'm simply trying to understand your method and your reasoning for it. I don't mean any disrespect.