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?

  • I believe that fluid flow is the most commonly used metaphor for traffic. So graphs. – Edward Strange May 16 '12 at 7:38

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.

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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