City Simulation Feasibility

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Smark
Posts: 14
Joined: Sun Jul 11, 2010 10:11 pm UTC

City Simulation Feasibility

Postby Smark » Thu Sep 09, 2010 10:46 pm UTC

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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: City Simulation Feasibility

Postby WarDaft » Fri Sep 10, 2010 4:03 am UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Izawwlgood
WINNING
Posts: 18686
Joined: Mon Nov 19, 2007 3:55 pm UTC
Location: There may be lovelier lovelies...

Re: City Simulation Feasibility

Postby Izawwlgood » Fri Sep 10, 2010 4:08 am UTC

... with gigantic melancholies and gigantic mirth, to tread the jeweled thrones of the Earth under his sandalled feet.

Smark
Posts: 14
Joined: Sun Jul 11, 2010 10:11 pm UTC

Re: City Simulation Feasibility

Postby Smark » Fri Sep 10, 2010 5:34 am UTC

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!

somebody already took it
Posts: 310
Joined: Wed Jul 01, 2009 3:03 am UTC

Re: City Simulation Feasibility

Postby somebody already took it » Fri Sep 10, 2010 6:09 am UTC

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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: City Simulation Feasibility

Postby quintopia » Fri Sep 10, 2010 2:09 pm UTC

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...

Smark
Posts: 14
Joined: Sun Jul 11, 2010 10:11 pm UTC

Re: City Simulation Feasibility

Postby Smark » Sun Sep 12, 2010 8:22 am UTC

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.

Axidos
Posts: 167
Joined: Tue Jan 20, 2009 12:02 pm UTC
Location: trapped in a profile factory please send help

Re: City Simulation Feasibility

Postby Axidos » Sun Sep 12, 2010 1:25 pm UTC

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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: City Simulation Feasibility

Postby WarDaft » Mon Sep 13, 2010 6:37 am UTC

It doesn't have to be 3D. It could be Direct2D instead.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7605
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

Re: City Simulation Feasibility

Postby Zamfir » Mon Sep 13, 2010 10:26 am UTC

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.

fr00t
Posts: 113
Joined: Wed Jul 15, 2009 11:06 am UTC

Re: City Simulation Feasibility

Postby fr00t » Mon Sep 13, 2010 5:21 pm UTC

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.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: City Simulation Feasibility

Postby Yakk » Mon Sep 13, 2010 5:53 pm UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
SWGlassPit
Posts: 312
Joined: Mon Feb 18, 2008 9:34 pm UTC
Location: Houston, TX
Contact:

Re: City Simulation Feasibility

Postby SWGlassPit » Tue Sep 14, 2010 1:23 pm UTC

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.
Up in space is a laboratory the size of a football field zipping along at 7 km/s. It's my job to keep it safe.
Image
Erdös number: 5

User avatar
kjsharke
Posts: 70
Joined: Fri Dec 07, 2007 3:53 pm UTC

Re: City Simulation Feasibility

Postby kjsharke » Wed Sep 15, 2010 7:47 am UTC

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

User avatar
Josephine
Posts: 2142
Joined: Wed Apr 08, 2009 5:53 am UTC

Re: City Simulation Feasibility

Postby Josephine » Wed Sep 15, 2010 4:06 pm UTC

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.
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: City Simulation Feasibility

Postby troyp » Wed Sep 15, 2010 10:22 pm UTC

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.

Smark
Posts: 14
Joined: Sun Jul 11, 2010 10:11 pm UTC

Re: City Simulation Feasibility

Postby Smark » Thu Sep 16, 2010 1:06 am UTC

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.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: City Simulation Feasibility

Postby squareroot » Thu Sep 16, 2010 5:20 am UTC

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.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Smark
Posts: 14
Joined: Sun Jul 11, 2010 10:11 pm UTC

Re: City Simulation Feasibility

Postby Smark » Thu Sep 16, 2010 10:43 pm UTC

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!

ecigrev
Posts: 1
Joined: Fri Sep 17, 2010 2:17 pm UTC

Re: City Simulation Feasibility

Postby ecigrev » Fri Sep 17, 2010 2:53 pm UTC

We should be researching if any thing that can be feasible with another but we should know our limits as well of course .

User avatar
Aaeriele
Posts: 2127
Joined: Tue Feb 23, 2010 3:30 am UTC
Location: San Francisco, CA

Re: City Simulation Feasibility

Postby Aaeriele » Wed Sep 22, 2010 7:17 am UTC

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.
Vaniver wrote:Harvard is a hedge fund that runs the most prestigious dating agency in the world, and incidentally employs famous scientists to do research.

afuzzyduck wrote:ITS MEANT TO BE FLUTTERSHY BUT I JUST SEE AAERIELE! CURSE YOU FORA!

User avatar
negatron
Posts: 294
Joined: Thu Apr 24, 2008 10:20 pm UTC

Re: City Simulation Feasibility

Postby negatron » Wed Sep 22, 2010 6:27 pm UTC

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.
Image
I shouldn't say anything bad about calculus, but I will - Gilbert Strang


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 2 guests