Bug on inserting/removing stops to lines

[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.

[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.

[jamespetts]

Excellent - thank you for the patch!

[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]

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.

[z9999]

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]

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?

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*

[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]

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]

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]

Please freely test it, but it may not read your mind.

goto is evil -  but it may help at mind-reading

[z9999]

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

goto is evil -  but it may help at mind-reading

Thanks. break;break;break; is better ?

[prissi]

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]

But it seems you don't like this approach, I don't work for this anymore.

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.

[prissi]

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

[z9999]

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

         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

            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.

                  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]

Good idea, thank you.

[z9999]

                  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.

            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;

         }