Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This has never come up, so I've never thought how a data or programming model should work that simulates (a) bird's eye view of cars moving and some rudimentary physics, (b) how the cars would follow a road layout and (c) how an efficient data structure for roads would look like.

Obviously, this question also means to ask how the road data structures would interact with cars.

Any recommendations, or reviews of such data models?

share|improve this question
I believe that fluid flow is the most commonly used metaphor for traffic. So graphs. – Crazy Eddie May 16 '12 at 7:38
up vote 3 down vote accepted

I don't know whether you need life-perfect simulation or not, just one of my previous project as an example.

enter image description here

This was a part of the program for studying highway code (I'm not sure this is the correct word). It was developed in 1996 for Window 3.1 so the computer resources were much more limited that today. The program consisted of multiply random moving vehicles and single handled by the user (blue one on the screenshot). I divided the area with 40x40 cells that could be visually distinct but from the point of view of a car this was a single unit of analyzing and decision making. So for a virtual area of 4000x3000 pixels the program needed only 100x75 array of different data specific to road traffic and positions of the vehicles. The crosses were a more complex structures with the states of allowed directions and intentions of the participants appearing as temporal states and available for others also.

share|improve this answer
Makes sense; how did you track/assign direction of the road that an autonomous vehicle should follow? – pp19dd May 16 '12 at 12:56
As long as I remember a vehicle chooses one of the possible directions absolutly randomly some time before intersection (including U-turn). There wasn't a goal to make them look too smart, but when there are dozens, they look convincing even with absolutely random choices – Maksee May 16 '12 at 14:16

Roads need defined lanes: a spline that determines the center of each lane is probably the most convenient. Lane and shoulder boundaries may also make sense, if only for road-drawing purposes.

The interesting datastructure element is the ability to split and merge lanes: your lane splines should be associated with edges in a directed multigraph.

Cars need a position and a velocity; they should be able to efficiently query which cars are ahead/behind/beside them, in order to do rudimentary navigation. They will also need a bounding box, and of course a collision model...

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.