Original link: https://blog.codingnow.com/2022/09/cargo_matching.html
We’re making an automation-themed game like Factorio. There are many algorithmic problems encountered in game development, and the solution process is very interesting. For example, I wrote a fluid system before.
The biggest difference from the Factorio experience is that we don’t use conveyor belts as the primary means of logistics, but instead rely on the road network and trucks. This format isn’t new, I’ve played it in Caesar 3 over 20 years ago (and in the same series as Pharaoh, Zeus, Rise of the Dragon, etc.). Games that use this logistics method have never been interrupted. In the past few years, I have played the city of exile, hypoxia, around the world, and Beaver’s Life. This is also the case.
The commonality of these types of games is that they need to rely on urban resources to support a group of workers, and then these workers work to support the city. One of the important jobs is logistics. Generally affected by resource capacity, it will not raise too many workers, otherwise it will be difficult to generate a positive cycle. Therefore, the proportion of logistics work is not large. Most of the workers’ jobs (in production buildings) are in production.
Our game may be closer to Factorio, no need for workers to operate the machine, and the logistics are more pure. The cost of supporting trucks is not high, and players are encouraged to add as many trucks as possible to improve logistics efficiency. Unlike the aforementioned series of games, our road resources are limited. Vehicles must obey traffic rules on the road, and congestion will occur if there are too many vehicles. So it is the roads, not the resources, that limit the efficiency of logistics.
The experience I want to give players is that the operation of logistics will follow certain rules, players can roughly perceive the existence of the rules, and improve the overall efficiency through different layouts and adjustments. It’s not as clear-cut as the conveyor belt rules, and it’s not like a black box with no fine-grained control.
At the beginning, I wanted to design a logic that is biased towards railway transportation. Players plan their own routes. The trucks strictly run on the route, and only receive the loading and unloading goods along the route. Later, I felt that the game experience and interaction were not very good. Recently, it has been changed to smarter rules, which no longer limit the route, and let the AI decide where the vehicles go to pick up and drop off the goods.
The AI dispatched by this logistics system is difficult to do. I don’t want it to be so stupid that the players curse while playing; also, don’t be so smart that the logistics part of the game does not require any choice from the player and becomes a mindless placement game. .
Its complexity lies in the fact that the system has to coordinate three things: supply, demand, and capacity.
When the supply is greater than the demand, the vehicles should not run to load the goods without destination; when the capacity is abundant, the empty vehicles can also be deployed to the area where the capacity is most desired; and when the capacity is insufficient, it is best not to let the cars always concentrate Work in a small area.
Since the road network and supply and demand sides are dynamic (players can expand or delete the road network while playing), new and logistics-related buildings will also be demolished. So while the vehicle is in transit, the destination may also change dynamically, or even lose the original destination (or become unreachable). This also increases the complexity of the algorithm.
As mentioned earlier, one approach to the series of games is to bind logistics workers to specific buildings. For example, workers in bakeries are also responsible for collecting raw materials in addition to making bread; workers in warehouses are only responsible for the entry and exit of goods in their own warehouses. This means that the capacity part of the three elements of supply and demand capacity is bound to a specific building and does not participate in the overall coordination. The algorithm will be simpler.
Another approach is based on the premise that there are fewer workers and more things to do. The player sets the job preference and priority for each worker, and when a logistics task is generated, the worker is matched according to the priority. In this way, the factor of capacity is also ignored.
In our game, the transportation capacity can be very sufficient, and we do not want players to pay attention to a specific car for refined control.
Therefore, when designing the scheduling algorithm at the beginning, the mutual matching of the three elements was considered at the same time. Match the supplier from the demand side, then lock the goods and receiving fields of both parties, and then match the vehicle. When the vehicle leaves, lock all related resources until the waybill is completed or the state that affects the transportation is changed in the middle (for example, the road network is destroyed, the destination is unreachable, or the supply receiver is removed, etc.), and then the state is returned.
The whole process is more complicated, and it took a few days to write it clearly.
Later, I thought that the complexity here is because there are three dimensions to consider. To simplify the algorithm, we need to first simplify the system. We can split the logistics system into two independent subsystems:
First, it is more like a warehousing system like JD.com. When there is an order from a customer (demand side), this system is used to reasonably match warehouses and decide which warehouse to supply to it. This system is only responsible for placing orders: transporting goods X from A to B. Rather than thinking about how the transport will be done.
Second, compare with express delivery systems like SF Express. Receive orders from the previous system, and reasonably use the capacity on hand to complete the transportation order.
Once the status changes, we can revoke the waybill in different ways, depending on the waybill, either during the submission process of System 1, or during the shipment of System 2. This makes each individual system much simpler to implement.
In addition, we have another kind of transportation order, which is to let the empty car go to the parking lot and stand by. This is the player’s active participation. Players can set up empty car depots in areas where the supply side is relatively dense (such as mining areas, which only produce unneeded ones). When system 2 finds that there is a surplus of capacity, it can deploy excess empty cars to go to the depot to stand by in advance. These depots themselves can set filters for parking spaces. For example, empty cars parked in the depot in the mining area can only receive ore waybills, and are not subject to the deployment of waybills for other needs.
This article is reproduced from: https://blog.codingnow.com/2022/09/cargo_matching.html
This site is for inclusion only, and the copyright belongs to the original author.