# How to create a path-finding compatible road map from user input?

I'm currently working on an agent simulation (inspired by the recent SimCity release). Now, basically I understood how agents work but I do not understand how to put them into context. Agents travel along roads on a map and pursue their own goals.

As in SimCity, I want the player to be able to create his own roads. If I used grids, I would run into a problem caused by user input: Imperfect grids will be created where two roads would need to share one "box". This would be even worse with bevels.

(Grey = Street, Orange = Agent road, Dots = Immobile Agents)

Is there another, more clever way of building a road map that would support this kind of map and is compatible with path-finding?

Thanks a lot!

Paul

You don't need to use a grid, you can easily extract node information from the roads (or keep it when placing roads). Path finding only cares about connectivity. Once you get to one node, which nodes can you go to next?

Red dots are nodes in your path finding algorithm. The orange lines define their conectivity.

The Green agent wants to go from its current location to K. If finds a path along G-H-I-J-K. The Blue agents wants a path to A, it finds its path along G-E-F-B-A.

The grid is still useful for placing your nodes, as it keeps the spacing for regular sized buildings, helps the user make straight lines and so on. But I wouldn't use the grid for path finding, use the nodes that have been placed.

Nodes are created at each end point and each intersection. Agents not on a road can find the road nearest to them. Likely you'd want to force them to be connected to a road at some point, and may even want to create additional "minor" nodes for each connected structure or object that can contain agents.

• This sounds like a good solution. I guess, this means that the simulation needs to detect route intersections and create a new node at that position for the agents to be re-routed. But that should be possible. :)
– Paul
May 15 '13 at 14:25