Topic: wishlist: preferrably split selcted ware among warehouses

41 — 50 of 60 Posts « previous 1 2 3 4 5 6 next »

Tibor Joined: 2009-03-23, 23:24 UTC+1.0 Posts: 1377 One Elder of Players Location: Slovakia	Posted at: 2015-12-04, 21:52 UTC+1.0 einstein13 wrote: I am against checkbox too. As I understad now: You want to add a window with some values that will differ a bit the results of algorithms inside the core of Widelands? It will not work properly with multiplayer. Or you will spot more problems then. This must be considered. I dont understand completely how logic is distributed between server and clients, but a checkbox is just an idea... We would mainly discuss about treshold. Do we want consider only x nearest supplies (available wares) at all? Small maps negligible difference, but on huge maps - this will make an big difference - in speed.... Top Quote

GunChleoc Joined: 2013-10-07, 15:56 UTC+2.0 Posts: 3317 One Elder of Players Location: RenderedRect	Posted at: 2015-12-05, 01:30 UTC+1.0 I think the interval idea has its merits, to make the threshold a bit dynamic - or set it at a percentage of max possible distance?. Busy indexing nil values Top Quote

Tibor Joined: 2009-03-23, 23:24 UTC+1.0 Posts: 1377 One Elder of Players Location: Slovakia	Posted at: 2015-12-05, 19:49 UTC+1.0 If we tie a treshold to the size of map (increase for bigger maps) than we can just throw it away. Especially on big maps it would have biggest benefits - bigger inaccuracy but huge CPU savings. Top Quote

Tibor Joined: 2009-03-23, 23:24 UTC+1.0 Posts: 1377 One Elder of Players Location: Slovakia	Posted at: 2015-12-05, 19:53 UTC+1.0 In other words, with current algorithm we can achieve shortest routes, let say average length 80 hoops/fields. With my proposal, the average will be 85, but we will reduce calculations to 1/3. On small map average route length will be increased by let say 1%, on big let say by 5-10% But calculation of routes on big maps is really huge CPU intensive... Top Quote

king_of_nowhere Topic Opener Joined: 2014-09-15, 18:35 UTC+2.0 Posts: 1668 One Elder of Players	Posted at: 2015-12-05, 20:28 UTC+1.0 an increase in lenght by 5% to reduce calculation by 60% would be perfectly acceptable, if the increase in lenght was spread evenly. But as it is, there is the risk that in some situations - namely, a narrow water channel, with wares required to make long detours around it - will sistematically give bad routes, that twice or more longer than needed. Some thought is necessary to avoid such systematic errors. think of the nile map, for example; a ware could be 10 steps away, but actually require going all around the map. if the 5 closest wares are on the other side of the river... Just off the top of my head, the distance-crow could be considered only over passable ground that the player controls. that will avoid the problem with a river. another solution could be to always run the distance calculations until the crow-distance of the ware is equal or bigger than the road distance of the best ware found so far. that way the program would always find the best ware. the cpu saving would be smaller, but still having ordered the wares in order of distance means that only a few of them will actually be calculated, so there is still a save compared to the current situation. Thinking about it, it may well be the best solution. We're talking statistically here, and statistically people tend to make straight roads, so the crow-distance isn't much smaller than the road-distance. in the vast majority of cases, it would only calculate a couple of wares before deciding that one is certainly the best. It may even be more efficient that the actual threshold at 5. Top Quote

Tibor Joined: 2009-03-23, 23:24 UTC+1.0 Posts: 1377 One Elder of Players Location: Slovakia	Posted at: 2015-12-05, 20:39 UTC+1.0 king_of_nowhere wrote: But as it is, there is the risk that in some situations - namely, a narrow water channel, with wares required to make long detours around it - will sistematically give bad routes, that twice or more longer than needed. Some thought is necessary to avoid such systematic errors. think of the nile map, for example; a ware could be 10 steps away, but actually require going all around the map. if the 5 closest wares are on the other side of the river... This. Exactly this is risk. But if there is only 5 supplies or less on map, no difference at all. Must be considered Just off the top of my head, the distance-crow could be considered only over passable ground that the player controls. that will avoid the problem with a river. another solution could be to always run the distance calculations until the crow-distance of the ware is equal or bigger than the road distance of the best ware found so far. Take distances 40,45,50,55,60,65,70. Route distance to the first one is 85. The result is that all of them might be calculated, or partially calculated..... Situations like distances 5,50,100 are rare... Top Quote

