The International Simutrans Forum

 

Author Topic: [Patch (obsolete)] New cornering algorithm - allows for tilting trains  (Read 27481 times)

0 Members and 1 Guest are viewing this topic.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 10672
  • Languages: De,EN,JP
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #35 on: December 27, 2008, 01:42:51 PM »
Sorry, I am teaching physics at university and I can assure you modern train derail mostly on switches with radius smaller than hundred meters or so. Any other normal track cannot exert the necceesary g-force. Even more, the world fastest trains do not have tilting.

Especially the TGV has a quite "aggressive" track routing, since it can tilt the tracks without taking care of freight trains falling to the inner side when stopping in such a curve.

corsa319

  • Guest
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #36 on: December 27, 2008, 02:02:15 PM »
Hi thanks for that answer but did you know that french railways are straighter than almost every railway in BRITAIN! That is why they are so fast also all trains have a limit of speed they can get to before coming off as it is impossible to go round a corner at any speed. Tilting trains only go a small amount faster but it makes up for in time on the long distance routes like the APT-P could have knocked hours of of the west coast mainline. Also many countries in europe have tilting trains like sweden (my partial home) has many and they have some of the fastest trains in Europe.  ???

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 10672
  • Languages: De,EN,JP
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #37 on: December 27, 2008, 02:17:02 PM »
All really fast trains run on dedicated tracks. Epsecially since crossings, slopes and noise emmission prohibit normal tracks. The X2000 is not especially fast given ICE/Valero, Shinkansen and TGV. Moreover, only the cars are tilting with the X2000, the engine is not as far as I know.

Also the Shinkansen is not very straight, given that Japan is a hilly country. But they allow heigher tilting of track and steeper slopes (some as french) for those high speed only tracks.

Tilting is only for comfort (or should be, the swiss trains I found either the tilting makes me retching). This can be easily seen that heigher corner speeds are allowed for the Talgo (I saw that between Portland and Seattle in the US), which is a passive system. Even more, with tilting the center of gravity on a passive system is farther out from the center, i.e. such trains should fall over more easily. Also in this case the engine was the same as used for the regular trains.

corsa319

  • Guest
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #38 on: December 27, 2008, 02:45:53 PM »
Yes also with the shinkansens of japan they rebuilt there whole railway for speed and so it is. One driver was fired for being 2 minutes late and they have never had a crash or derailment... YET!

Offline DirrrtyDirk

  • Devotees (Inactive)
  • *
  • Posts: 1253
  • JR 700 Series Shinkansen
  • Languages: EN,DE
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #39 on: December 27, 2008, 03:55:23 PM »
they have never had a crash or derailment... YET!

Well, they had one - during an earthquake.

corsa319

  • Guest
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #40 on: December 27, 2008, 03:58:54 PM »
fair enough

Offline KrazyJay

  • *
  • Posts: 172
  • Infrastructure & Transportation Junk
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #41 on: December 27, 2008, 06:58:05 PM »
I guess the whole discussion is caused by misinterpretation of the definition of tilting. Tilted tracks do help stability and do allow trains to go around corners faster, but tilted trains on flat tracks can go just as fast as regular trains on the same tracks. Tilted trains only serve convenience. Goods and mail don't compain much about car-sickness and nausea, so non-passenger trains are commonly not tilted trains but can drive on tilted tracks.

Still I think the work James has done is good work. It helps us keeping Simutrans in the same age as RL is. Even a little increase in the use of system resources wouldn't make too much of a problem for the vast majority of Simutrans players.

Offline isidoro

  • Devotee
  • *
  • Posts: 1142
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #42 on: December 27, 2008, 08:41:04 PM »
Ahh - can you tell me where it was talked about?
I'm sorry.  I've tried to find it to no avail.  It was a topic talking about that the way a road vehicle stops when reaching another is very unnatural.  It works like this:  when a road vehicle enters a new tile and that tile is occupied by another vehicle in the same direction, it stops abruptly.  In that topic, it was suggested to look for a way in which the following vehicle would adapt its speed to the one in front of it and just queue.

Incidentally, I remember that Zeno participated in that thread.  It was funny to me that the thread had so many things in common with Zeno's paradoxes about the continuity of movement.   ;D

