Currently Online

Latest Posts

Topic: Solution proposals for maritime shipping problems

Tibor

Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-01-31, 10:27

Solstice_s_Return wrote: One solution to mitigate this on big maps would be to assign home ports for players' ships

interesting idea... and non-disruptive


Top Quote
JanO
Avatar
Joined: 2015-08-02, 11:56
Posts: 177
Ranking
At home in WL-forums
Posted at: 2020-01-31, 11:52

The problem that all the division into sub-economies would have to be done after each set flag exists, you are right. But I think it could be handled.
I assume that each warehouse has an explicit identifier (lets call it w), here I presume it to be a number. Flags might have that as well, probably. I would now save an array a_f = (d,w) on each flag f. This should contain the distance d to the next warehouse and the identifier w of that warehouse. These arrays could be filled by just counting. You start with the flag in front of a warehouse and call the distance zero. It's the first flag, so array a_1=(0,0). Now you build the first building and road with the three flags 2, 3 and 4. The function that fills the arrays has to start next to the array with the lowest distance-number, which is easy here. Next flag's array is a_2 (or a_4 if you start the road on your new building) = (1,0) Distance one from warehouse 0.
We build a second building and and road (length: 3 flags), connect it to flag 3. Flag 3 has the array a_3=(0,2). Now we do not need to recalculate everything, we just have to increase the given distance of a_3.
Lets now build a shorter road from our second building to the warehouse. It has 2 flags again, so the distance to headquarters via this road is 3, while old road has distance 5. We call our function to fill the new arrays - but that is not sufficient. We need to add some lines to the function, which check if the new distance is lower than the existing. If yes, overwrite the old array. Else keep the old one and quit. This should even work for equal lenght, and maybe even for weird stuff with circles or whatever. At the moment I think we don't even need special code for destroying warehouses or cutting roads. When we delete existing arrays on each flag that gets a new connection and trigger the function afterwards, this shoud be sufficient and leave most of the arrays in the economy untouched.
With that, wares that want to find their way to a warehouse just have to check which neighbouring flag has the lowest distance in the array (there can be more than one higher or even distances, but only one lower one, even if other warehouses are involved) instead of calculating the complete path (including the question how often this path should be recalculated)


Top Quote
Tibor

Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-01-31, 12:23

What if there will be situation (giving distance to nearest warehouse):

----10------7--------8-------10

The ware would just forever ping between two flags. Because if I understand correctly you are not suggesting complete recalculation, only some partial...

Also imagine situation - new warehouse - now you need to quite extensive recalculation (involving easily over 100 flags) to find out which one will belong to new one warehouse and set their new distance... Also, if some of current flags have inaccurate distance - that would mess up the divisioning...

So I believe every change to road network (new one, dismantled road, new warehouse, dismantled warehouse) should need complete recalculation - within some region. F.e. flags that belonged to warehouse A, might now belong to warehouse B but that needs to be calculated thoroughly....

AI is therefore not doing it on all events, but in periods.... and distance to a warehouse has an expiration time .... but AI is using this only for building new roads - trying to connect as close to a warehouse as possible

But I might be wrong and too pessimistic, somebody just need to start working on this and testing it...


Top Quote
JanO
Avatar
Joined: 2015-08-02, 11:56
Posts: 177
Ranking
At home in WL-forums
Posted at: 2020-01-31, 18:18

The situation ---10---7---8---9---10--- should be impossible, if the function is triggered correctly. I say "should be" because I need some time to figure out if I'm wrong face-wink.png
You would need to have an old road -6-7-8-9-10-. Now you delete flag 6 and build a loop -6-7-8-9-10- and connect the new 10 to the old 7. The setup described in my last post would now empty the array of old 7 (because of the new connection) and then start filling the arrays at new 6-7-8-9-10-11- and probably then find a lower number and stop.
Maybe this could be solved by emptying all arrays that get disconnected from their (or any) warehouse, triggered by road destruction.
You are right, building or destroying a warehouse would potentially cause a lot of recalculation. The question I cannot answer is: How much calculation is needed by the current way of routing, does the potentially more efficient routing calculation outweigh the needs for marking the flags? No Idea, but at the moment I think routing consumes calculation power that depends non-linearly (read: exponentially) on the number of flags.


Top Quote
Tibor

Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-01-31, 20:07

JanO wrote:

The question I cannot answer is: How much calculation is needed by the current way of routing, does the potentially more efficient routing calculation outweigh the needs for marking the flags? No Idea, but at the moment I think routing consumes calculation power that depends non-linearly (read: exponentially) on the number of flags.

One of very CPU intensive thing is looking for nearest available ware. The problem is when you have a lot of providers (can be a warehouse with stock of 100 pieces, but also a flag with single ware) because to find out which one is closest is basically running the pathfinding algorithm for each provider. There are some optimalizations, but not enough. I think this is one of biggest CPU use - especially if the economy is very big - hundreds of flags...

Knowing the current implementation and bottlenecks would be good starting point for redesign.


Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1668
Ranking
One Elder of Players
Posted at: 2020-01-31, 20:36

and yet i remember that the settlers2 routing management, which was very light to use the cpu of the time, was very efficient. perhaps more so than the current one. just one example, if a road was blocked the wares there would automatically take a detour. i've seen many times a road leading to a warehouse being full of wares moving into/out of the warehouse, while the other 5 roads moving into that warehouse are not being used. and sometimes with large economies i try to make multiple roads leading to the same destination to increase transport capacity, but only one of those roads is used, even if badly congested, because the other is slighly longer. Again, i clearly rember settlers2 avoiding this issue.


Top Quote
JanO
Avatar
Joined: 2015-08-02, 11:56
Posts: 177
Ranking
At home in WL-forums
Posted at: 2020-01-31, 21:15

Yes, I remember wares in settlers2 took alternative routes when congestion occurred. But I also remember that wares did not even start to be transported in very big economies. So basically there were the same problems with the one difference that there was an additional functionality for the alternative routing. I liked that, too, but I'm not sure if it should be implemented in the normal routing or if it might fit better into the stuff that handles second carrier and road promotion.
Wares waiting at flags for long time could virtually stretch the length of the road to trick the routing algorithm into picking another path. All this road-business-data is calculated in road promotion anyway.

Tibor
Sounds reasonable. Finding the nearest ware is a though one. I'm wondering if sub-economies could help here, but then I would need a meaningful definition of "distance between sub-economies". As they can be connected via more than one path, this is not really simple...


Top Quote
Tibor

Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2020-01-31, 21:49

According to description the difference is quite cardinal:

  • Widelands - whole route is calculated at once on the begining of transporation and unless something very serious happen is adhered to.
  • Settlers - the ware knows the destination and is able (have to?) to (re)calculate next flag on every flag

So if transporation takes very very long (in widelands) the cognestion on the road can happen or disappear in between and the ware has no capability to react and reroute...

EDIT: So my conclusion is this needs complete rework, not just "patching"

Edited: 2020-01-31, 21:50

Top Quote
Solstice_s_Return
Avatar
Topic Opener
Joined: 2020-01-28, 13:24
Posts: 62
Ranking
Likes to be here
Location: Finland
Posted at: 2020-01-31, 21:55

king_of_nowhere wrote:

and yet i remember that the settlers2 routing management, which was very light to use the cpu of the time, was very efficient. perhaps more so than the current one. just one example, if a road was blocked the wares there would automatically take a detour. i've seen many times a road leading to a warehouse being full of wares moving into/out of the warehouse, while the other 5 roads moving into that warehouse are not being used. and sometimes with large economies i try to make multiple roads leading to the same destination to increase transport capacity, but only one of those roads is used, even if badly congested, because the other is slighly longer. Again, i clearly rember settlers2 avoiding this issue.

I remember at least one occasion with s2 when I had no other option left but to cut the road between several flags and let the wares vanish. I also remember those problems janO mentioned. Fond memories might not be the most accurate..


Top Quote
Nordfriese
Avatar
Joined: 2017-01-17, 18:07
Posts: 1929
OS: Debian Testing
Version: Latest master
Ranking
One Elder of Players
Location: 0x55555d3a34c0
Posted at: 2020-01-31, 22:07

Tibor wrote:

According to description the difference is quite cardinal:

  • Widelands - whole route is calculated at once on the begining of transporation and unless something very serious happen is adhered to.
  • Settlers - the ware knows the destination and is able (have to?) to (re)calculate next flag on every flag

Nope. In Widelands, every ware and worker recalculates the entire route at every single flag. No item in transfer even remembers the full route, only the next one step.


Top Quote