Patch: RouteMarkers

[richk67]

This is a development out from the old Speed Signs patch.

Speed signs had a few nice things, but it would have been a multiplayer nightmare - since the server would have to set the speed range brackets, and these change over time. If it were left client-side, then muchos desyncs!

Concept
OK... the concept: you have a long mainline with a mixture of freight, and passenger (pax) traffic. The passenger trains run a lot faster than the freight (especially when using, say, UKRS... where freight max is 92mph, and pax max speed is 180mph - normal rails).

So you put in passing places, and to ensure the freight goes into them, you put a waypoint in. And another, and another... and then setting up the freight routes becomes a tedium of click this waypoint, then the next, etc.

This is not how its done IRL... the signalman sees a pax train coming up behind a freight, and sees it will be delayed. So the freight is diverted off the mainline, and the pax continues along.

In OTTD we can set up the signalling to send a train into the bypass, and the only way to differentiate the actual trains, is to add the tedious waypoints. So you cannot tell what sort of train will take the bypass... one time it could be the freight, the next time its the passenger. And so, the signals on the exit cannot then be customised to prioritise the mainline, as you cannot tell which route is actually taking the faster traffic.

Introducing RouteMarkers
So here is where RouteMarkers come in. You assign a colour to your train (in the train information panel). So you may decide that "my freight will be dark blue, and my passenger will be yellow". Then at the decision point, you place a coloured routemarker that says "Yellow trains DO NOT come this way". And they will try not to. To ensure differentiation, also place a Dark Blue sign on the route you do not want the freight to take.

The RouteMarkers are a bias - not a hard-and-fast "YOU SHALL NOT COME THIS WAY"... if there is no better way, then the train will still take that route. However, you can add more markers to the route (in my example I have 3 Light Blues in a row!) to make it less-and-less friendly to that colour.

How to Add Markers
In the Rail toolbar, there is now a new icon on the end, with a sign with a red cross. This is the RouteMarker button.

Placing a marker is just like adding signals. It obeys the same placement rules, except it applies to all rails within the tile. So, to avoid confusing the pathfinder, place the markers carefully on multiple diagonal tracks.

The first colour you see will be a Dark Blue sign with a red cross. Click again, and again, and it cycles through the available colours. I have selected 10 colours, but what the selection is may change. When you reach white, the next colour is dark blue again.

You can press CTRL to have the marker change colour in the opposite direction. Use the Remove tool (or press R) to remove the sign in exactly the same way as signals.

Setting Up the Trains
In each train's information panel is a drop down where you can select the train's colour. This choice is NOT included in shared orders, as it may be the very thing you want to differentiate within. However, if you clone the train, then the colour is also cloned.

Let them rip...
Start them up, and they should start separating into the different coloured groups when they reach the signs.

-------
Many thanks to peter1138 & Dalestan for guidance/assistance on using the company colour redrawing to save on multiple colour sprites.

Most thanks to KUDr for his kind work on YAPF part of this patch, and general education on what I could and could not do to the pathfinders

-------

Have fun, and let me know how you get on!

[richk67]

Here is an example of the routemarkers in action.

In the first pic, train 6 is set up as a Light Blue, and some light blue markers are placed to make it avoid the top track.

It avoids the top track, but is now faced with a choice between a long winding route without penalties, and a straight one with 2 penalty routemarkers.

It chooses the long route...and boy, its winding!

[MagicBuzz]

Nice patch
I just tested it, and it seems to work just fine with lastest trunk and my patches

[skidd13]

Nice patch! A merge with the group interface patch would be very usefull. So typo-colors could be assigned to a group.

[red]

Thanks, richk67.

[MagicBuzz]

I played a few hours with this patch, and I have to say it's really fine, and doesn't seem to be bugy.

Althought, I have a suggestion : could it be possible to make it available also for trucks ?
This could help us designing sorts of highways, as we could send faster vehicules to dedicated routes

[Bjarni]

Speed signs had a few nice things, but it would have been a multiplayer nightmare - since the server would have to set the speed range brackets, and these change over time. If it were left client-side, then muchos desyncs!

Maybe this is the wrong time to say so, but what if the speed limits were put in an array in the player struct?
That way it can be configured for each player if needed and you just need to keep the arrays in sync to keep the game in sync.

Anyway, I looked really quickly at the diff here and found two issues.
1: in cloning:

Code: Select all

w->u.rail.routemarker_colour = v->u.rail.routemarker_colour

Since it's code that's common to all vehicle types, you should make sure that it's only executed for trains by writing

