News:

Do you need help?
Simutrans Wiki Manual can help you to play and extend Simutrans. In 9 languages.

Bug on inserting/removing stops to lines

Started by Borgoth, July 24, 2009, 09:55:58 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Borgoth

Or maybe someone considers this a feature...

Route A->B->D->E. Let's say it's a tram looping around town, on one-way track. Could be trains too. One way track is the key. Behaviour is same for all kind of lines, but more serious problems occur with one-way tracks.

Tram is currently heading to E.
I alter the line by adding new stop C between B and D.
Tram is now heading to D.

On one-way track system getting back to D is a problem. Even if it wasn't one-way, it'd be considerable amount of time and money wasted going a whole back to previous station for absolutely no reason.

Not having looked into code, I'm guessing that convoy destination is stored as the number of stop on its schedule, and if schedule is altered, this number now points to something else. If this is the case, could the current destination just be saved as the stop ID or some other suitable identifier that doesn't get messed up when inserting new stops?

Severous

Hi

This was a massive problem in my 1810 game.

With hundreds of carts on some lines it was a chore to amend line routing efficiently. 

Adding a stop often meant many vehicles were now heading back to where they just came from.  No income was generated at that point (as individual vehicle schedule was not opened). Vehicles are not only going the wrong way but are retracing steps and 'unearning' the income they have already built up for this trip.  Unless I went through each vehicle on the line I was heading for massive congestion and drops in income.
Regards
Sev.

Dwachs

here is a patch that fixes this. If the schedule is changed, the first entry in the new schedule that matches exactly the old target is chosen as new destination.
Parsley, sage, rosemary, and maggikraut.

jamespetts

Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

z9999

Is that patch match for a bus route like a-b-c-d-c-b-a ?
And if destination doesn't contain on route anymore, where they to go ?

Dwachs

Quote from: z9999 on July 25, 2009, 11:58:56 AM
Is that patch match for a bus route like a-b-c-d-c-b-a ?
And if destination doesn't contain on route anymore, where they to go ?
If the old route is a-b-c-d-e-a-b-c then the first 'a' etc will be chosen. But only if the exact coordinate matches.

If the old destination is no more in the schedule the original behavior comes in, that is, if the vehicle goes to destination 5 in the old schedule, it will go to destinatoin 5 in the new one.
Parsley, sage, rosemary, and maggikraut.

z9999

Quote from: Dwachs on July 25, 2009, 04:16:20 PM
If the old route is a-b-c-d-e-a-b-c then the first 'a' etc will be chosen. But only if the exact coordinate matches.

That is funny. That break the game.

Many of the cases, for example you replace one stop by stop moving tool, order of other stop don't change. So, you must check first, position of next stop is the same or not. In this case, you don't need to change next stop.

And also you need to search best match stop.

Dwachs

Quote from: z9999 on July 25, 2009, 09:07:37 PM
Many of the cases, for example you replace one stop by stop moving tool, order of other stop don't change. So, you must check first, position of next stop is the same or not. In this case, you don't need to change next stop.
you mean if schedule-change window is open and stop moving tool is used?

Quote
And also you need to search best match stop.
What is the best match stop? Here, a read-my-mind-button could be usefull *g*
Parsley, sage, rosemary, and maggikraut.

z9999

Then I must say current behavior is better than your patch.

whoami

What's the state of this?

I think that deterministic behaviour could be achieved by adjusting effective schedules step-by-step:
- insertion at position i of the line schedule: increment position (within effective schedule) by 1, for all convoys with a schedule position >=i
- deletion at i: do not adjust convoys' positions, but take care of overflow (reset to first if at the last position)
- append: nothing to do

As there can be several changes in one dialog call, these need to be queued until the whole dialog has been confirmed. BTW, hasn't a CANCEL option been under consideration?

z9999

I think that is not good.
That is the difference of version n and version n+1.

If you use pause and open line window and change it and close it. schedule will change from version 0 to version 1.
If you do the same again, schedule will change from version 1 to version 2.
In this case, schedule of each convoi is still version 0, so difference of version 1 to version 2 is meaningless.

Dwachs's patch compares to schedule of each convoi. I think this is correct way, and it is the best place to compare.

whoami

Quote from: z9999 on August 28, 2009, 06:03:48 AM
In this case, schedule of each convoi is still version 0, so difference of version 1 to version 2 is meaningless.
That is the reason to queue the changes, to apply all of them in order. Or do you mean the case where player wants to cancel version 1 entirely, and change from version 0 to version 2 instead? That's not the program's fault then.

But there is another problem with the deletion of schedule items for trains: track and signalling may not be fit to allow this schedule change. Instead, the trains could still go to the deleted stop, and only then delete it. Well, this is even more complicated, and not really transparent to the user.

What I didn't cover is the case where delete+insert are used to replace a stop. The stop-mover can't be used if only certain lines are to be moved. Special case handling could be used to not change convoys' schedule position, if it looks like the player intends a replacement.

Amelek

#12
why can't just convoys, going to deleted schedule point, go to most closer (in terms of BFS) stop in schedule? That won't break anything.

whoami

With trains, it can break stuff, e.g. by causing congestion due to vehicles taking unforeseen routes, eventually leading to deadlocks.

z9999

Changing schedule and recalculate route is difference thing.
In current code, all convoi, exclude loading convoi at destination, recalc their route after changing schedule.

z9999

Since read-my-mind-button was requested, I wrote a yet another patch.
Please freely test it, but it may not read your mind. :)

- using An O(ND) difference algorithm and its variations to find better destination.
- convoi going to depot keep their way after changing line.
- if next destination is the same position, it won't re-routing and keep their way after changing line.
- will avoid convoi going back wherever possible. this is most important.

