The International Simutrans Forum

 

Author Topic: Enhanced Braking (drive ahead)  (Read 3473 times)

0 Members and 1 Guest are viewing this topic.

Offline Fabio

  • Devotee
  • Administrator
  • *
  • Posts: 2898
  • The Pak128 Guy
    • Visit me on Facebook
  • Languages: EN, IT, RO, FR
Enhanced Braking (drive ahead)
« on: January 06, 2009, 11:54:55 AM »
The braking problem has come in the new bend algorithm, it's one of more troublesome, appears now and then, and has defferent solution (signals, stations, etc...)

I propose a single braking routine for trains and roads. Unfortunately i can't code it myself, but i'll try to be as accurate as i can and i hope some patcher will be interested in.

  • instead of looking into the next tile, the driving routine should look n tiles ahead, where n is the breaking distance, calculated according to convoy total_weight, max_speed and braking_friction (given in DAT and different for trains and road vehicles).
  • when this routine sees a speed limit or a stop, it calls a braking routine, with parameters start_speed, end_speed (0 to stop) and n as the number of tiles in which it needs to stop.
  • this braking routine gradually slows down the actual speed, to reach the expected end_speed


Offline colonyan

  • Devotee
  • *
  • Posts: 526
  • Full and Warm
Re: Enhanced Braking (drive ahead)
« Reply #1 on: January 06, 2009, 02:35:06 PM »
...? With this we will have more smoother braking?
I would like to see smoother braking.

Offline Fabio

  • Devotee
  • Administrator
  • *
  • Posts: 2898
  • The Pak128 Guy
    • Visit me on Facebook
  • Languages: EN, IT, RO, FR
Re: Enhanced Braking (drive ahead)
« Reply #2 on: January 06, 2009, 02:57:37 PM »
With this we will have more smoother braking?

this is the idea. i really hope it's doable...

this is what we said elsewhere>

Couldn't be possible, to look - say - 4 tiles ahead looking for a speed limit (either imposed by tracks, either by corners) and, if so, start reducing gradually the speed?
These limits could be considered by the routing procedure the way signals are, using the smooth breaking used for a red signal.

That would be better, certainly - but I'm worried about the impact on performance. If looking a number of tiles ahead is already done in the signalling code, however, it might work. Indeed, the calculation of the speed limit could be done x tiles ahead instead of on the fly, rather than as well as, making the computation not take much longer (except when it first starts, when it will not have any data as to the next tiles). Do you happen to know where the look-ahead part of the signalling routine is in the code?

Look-ahead is costly only if you read N tiles for every tile advanced, if you keep "driving" the virtual convoy head in front of it and remember what you passed, you have to read only one tile per advance again... I don't know how to explain this better. But the question can be freely chosen from "is looking at more tiles [from map] per move costly" and "is looking at more data [of any form] costly".

This would be great and also wery realistic, because each vehicle in RL is driven taking into consideration what is expected to be on their way in the next few km. the number itself of tiles ahead could depend on the max teoretical speed for a given vehicle (a high speed train will consider more kms of way ahead rather than a slow truck, because their braking time is different). and if this routine limits the speed in switches as well, this is good, because switches slow down trains in RL as well.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Devotee
  • *
  • Posts: 18410
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Enhanced Braking (drive ahead)
« Reply #3 on: January 06, 2009, 03:19:11 PM »
Ahh, unfortunately, I spent days trying to make this work, and failed: my attempts drastically impacted on performance in larger games, and could not be made to work reliably: the looking ahead part would behave erratically and jump seemingly at random, making the whole list have to be recalculated from scratch every few tiles; the system for reading back whether any given tile is a corner and the direction that was taken before the corner, and then the target speed for that tile based on a hashtable of the tiles ahead also failed for reasons that I was never able to track down - the routing system is massively complicated and has, as far as I can tell, made proper look-ahead breaking impractical without a complete rewrite of large chunks of the main game engine. I did post some experimental code here if anyone would like to try again to make it work.

Offline isidoro

  • Devotee
  • *
  • Posts: 1128
Re: Enhanced Braking (drive ahead)
« Reply #4 on: January 06, 2009, 05:28:20 PM »
I see this only feasible for railway, and not too difficult at first glance.  I'll have a look.  For road veehicles, I see it more complicated (overtaking, for instance).

Edit:  I have had a look at the code and it is already implemented, AFAIK.  In simvehikel.cc:1086 and following:
  • if vehicle is the first of the convoi and number of tiles to the next stop is less than 4:
  •      if at half of last tile of a station: limit speed=25
  •      else limit speed depending on how many tiles to go: 3->200 kmh, 2->100 kmh, 1->50 kmh

Only some friction can be added as seasoning if wanted, but it is already there.
« Last Edit: January 06, 2009, 06:43:50 PM by isidoro »

Offline Fabio

  • Devotee
  • Administrator
  • *
  • Posts: 2898
  • The Pak128 Guy
    • Visit me on Facebook
  • Languages: EN, IT, RO, FR
Re: Enhanced Braking (drive ahead)
« Reply #5 on: January 06, 2009, 07:27:21 PM »
fair enough, thank you!

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Devotee
  • *
  • Posts: 18410
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Enhanced Braking (drive ahead)
« Reply #6 on: January 06, 2009, 07:40:10 PM »
Isidoro,

