Sign in to follow this  
lucky6969b

Road Network pathfinding on Hierarchical type of map?

Recommended Posts

I've read some materials that road network pathfinding is best done on a grid type of map. Since my world is fairly large, say 5km x 5km, it would be a lot of cells if I generate a grid on it, however, a hierarchical map would be more easily, but it is not very intuitive to do road network pathfinding on hierarchical maps?

Thanks

Jack

Share this post


Link to post
Share on other sites

Yeah, not sure why you would overlay a grid onto something that is inherently edge-based like a road network. In fact, road networks are a dream for pathfinding. It's open areas with arbitrary geometry that are a PITA. 

That said, there is something to the notion of putting it into a hierarchy. Cluster graphs are the best bet. That's where you find groups that are close together and largely interconnected and treat them as a single "meta node". You then find which meta nodes are connected to each other and store the aggregate distance between them. You can then do a high level pathfind knowing full well that lower level ones will work. I'm oversimplifying, of course, but I'm wondering if you actually need that. Depends on how many intersections (nodes) you have on your map.

Share this post


Link to post
Share on other sites

How can I generate a graph if the geometry of the scene is a triangle chunk of mesh(es)? And I got those source of mesh(es) from some other places. Also, how do you simulate traffic, say you would have left, mid and right lanes, traffic lights etc

Share this post


Link to post
Share on other sites

Second question first:  With the additional requirement of simulating traffic and lane navigation, you're probably now looking at a navigation mesh, which is really just a specialized form of graph that overlays your landscape geometry.  The nav mesh provides additional information about where specifically on the map entities can travel.  It can also include, for example, preferred direction of travel for multi-lane roads.  Traffic lights and behavior around other vehicles would be handled by the AI separate from the nav mesh.

 

First question:  At some point along the line of generating the scene, somebody has to define what is navigable road and what is off limits.  If the meshes you are using don't have these defined in some way, then it's simply up to you to do so.  Now you may be able to key off things like textures to aid in this task.  Any poly that's using a road surface texture is likely part of a road.  Defining lanes of travel may possibly be done programmatically if you have consistent lane widths, but even this will likely require some hand massaging to handle special cases.  This is part of the purpose of level editors.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this