Improve tradeships

Post Reply
Posts: 10
Joined: Sat Jun 06, 2020 12:12 pm

Improve tradeships

Post by Gliese852 »

I would like to describe here in more detail what was done in PR 4984.

The main goal is to make the position of the NPC ships balanced when starting the game, so that it does not look strange, and did not turn into something completely different over time.
The second goal is to increase as much as possible the presence of ships at stations

First, we need to implement the ability to spawn a ship as if it has been flying along a given route for a long time.
The first two commits are dedicated to this.

1. Add class for pre-calculating spaceship path.

The task is to calculate the speed and the remaining fuel at any point on path for a given path length and ship parameters. I took as simple a case as possible - one dimension, gravity is not taken into account. But we need to take into account that the ship is getting lighter, and it's acceleration increases with time. Also, upon reaching a certain threshold acceleration, the ship will not increase the acceleration so as not to break down, but will decrease the power of the engines.
So we can have 2 flight modes: force = const, and acceleration = const.
For these modes you need to use different formulas.
We also need to leave a reserve of fuel, and a reserve of engine power when braking.

The flight of the ship can consist of two or three stages - [accelearation, decceleration] or [acceleration, free flight, decceleration], it depends on whether it has enough fuel to thrust all the way, or not.

For these calculations, the PrecalcPath class was created.

It takes route parameters and ship parameters into the constructor, and immediately calculates the general path parameters - the number of stages and their division along the length of the route. After executing the constructor, you can immediately find out the total duration of the route.
Then (using a class method) you can set the distance from the beginning of the route, or the time from the beginning of the movement, and all parameters of the ship at this point will be calculated - speed, fuel, elapsed time, distance traveled.
Well, now we can calculate the speed and fuel consumption of the ship at any point in the given abstract path, we can go to the second commit,

2. Add function PutShipOnRoute

The task of this function is to position the ship on the route, according to a given ratio of elapsed time (t_ratio). t_ratio = 0.0 means the beginning of the route, t_ratio = 1.0 means the end of the route. t_ratio = 0.5 means that exactly half of the route duration has passed.

Why was time selected as a parameter? Because it is supposed to generate a random number from 0 to 1 and pass it to this function. The probability of finding a ship where it is moving quickly is lower than where it is moving slowly. Therefore we need to place ships more densely at the beginning and at the end of the route and less densely in the middle. But time flows evenly, so if you choose a random t_ratio, this ideally solves our problem - the ship is more likely to spawn in "slow locations" and less likely to spawn where it moves fast.

The next problem is that the flight of a ship depends very much on its initial mass, so we cannot just generate a ship on the route, we must spawn the ship before performing this function, put equipment, cargo into it, and only then call this function. Therefore, it takes an already created ship as a parameter, and just moves it to the right place. As the beginning of the route, the function takes the current position of the ship - and as the end - the position of the given body of the space station.

There is a small chance that a ship will be created inside a star, for example, and that's not good. To avoid this, the autopilot function was used, which protects the ship from collisions with space objects, CheckCollision. If this function returns anything other than 0, trouble can happen. Therefore, we move the ship to a safer place, while maintaining the distance to the destination. We simply rotate the ship's route around the destination point until it stops crossing the obstructor.

Now we have reached the preliminary goal - we can safely create ships as if they flew along this route for a long time. Now we can use this to create more beautiful ship traffic.

3. Improve Tradeships.lua

Typical life cycle of a tradeship in a system is: jump into the system near a star, fly to the port, sit there for a while, undock and jump out of the system. To keep it simple, I did not introduce intra-system flights between stations, yet. So we get a simple "ray" graph - from the star to the stations.

While studying the question, I realized that a convenient traffic characteristic is the flow of ships. That is, how many ships pass on average per hour. Based on this characteristic, we can derive several rules for successful traffic generation:
- The flow to the system must be equal to the flow from the system.
- The flow to the system is equal to the sum of flows on the routes.
- The sum of flows on routes is equal to the sum of flows at stations.
- The number of ships at station or route = flow * time spent at the station or route.


The last bullet shows that by changing the parking time, we can change the number of ships at the station, for a given flow. But we cannot change the time of passage of the route, so the flow completely determines the number of ships on this route.

Unfortunately, we cannot provide a dense flow to all stations of the system, for example Sol, because this would require too many ships, so I decided to introduce a non-linear route popularity in order to concentrate most of the traffic on several routes. The popularity (weight) of the route is calculated for each type of ship separately, and is calculated as:

weight = num_docks^2 / route_duration^2

num_docks - number of landing pads per station
route_duration - the duration of the route by a ship of this model.

