Page 1 of 1

City Simulation Feasibility

Posted: Thu Sep 09, 2010 10:46 pm UTC
by Smark
First I'll do a quick explanation then go into details, think of this as the TL;DR:

How feasible is to generate a city randomly, populate that city with traffic and emulate traffic (including traffic lights, accidents, construction, etc)? Obviously its possible seeing as how there is SimCity, but I'm doing this in C# and in my spare time.

The rest of the story:
So I've wanted to develop some sort of a simulation program for a while. At first I wanted to do a model of the internet (basically modeling packet routing), but then decided against it. My goal is to develop a type of automated SimCity with sliders for different options (commercialization, population, etc), generate the city, then populate it with "people" in the form of cars that travel around the city. I except my project will have 2 major design flows:

1. Generating the City Layout (this includes positioning traffic lights, office buildings, streets, residential areas, etc).
2. Emulation of City Life (this includes Cars obeying traffic laws, causing accidents, choosing destinations, traveling, etc).

I realize this is a VERY ambitious project. I'm somewhat new to C# as a language but I've gained a lot of experience with some of my previous projects (Conway's Game of Life, MP3 Streaming Media Server, Monopoly Game, Implementation of Dijkstra's Algorithm). I'm trying to plan out as much of this as possible before I do any coding. I realize this is going to have to have a lot of changes made as it is built but I'd like to get as many issues out of the way as possible so I can plan for them ahead of time. I'd hate to get the City Layout generator done, then find I implemented no way of representing the "roads" in a way that "cars" can use.

Obviously this will require an OOP approach with almost everything imaginable represented as a class/object. That includes, vehicles, roads, buildings, traffic lights, etc. Theres SOME but not a lot of resources out there for generating city layouts. There are more for generating terrain (such as a game map), but not as many that explain approaches to generating CITY layouts. I'm planning on implementing the actual visual view of the city using a PictureBox and just paining a Bitmap over and over. I'll have to figure out some sort of scrollability or possibly zoomability.

I'm looking for any concerns/comments/recommendations/questions/objections that anyone at xkcd may have. I know this forum has some pretty bright people lurking around and I'm hoping to gain some valuable insight into ways to tackle this issue.

Re: City Simulation Feasibility

Posted: Fri Sep 10, 2010 4:03 am UTC
by WarDaft
It strikes me as quite feasible but probably a bit arduous.

Generating the city could be anywhere from rather trivial to quite complicated, depending on how much you want the generation process to emulate actual city growth.

Cars that obey the laws of traffic shouldn't be too hard. Accidents and such could be more difficult, depending on how much of their real world implications you want to implement.

Also, don't worry about a representation of the city being usable by the cars, worry about it being efficiently usable by the cars. Almost any practical representation you might go with could be usable by the cars, but storing additional data could make things much more efficient. Pathfinding and poorly optimized collision detection would almost certainly be your biggest slowdowns.

Re: City Simulation Feasibility

Posted: Fri Sep 10, 2010 4:08 am UTC
by Izawwlgood

Re: City Simulation Feasibility

Posted: Fri Sep 10, 2010 5:34 am UTC
by Smark
I'm not really focused on GROWING the city persay. The way I imagined it was that I would run a task which would generate a layout for a city and finalize it, then have an ongoing task of simulating the actual traffic and such in the city. Generating the city can take however long it wants, though I cant imagine it taking more than maybe 5 seconds of actual computations. Pathfinding I know is going to be my biggest bottleneck. I'm still not sure how I want to visually represent the city. I know it'll be very basic lines, circles, rectangles, etc. What I don't know is the best way to display it... Should I make a jump to Direct3D or stick with a constantly refreshing PictureBox/Bitmap? Obviously the Render class will be all on its own and it'll do nothing except read the current state of the city and draw it over and over and over.

The Slime Engineer article was a bit of an interesting read but I'm not sure it specifically relates to laying out a city as far as roads and such.

Good comments, I like it, PLEASE keep 'em coming!

Re: City Simulation Feasibility

Posted: Fri Sep 10, 2010 6:09 am UTC
by somebody already took it
I remember at some point hearing about UrbanSim, which seems related to the general topic, although I don't know if it will be applicable to your project Smark. If it's not useful, I hope it's at least interesting.

Re: City Simulation Feasibility

