Latest Posts

Topic: New pathfinding

GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 3324
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2018-11-20, 09:03

Ypopezios already implemented swapping.


Busy indexing nil values

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: 2018-11-22, 13:26

A suggestion to make swapping more intelligent:

Let´s say you have a long road divided into nice short sections. There´s a log producer (e.g. lots of lumberjacks) at one end of the roads and a building B that needs lots of logs at the other. Halfway down the road, there´s one segment where no carrier has arrived yet for some reason (e.g. the next warehouse is very far away), so all the logs are piling up at the flag F before it. Now build a new constructionsite C at that flag.

The logs for the constructionsite are sent down, but it takes ages until they arrive there due to congestion (as the carrier isn´t there yet to clear the flag). Construction is therefore delayed. The intelligent thing to do now is to swap the destinations of one of the logs waiting at F that is destined for B with a log that heading to C that is waiting at the flag before F until F has capacity for it.

This issue appears only in corner-cases in trunk, but it´ll happen much more frequently when ferries are implemented, so this should be solved for build 21 IMHO. Suboptimal placement of waterways and ferry-yards can result in deadlocks because of this issue.

Edited: 2018-11-22, 13:32

Top Quote
einstein13
Avatar
Topic Opener
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-11-22, 15:19

As far as I know, the described swapping is already in place. But it is working only for wares that are going to the warehouse, not to production sites.

I remember, that I was using this mechanism when I was producing coal from wood. I had pile of woodcutters that were producing much more wood than the roads could handle, but the coal burners were placed along the road. And when coal burners were finished, all the trunks that were going to the warehouse were redirected to the coal burners.

Adding "intelligent swapping" which will include also swapping wares that are going to the other workplaces, can cause other implications. Of course you can find very smart algorithm that will find best possible situation, but it can differ if somebody will change the main transportation system, for example when there will be prioritizing types of wares.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 3324
Ranking
One Elder of Players
Location: RenderedRect
Posted at: 2018-11-23, 17:35

The way this discussion is going, I think the essence of it is:

Performance

  1. Precalculate paths as much as possible, both for roads and ships
  2. Split ware pathfinding into long-range and short-range pathfinder, with long-range ignoring flags that have less than 3 roads

Routing improvement

  1. Make ware swapping more long-distance/intelligent
Edited: 2018-11-23, 17:37

Busy indexing nil values

Top Quote