After calculating the popularity, we can find the most popular route, and start the flow calculation from it. MAX_ROUTE_FLOW was selected as the main free parameter - flow to the most popular station in the system. Knowing what weight the maximum flow corresponds to, we can calculate flows for all routes. Summing them up, we can get the total flow of ships into the system - that determines at what interval ships should jump into the system.
Now we know the flow to the station, and we can calculate such a parking time so that it is loaded as we need. Second free parameter - MAX_BUSY determines the maximum load of the most popular station. I would like the ships to stay longer at unpopular stations, so the occupancy of the station will not linearly depend on the flow, but radical.

Since we calculated the duration of the stay, we know how long, on average, a merchant ship should stay at the station so that it does not overflow or empty with a given flow.

But there are several nuances.

if there is too much flow to the station, the parking time may turn out to be too short, and problems may begin at large time accelerations. So I introduced another parameter MIN_STATION_DOCKING_TIME. Now, if the calculated landing time is too short, we reduce the flow to the station, until the time equals the specified limit.

Also, we can generate too many ships, and this will affect performance. therefore, after calculating the total number of ships in space, if it turns out to be more than MAX_SHIPS, we reduce the total flow of ships into the system.

Having determined the total flow of ships into the system, we can calculate how many ships should be in hyperspace. To do this, we calculate the lifespan of the hyperspace cloud for each ship when jumping from each near system, and calculate the weighted average.

Now all preparatory calculations are over, and we can generate ships!


Since we already know how many ships should be in the system, we just create that number.
The main task is to arrange the ships so that with the passage of time the situation on average does not change.
We have already calculated all possible local routes for all possible ships in this system, and all possible hyper routes for all possible ships, with weights. All we need is to select rows from these tables in accordance with their weights, and place the ships on the routes or hyperspace clouds.

If we need to put a ship on a local route, we first create it at the point where the ship usually exits hyperspace, not far from the star, equip it, and then use the PutShipOnRoute function to move it to a random point on the route.

If the ship should be spawned docked, we also select from the station table according to the weights where to dock it.

Key traffic events

After all ships are inserted, it remains only to support the process. This is provided through deferred execution of functions.
The flow of ships from hyperspace is provided by the function, which is launched at random intervals to ensure the correct flow of ships on average. It creates one new random tradeship in the hypercloud. In fact, even then the tradeship's destination is predetermined, because the target port depends on which star to create the hypercloud.

The main events that govern local traffic are onEnterSystem and onShipDocked.
Since the destination was determined in the cloud, upon entering the system, the merchant simply goes there.
When landing at a station, a random duration of a tradefhip's stay at the station is generated, on average equal to the previously calculated average stay time for current station. This ensures the estimated load of the station.

Ok, the process is going on, but we need to control it.

Debugging tools

The Tradeships tab was created in the debug window.
In general, everything is clear there, but I would like to add that you can sort a column in any table. Also, some tables are associated with the system map, when you click on a line with a station or ship, it is centered in the system map. And vice versa.
Also, a table with equipment and cargo opens for the selected ship.
In order not to spam the console, I moved the log here, search by string is also supported.

Known problems

A sharp increase in the number of ships in the system opens up some problems that were not noticed before.
- Drop in performance - this issue has already been resolved, sturnclaw already has a branch in which the number of ships can be greatly increased without sacrificing performance
- Autopilot problems - ships sometimes crash on planets, or can hit each other when docked, etc. In fact, these are not such frequent events, and I hid the log in the debug tab, so all these deaths pass almost imperceptibly, and I have a PR work in progress, which should significantly improve the situation.

I tried to keep it as simple as possible, but it didn't work out very well. I hope this text will make it easier to understand the motivation and implementation of PR. Questions and suggestions are accepted.
Last edited by Gliese852 on Sun Mar 28, 2021 4:22 pm, edited 1 time in total.
Posts: 1314
Joined: Tue Jul 02, 2013 1:49 pm
Location: Beeston, Nottinghamshire, GB

Re: Improve tradeships

Post by FluffyFreak »

Nice work and an excellent writeup.

Much appreciated, thankyou!
Posts: 908
Joined: Fri Dec 20, 2013 9:54 am
Location: Tellus

Re: Improve tradeships

Post by impaktor »

I applaud the ambition level. I'd advice to get the PR in a mergable state as soon as possible so we can get it into master before you loose motivation, or some other thing pops up. Would be a shame to see this bitrot.

Just ideas for the (maybe distant) future:

To model which ship goes to which station (both for out-of-system and future inter-planetary local flights), one could build a fully dynamic economy, for starters just make each market produce and consume goods, where e.g. production of robots depend on amount of iron, and have trade ships act on this market.

Note: what and how much is brought into the system would still be hard coded, but given that caveat, the local economy should be able to be dynamic, to the point that blowing up a bulk ship with grain in deep space will increase the grain price at the target station.

regarding how long they stat at a station, could be coupled to how long it takes to unload, with depends on how many ground & flight crew, but this is likely too much to include in the model right now.

It would be cool if landing fee went up when few pads were available, so incentive would be to dock shorter time, or choose another station.

ideas for commodity prices
Post Reply