Topic: wishlist: preferrably split selcted ware among warehouses

31 — 40 of 60 Posts « previous 1 2 3 4 5 6 next »

einstein13 Joined: 2013-07-29, 00:01 UTC+2.0 Posts: 1116 One Elder of Players Location: Poland	Posted at: 2015-12-01, 23:59 UTC+1.0 Tibor wrote: You know two warehouses: W1 with 1 piece of X, W2 with 0 pieces of X. Engine can keep sending wares to W2, and there can be 10 pieces of X on way there... If you really don't want to spot this situation, we can just add randomness to the engine: `X1, X2, X3, X4 //nubers of wares in warehouses with "preffered" check x1 = X1+1 //modified number x2 = X2+1 ... p1 = 1/x1 //(raw) probability p2 = 1/x2 ... S = p1+p2+p3+p4 //sum of raws p1=p1/S //normailzed probability p2=p2/S ... r=Random(0...1) //random number in 0...1 range r < p1 -> send the ware to warehouse "1" r < p1+p2 -> send the ware to warehouse "2" r < p1+p2+p3 -> send the ware to warehouse "3" r < p1+p2+p3+p4=1 -> send the ware to warehouse "4"` of course this algorithm is simple from math side, not from programmistic side Adding one to Xn (to make xn values) is only to avoid infinity problem when dividing. EDIT: This algorithm will not solve completely the problem, but it will avoid the situation when all wares will go to the warehouse with 0 wares inside, while second warehouse will have only 1 ware. With situation avbove (1 & 0 warehouses, 10 wares to split), the solution will be 4 & 7 wares instead of 1 & 10. Better? Or not? Edited: 2015-12-02, 00:09 UTC+1.0 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-02, 21:54 UTC+1.0 So I just pushed branch request_supply_opt with couple of changes in economy.cc file. First, I introduced splitting wares between warehouses with increased priority. It is the simplest design - sending ware to a preffered warehouse with least wares of the type. It works nicely, but I tested it only on small map... Second change is the way how available ware vs request for ware is paired. The algorithm tries to calculate routes between all such pairs (ware<->requestor) and picks one with shortest route. The calculating the route is very expensive. So to save some computations, I reordered all pairs by the direct distances and it tests only first 5 pairs now. So if before the distances were 100,50,20,70,10,15,120,130 and routes for all pairs were calculated, now they are orderd like 10,15,20,50,70,100,120,130 and only route for first 5 are now calculated. The efect is a reduction of cpu use, but on big maps it can lead to picking wares that are not optimal (=not closest to a requestor). It should not happen frequently, probably less then 5%. But I think speed up can be perceived. So this is something that must be decided. Or alternatively I was thinking about Slow PC/Big Map checkbox, that would turn this simplification on. This could be a good compromise... And probably this check box could activate further simplifications that would be coded later on... Top Quote

