mmm... the algorithm has to me more complicated than I initially though. To avoid a n^2 cost (or something like that I can't figure it out now) algorithm I need some data structures, still on it. Will use more cpu than the actual algorithm, but it will not be terrible, I think.

For the curious, the current state of the patch:

https://dl.dropboxusercontent.com/u/30024783/longdistance-2.patchEDIT2: *SOLVED*. The problem was not *so* simple to solve, processing the schedule stops in order, and considering nothing more than how full the convoi was, was in fact a lot hiding of computational complexity. I should have suspected this as this smells *similar* to the

knapsack problem.

Well, to make it short, and with an example, in our previous example:

A>B>C>B

When train goes to A, and starts loaging cargo, you know wich is the farthest station in the schedele? Our intuition tells us that it's C, right? No, it's B. It's the last entry. This is a problem.

Also, on:

B>C>B>A

The farthest one, as I already commented, it's A. Another problem.

Second problem is easily solved, I just transverse the list from the *current* stop, and I "cut" the schedule when I reach the current stop again, so:

B>C>B>A

turns into:

B>C

Problem solved, we still need to solve the first one. (Consider that are even worse situations like A>B>C>D>B>C, that are solved also by the algorithm that I'm exposing, we use the simple example for simplicity)

Ok, after I apply the solution just exposed, I transverse the list, and calculate the *minimum* number of stops the traveler will have to do to reach *each* station on the schedule, so:

A>B>C>B

Assumming that we are just loading at A:

B is 1 stop from A, and also at 3 stops. So B is at distance 1

C is 2 stops from A

Then I use our first discussed algorithm, so we transverse the list in *reverse* order.

I start with B, the B that's 3 stops away, I *know* there is a shortest path at just distance 1, according my previous calculations, so I *IGNORE* this stop

Then C, at 2 stops away, that's coherent with my notes that indicates that's effectivelly at distance 2, so I *LOAD* the convoi with passengers to C.

*IF* the convoi still has available space, I check passengers for B, at distance 1, and my notes indicates this is the correct minimum distance, so I *LOAD* more passengers here.

Well, that was done, with one hash table. Could be worse, but still, quite a lot of load. And you know what? If my intuition about this is correct, proportional loading will require this approach, or a similar one to the problem (or maybe not, maybe just with the intial "cut" it's enough,since you load *all* stations, in not a precise order, just in proportion to the passengers "waiting".

Performance, it's worse than our current, simple but fast, implementation.

*BUT* assuming we can pre-calculate this hashes (minimum distances), and re-use them, storing them on the schedule_t class, and knowing schedules are just updated manually by the player (that's really not often), whis can work, because if the hashes are stored in memory, and not created on every convoi load, this is *very* assumible.

Anyway, if anyone has a better idea, or comments about this, just tell me. The patch, with debug printf and get_rep() instead of get_id() (that needs to be reverted but I'm too tired to do it now):

https://dl.dropboxusercontent.com/u/30024783/longdistance-3.patch If anyone needs a binary to test, just tell me (or maybe anyone wants to upload one), but if you ask me for it, please take your time to test and publish your impressions later, please.

EDIT3: Before going to sleep, I compiled a windows version, might not work in something less than windows 7, and *could* require you to install Microsoft redristibutable librarties, probably 2013 ones, or not, or something else, won't look more about it right now

:

https://dl.dropboxusercontent.com/u/30024783/Simutrans_longdistance.exehttp://www.microsoft.com/en-us/download/details.aspx?id=40784