Train3D has the possibility for dozens to hundreds to thousands of vehicles all running around the map. Each vehicle has its own set of orders and follows a route but road vehicles need to share the space in a realistic way. Up until now, each vehicle ignored the others which meant they would drive through each other and that took away from the atmosphere. It also meant that traffic was not a challenge in the game. You didn't need to worry about road capacity because it was unlimited. Not anymore.
My first thought was to use colliders in Unity to look for an event whenever two vehicles got too close together. I tried a couple of different options including box colliders, capsule colliders and triggers vs. collision events. The short story is that it just ate up too much processor time and generated a lot of extra events (like vehicle colliders bumping into hills on their way up/down the road). Colliders make a lot of sense if you're using the physics module in Unity but I really just need to know if there is a vehicle ahead that I'm going to run into.
My next thought was to loop through the vehicles and check to see if any are near, then calculate the distance, direction, etc. Just a quick analysis showed that was a lot of looping over the vehicles in a recursive pattern. Too much crunching in a single frame. Also, not a great algorithm.
Next I thought about having each vehicle register itself with a tile on the map as it entered. This would let me keep a list of every vehicle in a given tile so that I would have a much smaller list of items to check. But one good cup of coffee later and I realized that each road segment is essentially a pipe with an entrance and exit. One pipe in each direction. Intersections are a different case but I'll deal with those later. Realizing that each road segment is a queue, I then can simplify things because if I'm travelling East, I only care about the vehicle directly in front of me for possible collisions.
Vehicles can register their entrance direction and id with a given map tile. As the vehicle enters the tile, it first checks to get the id of the last vehicle also entering in that direction. That is the only possible vehicle to follow. Then, the vehicle registers itself as the last vehicle to enter in that direction. As the vehicle moves through the tile, it only needs to check the absolute distance to the single vehicle to follow. No more looping over thousands of vehicles recursively.
Now, each vehicle dutifully follows the previous one heading in the same direction while ignoring vehicles driving in the opposite direction. I've tested with over 10,000 vehicles at once and the framerate is still buttery smooth. The biggest issue with that test was that 10,000 vehicles can now lock up the roadways in grid lock if there isn't enough space to spread out.
Intersections are next on the list. I expect to be using a similar system. As a vehicle approaches an intersection, it registers its entrance direction and intended move (straight, left turn, right turn). The intersection tile will play traffic cop in a first come, first served manner. Vehicles will stop and wait for permission to proceed. Optimizations will include the intersection realizing that East to West and West to East traffic can safely proceed at the same time. Same with Forward and Right Turns in opposite directions.
Read More