I am the guy who builds agent-based models for fun. A lesson you learn quickly is that heterogeneity is your guardian angel - varying the path-finding model a little bit from agent to agent hedges against the resonance structures on display here. Additionally, you periodically check the accumulated micros against a macro model and correct gross deviations. Neither step is computationally strenuous.
If you're the guy that builds agent-based models for fun, why not build an open-source citiy simulation engine? Grafting your simulator with an open-source tile-based graphics engine such as the one used in OpenTTD would make a lot of nerds very happy.
That's something I would be really interested to follow and maybe contribute to, so if anyone shares any pointers or links to existing OSS projects, I'd be very grateful.
Now necessarily city-simulation engine - just routing/pathfinding in graphs would be great.
Netlogo is an open tool written in Java for agent-based simulations (and much more), and quite mature, well worth checking out if you are into this sort thing. I always had a down on Logo because when I was a kid it seemed only to be mentioned in the context of turtle graphics, but the implementation here is powerful and reasonably terse.
Could you explain a little bit more about how that works - you used words I don't understand :) It seems as though something as simple as a random selection when presented with intersections is better than the behaviour here. I guess there should just be a weight on the streets though, right?
Let me translate this to physics talk for you: when you use a greedy algorithm with no interaction between agents and no randomness, it's effectively like bosons at zero temperature, they will all fall in the lowest energy state and form a Bose-Einstein condensate.
This can be avoided in one of two ways, make them aware of each other, so that they can't all be in the same state (like fermions) or raise the temperature, i.e. add randomness. Probably you'll need to do both and find an energy function that's less retarded than choose the first branch you see…
I'm not the person you're responding to, but I think this is how what the poster said applies to a SimCity-like model:
>heterogeneity is your guardian angel - varying the path-finding model a little bit from agent to agent hedges against the resonance structures on display here.
Adding a small amount of randomness (occasional 'wrong' turns) reduces congestion on the major paths that would be the dominant route for agents.
>Additionally, you periodically check the accumulated micros against a macro model and correct gross deviations. Neither step is computationally strenuous.
Every once in a while, check and make sure those wrong turns didn't add up to some agents being way far away from their destinations; if so, turn them in the right direction.
AFAIK it doesn't even have to be wrong turns. You can just have some agents prefer to turn more often and others to drive straight for longer stretches, or have some prefer to approach things from the left and others from the right. They won't be randomly turning the wrong direction, but they'll prefer different paths.
Or to put it in a more socioeconomic context, consider a low-wealth actor that might prefer to avoid toll roads, versus a high-wealth actor that would rather pay a little bit to save some time. Those are the kinds of motivations I was hoping to see in this game.
In some situations, a greedy algorithm works well but a totally random one works terribly, in other situations a random algorithm works well but a greedy one works terribly. Combine the two, and everything works out well enough to be plausible under all circumstances.
Case in point: The Heroku load-balancing issue is a nasty one. The random algorithm (the one they went with) leads to really nasty queues in some places, it's super inefficient. On the other hand, a greedy algorithm doesn't scale well. You get one Heroku dyno (or SimCity road) swamped by all the agents making the same decision.
A popular load-balancing strategy that finds a middle ground is "best-of-two" routing where you choose two servers at random and route to the one with lower load. There are probably similarly simple ways to introduce variety and randomness into the SimCity agents.
In a nutshell: Make very agent a bit different in the sense that they all won't make the exact same choices. i.e. Rather than have a human always choose the first source, vary this and have some humans that go for the fifth and others for the sixth, etc. etc. Your random selection would also work I guess. Although how well? I don't know.
Then, have a global pattern of how everything should be working, more or less. When a major deviation is found from the global pattern, adjust. How exactly? Those are implementation details.
