4 ms·
Currently I can close edges (i.e. an individual road between two intersections), but right now I would have to rebuild the path finding graph each time the grap
by YesBox 4y ago
Currently I can close edges (i.e. an individual road between two intersections), but right now I would have to rebuild the path finding graph each time the graph changes. I was thinking of this problem too, cause it would be really cool to temporarily close a road down for repairs/construction. I think there is a way to make it work without needing to rebuild! Just havent had time to look into it.
- theanzelm 4y agoThe way I did it in Citybound is to assume that the graph constantly changes anyways (also because the player can add/remove roads quite rapidly) and route the cars more like packets on the internet than with static A*-ish algorithms. That way, road nodes can propagate changes locally.
- YesBox 4y agoInteresting, I assumed the roads were not going to change frequently (but rather, in bursts). So I used that premises to develop my algo. To enforce this behavior (on a code level), I will be adding a "planning" mode, where roads can be placed freely/frequently. Once the user sends the plan off to be constructed, then the graph will update. I may go one step further and have construction (i.e. graph updating) only happen at night, and give the user something else to do while its updating. That being said, if they have a modern machine, then there will be no need for this at all (just need to figure out the avg user CPU GHz & core count). It takes 10 seconds for my algo to find the all pairs/all possible shortest paths between two nodes on my machine for 10,000 nodes, which by that point is a HUGE city. The reason I did not go with A* is because it doesn't scale to 100K+ units and it always chooses the same path.