Edit: Can you explain a little more about the sort of array that you suggest?

Simple.  With a linked list you have to store the data and one/two pointers to link the following/preceding cells.  Too much memory.  And you have to reserve and free a lot of cells.  Too complicated.  Since the size of the array would be small, it is easier to put a fixed size circular array (even of chars) and two (even one) indices to tell us where the head of that circular array is.

[-][-][7][6][8][-][-][-]
       ^H    ^T

H stands for Head and T for tail (in the example above, H=2, T=4).  It's very easy to add/remove items at both sides and if you pack everything in a char array, you can have a 6 items array for the price(size) of two ints.

But I recognize that I'm too low-level biased...  :police:


Offline VS

  • Senior Plumber (Devotee)
  • Devotees (Inactive)
  • *
  • Posts: 4856
  • Vladimír Slávik
    • VS's Simutrans site
  • Languages: CS,EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #43 on: December 27, 2008, 09:56:37 PM »
On the data structures - it is probably silly in the end. Division isn't something to be afraid, especially if it's power of two :P



If you are still interested in the list idea:

First I indeed thought items could be popped and appended (deque?). But it can be improved really simply. You could join end with front, and then simply "rotate" or "move forward around it" two heads, one writing the way in front, one reading it. Once you create this structure, no changes to memory except the values itself. Also backward pointers are not needed since heads always move forward.

You could even create this in a flat array and store value and offset of next item, so that all items are +1 and at the end -N and manipulate index with this... many ideas. But they require always only dereference and addition, no?

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20805
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #44 on: December 27, 2008, 10:03:20 PM »
Update: I am currently working on a new data structure at present, which I am making in template form so that it can be used generally in Simutrans (and, indeed, anything else opensource). It is designed to be an ultra-light array based list of 32 or fewer items (a fixed sized array is used: the number can simply be manipulated in the code, of course). I will post it when it is done.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20805
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #45 on: December 28, 2008, 12:11:12 AM »
I have now written a very lightweight class in a header file, but cannot for the life of me get the program to compile: whenever I add:

Code: [Select]
#include "../tpl/fixed_list_tpl.h"
to one of the existing files, I get dozens of cryptic errors, stating that I am missing a semicolon before the first line of code below the #include statements, even though there would never be a semicolon there normally, and there was no semicolon there before. Removing the reference to my new file allows it to compile. I get the impression that the file is somehow not properly included for compilation, but I cannot find a way of adding it: when I try Project>Add Existing Item (in MS VC++) and add fixed_list_tpl.h, it has no effect (and is actually the only header file added in that way: the others seem to work fine without explicitly being added!).

For reference (for the low-level fans), here is my code:

Code: [Select]
/* A very light 32 or less element list
 * using a fixed sized array with a
 * head and tail node. Template type.
 *
 * Author: jamespetts. Released under the terms
 * of the Artistic Licence. Intended for use
 * with Simutrans, but may be used elsewhere.
 */

#include <typeinfo>
#include "../simtypes.h"
#include "../simdebug.h"

