Original link: https://blog.codingnow.com/2022/09/routemap.html
In the game we’re making, traffic and logistics are based on a road network. The road network is actually a (undirected) graph composed of intersections as vertices and roads as edges. Since we have a large number of vehicles on this network, I need a space efficient way to store the paths of these vehicles.
In most cases, our vehicles choose the only shortest path, that is, if there is a planned path from intersection A to intersection B, all cars will take this road. Based on this, we can combine storage for multiple paths.
I choose to use the current intersection id and destination intersection id as the key, and the next stop intersection id as the value, and save it in a hash table. In this way, first use the Dijkstra algorithm to find the shortest route from the start point to the end point, and then save each section of the route with this structure.
When the vehicle reaches a certain intersection, it only needs to use the current intersection and its own destination to index which direction it should go. This structure is well suited to be kept in a Lua table, using the metatable to trigger paths that have not yet been computed. And such a path table is just a cache, which can be cleaned and rebuilt at any time.
If the road network is already stable, you can also choose a more memory-compact structure to store them.
For each intersection, the connected roads are limited. In our game, there are actually only two intersections (4 forks) and T-junctions (3 forks). We can number the roads connected by intersections 1-4. We can store all the path information in 4 arrays.
Routes to the same numbered exit can be stored together. For example, if the car going from junction 42 to junction 100 needs to take the 2nd exit at junction 42, we will record (42,100) in the 2nd array.
Each array is ordered so that binary search can be used to determine whether a path is in the array. Because the most complicated intersection has only four exits, and the car is in our rules, it is not allowed to turn around at the intersection and turn back on the original road. Therefore, to query the whereabouts of the next stage at an intersection, you only need to do two binary searches at most to determine (four queries at the starting point can be used to know whether it is reachable).
When the road network is fixed and will not be dynamically added or deleted, these four arrays can be stored in a continuous memory. It stores the shortest path between any two intersections in this road network.
Above, I made a simple implementation .
This article is reproduced from: https://blog.codingnow.com/2022/09/routemap.html
This site is for inclusion only, and the copyright belongs to the original author.