Dwachs

Quote from: z9999 on September 13, 2009, 08:02:30 AM
Please freely test it, but it may not read your mind. :)
goto is evil -  but it may help at mind-reading :D
Parsley, sage, rosemary, and maggikraut.

z9999

I found many bugs. Old one didn't work well.
New patch attached.

Quote from: Dwachs on September 13, 2009, 01:56:54 PM
goto is evil -  but it may help at mind-reading :D

Thanks. break;break;break; is better ?

prissi

#18
goto is not necessarily evil; if several breaks can be avoided, a goto is superior. I used also some in the airplane routing for that purpose.

Having said that, it seems, since the route know last starting and endpoint a clever best match is indeed the best solution. I will look into your patch.

EDIT:
Maybe a check with cnv->route[0] and cnv->route[max_index] for current target and starting position should go in first, since this is the ultimate criterion. What do you think?

z9999

I'm ashamed to say I can't understand the purpose to check cnv->route[0] and cnv->route[max_index].
Is there any advantages ?

prissi

I though it would make life easier, since the route contains the starting point of the convoi and the current endpoint. Under most conditions, if those two match the schedule entries, this give the correct position in the schedule. Only if no match is achieved, one needs the more comlex approach you did.

So I think you did the difficult part ... I will have a look at it.

z9999

As I wrote before, route and schedule is different thing.
The place where convoi goes is not aktuell.
cnv->route[max_index] isn't the same as aktuell.

So, cnv->route[max_index] is meaningless to determine aktuell.
But it seems you don't like this approach, I don't work for this anymore.

Dwachs

Quote from: z9999 on September 14, 2009, 05:52:28 PM
But it seems you don't like this approach, I don't work for this anymore.
:::)
Quote from: prissi on September 14, 2009, 04:38:33 PM
So I think you did the difficult part ... I will have a look at it.
According to prissi's statement, your patch is under consideration for 'considered patches'. Don't give up that quick.
Parsley, sage, rosemary, and maggikraut.

prissi

Inspiered from z999 version, I included a little variant of the thema.

z9999

#24
Your patch is completely wrong.
As I said "where is the next stop" and "where to set aktuell" is very different thing.
We must think both.

Your patch behave exactly the same as Dwachs's patch.
No difference, worse than that.

prissi

The main problem was a & instead of a correct % which resulted in the first two stops only allowed. That made it indeed much worse. I also added test for the next three stations to have a "better" best  match. (Although the nextnext one was already be good enough for my testcases.)

z9999

Okay, since you changed the code, I tested r2677.
Nothing worked in this version.


If I insert one stop, convoi will going back to last stop.
The behavior of this version is the same as old version of simutrans.
Your patch doesn't need.

prissi

There was still some errors in the code.

Please, see the pm.

z9999

I don't get your PM, sorry.


I found many problems in your code.

is_same

Quote
         if(aktuell<new_fpl->get_count()  &&  current==new_fpl->eintrag[aktuell].pos  ) {
            // next pos is the same => keep the convoi state
            is_same = true;
         }

In this case, you need to do nothing, because convoi can go there.

But later on, we need to check is_same again to avoid deadlock of choose signal or airplane.



is_depot

This will change the schedule position of depot.

Assume A convoi has schedule 1-2-3-depot-4-5, and it is going to depot.
If I change line, it will bocome 1-2-depot-3-4-5.

Is this intended behavior ?
If I start this convoi from depot, it will go back to 3.



quality
Quote
            int quality =
               (new_fpl->eintrag[ i ].pos==current)*8 +
               (new_fpl->eintrag[(i+1)%new_count].pos==next)*4 +
               (new_fpl->eintrag[(i+2)%new_count].pos==nextnext)*2 +
               (new_fpl->eintrag[(i+3)%new_count].pos==nextnextnext);
This is not good, because 8 will always win to 4+2+1.

Assume Line 1-2-3-4-5-4-3-2.
I removed seocnd 4 stop during a bus going 5 to 4 result is 1-2-3-4-5-3-2.
In this case, the first 4 stop is 8 and 5 stop is 7.

This convoi go to 4 and back to 5. This is very bad, but 5 stop is also not suitable destination.
It must go forward.

prissi

You raise valid questions. I have long though about quality. I think 3, 4, 2, 1 are a good compromise. If only next matches, then the convoi will go to next; but if current and next matches, it will win.

z9999

Thank you.
I'm not yet fully tested but it seems to be well working.
And it is really fast(!) than mine.

By the way, is it possible to add this code below ?
It will avoid deadlock problems.

Quote
                  aktuell %= new_count;
                  how_good_matching = quality;
               }
            }

            is_same = new_fpl->eintrag[aktuell].pos==current;

            if(how_good_matching==0) {
               // nothing matches => take the one from the line
               aktuell = new_fpl->get_aktuell();
            }

prissi


z9999

#32
Quote
                  aktuell %= new_count;
                  how_good_matching = quality;
               }
               // if we go to same, then we do not need route recalculation ...
               is_same = new_fpl->eintrag[aktuell].pos==current;
            }

Sorry prissi, your code is wrong.
Because if old aktuell is 5 and new schedule has only 2 stops, it crashes.

Why did you write that code in loop ?
It needs only once after exiting loop.


Okay, mine is also wrong, it also causes crash,sorry.
It must check here.

Quote

            if(how_good_matching==0) {
               // nothing matches => take the one from the line
               aktuell = new_fpl->get_aktuell();
            }
            // if we go to same, then we do not need route recalculation ...
            is_same = new_fpl->eintrag[aktuell].pos==current;


         }