king_of_nowhere Topic Opener Joined: 2014-09-15, 18:35 UTC+2.0 Posts: 1668 One Elder of Players	Posted at: 2015-12-05, 23:32 UTC+1.0 Tibor wrote: king_of_nowhere wrote: But as it is, there is the risk that in some situations - namely, a narrow water channel, with wares required to make long detours around it - will sistematically give bad routes, that twice or more longer than needed. Some thought is necessary to avoid such systematic errors. think of the nile map, for example; a ware could be 10 steps away, but actually require going all around the map. if the 5 closest wares are on the other side of the river... This. Exactly this is risk. But if there is only 5 supplies or less on map, no difference at all. Must be considered Just off the top of my head, the distance-crow could be considered only over passable ground that the player controls. that will avoid the problem with a river. another solution could be to always run the distance calculations until the crow-distance of the ware is equal or bigger than the road distance of the best ware found so far. Take distances 40,45,50,55,60,65,70. Route distance to the first one is 85. The result is that all of them might be calculated, or partially calculated..... Situations like distances 5,50,100 are rare... well, as i said, most times roads are straight, so if first distance is 40, road distance is likely to be 50 or 60. if first ware is 85 because there are obstacles, maybe second willl be 60. most times. so most times it really will do less calculations, and if it does more, then it will likely be a time when more calculations are needed. so far the game can take 8 players at 30x speed, those calculations can't be that bad. other possible ways too check would be to keep looking for more wares if distance-road > 2 * distance-crow. because iif the distance by road is much longer, then there is probably some obstacle with some detour. if it is not too long than the distance-crow, then you can't go wrong by much. Top Quote

einstein13 Joined: 2013-07-29, 00:01 UTC+2.0 Posts: 1116 One Elder of Players Location: Poland	Posted at: 2015-12-07, 02:03 UTC+1.0 What about checking not-all-possibilities: Get all distances (not road) Sort them (like Tibor suggest) Have a loop where we are trying all real distances (by roads) save min distance and the ware with that feature if min distance is less than next not-road-distance, break the loop That is solution for long lakes or rivers (like The Nile), but will not work with distances like [80,85,87,88,88,89,90,..., 100] where min distance will be 101. But breaking the loop can be also `if(min_distance < next_not_road_distance * factor) break;` where factor > 1. einstein13 calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/ backup website files: http://kartezjusz.ddns.net/upload/widelands/ Top Quote

Tibor Joined: 2009-03-23, 23:24 UTC+1.0 Posts: 1377 One Elder of Players Location: Slovakia	Posted at: 2015-12-18, 21:34 UTC+1.0 Well, let revive this discussion a bit. I propose a compromise. If a map is bigger then 160.000 fields (f.e. 400x400), the threshold will be applied. Otherwise - no threshold. Can it be? Top Quote

king_of_nowhere Topic Opener Joined: 2014-09-15, 18:35 UTC+2.0 Posts: 1668 One Elder of Players	Posted at: 2015-12-18, 23:52 UTC+1.0 Tibor wrote: Well, let revive this discussion a bit. I propose a compromise. If a map is bigger then 160.000 fields (f.e. 400x400), the threshold will be applied. Otherwise - no threshold. Can it be? On one hand, it makes sense, because bigger maps have more problems with cpu usage. On the other, bigger maps are also those where there is the largest number of wares. In smaller maps the threshold is redundant because likely there won't be more than 5 wares. In a bigger map instead the threshold will be more likely to cause malfunction. What's wrong with my proposal that the algorithm will stop searching only when the crow-distance of the next ware is bigger than the best road-distance found so far? In 90% of cases, the shorter crow-distance is also the shorter road-distance, so the program will stop calculating after two or three wares, big cpu saving. And in that few % of cases when it will have dozens of wares to analyze, those will be exactly the cases where those farther wares are the shorter ones by road transportation, so you'll be glad the cpu took that extra effort. Anyway, even in those rare cases it won't consume any more cpu than right now, so it's still a big cpu saving overall. furthermore, I have seen that often the program will request a ware from the other side of the map even with a warehouse chocking full of the requested ware a stone throw from where the request was issued (full story here https://wl.widelands.org/forum/topic/1762/?page=11#post-15596) so you should fix that malfunction first. It's little good to have a better algorithm for sorting the closer ware if then the program will not use the closer ware. Edited: 2015-12-18, 23:53 UTC+1.0 Top Quote

41 — 50 of 60 Posts « previous 1 2 3 4 5 6 next »