Jump to content
  • Advertisement
Sign in to follow this  
Tangletail

Hope this Will help: Research AI Navgrid generation in a 3D world

This topic is 853 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement

a good post.

 

i've been starting to think about this problem myself.  i tend to always use procedurally generated content, and have been thinking about generating nav meshes for it.

 

but my first impression from my typical outside the box perspective is that floor and elevated sections should be handled separately, and shrink wrapping a grid down over the scene from above and checking height difference between adjacent verts to determine passable might be one possible approach. but thats just if i was going to try an aglo off the top of my head. i often find it useful to think of how i would do it before i take on the "cognative burden" (1)  of other people's approaches.

 

(1)  "cognitive burden" comes from the design sciences,  usually a branch of systems engineering, if not a stand alone discipline. it speaks to the mental bias we carry into a design session based on what we've already experienced. oct-trees and scene graphics are good examples. many folks hear about these, and wrongly think they are the correct or only way to do something.  that's cognitive burden.   all the solutions you've seen in the past can color your judgement as to how to best design something (and NOT color it for the better).  which is actually rather obvious,  you wouldn't be designing a system if the current solutions worked.  so why clutter your brain with the current so called solutions? doing so can tend to steer you in the same direction, sometimes without your even noticing it. so in the design sciences, one must always be aware of one's cognitive burdens (what you already know) and how that can prejudice you towards or away from specific types of solutions, which is a bad thing, as the optimal solution may be one that your cognitive burden prejudices you away from.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites
Oh believe. Me I thought about using simpler solutions. But the problem arises with my engines scope.

It needed to deal with larger worlds, and Ai behaving at real time. When the navmesh becomes that dense, a* and jps a* will take much longer. So partitioning is required to help break up the required frame time.

I thought about using tiles of squares, and raycast. But a section can loop back onto its self creating a problem. Or the destination can exist on another side of a wall that divides a tile.

Share this post


Link to post
Share on other sites


When the navmesh becomes that dense, a* and jps a* will take much longer. So partitioning is required to help break up the required frame time.

 

so your solution to the "large search area" problem is to slice it up into smaller partitions? and you path across a partition to a point known to connect to the next partition, when traversing multiple partitions?

Share this post


Link to post
Share on other sites

Yup. Solve a general case of connectivity. So... when we initilize a path. If the two points do not exist in the -same- partition, then we path find on a connectivity graph.

The nodes in that graph are the partitions. We do not care about the details of each partition yet, we're only concerned about a general path.

With fewer nodes to traverse, this won't take very long. Once the general path is found, we then solve for a detailed path for each partition.

We can solve for each partition per frame, but this doesn't scale well with large amounts of entities, plus the path may change at some point (waisted processing)

Or, we can increase our through put by solving for only the current partition the AI is in, wait till he nears the end, then solve for the next partition.

 

For a large world, this has actually reduced the computation time for each AI by doing it incrementally.

Edited by Tangletail

Share this post


Link to post
Share on other sites


Once the general path is found, we then solve for a detailed path for each partition.

 

ah, sort of an A* or navmesh at two resolutions type of thing, first path across the level map, using partitions as nodes, then path across each partition, using grid verts as nodes (i assume).   somewhat analogous to 1st pass coarse grain and 2nd pass fine grain collision detection.

 


For a large world, this has actually reduced the computation time for each AI by doing it incrementally.

 

yes, i was thinking a limited search area might be the way to go.  i'd like to improve the pathing in Caveman in dense terrain. but like everything else, its procedurally generated. thus my interest in navmesh generation for arbitrary level designs.  when a terrain chunk is generated, four interleaved ground meshes with different tileable textures are generated, along with a list of renderables (plants, trees, rocks, bushes, etc). at the same time, a terrain collision map is also generated.   i was thinking i could use the collision maps as a start for short range A* to path the way through nearby dense terrain.  from angle (or line of sight) to target and A* area BBox radius, you can calculate where your optimal end node is. from there search along the edge of the A* area until you find an open node to use as the target node for this area (maybe an open node at the edge of both this area and the next one). then just A* to the target node, then move to the node in the adjacent area and repeat.

Share this post


Link to post
Share on other sites

what about....

 

1. define a "search area" as being contiguous and all on the same level, or a ramp, or stairs.

 

2. define an "exit" as any door, or the end of a ramp or stairs.

 

3. create a 2d collision map for an area (IE a tile grid: passable or impassable). maybe just special case stairs and ramps.

 

4. run A* or jump A* on the area.  

 

5. to move across a tile, simply move from the center of one edge to the center of the next.

 

a low rez collision map would run faster, higher rez would produce nicer results.

 

in your first example image, the floor would be one area, the ramp a second, and the elevated platform connected to the ramp would be a third area.

 

 

you might even do a coarse to fine multipass method. start with a really low rez grid, like each tile is 50 units across. you might get a collision map thats 4x4 or 6x6 or something, IE really big tiles.  A* would be trivial on such a small search area. if it fails, you cut the tile size in half and try again.   that way you never deal with a higher rez grid than needed to find a solution.

 

for outdoors, when generating the collision maps, steep slopes are simply treated as impassable, or the end of a ramp (your choice). rocks, trees, buildings and such are obviously impassable.

 

 

in fact, a coarse to fine collision map, combined with heuristics might even work in lieu of A*.   i'm thinking that the coarser maps might allow you to avoid pathing down a dead end at higher resolutions. and the finer maps would be used to follow the correct path. a simple line of sight and follow the wall algo can traverse an arbitrary level pretty quickly. with sufficient look-ahead it might even give A* a run for its money. of course, it might also be scene dependent.  pathing a dungeon vs around a tangle of rocks and trees outside are somewhat different. although in the end, it all boils down to convex or concave obstacles.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!