Posted: Fri Sep 10, 2010 2:09 pm UTC
by quintopia
I believe this is the standard project my university uses to teach object-oriented programming to engineers. Of course, they provide the roads, and just ask students to design vehicles and their behavior. My friend was one of the ambitions ones, designing a tank that, for various reasons, did not need to follow traffic laws...

Re: City Simulation Feasibility

Posted: Sun Sep 12, 2010 8:22 am UTC
by Smark
So I've had one hell of a busy weekend, and I'll be working on more class work tomorrow so I don't know how much I'll be able to get done, but I need to figure out two things which I have no idea how to tackle.

I need to figure out how I want to think all of the various "entities" together to form a city. I'll have to answer questions like: How do I create a road in a way that allows it to be "attached" to other entities such as other roads, houses, cars even?

I also need to decide how I want to visually represent the city. First, it'll make it 100x easier to debug, Second, it'll actually be something to look at that will be interesting. I don't think going to with a Bitmap/PictureBox is the best idea, especially if I want zoom/pan capabilities. I was thinking DirectX but to be honest I have no idea where to start with that. I've spent a few minutes googling and have found a few tutorials but haven't actually done any coding yet. Is DirectX an appropriate tool to use in a situation where I'll be drawing purely 2D objects and requiring some easy way of zooming/panning?

I'm really at a loss for how to generate a city randomly using nothing but code. I except i'll pick some random coordinates for a business sector and a residential sector and "build" appropriate constructs in that area. Road Placement? House Placement? It'll all be hard decisions. Randomly placing roads isn't going to work well since I'd like to implement the concept of freeways and such between busy parts of a city (just like in the real world).

Any suggestions would be appreciated. I'll keep updating this thread as I tackle situations. Maybe this is something I could write a VERY long blog article about sometime.

Re: City Simulation Feasibility

Posted: Sun Sep 12, 2010 1:25 pm UTC
by Axidos
From what I gather, programming your own 3D rendering engine is quite the task. For now you might want to just stick with a free 3D rendering engine, such as OGRE 3D.

Re: City Simulation Feasibility

Posted: Mon Sep 13, 2010 6:37 am UTC
by WarDaft
It doesn't have to be 3D. It could be Direct2D instead.

Re: City Simulation Feasibility

Posted: Mon Sep 13, 2010 10:26 am UTC
by Zamfir
If you are just drawing shapes like rectangles to the screen, .net's built-in graphics are completely fine.

But for starters, you could stick to text. Attach to each object a "print history" command, that says things like "t=23: Car 123 passed" for a piece of road, "t=23: Drove on roadpiece AF-23" for a car, "t=34: Car 123 arrived" for a building.

As long as your model is simple with a few destinations, roads and vehicles, you can easily run a simulation, then manually query some objects to see what they have done.

Re: City Simulation Feasibility

Posted: Mon Sep 13, 2010 5:21 pm UTC
by fr00t
1. Sim city doesn't do what you're talking about to any degree whatsoever.

2. Graphics beyond something like dwarf fortress are probably both not feasible given your knowledge and realistic time constraints, and maybe also due to computational limitations depending on implementation. You definitely want to implement 95% of the abstract work before you think about graphics.

3. As noted above, it could be VERY simple or VERY complex depending on how realistic you want your cities to be. In fact, that's really a project all on it's own, and an interesting one. Starting with a small commercial blob, people move in and have certain weighted preferences. People want to be close to where they work, but not in too bad of a neighborhood. Businesses have to balance property value with things exposure, crime. The government has to spread out hospitals everywhere, but schools mostly only in residential areas. Different socio-economic groups will form and create distinct boundaries in the city. Etc etc.

4. You definitely want to think about the abstract implementation of your city. Like a graph, with intersections, houses, and businesses as nodes. How do individuals pathfind? How do you keep track of "real-time"? How do people decide when to go somewhere? This is actually a massively computationally rich and complex project. I think you could pull off a city of a few thousand locations and people. It would have to be at least that big to be interesting, I think.

5. You can simulate things such as congestion, speed limits, and traffic lights, but you can't simulate other real-life factors such as how driving experience, time of day, demographic information, etc. all effect driving. Well you can, but they would just be arbitrary constants that have no real-world meaning or application.

Re: City Simulation Feasibility

Posted: Mon Sep 13, 2010 5:53 pm UTC
by Yakk
I'd go with a local automata based approach.