template<class T> class fixed_list_tpl
{
fixed_list_tpl() : size(0), head(0), tail(0)   { }

public:

T get_element(uint8 e)
{
if(e > size)
{
return NULL;
}
else
{
uint8 i = add_index(head, e);
return datum[i];
}
}

void clear()
{
size = 0;
head = 0;
tail = 0;
}

void trim_from_head(uint8 trim_to)
{
if(size <= trim_to)
{
return;
}
else
{
head = add_index(head, trim_to);
size -= trim_to;
}
return;
}

void trim_from_tail(uint8 trim_to)
{
if(size <= trim_to)
{
return;
}
else
{
tail = subtract_index(tail, trim_to);
size -= trim_to;
}
return;
}

uint8 get_size()
{
return size;
}

void add_to_head(T datum)
{
uint8 i = subtract_index(head, 1);
data[i] = datum;
head = i;
if(tail == head)
{
tail = subtract_index(head, 1);
}
else
{
size ++;
}
}

void add_to_tail(T datum)
{
uint8 i = add_index(tail, 1);
data[i] = datum;
tail = i;
if(head == tail)
{
head = add_index(tail, 1);
}
else
{
size ++;
}
}

bool add_to_head_no_overwite(T datum)
{
if(size < 32)
{
add_to_head(datum);
return true;
}
else
{
return false;
}
}

bool add_to_tail_no_overwrite(T datum)
{
if(size < 32)
{
add_to_tail(datum);
return true;
}
else
{
return false;
}
}

uint8 get_index_of(T datum)
{
uint8 tmp = 999;

for(i = 0, i < 32, i++)
{
if(data[i] == datum)
{
tmp = i;
break;
}
}

if(tmp > 31)
{
return NULL;
}
else
{
uint8 index = subtract_index(tmp, head);
return data[index];
}
}

private:

T data[32];

uint8 size;

uint8 head;

uint8 tail;

//These methods are used for automating looping arithmetic
uint8 add_index(uint8 base, uint8 addition)
{
uint8 tmp;

if((base + addition) < 32)
{
return base + addition;
}
else
{
tmp = (base + addition) - 32;
}

if(tmp < 32)
{
return tmp;
}
else
{
//There could be a sophisticated system of trimming here,
//but it would take extra work/memory/processing power, and
//is only used internally, so not worth it. This code should
//never be reached.
return 31;
}
}

uint8 subtract_index(uint8 base, uint8 subtraction)
{
uint8 tmp;

if((base - subtraction) < 32)
{
return base - subtraction;
}
else  //Will be > 32 if has gone to < 0, as unsigned ints are used: overflow.
{
tmp = (base - subtraction) + 32; //Should re-set the overflow
}

if(tmp < 32)
{
return tmp;
}
else
{
//There could be a sophisticated system of trimming here,
//but it would take extra work/memory/processing power, and
//is only used internally, so not worth it. This code should
//never be reached.
return 31;
}
}
}

I should be very grateful for any ideas on how to make it compile properly with the other code.

Offline isidoro

  • Devotee
  • *
  • Posts: 1142
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #46 on: December 28, 2008, 02:43:41 AM »
I'm deeper low-level still  8)   ;)

Perhaps the missing semi-colon is at the end of the template class definition?

One suggestion: why making the 32 part fixed and not variable/adjustable, yet constant.

Offline VS

  • Senior Plumber (Devotee)
  • Devotees (Inactive)
  • *
  • Posts: 4856
  • Vladimír Slávik
    • VS's Simutrans site
  • Languages: CS,EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #47 on: December 28, 2008, 10:18:48 AM »
Yup, my C++ reference says there should be a semicolon after final } of template.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20805
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #48 on: December 28, 2008, 11:39:57 AM »
Isidoro/VS,

excellent, thank you, that did it. And I will take your suggestion, Isidoro, and make the number a const so that it can be changed by changing a one line definition, instead of a number of values.

Offline VS

  • Senior Plumber (Devotee)
  • Devotees (Inactive)
  • *
  • Posts: 4856
  • Vladimír Slávik
    • VS's Simutrans site
  • Languages: CS,EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #49 on: December 28, 2008, 12:22:45 PM »
You could even make it a template parameter?

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20805
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #50 on: December 28, 2008, 12:30:33 PM »
You could even make it a template parameter?

Hmm... how would I make a const a template...? Or have I misunderstood you? (The class is a template class...)

Offline VS

  • Senior Plumber (Devotee)
  • Devotees (Inactive)
  • *
  • Posts: 4856
  • Vladimír Slávik
    • VS's Simutrans site
  • Languages: CS,EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #51 on: December 28, 2008, 12:47:59 PM »
...
template<class T, int N=32> class fixed_list_tpl

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20805
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #52 on: December 28, 2008, 12:57:44 PM »
VS,

ahh, excellent idea - thank you :-) Makes it much more flexible and efficient. I hadn't even realised that that was possible with C++ until now.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20805
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #53 on: December 30, 2008, 10:23:39 PM »
I have finally perfected my fixed list design (attached as a header file - feel free to use under either the Artistic Licence or the GPL v. 2 for anything), but am having trouble applying it to the reading ahead of the way in Simutrans. I have attached a patch with my code as it currently stands, but, as will be apparent from trying it, it does not work reliably: the speed ought be smoothed, but this does not appear to work well in practice; also, corners are often either ignored or under-estimated in severity, and the speeds set for them too high. I suspect that the problem might be in the synchronisation of the various different sets of data (the tile itself, whether any given tile is a corner, the speed limit for that tile, and the previous direction if it is a corner), although working out how to synchronise them is not in the least easy.

