einstein13 wrote:

1. Prior: upload wares to the ship that are going to the same locations as wares already on the ship
2. If there is more space, upload the rest wares.

Good for me, this "level" of logic is doable and I was thinking exactly about something like this. But still it is not fail-proof. In theory a ship can shuttle between two ports and never visit third one.

Top

Quote

Also this algorithm will make difference only when ship is not able to load all wares in port. If your ideal is to have 1-2 items in a ship, there will be no difference whatsoever.

Top

Quote

How to create good logic for creating new routes? A bit more complex. I've added "return 0" where no return is necessary.

global method:
global::get_distance_between_ports(port1, potr2)

SHIP variables:
list wares_on_board
list destinations_list
//destination_list contains: port object (0), control number - integer (1)

# those values are possible to be more global:
list distances_between_ports_distances --> 2D matrix of integers or doubles
list distances_between_ports_ports --> 1D list of port objects

SHIP methods:

method add_port_to_distances_table(port)
    {
    //Expand tables by 1 row/column
    self::distances_between_ports_distances::add_one_row()
    self::distances_between_ports_distances::add_one_column()
    self::distances_between_ports_ports::add_one_row()
    //fill last record of _ports
    len=length(self::distances_between_ports_ports)
    self::distances_between_ports_ports[len]=port
    //get all values for _distances
    for(itr=0;itr<len;itr++)
        {
        self::distances_between_ports_distances[itr][len]=global::get_distance_between_ports(self::distances_between_ports_ports[itr],port)
        self::distances_between_ports_distances[len][itr]=self::distances_between_ports_distances[itr][len]
        //second value is the same as the first here -> so copy it
        }
    self::distances_between_ports_distances[len][len]=0
    return 0
    }

method get_distance_between_ports(port1, port2)
    {
    itr1=-1
    itr2=-1
    for(itr0=0;itr0<length(self::distances_between_ports_ports);itr0++)
        {
        if(self::distances_between_ports_ports[itr0]==port1)itr1=itr0
        if(self::distances_between_ports_ports[itr1]==port2)itr2=itr0
        if(itr1>0&&itr2>0)break;
        }
    if(itr1<0) //port1 is not on the list
        {
        self::add_port_to_distances_table(port1)
        return self::get_distance_between_ports(port1,potr2)
        }
    if(itr2<0) //port2 is not on the list
        {
        self::add_port_to_distances_table(port2)
        return self::get_distance_between_ports(port1,port2)
        }
    return self::distances_between_ports_distances[itr1][itr2]
    }

method calculate_length(destinations_path)
    {
    old_port=None
    new_port=destinations_path[0][0]
    path_length=0
    for(itr=1;itr<length(destinations_path);itr++)
        #"1" is optional. If 0-> first iteration will add 0 to path_length
        {
        old_port=new_port
        new_port=destinations_path[itr]
        path_length+=self::get_distance_between_ports(old_port,new_port)
        }
    return path_length
    }

method add_to_destinations_list(destinations_list, port, control_number, index)
    {
    list returned_list //length -> length(nestinations_list)+1
    for(itr=0;itr<length(destinations_list);itr++)
        {
        if(itr<index)
            {
            returned_list[itr]=destinations_list[itr]
            }
        if(itr==index)
            {
            returned_list[itr][0]=port
            returned_list[itr][1]=control_number
            }
        if(itr>index)
            {
            returned_list[itr]=destinations_list[itr-1]
            }
        }
    return returned_list
    }