GunChleoc Joined: 2013-10-07, 15:56 UTC+2.0 Posts: 3317 One Elder of Players Location: RenderedRect	Posted at: 2015-12-02, 22:02 UTC+1.0 I am against a checkbox - this would mean that the user would have to do our (the programmers') job. Is there a way to find a good cutoff, so the algorithm can decide itself? Map dimensions can be read from the map, or you could go by number of flags in the economy. 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-02, 22:23 UTC+1.0 Well, for a single request a number of available wares varies from 0 to 20 (rarely more). The smaller map the lesser average. So for smaller maps it will be 5 from 'smaller number' and for bigger maps 5 from 'bigger number'. Usually there is good correlation between direct distance and walking distance, but mainly seafaring makes thinks complicated (not proportional). Anyway, we can manipulate the treshold 5. I picked 5 because it seems a good tradeoff. If we set it to 10, CPU savings will be much smaller. This is why I thought of check box - let everybody think what he prefers - speed or accuracy..... EDIT: Game uses world Supply - a warehouse is a single supply even if it contains many pieces of ware... Edited: 2015-12-02, 22:40 UTC+1.0 Top Quote

GunChleoc Joined: 2013-10-07, 15:56 UTC+2.0 Posts: 3317 One Elder of Players Location: RenderedRect	Posted at: 2015-12-02, 22:46 UTC+1.0 Well, I expect that most players won't understand the checkbox and never change the value. Even for people who are good at computers, they won't know why it's there and what to base their decision on. I don't really know that part of the code - would it be feasible to make the threshold dynamic, or maybe do a fuller check every few cycles, to make sure that edge cases eventually do get a ware assigned? 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-02, 22:58 UTC+1.0 Well - a ware will be ALWAYS assigned - providing there is at least one available in economy at all. This all is only about cause that supply 100 fields away ('as crow flies') can be closer (walking on a roads) then 5 supplies in distances 20,30,50,70,90. Probability of this is low, but can happen.... On small map you might have 3 warehouses and handful of wares just on road. Let say 7 supplies. Pick 5 closest ones, changes are close to 100% that you will pick just the exact piece of ware as if you tested all wares... I expect that most players won't understand the checkbox Yes, probably.... 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-02, 23:28 UTC+1.0 i don't understad this thing aboout available resources. when a building requires a new resource, it get it if it is available in the economy, i.e. if it is available in a warehouse. if there is no such ware in a wharehouse, then all such wares are already "booked" for a destination and the building must wait. So this modification would take effect only if one has more than 5 warehouses. except you are talking like it referred to wares on the road. does it mean that wares on the road can now be rerouted if they were being sent to a warehouse and another building requires them? Regardless of whether I understood it right, I think there would be a better way to save cpu, although it would likely require a bit more coding. Basically, you'd have to confront the distance as the crow flies with that along a road, and if a ware is closer by road than any other is as the crow flies, then it can skip further calculation. So the logic would be like get closer(crow) ware(1) calculate its distance(road)= distance(road)(1) get second closer(crow) ware(2) if distance(road)(1) <= distance(crow)(2), then send ware 1 else calculate distance(road)(2) if distance(road)(2)<=distance(road)(1) then ware 2 is new ware 1, and start from the beginning. else get third closer(crow) ware 3 EDIT: also, your cutting at 5 wares may or may not work. it would work if the 5 closer wares have largely different distances. but if the 6 closer are at 50, 55, 57, 60, 61, 63, then likelyhood that the closer oneis actually the 6th are rather high. i think a better way to cutoff would be to use difference of distances. if you cutoff as crow-distances that are longer than the shorter road distance calculated so far, then you are safe. or, you could cut off when distance(crow) is twice the diistance(crow) of the closer ware Edited: 2015-12-02, 23:47 UTC+1.0 Top Quote

Tibor Joined: 2009-03-23, 23:24 UTC+1.0 Posts: 1377 One Elder of Players Location: Slovakia	Posted at: 2015-12-02, 23:47 UTC+1.0 yes, the algorithm you proposed is actual there. And this is another reason I reorders wares by distance. If distance (as crow flies) is 100,50,10 - all three routes will be calculated. But now I reorder them to 10,50,100 and chances are that only first one will be calculated... But if distances are like 40,45,50,55,60,65,75 - changes are that all of them will be calculated..... Or an algorithm will go to the middle of expected road and decide to not go on. Astar compares actual_distance + remaining_distance_as_crow_flies to distance_of_best_route_up_to_now and may decide anytime to drop calculation of a route... But this could be after spending a lot of time on calculating a route... So reordering wares itself brings some benefits. does it mean that wares on the road can now be rerouted if they were being sent to a warehouse and another building requires them? In fact I dont understand that logic fully - but yes, also unassigned wares on roads can be under some circumstances used as a supply Top Quote

einstein13 Joined: 2013-07-29, 00:01 UTC+2.0 Posts: 1116 One Elder of Players Location: Poland	Posted at: 2015-12-04, 10:04 UTC+1.0 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. 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-04, 20:55 UTC+1.0 einstein13 wrote: But for me default settings should be as it is now (move resources to the closest warehouse). Otherwise (with no micromanagement) most of resources will come across the whole country without purpose. "Normal policy" (the default) is not changed "Preferably ...." - this is affected. Or do you suggest new type of preferred policy that would include even distribution? You should discuss it now not two weeks after merging into trunk! EDIT: Oops, what I was reacting to??? Edited: 2015-12-04, 21:48 UTC+1.0 Top Quote

31 — 40 of 60 Posts « previous 1 2 3 4 5 6 next »