Hacker News Reader

Comment by ChrisLTD | Hacker News Reader

"in reality their pathfinding results in basically random behavior"

It's actually the opposite, sims always go to the nearest source for whatever it is they need despite traffic or congestion. Some randomness in picking a destination might actually solve the problem without requiring any particular intelligence.

View on HN

It's semi-consistent when it comes to city vehicles like garbage trucks or school buses. What you get is groups of vehicles traveling in a pack, bumper-to-bumper, taking a seemingly random path between bus stops/garbage pickups.

At various points in this one or two vehicles will peel off from the pack in a random manner - often towards stops with nothing to pick up.

So the aggregate effect seems to be a clump of city vehicles moving randomly around the city, neither towards nor away from places where they're needed, and you're relying mostly on the random "split from pack" behavior to get any real work done.

It's SUCH a better idea to simply weight paths based on their congestion. Like, that's A* path-finding 101.

I'm not sure they're actually using A*. In the following video, some cars are going directly right, although it isn't the shortest "bird-view" distance to their destination.

http://www.youtube.com/watch?v=l_ufAd79bOA

Edit: actually, they seem blocked by cars from the left lane. They'd go left otherwise!

Though I can't find any official sources to back it up, various internet citizens seem to claim they're using a D* Lite algorithm. I find it hard to believe. Either they're using some much cruder algorithm or they've implemented D* Lite horribly.

D* Lite Source https://twitter.com/MaxisGuillaume/status/311218564600315905

  A developer has said that they are using D*

They should be using min-cut max-flow graph algorithms rather than dist based metrics.

From past experience with traffic routing in real life, the best bet is to encourage a heavily monitored subset of traffic to take alternative paths. If this traffic continues to route faster than, you gradually increase the share of traffic to the alternative path until you observe it run slower than the primary route, or until there is no more traffic to route.

I have no idea how they have let this go out without putting more work into this...however maybe the same people who wrote the AI are responsible for running the servers and this is why we're seeing problems there too?

Reply on news.ycombinator.com