..lesson 1 and 2 together in action..

[Naughty Alien]

..its entirely possible to add some weighting (its not included in lesson), trough heuristics so it can do exactly what you want. Crazy zig-zags are due fact that closer node in search was marked as non available because of alignement of node(uneven terrain). Thats why vertical offset is there, i just didnt used it in order to test how 'smart' algo is and is it going to get alternate route. As for waypoints..navmesh output is also walkable node list and its nothing but list of waypoints and final list is not part of cycling, its returned as a result. As for quads, its not about quads but their convex regions connected to each other, and that means parenting is important in order to know what is connected with what. Grid generator provide that easy, without necessity to render out a thing since everything is just a pivots. Try load 100 000 quads and try same with 100 000 pivots and let me know how renderer will like it, or memory for that matter. Each quad is eventually 4 nodes anyway, soo..and A-star in lesson is MODIFIED A-star, means there is no closed or open list, there is no processing wasted on seeking and defining parents, nothing..just plain look up over grid data what in worse can be 8 nodes(diagonal movement) and even less if you know in advance parent of each child and each child as a parent node structure without seeking that. Now, organize those nodes in to larger blocks and check those blocks against heuristics and you will be able to cut off MASSIVE amount of already minimized search steps. Its really fast..on my crappy 1.8 GHz machine i cant any ms value..its below 1ms...insanely fast..

[Naughty Alien]