method add_one_new_destination(destination)
    list old_path
    list new_path
    old_cost=0
    new_length=0
    new_length=0
    {
    for(itr1=0;itr1<length(self::destinations_list)-1;itr1++)
        #IMPORTANT: "-1".
        {
        if(self::destinations_list[itr1][1]==0)
            {
            old_path[0]=self::destinations_list[itr1]
            for(itr2=itr1+1;itr2<length(self::destinations_list);itr2++)
                {
                old_path[itr2-itr1]=self::destinations_list[itr2]
                if(self::destinations_list[itr2][1]==0)break;
                }
            old_length=self::calculate_length(old_path)
            for(itr2=1;itr2<length(old_path);itr2++)
                {
                new_path=self::add_to_destinations_list(old_path, destination, 1, itr2)
                new_length=self::calculate_length(new_path)

                #Basics of my idea:
                if(new_length<=old_length*1.2)
                    {
                    self::destinations_list=self::add_to_destinations_list(self::destinations_list, destination, 1, itr1+itr2)
                    return 0
                    }

                }
            }
        }

    //if none of positions are optimial -> add to the end
    self::destinations_list=self::add_to_destinations_list(self::destinations_list, destination, 0, length(self::destinations_list))
    retrurn 0
    }

method add_new_destinations(new_destinations_list)
    {
    for(itr=0;itr<length(new_destinations_list))
        {
        self::add_one_new_destination(new_destinations_list[itr])
        }
    return 0
    }

method find_new_destinations(old_list, new_list){
    list returned_list
    number_of_objects=0
    for(itr=0;itr<length(new_list);itr++)
        {
        if(not(self::check_if_objects_exists_in_list(old_list,new_list[itr])))
            {
            returned_list[number_of_objects]=new_list[itr]
            number_of_objects++
            }
        }
    return returned_list
    }

method find_reached_destinations(old_list, new_list)
    {
    list returned_list
    number_of_objects=0
    for(itr=0;itr<length(old_list);itr++)
        {
        if(not(self::check_if_object_exists_in_list(new_list,old_list[itr][0])))
            {
            returned_list[number_of_objects]=old_list[itr][0]
            number_of_objects++
            }
        }
    return returned_list
    }

method delete_from_destinations_list(list_to_delete)
    {
    for(itr1=0;itr1<length(list_to_delete);itr1++)
        {
        for(itr2=0;itr2<length(self::destinations);itr2++)
            {
            if(self::destinations_list[itr2][0]==list_to_delete[itr1])
                {
                //destinations_list[itr2] -> make it blank
                self::destinations_list[itr2][0]=None
                self::destinations_list[itr2][1]=0
                }
            }
        }
    self::destinations_list::cut_empty_records()
    }

method update_destination_list(){
    list all_destinations = self::get_all_destinations()
    list old_destinations = self::destinations_list[ALL_objects][0]
    list new_destinations = self::find_new_destinations(old_destinations, all_destinations)
    list reached_destinations = self::find_reached_destinations(old_destinations, all_destinations)
    if(length(new_destinations)==0&&length(reached_destinations)==0) return 0 // do nothing
    if(length(new_destinations)==0&&length(reached_destinations)>0)
        {
        self::delete_from_destinations_list(reached_destinations)
        return 0
        }
    if(length(reached_destinations)==0&&length(new_destinations)>0)
        {
        self::add_new_destinations(new_destinations)
        return 0
        }
    // return ERROR - none of cases should be here
    // sequence to make it working again:
    self::delete_from_destinations_list(reached_destinations)
    self::add_new_destinations()
    return ERROR
    }

method find_next_destination_to_go() ->return next port to reach
    {
    return self::destinations_list[0][0]
    }

method dock_to_port(/*whatever it is here*/){
    #
    # old code
    #
    self::update_destinations_list()
    }

method start_from_port(/*whatever it is here*/){
    #
    # old code
    #
    self::update_destinations_list()
    }

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

Top

Quote

Let's start from the beggining:

destination_list is basic list which is the most important for the ship. The wares are not conuted. They are the basic of the route (the ship can't go to the port C while none of the wares wants to get there).

recalculation of destination_list is every time when port is reached. It is made 2 times: when the port is reached (and the wares are unloaded) and when the wares from the port are uploaded.

reading from destination_list is twice:

1. When the port want to upload some wares (and "list of destinations" is needed)
2. When the ship start the journey from any port.

some additional comments:

• ANY name can be changed. I didn't have much time to name correctly.

• The code should be read from the bootom to top, like the computer does.

• update_destination_list is deciding which thing is to do: are we reaching the port or are we starting from the port? Both of things needs recalculating. If both cases are spotted, error should be thrown.

• about delete_from_destinations_list method: this method should delete ONLY one record, the first one. It is not supposed to do more (there is no chance in Widelands mechanism to do more). But the code will delete any number of records. The only known reason to delete the record is to reach a port. You can reach only one port at the time, so you delete only one record. But if is more record to delete, the methods still goes well.

• find_reached/new_destinations are basic comparing two lists. It could be done in once method.

• add_one_destination is the core method of my algorithm. It takes one destination which isn't in the destination_list and it tries to put it anywhere in the middle with condition

  new_path_distance < 1.2 * old_path_distance
  

If the condition never happened, it puts the new coordinates to the end of the list.

• path length is calculated by method calculate_length which is using get_distance_between_ports to get the correct values from matrix distances_between_ports_distances. This can be done more "global", especially for one economy. I've decided to introduce this because calculating distance between ports can be very long. I don't know how it is solved now, but ideally would be calculating only water routes through the map nodes. That can take ages (0.005 sec) to find correct number. For multiple queries in my algorithm it will take more and more time. Memory cost of matrixes will be less than 5 kB per huge economy (35 ports).

• the basic work of methods is splitted into two groups:

  • when the port is reached
  • when the ship starts the journey

Port is reached

update_destination_list
    ->
    find_*reached*/new_destinations
        ->
        delete_from_destination_list

Ship starts new route

update_destination_list
    ->
    find_reached/*new*_destinations
        ->
        add_new_destinations ->
            ->
            add_one_new_destination
                ->
                calculate_length (many times!)
                    ->
                    get_distance_between_ports
                add_to_destinations_list

And yes, wares aren't counting in calculations. They only tells new destinations needed to be added to destination list. They can be added simply in core by refactoring "1.2" into different value like 1.5 or 2.0.

Comparing old and my algorithm there is only one signifficant change: in old algorithm the destinations were in order of wares uploading to the ship (first go, first out). My algorithm allows the ship go to the ports not in the order, but only when it is worth it (1.2 factor means "we can spend 20% more time to deliver the ware quicker").

You have an idea of delivering wares with reagrds to their amount (10 wares to A, 1 ware to B). That is possible to do: just redefine the factor. It can be additional method.

My algorithm PROHIBIT going only between two very close ports while are other wares to other ports.

Maybe I will provide one more example (not only this from old PDF):

1. Ports:
   • All ports are on triangle corners
   • In every corner we have 2 ports.
   • So we have A1, A2 (one corner), B1, B2, C1, C2
2. Wares:
   • I assume that none of wares are produced while this example
   • I don't count wares. Let's say that there are 1 wares to each destination shown below
   • All wares are put to the ship while boarding
3. Ships:
   • One ship starting with A1 port.

STEPS of "simulation":

1) initial situation

Ports and wares:

Ship

2) Ship loaded wares from A1:

Port

Ship

New wares: B1, C1, A2, B2, C2

3) Recalculating route

Ship

• initial

New wares: B1, C1, A2, B2, C2

• step: add B1 to empty list

New wares: C1, A2, B2, C2

• step: add C1 to the end

New wares: A2, B2, C2

• step: A2: route B1->A2->C1 is longer than 1.2 * B1->C1, so A2 goes to the end

New wares: B2, C2

• step: B2: route B1->B2->C1 is shorter than 1.2 * B1->C1

New wares: C2

• step: C2: route B1->C2->B2->C1 is too long; route B1->B2->C2->C1 is ok.

• result:

THE SHIP IS GOING TO PORT B1

4. Port B1

Ports and wares:

Ship:

B1 unloaded

Next port: B2

5. Port B2

Ports and wares:

Ship:

New wares: B1, A1

Algorithm prohibit comparing the route with control number > 0 at the beggining. So the only place is C1->A2. Results are:

Next destination: B2 and C2, after that: C1

6. Port C1 (B2 & C2 are already ahead)

Ports and wares:

Ship:

New wares: C2, B2

Result:

7. end of simulation

the rest is known: as destination list

ROUTE:

A1 -> B1 -> B2 -> C2 -> C1 -> A1 -> A2 -> B2 -> B1 -> C2

As you can see first ware (and its destination) in the list is always the most important.

To solve the problem of "A2" ware here (it goes through all the port before it came to the correct one) we can put it in the first position in port. That will not affect infinite route between only 2 ports. It will affect only empty ships.

Also if you dock in port nearby another destination, it is hard to go there. That is most problematic, because we don't want to see a ship going between two ports and no other directions.

This example was a bit complex. Simple situation with "linear" (river) situation with ports A, B & C will provide route A -> B -> C -> B -> A -> B -> C -> ... (wares produced all the time).

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

Top

Quote

Tibor wrote:

OK, I understand entire algorithm - but it is overcomplicated for a game I think....

I don't understand. What is complicated here? Where is complication? You asked code-like algorithm and I've provided it to you. You asked (before) any algorithm and I've provided that over a year ago. You asked of explanation and I've provided to you now. What is complicated? If a human can produce such an algorithm it isn't too complicated. And what algorithm do you tink is "not overcomplicated for game"? What is "overcomplicated"?! I don't understand you

Also I don't think that this algorithm is very complicated. Some of the methods there are just basic work on lists. You can make it better in C++. I don't know the language well, only basics. So I've created multiple functions doing only one thing each (I've tried to do that).

For me A* (A star) algorithm is complicated. I don't know how it works (exactly, not basicly). But I know that to solve complex problem we need that. Here we have similar problem: find the best path. This problem is very close to Travelling salesman problem and there is no universal solution. In our case it is even more complicated because we have all-the-time changes. In basic problem we have static situation: find the fastest route.

I don't know what you've changed already in your branch, but it solves only bugs. The wrong behaviour of ships is still there. My algorithm will solve most problems. If it works (if it will be coded), I can polish it even more. There are few places that are very simple and none of algorithm is used there.

Also, I can not see any selection of wares that are to be loaded on the ship in a port based on actual route...

I will show it again: https://wl.widelands.org/forum/topic/1762/?page=5#post-14225

And I will tell you AGAIN: there is number of places where I can polish my algorithm. Now it is the simpliest way you can imagine. First step. It will work imperfect, but it will work better than now. I don't know exactly what I can do for "calling more ships to the port", "upload only few products into the ship", and so on. That will take more time to code. Not everything at once.

It is unbalanced, if you pay so much attention to a route, why dont you pay any attention to selection of wares?

I pay attention, but it is more complicated than this part here (selection of wares in port, I understand).

If you are talking about selection of wares onboard, it is not more important than the route. Why? Because for whole economy time is more important. My algorithm prevents of taking never-ending-route and all wares will finally reach the destination. Also it will be (almost) the fastest route for EVERY ware. If you have close ports A1 and A2 and far port B1 (0.5 hour trip), according to number of wares the ship will take A1 -> B1 -> A2 long trip and because of that half of economy stops (I've noticed that in current ship-route model) for 1 hour and the rest of economy will stop for 0.5 hour. With fastest route first half will never stop amd the second half is stopeed for 0.51 hour. So the difference is 1 hour less in first half and 0.01 hour more for the second half. That is why I think that routing is more important. (But wares are important too!)

I have to think about it...

Aks if you have ANY question- I will answer it.

If you want to provide different solution- I am open to it. If you will find much better algorithm or way to solve the route problem, I will go for it. Better means: ship will deliver all resources faster than in my algorithm. And faster in real game, not only here, in the forum posts .

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

Top

Quote