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
Sounds to me like what you really want is a graph that represents your road network and then perform the pathfinding on the graph.
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.
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
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.