[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.

 

dont worry man..im very humble creature, and i like when people critisizing on constructive way, and to me, I see nothing wrong with your posts but positive impulse and discussion leading to maybe even something I have missed, really..so no problem man..if u closer ill call for a drink

[Rick]

Thanks for taking the time to explain this. Your 1 line example seems to be in BMax. Did you say if you were going to release this for C++ too? I would be interested in checking this out.

 

Also that one line of code you have showed how to create the grid. I assume we just pass in 2 points (start/end) and we'd get back a list of pivots/points to travel along?

[Naughty Alien]

..no problems at all Rick..idea about algo is to use less engine commands as possible, and commands used should be natural part of any renderer, so it can be easy to plug anywhere..Bmax is language of choice i mentioned at begining because entire OpenCL port of system i use in my game is done in Bmax too. But once you see code, it will be really easy to convert since i have broke down every single execution step in to its own method, but i can convert to C++ and post it, no problem with that too..here is description of initial command:

 

GRID:TGrid = TGrid.Create(gridXsize:Int, gridZsize:Int, nodeDistance:Float, startExpansionPosition:TVec3, navMeshFileName:String,verticalOffset:Float, levelFileName:String)

 

gridXsize = number of navmesh nodes generated on X axis

gridZsize = number of navmesh nodes generated on Z axis

nodeDistance = distance between generated nodes at initial stage (unbiased)

startExpansionPosition = point from where nodes creation expand over navmesh surface

navMeshFileName = navMesh file name to be loaded

verticalOffset = offset for each node, determining how accurate node grouping will be based on terrain slopes

levelFileName = actual game level to be loaded for sake of adjusting availability of nodes based on real game level data and accuracy

 

so, first 3 parameters will determine how density you want your node structure to be..and its very flexible..for more complex levels you will just increase it and have very accurate navigation..as for areas with less comples structure, just use smaller density and you are set..

 

in your main game loop, you will have your walkable node list just like this. before main loop (init stage):

Global ShortestPath:int[]
Global Path:TAstar = TAstar.Create(GRID)

 

and in main loop you can assign array of result nodes like this:

 

ShortestPath=Path.update(source,target);

 

note that you can create as many as you want TAstar objects, and each of them use same grid and changing grid content in runtime, so other TAstar objects will be avared of it and avoid taken nodes..

[Pixel Perfect]

You can argue the pros and cons of path finding systems all day but in the end all most people want is something that works and works adequately well. I have already demoed my system which is essentially not dissimilar to Naughty Alien's as it too is a hierarchical grid based system and you can see it works well. There is always room for refinement in these systems but once you have a basic working system in place you can spend your own time working on that!

 

It's excellent of Naughty Alien to take the time out to do this and undoubtedly many will benefit from it.

[Rick]

Yeah, I'm not trying to argue really. Just trying to get an explanation of his method and why he thinks it's better than another method. I've been looking at navmeshes since that's the buzz word in the game industry for pathfinding these days. So when NA comes out with this and it's not quad navmesh oriented I was just trying to get information about it to see if this would be an option vs trying to get my own quad navmesh going. I love that he's done this for the community, but that shouldn't mean someone can't ask questions about it or challenge it to get more information about it. That should be a healthy thing for any of us to do with anything as long as it's not done in a negative manor. That's my view on it anyway. When my component editor comes out I expect tons of questions and challenges about why I think people should use it. Like NA said, and I love his attitude on this, it might help one find any holes or suggestions.

 

Keep up the good work NA!

[Pixel Perfect]

Yeah, I wasn't criticising you Rick, I was just pointing out that the majority of people don't care or even want to know the detail of what’s going on behind the scenes, so long as it works. I personally believe there are some definite advantages to nav mesh based systems and Recast as an example demonstrates many of those but they are not really essential in order to get a basic game up and running. If you already realise you have a need specifically for a nav mesh system then you are probably capable of integrating or writing one yourself and don't need someone else to do it for you. I went for the hierarchical grid based system because it seemed easier to implement especially when you have never done anything like this before. I suspect that NA probably did as well.

[Rick]

Yeah, good point. I will be studying the code release to see if I can make a component with it. This seems perfect in that it generates for you around your map automatically and would be a good fit for such a component.

[Naughty Alien]

Yeah, I wasn't criticising you Rick, I was just pointing out that the majority of people don't care or even want to know the detail of what’s going on behind the scenes, so long as it works. I personally believe there are some definite advantages to nav mesh based systems and Recast as an example demonstrates many of those but they are not really essential in order to get a basic game up and running. If you already realise you have a need specifically for a nav mesh system then you are probably capable of integrating or writing one yourself and don't need someone else to do it for you. I went for the hierarchical grid based system because it seemed easier to implement especially when you have never done anything like this before. I suspect that NA probably did as well.

 

well..every system has some advantages..but from my personal set of tests, i realized that navmesh has no real advantage over well organized grid system generated from navmesh. Amount of control you have in case of use such grid system compared to navmesh only is massive. Also, search speed can be controlled directly by heuristics and grid size. Such changes on navmesh itself require new navmesh and its a lot of work. Bottom line is, with navmesh you NEED to search your path anyway with a-star and there is no escape from that. Raw navmesh doesnt contain unwalkable / blocked path out of box, they need to be calculated as well, so once used in real world scenario, things are not that ideal as they seems to, on empty road or level with no npcs or props, etc...what i really didnt like about it that after you set navmesh manually (you have to), you are still out of searchable grid necessery for search. And when you have 40 levels and plenty of props, thats not a joke. Contrary, this simplified version of my system used in game im going to expose in lessons, does job in 1 code line. Done.

[Davaris]

If I am understanding the differences correctly, Naughty Alien's system can also be used in games where a regular grid system is required for every map - I'm thinking of turn based war games.

[cocopino]

Many thanks for sharing this with the community NA, very generous!

Out of curiosity: what will happen with "semi-open" meshes (houses with doors, walls/fences etc.), will your algorithm find the entrance?

[Naughty Alien]

Many thanks for sharing this with the community NA, very generous!

Out of curiosity: what will happen with "semi-open" meshes (houses with doors, walls/fences etc.), will your algorithm find the entrance?

 

yes..Grid generator will find entrance so search algo will not get confused..Ill prepare few extreme situation meshes to demonstrate that ..

[gamecreator]

I think I could definitely use the C++ version in the future. Thank you very much for this!!

[eleXity]

is there any download for that, or plans ?

would be nice to learn from.

 

keep up the great work!

[puki]

EDIT:

Ignore me, I see you have some sort of vertical offset thing.

 

vertical offset is there, i just didnt used it in order to test how 'smart' algo

You should have used it - stop me from looking like an idiot.

 

 

 

This is all done on a terrain though. If that terrain was meant to be mountainous, then in the first picture, the AI has just Larged itself right through the Alps, when it probably should have gone around it - assuming the player is a pin-point on that terrain.

 

You go on to discuss rooms which is going to be pretty much a flat terrain and nothing to do with this concept, which is where some people will think about NavMeshes.

 

I don't see any mention of gradient being stored in your nodes, but the images clearly show that they are being laid down in 3D. With that added, then it is easy for the AI to accurately work out the best route - ie, it doesn't try to walk down a sheer cliff or something - plus it means that your logic will be faster as, with this type of terrain (depending on scale), you can kill of a whole bunch of connections. For flattish terrain then it wouldn't be required.

 

You'll know when it is right when you have the same screenshots, but with a whole bunch of those nodes coloured red, for example, (after you add in the gradients), and you will then have actual walkable routes which can dynamically change as you alter the scale of the terrain - in a nutshell, your whole grid will modify to the terrain. All you add in is additional rules based on gradients, which can all be done from a master control which can be independent to whatever you like - ie a certain vehicle can handle a wider range of gradients, etc.

[Josh]

I completely missed this topic.

 

Regarding navigation meshes vs. A*, I don't really see what difference it makes. If one works, and the programmer is familiar with it and can produce actual results, that is infinitely better than a theoretical alternative that might or might not have any real advantage.

 

Thanks for posting this.

[Marleys Ghost]

Regarding navigation meshes vs. A*

 

 

Is it really a Vs?

[puki]

I don't like NavMeshes at all - I don't even get the point of them - example::

 

http://geck.bethsoft.com/index.php/Bethsoft_Tutorial_Navmesh

 

They basically filled the entire floorspace of a level with them. I don't see the point of this - it seems so wasteful. You could do it with less waypoints than NavMeshes and use collision avoidance. It is so easy to sever or move a waypoint than to delete a bunch of NavMeshes and rebuild them.

 

People sometimes think you have to use loads and loads of waypoints - you don't, you just need critical ones for the AI to navigate to with collision avoidance.

 

 

This is going to use 5 pieces of NavMesh (excluding the bit beyond the door)

 

It's a right angle - you can do that with 3 waypoints.

 

Waypoints are cute.

[Pixel Perfect]

Is it really a Vs?

No, you're quite right MG it's not. A* is still the primary route solver used with nav mesh systems. They are after all a collection of nodes.