that only works when a stop is approaching, not a speed limit: the transitions to lower speed limits are still harsh.

Offline whoami

  • Devotees (Inactive)
  • *
  • Posts: 693
Re: Enhanced Braking (drive ahead)
« Reply #7 on: January 08, 2009, 06:29:40 PM »
(The following is said without me having read, let alone understood the source of the existing program and the published patches, because I seriously lack experience and efficiency in reading C/C++ code, not having used such for years.)

my attempts drastically impacted on performance in larger games
That alone is a sufficient reason to omit a feature like that, unless it can be improved.

Quote
and could not be made to work reliably: the looking ahead part would behave erratically and jump seemingly at random,
I'd have guessed that the route is fixed until further notice, and stored in a way matching the order of the tiles, because the convoy has to know where it needs to go (an unordered list of tiles could otherwise explain that erratic behaviour).

Quote
making the whole list have to be recalculated from scratch every few tiles;
Is this due to route recalculations (e.g. at schedule refresh or track/signal change), or does it also happen if the convoy travels as planned? If it's only the first, then a notification is needed to invalidate the look-ahead buffer.

Quote
the system for reading back whether any given tile is a corner and the direction that was taken before the corner,
The current direction of the train need not be known, if you limit the prediction to start two tiles ahead, from when on the curves can be determined only from tiles that are going to be passed. The speed for the next tile could initially be calculated from acceleration capability, speed limit and friction alone, and after travelling two tiles, be taken from a buffer variable.

Quote
and then the target speed for that tile based on a hashtable of the tiles ahead also failed for reasons that I was never able to track down
Hashtable? A hash allows to find things fast, but may have a bad overhead (mostly memory consumpton) if used for a low number of target values, and it doesn't sort the values. (As said, I didn't read the source code.) So, is this the reason for tiles showing up at random?
Wouldn't a linked list of tiles (working as FIFO) be a better choice?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Devotee
  • *
  • Posts: 18410
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Enhanced Braking (drive ahead)
« Reply #8 on: January 08, 2009, 06:53:02 PM »
I'd have guessed that the route is fixed until further notice, and stored in a way matching the order of the tiles, because the convoy has to know where it needs to go (an unordered list of tiles could otherwise explain that erratic behaviour).

There is a route object, with an index, so that one can get at the next step by index of the route. But my system used that, and it still behaved erratically.

Quote
Is this due to route recalculations (e.g. at schedule refresh or track/signal change), or does it also happen if the convoy travels as planned? If it's only the first, then a notification is needed to invalidate the look-ahead buffer.

No - I had set the system to clear the tables and start again for route recalculations, but things would get out of step even when travelling as planned, such that the vehicle would appear to jump four of five steps backwards in the route. I had set up a special data structure especially for this operation, which enabled a placeholder to be set on a particular datum, and had written code set the placeholder to the current tile at each step. The data structure was read ahead a fixed number of steps in advance of the placeholder, and stored the tiles in the data structure. Whenever a tile was passed by a vehicle, the previous tile was removed from the structure. However, every few tiles, the current tile would not be able to be found in the data strucutre, and the whole structure would have to be recalculated. Using a debugger, I discovered that the reason for this was that, for some reason, the current step was seemingly jumping backwards to steps that had been deleted before. I could not make any sense of it.

Quote
The current direction of the train need not be known, if you limit the prediction to start two tiles ahead, from when on the curves can be determined only from tiles that are going to be passed. The speed for the next tile could initially be calculated from acceleration capability, speed limit and friction alone, and after travelling two tiles, be taken from a buffer variable.

There is no reason to calculate the train's actual speed, since what is being done is set a speed limit for the tiles ahead: the calculation of the actual speed is then done in the normal way, up to that limit. All that one has to do then is reduce the limit in gradual steps rather than all at once. But the direction taken before the corner is necessary, since one has to compare the start direction with the greatest deviation from that direction in the number of specified steps (themselves depending on the speed limit of the track). One cannot simply look at one step at a time, or else one will never register an angle of more than 45 degrees (I tested it), since, for smoothing purposes, trains move forward in units of less than one tile, and treat a 90 degree bend as a series of 45 degree bends in sub-tiles.

Quote
Hashtable? A hash allows to find things fast, but may have a bad overhead (mostly memory consumpton) if used for a low number of target values, and it doesn't sort the values. (As said, I didn't read the source code.) So, is this the reason for tiles showing up at random?
Wouldn't a linked list of tiles (working as FIFO) be a better choice?

The hashtable was used as a lookup, to synchronise the values, since I needed to know the target speed, the pre-corner direction and whether the step itself was a corner all at the same time. I could not use a series of separate lists for that, as they would get out of synchronisation (I tried it). So, there was a single sorted list (not a linked list, which I am told is inefficient, but a very lightweight data structure based on a fixed size array that I wrote especially for the purpose) of steps, abstracted from the route index, and a hashtable with pointers to those steps as the key, and the value being a struct of all the other data that I needed. I could then read the current tile in the usual way, get a pointer to it, and obtain the requisite values from the hashtable for the speed limit and so forth. Simply trying to calculate the number of steps away from the head of the list that the vehicle actually is did not work, as the number seemed to vary in an unpredictable way. However, I found that, more often than not, the entry to the hashtable for that particular tile had not been created (even though the route system had seemingly stepped over all the tiles), and the values would have to be calculated from scratch anyway.