I should be most grateful if anyone could take a look at the code and give me some pointers as to how to progress from here; I have spent much time on this speed smoothing code, and I very much hope to be able to move onto more straightforward things (such as adding a cumulative effect for consecutive slope tiles as requested earlier in this thread), and for adding weight limits to bridges and tunnels. Any assistance would be greatly appreciated.

Edit: Updated versions of the files attached: see post below.
« Last Edit: January 01, 2009, 04:50:58 PM by jamespetts »

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20805
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] New cornering algorithm - allows for tilting trains
« Reply #54 on: January 01, 2009, 04:57:29 PM »
Update:

I have now found and fixed a number more bugs in the fixed list class: an updated version has been added to the post above. I have also replaced the original patch with a heavily updated one, although I am still having considerable problems making the corner smoothing (and, indeed, any degree of look-ahead for the speed limit at all) work, and would very much appreciate any help.

I have attempted to solve the synchronisation issues by putting the speed limit data in a hashtable with a pointer to the particular tile in respect of which it is the speed limit as the key, and then retrieving that data by obtaining it from the hashtable using the pointer to the current tile, obtained the usual way for every hop. I still have a fixed list for a fixed number of future tiles, and a method for setting the target speeds (in the hashtable) by reading that list sequentially. I have found that, for some reason, the current tile seems to jump backwards in relation to the route index, and so have written code to repopulate the lookahead table backwards from the current position whenever it jumps behind what is still stored. The code in the modified patch is also considerably cleaned of old commented-out code that should make it much easier to read.

However, the program still does not work reliably. The trains will sometimes slow to a crawl on the straight (the correct speed for a hairpin bend), and take 90 degree corners at full speed. Any assistance in making this work would be very much appreciated indeed, especially as I have now spent about four days doing almost nothing else.

Edit: A further problem: testing it informally against the default 101 binary (r2197) for speed on a fairly large save game in Pak128, the speed seems greatly reduced: fast forward does not even double the speed on the modified version. I have some doubts that any speed limit smoothing will work within a reasonable level of performance because of the enormous complexities that I discovered when attempting to read ahead in the code (it is not as simple as has been suggested above of simply looking for the speed limit a number of tiles ahead and reading from that number of tiles down the list: the routing system appears to be internally inconsistent in unpredictable ways, and a record must be kept of whether all of the previous tiles were corners and what the direction of their previous tile was in order properly to compare for corners, all of which records must be synchronised with each other and with the current position (the latter of which appears to behave erratically and requires regular re-synchronisation). Adjusting for those complexities in the read-ahead code is probably what causes the performance impact.

I should still be very grateful for anyone to look at the code (and the light-weight fixed sorted list is available for anyone's use), but I have doubts about the future of speed limit smoothing due to the performance impact of the necessarily enormous code. If anyone can look at my code and find a way of doing it better with less of a performance impact, I should be extremely pleased. My view at this stage is that, unless anyone can rework the code to minimise the performance impact, the best way forward is to revert to a modified version of my original code (using the fixed sorted list) for speed limits, without smoothing, but still applying a system which checks the overall angle of the bend within a given number of steps and reduces the speed limit accordingly instead of (unrealistically and somewhat bizarrely) applying additional friction to the corners (which has the anachronistic effect of slowing all vehicles, even if they are already travelling extremely slowly, and making more powerful vehicles less affected by corners than less powerful ones). The speed would not be smoothed, but it is not in any event in the default code for changes of speed limits due to anything else, so the effects of the modified code would not be greatly different to the present situation in respect of speed limit transitions. Despite the sudden slowing, I still maintain that the original code is preferable to the default code in that it is more intuitive, more realistic, and gives players more interesting incentives to smooth their high-speed networks (but not so much the low speed ones, in respect of which there would be fewer incentives to make them straight: just as in reality).
« Last Edit: January 01, 2009, 05:52:09 PM by jamespetts »