Code: Select all

if (v->type == VEH_Train) {w->....

2: autoreplace (and autorenew. They share code at this place) will make the new engine use the default colour setting instead of reading the old one.

A possible solution is likely (I didn't try this):
in ReplaceVehicle(), find (somewhere around line 2060 in vehicle.cpp)

Code: Select all

if (old_v->type == VEH_Train && GetNextVehicle(old_v) != NULL){
    Vehicle *temp_v = GetNextVehicle(old_v);

Change it to something like

Code: Select all

if (old_v->type == VEH_Train) {
    Vehicle *temp_v = GetNextVehicle(old_v);
    new_v->u.rail.routemarker_colour = old_v->u.rail.routemarker_colour;
    if (temp_v != NULL) {

That's all I notice for now. This is not the same as I found every issue, specially because I didn't actually read the whole diff

[richk67]

I played a few hours with this patch, and I have to say it's really fine, and doesn't seem to be bugy.

Thanks. I had an early version just running in a loop on high speed, and it was really gratifying to see the engines diverting around on a merry dance.

Althought, I have a suggestion : could it be possible to make it available also for trucks ?
This could help us designing sorts of highways, as we could send faster vehicules to dedicated routes

I think that will be better done by Road Waypoints, which I think mart3p is taking a look at.

[mart3p]

Very, nice patch. I played for a while without finding any problems.

I replaced some of my waypoints, that keep delivery traffic separate from goods traffic, at the entrance to a busy factory station. Using Routemarkers instead worked perfectly. The great thing is, if you then what to change the routing, you just have to change a few routemarkers. Much easier that changing the waypoint orders for all the trains.

Well done richk67.

The road waypoints are ‘under consideration’ rather than ‘being looked at’. Don’t expect anything very soon, I’ve other things I want to finish first.

[Haukinger]

That's a nice patch ! Do you think it would be possible to make "positive" markers, i.e. having a negative penalty ? So that if you have a junction and want blue trains to turn right you place one "positive" blue marker on the right exist and not 3 negative blue markers on the other three exits...
It might distract an A*-pathfinder, though...

[Quark]

Its looking good, but Ive had to reverse the concept for performance reasons.

All pathfinders work best with a "if tile has XYZ, add a penalty". They all do not like it if you try to give a positive bias - ie. "if tile has ABC, deduct a bonus". However, if you have a "cheaper than straight line" rail, then the pathfinders can go beserk trying desperately to find a better route. The world then slooooooooooooooows doooooooooown!

So I have made the patch more a "route avoidance" patch.

If you place a marker on a route, then the train will be *less* likely to choose that route. Sort of "diversion signs", or maybe "no-entry" signs. (However no-entry implies its absolute - it isnt... if the unmarked route is significantly worse, then it may use the marked route anyway.)

richk67, how about to add penalty for rail without marker and not add it if marker is same as train color? Or add penalty before pathfinder and substract from it when marker encountered? If "straight line" cost is significant to pathfinder then it can count it without pre-added penalty.

[Rubidium]

richk67, how about to add penalty for rail without marker and not add it if marker is same as train color?

Then you will basically take the route with the least amount of unmarked tiles. So to take a longer route, you must mark more rail tiles than the length of the shorter route. That is a really bad idea.

Or add penalty before pathfinder and substract from it when marker encountered? If "straight line" cost is significant to pathfinder then it can count it without pre-added penalty.

The algorithm works under the A* principle. Anything that reduces the 'cost' of a single tile will mean you do not use A* anymore, but something different that has to calculate all possible routes, i.e. there is no way to stop searching one branch till it reached the destination or a dead end. It will also make it possible for trains to loop through route markers if the cost to go around is less than the bonus you get from the route marker.

[Quark]

Yes, the first idea is really bad — I don't think a lot on it

Why not just say clever in first why it's not possible to use bonuses to track? Like that

Anything that reduces the 'cost' of a single tile will mean …[that]… there is no way to stop searching one branch till it reached the destination or a dead end. It will also make it possible for trains to loop through route markers if the cost to go around is less than the bonus you get from the route marker.

But maybe it is possible to add bonus markers list to pathfinder and when it encounter new bonus marker it will check if it already pass him and try to find another way? But it still can make one loop if there is two connected in circle parallel tracks and longer one has marker while shorter not.

[Rubidium]

But maybe it is possible to add bonus markers list to pathfinder and when it encounter new bonus marker it will check if it already pass him and try to find another way?

Bonuses do not work with A*; only costs do. When you start adding bonuses you cannot use A*, which basically means that you have to explore the complete rail network to determine what is the shortest path, which is _very_ expensive.

[Quark]

Maybe modify A* to make it work with bonuses? For example assign to path counter, then if path has larger cost that other way start decreasing counter every tile until path cost will be lowest again or counter reach zero. The counter value is how far pathfinder will look to find bonus marker. For perfomance improvement path can have «select» marker, that will initialize counter, so perfomance will be as usual A* until «select» marker won't encounter.

[MagicBuzz]

Hmmm, a very simple way to do something like bonues but without negative penality is to add a new mark type.

I mean, when you use CTRL+mark, you'll create marks that will have penality points for ANY color but the chosed one.
So if you create a blue marker, then blue trains won't get penality while other trains will. So it should just work as a bonus marker.

PS : and I think this should be the defaut way the markers should work, as it may be more readable when using a lot of colors : "blue trains use blue lines" is more easy to see than "blue trains use lines without blue spots".

[Rubidium]

I mean, when you use CTRL+mark, you'll create marks that will have penality points for ANY color but the chosed one.
So if you create a blue marker, then blue trains won't get penality while other trains will. So it should just work as a bonus marker.

So, you say blue marker means add penalty for trains that are not blue, which means you cannot use it in any way to influence the blue train. Furthermore, a yellow marker on the branch, will make both routes effectively the same as without markers for all colors except yellow and blue.

[MagicBuzz]

I mean, when you use CTRL+mark, you'll create marks that will have penality points for ANY color but the chosed one.
So if you create a blue marker, then blue trains won't get penality while other trains will. So it should just work as a bonus marker.

So, you say blue marker means add penalty for trains that are not blue, which means you cannot use it in any way to influence the blue train. Furthermore, a yellow marker on the branch, will make both routes effectively the same as without markers for all colors except yellow and blue.

In fact you shouldn't have to bother about two markers :

If you put a blue and a yellow marker, then you have these penalities :

red : -20
blue : -10
yellow : -10
white -20
etc.

so blue and yellow trains will have more chance to enter this line rather than other colors

you'll just have to keep in mind placing blue and yellow penality markers on other routes and it should work as expected.

may be "bonus" markers should add a small penality (let's say -10) to any color, while "penality" markers will add a big penality (let's say -100) to the choosen color.
by this way you shouldn't have to multiply penality markers while using several different bonues markers on the same line.

[Haukinger]

So, you say blue marker means add penalty for trains that are not blue, which means you cannot use it in any way to influence the blue train.

Yes, but that's just another side of the same coin - one way you tell passenger trains not to use the sideways and the other way you tell freight trains to take the sideways. The effect remains the same.

Furthermore, a yellow marker on the branch, will make both routes effectively the same as without markers for all colors except yellow and blue.

Isn't that the way markers are supposed to work ?
After all, I think this situation happens only if the network isn't correctly designed.
Example:
If you have two routes from A to B and put a yellow marker on one and a blue marker on the other, blue trains will prefer the blue route and yellow trains will prefer the yellow route - exactly what you want the markers to do.
When you send a red (or unmarked) train from A to B, it has the choice between two evils, namely a route for yellow trains and one for blue trains, both of which it is not supposed to take. So it will take the shorter one, as it would with no markers present - that's the desired effect of markers.
If, however, there's an unmarked (third) route leading from A to B, it will happily take that route - that's the desired effect of markers, too.

EDIT: This works, a very minor tweak in the patch is necessary, see attached file.
The comparisons of sign to _train_routemarker_colour have been changed from == to !=.

Drawback: one has to reserve one marker colour as "unmarked" and not use it for any train. This markercolour is exclusively used at junction where some exits have markers and others have none. Those which have none, get one "unmarked"-coloured marker each. Otherwise those exits wouldn't look different from coloured exits to trains of the same colour as the coloured exit. Nothing terrible happens if you forget an unmarked-marker, however, just as if you forget to turn a signal into a exit-presignal in a presignal-block.

[richk67]

If you put a blue and a yellow marker, then you have these penalities :

red : -20
blue : -10
yellow : -10
white -20
etc.

The bottom line with the A* pathfinding algorithm is that you *CANNOT* have negative penalties on a tile. If the cost of a tile < the cost of a straight piece of track, then the A* performance is *multiple* times slower.

My original design had positive markers (via a -ve cost), and it ran so slow I could barely move the mouse to get to the Exit button!