3

I was thinking about creating a simple game/simulation where cars drive around in a city as part of a pet project.

That made me think how I would simulate these individual cars in a simulated world. How would you cope with the following:

The simulated environment has the concept of time. So I guess you need some kind of 'world-thread'. A Thread that keeps running and simulates the time of this world and everything living inside of it.

But you also have the cars driving around in this city. These cars can all individually accelerate, brake, stop, park or be destroyed/created.

Now my question: How to best simulate this world. Would each car be a Thread of its own. So if there are 10000 cars, you would have 10001 threads(10000 cars + 1 world thread). Or would there be just one thread that calculates the state of each thing living inside of it on every 'tick' of the time that has passed in this simulated world? Do you know some documentation/references/books/blogs that explains some game-world mechanics and how to simulate those?

Improve this question
2
  • 3
    To avoid this question to be closed, change the title to "Multithread traffic simulation" and remove the part where you ask for documentation/references/books/blogs. 1. Avoid "too broad" close votes, 2. avoid "off-topic, asking for resources" close votes.
    – Tulains Córdova
    Jul 28, 2017 at 14:41
  • You can acquire the necessary programming skills by doing a simpler project first: simulate a spring-mass system according the physics. Once you have reached that milestone, it will be easier for you to conceptualize a larger system.
    – rwong
    Jul 28, 2017 at 19:24

3 Answers 3

Reset to default
4

You would not have a thousand threads because this would be a performance overhead if you don't use a massively parallel supercomputer.

One common software architecture would be to have a queue with all the objects, and an optimal couple of threads that each read from the queue the next object to process, and put the object with its new state at the end of the queue.

Typically, this can be combined with the use of the flyweight pattern that aims at optimising resources needed for a high number of similar objects.

Improve this answer
3
  • 2
    +1 Threads don't bring CPUs into existence out of thin air.
    – Tulains Córdova
    Jul 28, 2017 at 14:58
  • 2
    OTOH, using one actor per simulated object is entirely possible. In fact, OO was invented for simulations, and actors were heavily inspired by objects, so having one object/actor per simulated object is not only possible but also sensible. Actors may or may not live on their own thread, or even on their own process. (In Erlang, each actor is its own process with its own heap and its own GC, and it is perfectly possible to have a million actors even on a not-that-recent laptop.)
    – Jörg W Mittag
    Jul 28, 2017 at 17:49
  • 1
    @TulainsCórdova That is a very good point that a lot of people forget.
    – T. Sar
    Jul 28, 2017 at 20:03
3

You can acquire the necessary programming skills by doing a simpler project first: simulate a spring-mass system according to physics. Once you have reached that milestone, it will be easier for you to conceptualize a larger system.

Your program is a loop. At each time step ("tick of time"), say t, your program must calculate the parameters (position, velocity, acceleration, driver's decision) of each car for the next time step, say t + 1.

  • You will have an array of cars, say carCurrentStates[carNumber].
  • You may need to create a duplicate array, carNextStates[carNumber].
  • At each time step, use the information from carCurrentStates[carNumber] to compute new information for carNextStates[carNumber]. When all calculations for the time step is done, copy the information from carNextStates[carNumber] back to carCurrentStates[carNumber].
  • The duplicate array carNextStates[carNumber] can be reused (overwritten) in the next time step.

You will need to synchronize these calculations.

Whether you use threads or not, you will have to use some kinds of synchronization techniques. Synchronization techniques for threads are also known as barriers.

Thread schedulers do not magically cause your threads to run in a synchronized way. They don't magically give equal share of time to each of your threads. If you do not use any synchronization techniques, some of your threads will get more execution time than others; they will lose sync.

If more than one threads need to update (write to) a certain program variable, that need to be serialized. Serialization means that one thread can complete a "read-modify-write" sequence before another thread can start its own "read-modify-write" sequence. If access to program variables aren't serialized, each thread's written result will clobber the earlier result, or that a thread may perform calculations based on a stale result that has since been clobbered.

Once you know how to implement the calculations in a synchronized way, and update the program's states correctly, you may find that you can implement the project either with or without threads.

As to simulating driver's behavior, each driver will accelerate or decelerate according to:

  • What is my speed? (Low/medium/high)
  • What is the speed of adjacent lanes?
  • How far is the car in front of me?
  • Is the space between me and the car in front: increasing (accelerating faster than me), same (same velocity/same acceleration), or decreasing?
  • Am I planning to change lane? If so, I need to match the speed of that other lane.
  • Do I have any other reason to slow down? If I am going to exit from a highway, or if there's a traffic light, or if there's a sharp curve, then I need to slow down.
  • Do I need to make a complete stop at a certain point? If I'm reaching my destination, or if the traffic light is red, then I'm not allowed to overshoot. I have to brake as hard as I can if that is necessary.
Improve this answer
3

You might want to look at the documentation for a gaming engine, like Unreal Engine 4, which will give you a good idea of what is involved in modeling a world in software. In that framework, everything in a game/world is an "Actor" and the game engine manages them all. From their documentation, I get the impression that each actor is not its own thread. Here is a link that describes their "ticking" system:

https://docs.unrealengine.com/latest/INT/Programming/UnrealArchitecture/Actors/Ticking/index.html

I get the impressing the actor objects are managed by the runtime in a linear fashion and not massively multi-threaded. Also worth pointing out that simulating a world with cars there is also a physics system, weather system, etc. Becomes very complex very quickly.

It is very interesting to take a deep dive into a modern game engines documentation and source code.

Improve this answer

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