I was sitting down and thinking about this today. You see, I'm planning a RPG sorta like Sword of Mana, where you have an AI controlled friend or two running around with you and fighting Zelda style. The thing is, its in 3d. I was sitting down and trying to figure out how to represent the level's graph nodes for A*, but I can't figure it out. Here's what I've thought through so far: Grid Based(the worst, really, how would I generate these from the level data) Edge Based(I have no idea how to visualize this, but I'm really sure it won't work) Points of Visibility(Its sorta limiting, because the points are joined by straight lines, so there's no guarantee they'll follow slopes correctly. Plus, how would I implement this into an editor? This seems like the best solution so far.) Can someone please suggest an alternative node implementation and maybe an example or two :)? Thanks in advance.

It would help to know what kind of data the program would have access to.

And if the levels are precanned (without much dynamic content) you could have a navmesh/network prebuilt using more complex analysis than you would use at gametime.


A grid could work but might be many more nodes than is needed. A simplified nav mesh with the triangles center points being the A* nodes might be possible.
(probably with graph edge remove and additional points added to handle sharp corners)

you may wish to have a look at www.jkilavuz.com. albeit it's written in Java it may give you some ideas about representation of a 3d level for pathfinding. the site also contains a demo jKilavuz applied to a multi floor Quake level.

r a f t
kinda self promotion but nevermind ;)

Quote: Original post by GavRobbs
Grid Based(the worst, really, how would I generate these from the level data)

Grid based is the easiest to automatically generate, it's just least optimial so far as number of nodes. Just like the jKılavuz link raft posted, an easy way to generate cell based nav data is by flood filling the environment. This works for 3d levels as well as 2d, and during this process you have alot of opportunities to generate some addition information from the flood fill, such as marking nodes near walls/edges, marking cover points, jump up connections, etc. The primary downside to such a method is that without a 2nd pass in optimizing the large number of grid cells, such as merging into sectors, the result will be a huge number of grid cells, which will give you a not so great performing path query. If most of your paths are relatively small distance its probably fine, but storing an entire map in grid cells, especially one that is made up of mostly open space, involves quite a chunk of memory.

If you are interested, heres a movie of a flood fill demonstration I built in the Half-life 2 engine.

http://omni-bot.com/_misc/ob_navmesh.wmv

It shows a flood fill generation of a gridded nav throughout a level of fortress forever(at 2 different grid sizes). It's a very convenient and easy way to generate navigation, but very memory intensive due to the number of nodes, which would translate over into a very expensive path query across an entire level. The video also shows some of the node merging stuff I was experimenting with in order to reduce the size. The end results I'm not very happy with, as it's less than ideal for maps that aren't axis aligned(the merging routine is simple that way), although in reality the counter-strike automatic nav generation is also axis aligned, so it can probably still work fine as-is. This technique however sucks on terrain, as it is very difficult to optimize a cell based nav mesh on terrain. The HL2 CS auto nav and the AAS system of Quake both generate really bad pathing on terrain patches too. I'm pretty convinced that terrain patches likely need to be treated seperately so far as nav generation, such as just using the terrain patch itself as a navmesh and then cutting holes in it where static props block navigation, or just using local avoidance if the obstacles are simple. Unfortunately from the SDK of a game, I don't have access to the low level structure of the geometry of a map, so I think next I will probably use the flood fill to generate the mesh vertices at a larger grid size than what internal areas are typically flood filled at.

Any questions about it let me know. The rendering of the nodes in the video are distance limited or it would kill the framerate, and the colors of the nodes mean different useful things, such as red showing "next to an object or edge". That information would be useful for generating cover points and such. Later in the movie I start the process over with a finer grid size and it is noticably slower, but it allows you to see the process happening much easier.

Quote: Original post by DrEvil
The primary downside to such a method is that without a 2nd pass in optimizing the large number of grid cells, such as merging into sectors, the result will be a huge number of grid cells, which will give you a not so great performing path query.

yes, definetely a second pass is required to collapse grid cells into sectors and portals. but indeed i won't consider this as a downside but a necessary part of process. other way, as you mentioned, besides the accessive memory requirement the performance of pathfinder will suffer too.

btw, in the Quake demo of jKilavuz, the grid cells take about ~5M but the runtime pathfind data (collapsed into sectors and portals) takes only ~200K uncompressed

Quote: Original post by DrEvil
This technique however sucks on terrain, as it is very difficult to optimize a cell based nav mesh on terrain. The HL2 CS auto nav and the AAS system of Quake both generate really bad pathing on terrain patches too.

i have tested jKilavuz on a couple of terrains (outdoor levels) and it all went well. what is your concern about terrains here exactly ? one issue may be sector creation. if they are heavily bad shaped (long and thin sectors etc) pathfinding may behave strange. but there are technics to create good shaped and balanced sectors.

what we are doing here is hierarchal pathfinding and as you know hierarchal pathfinding can not guarantee optimal paths as heuristics at higher levels are not admissable anymore. but this behaviour is not specific to outdoor levels.

By downside I meant it's a significant extra complexity to the process. I don't mean its hard to merge sectors, but to get optimal sectors is non trivial. You can see in that demo all the extra noise of small sectors all over, particularly in non axis aligned areas, such as the rounded room. It works, but it isn't clean, and isn't optimal. It's probably good enough for most cases. In addition, 200k for such a small level I wouldn't consider very optimal either. The jKilavuz seems to effectively gives about the same results as my flood fill sector merging.

The concern about terrains is that it's difficult to get good sectorization. It tends to result in a bunch of small sectors, which again may work but it's not optimal.

Not trying to knock the technique, as I'm very interested in it myself or I wouldn't have built my own such as in the video. I'm just unhappy with the results in more realistic modern day environments that involve more curvature, less axis aligned rooms of the quake days, and more terrain. Those cases serve to bloat up the resulting meshes. It's probably fair to say that I'm expecting too much from such a technique as far as how optimal the results will be.

If I were ever to build a 2d tile based game, this same technique would be perfect for creating sectors out of tile data for a perfect navmesh in a 2d axis aligned tile world. It's a convienent and easy way to generate for 3d worlds too, just tends to produce alot of small sectors due to the merging techniques typically involved, and the variation of the ground surface complicates the merging process.

i agree almost all. but i cant see what differs for a terrain. all apply to indoor scenes too. maybe i havent faced such a problematic terrain yet. if you post a link of such a terrain in 3ds or obj format i can test it with jKilavuz

for optimallity of 200k, well i'm pretty happy with the result :) the cell size was a quarter of avatar so the grid includes all reachable space including jump overs.