Your city is a bunch of cells, roughly the size of an individual mobile unit. For this approximation, we'll make cars and people the same size. (maybe we'll allow people to "stack" to a certain depth).

We need structures larger than individual cells. Chunks of road, for example, are larger than individual cells, as are buildings. However, keeping things simple, such structures are immobile.

Each automata can examine structures in its local area to a certain radius.

There is metadata attached to the cells in a structure. Ie, the cells of a section of road include "cars tend to go this way on this section of road", or "turning lane".

Because cars follow each other closer than their size, automata need to be able to move between cells in a continuous manner.

Some automata need to be able to change the metadata (or overlay new metadata) on the cells of a structure -- this is a simple way for traffic cops and road construction workers to work -- or on automata in a region.

Each simulation cycle, you ask each automata what it wants to do based on its environment, then you have it attempt to do that. The length of a simulation cycle, if you want to be impractical, should be based on human reaction time (0.1 seconds or so).

If each automata checks a 11x11 cell radius for metadata, then runs 10000 instructions per cell, that is ~1E6 instructions per automata per cycle.

In a city of a ~million souls, there might be 300,000 cars in motion and 100,000 pedestrians, for 400,000 automata, or 4E5.

1E6*4E5 = 4E11.

A Ghz computer is running at ~E9 speed, so the above simulation would take about 400 seconds per 0.1 seconds of city life, or run at 4000:1 slowdown over reality.

So if you ran the crude city simulation for a week, it would advance time by 2.5 minutes or so.

The punchline is "you need to cheat". Modern computers cannot run a city of individually acting beings at human-reaction time resolution even with relatively simple rules. Instead, you need to treat masses of things statistically and abstractly.

Re: City Simulation Feasibility

Posted: Tue Sep 14, 2010 1:23 pm UTC
by SWGlassPit
Yakk wrote:I'd go with a local automata based approach.


The way you described above is more or less exactly the way SimCity works. The source code for the original SimCity is now released under GPLv3, and the algorithms for the later incarnation, SimCity 2000, are reasonably well documented.

Re: City Simulation Feasibility

Posted: Wed Sep 15, 2010 7:47 am UTC
by kjsharke
Yakk wrote:The punchline is "you need to cheat". Modern computers cannot run a city of individually acting beings at human-reaction time resolution even with relatively simple rules.


