Topic: Ships optimization - project
einstein13 Topic Opener |
Posted at: 2015-08-28, 22:23
For sure most of AIs will build separate economies in different world parts. Yes, this situation makes your port less loaded and your ships less stressed. But for people the situation can change dramatically. How? Let me explain...: I like to build separate parts of economies, connected by water (ships) and not very independent. The Colonies map is designed EXACTLY for that style. In one place I build lots of woodcutters and burners to produce large amount of coal. No other types of buildings is there. In second place there is number of farms producing crops for whole empire. Those two places are very, very quiet (no enemies for long hours of gametime). The last part is using all the produced coal and crops (all are transported) to one spot where everything is processed to highly trained soldiers. That part is not so quiet: closer enemies are fighting very well. Second try can be The Nile map. I used to build great economy (mills & bakeries, smelters, smithies, trainings camps) on one river bank, and the second bank is used for farms (~45 is needed for my type of game). So all crops needs to be transported to the second bank. It is quite problematic to transport everything at once. When I had not enough ships (~10-20) the port was full of crops. Crops going to the second bank (and specific warehouse). In both situations (first more likely!) in ports there were more than 400 wares waiting to be transported. Also when I had enough ships, I had so much to transport, that some ports were stuck while MOVING OUT wares. I remember that some of the queue of wares going out of the port was so long that it took more than 2 hours of gametime to end (I manually cut the roads and all the wares were going out and almost simultaneously they were taken back). I know exactly that those situations aren't very popular and most of them could be solved by a player long before they happened, but I've spotted them in my life. Also I've noticed that those situations cause most problems for ships to be efficient, so I've tried to simulate them. On that situations the algorithms are very different. I can't imagine other situation where we can compare our algorithms in good way. If you have any better idea, I am open to it! I've just noticed that all algorithms have almost the same results (statistics results) for all other cases. Less stress and everything is going the same. And to answer your question: yes, my algorithm for ports should differ only for overloaded ports. This algorithm is the first step to other, more complicated one: load wares that will be taken to other ports directly (destinations exist in ship's list), then take some other wares-destinations, that are "on direction" of a ship. And I have questions for you, Tibor: does your algorithm differ much between widelands branch and python code you've sent me? If not so much, can you add two small patches I've mentioned above?:
Ps.: sorry for so long post... Edited: 2015-08-28, 22:23
einstein13 |
Tibor |
Posted at: 2015-08-28, 23:04
first of all, your python test only let me say naively mimics C++ code. F.e. C++ has to cope with situation when ware on a ship loses its destination (site is destroyed). If all wares on board loss their destination, ship must cope with this. Also current C++ has couple of problematic places when a ship was sent to first port in ports vector - without any good reason. I believe you have no such behavior in you code. So your BASE algorithm in fact performs bit worse in C++ then in your tests. Also in C++ ship sometimes happen to be out of any portdock (and in idle mode), this situation does not happen in your tests as well I presume... I wrote my python code only from my head, it is not 1:1 rewrite from C++, so some slight differences are there, if not for other reasons but because C++ copes with more situations as your model... I see you are focusing on a bit different scenario - on my tests ports are never that badly overloaded by wares.... My approach is to score potential destination ports. So if a ship has 25 wares on it and port X requires a ship, port X can get max 5 points (if there is at least 5 wares waiting there). But loaded wares also matters. If 15 wares go to Y and 10 wares to Z, port Y gets 15 points and Z get 10 points (X already has 5 points). So winner is port Y. And this does not consider oldest wares onboards yet that gets additional points to avoid 'eternal sailing' This is in regard to your proposal "the next port shouldn't be taken from all ports" - this is taken care for .... As for your first proposal - I dont understand what you mean with "rank" and so on... EDIT: if port asks for a ship, score is min ( free_capacity_of_ship , wares_waiting_there ) + wares_going_there plus special bonus for oldest ware if it goes there to this port... Edited: 2015-08-28, 23:11
Top Quote |
einstein13 Topic Opener |
Posted at: 2015-08-28, 23:53
The ships now can have 3 states: iddle, docking and going. While iddling, the ship stands next to destination port and it isn't moving. While docking it is standing next to the port, but in next step of simulation it will go to other port or change state to iddle. Going state is just going between ports: so on river/ sea/ ocean. If all ports are empty, but simulation didn't end (some wares will appear in the future), the ships can iddle.
I understand. Widelands is much more complicated than my model. I have more like static. Widelands is dynamic. I can imagine that in Widelands "the more you transport, the more you have to transport": if you transport 30 wood to one port, in few minutes you will have to transport 15 planks to other port. If you don't transport anything- you don't have to transport anything more. Also destroying port is something I don't think about in my project. All ports are built and will exists forever. So yes, you're right that you can't rewrite algorithm 1:1 to python code. Or... yes, you can, but you have to rewrite much more from Widelands to python. That is worthless
Yes, I am focusing on that scenario, because that situations can differ the most. But I am considering 3 types of scenarios:
Last part of your algorithm is to choose the best port in the list. In Python code you have list of ports and counts: [[port1, count1], [port2, count2], ...] and you are trying to choose the best port based on count number (highest=best). You assumed that the count can't be less than 0 in all possibilities. But with very long distances between ports that can happened. In one of the cases I've spotted that the highest number was... 0. (I was debugging the code, so I've seen the problem there). I can see that in most situations your algorithm is better than base one. That is very good sign! But the algorithm can be even better! My question is: what is our goal? Mean efficiency of the route? Mean existence time of ware (time between appearing in first port and getting last port)? Total simulation time? What do you (all readers) think? einstein13 |
Tibor |
Posted at: 2015-08-29, 21:08
Oh, I had to looked to C++ code, here it is: there is variable score_for_distance that is guaranteed to be above zero. My python code is simply not good/exact enough...
My goal was to fix worst aspects of current implementation and bring some performance enhancements. Without complete rewrite of ship logic. Top Quote |
Tibor |
Posted at: 2015-08-30, 20:59
I have merged my branch - we will see what feedback we will get... Top Quote |
einstein13 Topic Opener |
Posted at: 2015-08-30, 22:01
Great! I want to see the results in game too So I have to wait for Win version --> Tino (I don't like Ubuntu control system). I am currently working on better statistics results display. Now the stats are displayed as:
The last point is using setting disabled in last versions of project. All statistics display can be enabled/ disabled in STATISTICS_DISPLAYS in settings file einstein13 |
einstein13 Topic Opener |
Posted at: 2015-08-31, 16:09
I've added few more functionalities. For example:
All changes were tested manually. Any feedback needed. Results of tests for me were quite... surprising! In every test case, results were different. In some cases my algorithms were better than Tibor's, for other Tibor's had better performance. Algorithms were basicly better than old Widelands one. So there is a progress. If you want to test the project by yourself, please do it! https://github.com/einstein13/wl_ship_optimization einstein13 |
kaputtnik |
Posted at: 2015-08-31, 18:00
Sorry for posting it here... i got a hint while compiling:
But compiling still work Edited: 2015-08-31, 18:00
Fight simulator for Widelands: |
GunChleoc |
Posted at: 2015-08-31, 19:38
That's a hint for code style, which doesn't effect the validity of the code - we don't want lines to become too long, so that they will fit on screen. Busy indexing nil values Top Quote |