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.

Example Map (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!



1 Answer 1


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?

enter image description here

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.

  • \$\begingroup\$ 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. :) \$\endgroup\$
    – Paul
    May 15, 2013 at 14:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .