Latest Posts

Topic: A few ideas to optimize road transport

king_of_nowhere
Avatar
Topic Opener
Joined: 2014-09-15, 18:35
Posts: 1668
Ranking
One Elder of Players
Posted at: 2014-09-17, 18:42

So, I was playing nile, which is a map with a thin strip of land around a river surrounded by desert. You can't grow large, you have to grow long. I planted a wood around my headquarter, with all the wood economy, and as I expanded east and weest I started setting up food economies there. After a while, i see a shortage of water. i make more wells and for a while the problem is fixed. then i find again lack of water, but this time I had over 1000 buckets in storage. looking better, I saw the problem: the production area east was sending buckets to the production area west, and viceversa. while a bakery would immediately get water sent as soon as it consumed it, it would still take it 2-4 minutes to arrive, and in the meanwhile the bakery would remain inactive. all the carriers on my main highway were spending most of their time carring a bucket from flag 1 to flag 2, then taking another bucket from flag 2 and bringing it to flag 1. And I'm just glad I took great care to make a road without choke points or longer segments, or i would have had a complete traffic jam too.
THat's a problem for a human, but it is a much biggeer problem for ai. a human can make better roads that are more difficult to jam. even if there is a traffic jam, a human can figure out a solution (in my case, I just made more bakeries, accepting that they would all work at 30%). an ai, not so much. an ai may get completely stuck, with all the flags saturated of items and all carriers unable to move. So fixing this problem is also a step towards a better working ai.

So, I got a few algoritms that should be relatively easy to implement and should fix or at least mitigate the problem. I have no programming capacity whatsoever (i took a university course in my first year that entailed 10 hours of very basic programming; now I don't even remember what the programming code name was), or I would try to write them myself.

algorithm 1: if two wares of the same type (from now on, I will call them water for simplicity) are going to two distant places, swap their destination if it would be shorter.
I would like to put it under a spoiler for the sake of an orderly post, but can't find the function

- whenever a water W1 is sent to building B1 check
__ IF there is another building B2 that consmmes water THEN check
____ IF there is another bucket of water W2 coming to B2, THEN check
______ IF ((distance W1 to B2 + distance W2 to B1) < (distance W2 to B2 + distance W1 to B1)) THEN // make it at least 3 steps shorter, so to avoid risk of loops with redirections
________ redirect W1 to B2 and W2 to B1 instead.

If there are many buildings closer to the destination and many buckets coming to them, the calculations to make the minimum distance could take a while and cause lag - especially if the game has to do it for every resource produced. To avoid that, the game could just be instructed to make a comparison with a random water bucket. it will be much less efficient that way, but still an improvement over the lack of this algorithm. I specifically conceived it so that it cannot make things any worse.

Algorithm 2: if two buckets crosses each other on a road, swap their destination
- taken a road going between flag 1 and flag 2
__WHEN a bucket W1 is dropped af flag 1 with destination flag 2
____ IF there is at flag 2 a bucket W2 with destination flag 1 THEN
______ swap the final destination of W1 and W2
______(or teleport W1 to flag 2 and W2 to flag 1 if it's simpler; on the practical side, there is no difference whatsoever)
This is the simplest algorithm, and should not require much calculus. Another important test is that it cannot complicate things in any case: redirecting W1 and W2 in that situation has the same exact effect of teleporting each bucket to the next flag, so in the worst case scenario at least the carrier didn't have too lose time. The weakness of this algorithm is that it won't do that much good. the wares would still move up until midway, and when redirected there they would only skip one road. Going backwards, those wares would "bounce" against other wares sent, cascading a mechanism that will eventually save some time. But still, it would only partially mitigate the problem, not ensure that every resource is sent to the closer building

Algorithm 3: similar intent to 1, but focused on the building instead of the resources
- whenever a water is sent to a building that consumes it
__ consider all buildings that are scheduled to receive a bucket
__consider all buckets going to those buildings
__ remove all destinations from all buckets, then
____ take building 1: that building had 2 buckets going towards it? then send to it the closer 2 buckets you can find
____ take building 2: it had 3 buckets coming to it? then give it the closer 3 buckets you can find, provided you didn't already sent them to 1
____ repeat for all buildings using water
obviously distance is measured by road required to get there, not as the crow flies
while this algorithm does not provide the minimum possible travel for all resources, it also does not require extensive calculation to determine that minimum. If the "picking order" of buildings is always the same (for example, the older buildings get precedence) there is also not the risk of creating loops where buckets keep being redirected to different buildings without ultimately going nowhere: if you always start with building 1, then a bucket going towards it will always be closer to it than to anything else. there may be some slight disruption is you make a new bilding, but i doubt it would be noticeable.
Eventually, it would also be possible to simply run this algorithm for all wares every once in a while, say every 30 seconds. that would not prevent wares being sent to the wrong place, but it would redirect then soon enough to avoid the worst delays. I think of the three algorithms, this is my best idea and the most likely to work without requiring too much calculation form the processor.

Notice how, with all algorithms, the number of buckets going to different buildings is NOT modified. if three buckets were going to that backery, three buckets are still going to that backery, they will simply be not the ones originally assigned there. so there is no risk that your farther buildings will be underused.

EDIT: edited for clarity

Edited: 2014-09-17, 18:53

Top Quote
Tibor

Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2014-09-17, 22:10

Hi,

the AI choked with wares on roads is known problem, indeed.

I dont know the code that controls movement of wares, so I cannot comment on feasibility of your ideas, but my idea how the AI should cope with choked roads is to control the production. Because if you have flags full of water, you probably produce too much water. So AI should have tresholds ( and I implemented them to some degree) - if above upper treshold, stop production, if below, resume production, or built new production buildings.

Also more warehouses mitigate the problem, and also AI when notices a flag full of wares tries to built a "shortcut" from it - additional road. Usually it is not possible thought face-smile.png

But at the end of day - AI is too stupid to cope with narrow passages (as bottlenecks for ware transportation) on the same level as human player can, this is what we have to live with...


Top Quote
king_of_nowhere
Avatar
Topic Opener
Joined: 2014-09-15, 18:35
Posts: 1668
Ranking
One Elder of Players
Posted at: 2014-09-18, 19:49

well, this had less to do with ware passage on choke points, and more with optimal ware distribution in a delocalized economy, that would minimize ware transportation times. the fact that unoptimal ware distribution lead to stuff being sent all around the map and can also result in clogging roads was merely a side effect.


Top Quote
ypopezios
Avatar
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-06-26, 18:40

An implementation of Algorithm 2 is available here. Nile should now be a much more playable map.


Top Quote