Or get a bigger computer? Make an "@home"/BOINC project :) If you relaxed some of those parameters, it might not be so bad. Make decisions every 10 seconds, have automata represent ~5 cars, use lazy evaluation for obstacles... I guess that's cheating to a certain extent (though I would argue that most humans use lazy evaluation), but I don't think you have to change the model. (anyway, you wouldn't start with 1000000 people)

See also: http://en.wikipedia.org/wiki/Transims

Re: City Simulation Feasibility

Posted: Wed Sep 15, 2010 4:06 pm UTC
by Josephine
the problem with doing a "City@Home" project is similar to the reason Dwarf Fortress (to reference it a second time in the thread) slows down. This kind of simulation doesn't lend itself to massively parallel processing.

Re: City Simulation Feasibility

Posted: Wed Sep 15, 2010 10:22 pm UTC
by troyp
nbonaparte wrote:This kind of simulation doesn't lend itself to massively parallel processing.

Why not?
In the scenario Yakk suggested, at least, everything acts according to its local environment. That seems to me like an ideal target for parallel processing: you could just split the city into squares (or hexagons, whatever), and handle each one separately - they'd only need to communicate about interactions across boundaries.

Well, on second thought, squares or hexagons mightn't be the best if there're cars driving everywhere: maybe make the sections correspond to groups of roads or something.

Re: City Simulation Feasibility

Posted: Thu Sep 16, 2010 1:06 am UTC
by Smark
I havent made any progress on this yet, I'm still kind of letting it simmer in my mind a bit and explore exactly how far I'd like to go with this.

I'm not going to go quite as extreme as fr00t suggested. I was planning on having VERY simple algorithms for the city. Rules such as "work starts at 8:00am for 70% of people, 9:00am for 10% of people, 15% of people work from home, 5% of people are sick today" with a little bit of randomness thrown in. I'm not trying to reproduce PEOPLE persay, but the traffic itself. Emergencies and such can all be grouped up into a "randomly leaving the house" probability, with their destination being any number of popular locations (hospital, supermarket, whatever).

I feel the need to atleast get some rough rendering of the city built. Its nothing fancy but it needs to have a bit more detail than just ASCII characters.

Yakk, I have (without doing the calculations) considered that a project of this sort may quite more computing power that I expected. I have an AMD Phenom II X4 3.4Ghz Quad Core and a GTX470 to work with. I'd like to somehow take advantage of the video card to relieve some of the stress from the CPU (mainly why I was considering DirectX). I'm planning on implementing as much threading as is reasonable. I expect headaches.

I knew that the Original SimCity code was release a few years ago and was planning on taking a look at it. I'm in no way trying to build an elaborate AI, just trying to roughly emulate one using preset values and actions with some RNGs in the mix.

I'm still thinking about this. I'm planning on making a significant effort to get some code written this weekend.

As always, you've all been very helpful and I look forward to any other ideas or suggestions you might have.

Re: City Simulation Feasibility

Posted: Thu Sep 16, 2010 5:20 am UTC
by squareroot
One interesting thing would be varying the amount of "intelligence" people have:
-Some go the shortest way
-Some go the shortest way, avoiding any congestion over a certain threshold
-Some go the fastest way, taking into account congestion on all streets
And so forth.

You'll also want a good way to model traffic jams, which occur on one-person or two-person basis, when people at the front start going more slowly. As they feel more pressured to move ahead from those behind them, the more they slow down - either because it's nerve-wracking for them to be honked at, or they take a "they'll pass me" mentality, unaware that there's some with the same mindset driving next to them. This can effectively reduce a 3 lane road to a 1 lane road (with the other two lanes moving very slowly) just long enough to build a short jam. Then more cars get stuck at the back of the jam, and it immediately begins to grow and propagate backward.

^That's a pretty intricate process, dealing with the psychological aspects of individual people; it will be tricky modeling that.

Re: City Simulation Feasibility

Posted: Thu Sep 16, 2010 10:43 pm UTC
by Smark
Hello everyone,

This is what I'm showing after a few hours of work...

Image
(click for full version)

I've got the basic rendering done and I think it'll work out good. I've spent about the last hour making a bunch of sprites for all kinds of traffic situations (2 Lane Northbound Passing with Left Turn, 2 Lane One Way with North Turn, etc)... I think that part is going to be a lot of work. I've found I'm running into a small problem. Each sprite is 25x25 which works just fine for simple objects like roads and such, but for more complex single "block" objects such as a 4way stop with a traffic light I'm not sure how to represent a traffic light in just a few pixels.

In the TrafficSim box that just has the FPS TrackBar I'll be adding a whole bunch of settings which have yet to be determined. The map was not automatically generated, I made a byte array to hold the map layout and just populated it manually for now for now. I may keep this in the final project as it seems to be an efficient way of storing atleast what sprite goes in what "slot". This will likely change though. As of now you can scroll side to side using the keyboard. I will likely add mouse support sooner or later depending on how well the keyboard works out in the long term.

Now that I'm about over my first roadbump (how to render the simulator) I have to focus on the objectification of almost everything related to traffic. I guess its time to get to work!

Re: City Simulation Feasibility

Posted: Fri Sep 17, 2010 2:53 pm UTC
by ecigrev
We should be researching if any thing that can be feasible with another but we should know our limits as well of course .

Re: City Simulation Feasibility

Posted: Wed Sep 22, 2010 7:17 am UTC
by Aaeriele
One way you might investigate using to "generate" a city would be the same random-map generation algorithms often used by roguelike RPGs - have a set of "prefabs" that have defined connection points, and randomly select different prefabs to string together.

Re: City Simulation Feasibility

Posted: Wed Sep 22, 2010 6:27 pm UTC
by negatron
Yakk wrote:1E6*4E5 = 4E11.

A Ghz computer is running at ~E9 speed, so the above simulation would take about 400 seconds per 0.1 seconds of city life, or run at 4000:1 slowdown over reality.

You're vastly underestimating the processing power of modern parallel architectures. A CPU is highly unfit for such simulation. One GTX 480 would comfortably execute 4E11 instructions in a second, even if it's arithmetic units are under-utilized due to cache misses/latencies. A simulation on that scale could easily run on a modest machine in real-time, but I won't under-estimate the development effort required to achieve that.

It also seems to me that an actor-based rather than cell-based approach would be more suitable. Doesn't seem like an optimal approach to use cells for potentially very non-uniform densities.