New map features

[wallyweb]

Makes me wonder what a track finder has to do with speed limits?

The pathfinder applies a penalty for using slow bridges, so that vehicles will try to avoid them.

Is this penalty really needed for game play? A bridge speed that is slower than a vehicle's maximum speed could cause a bottleneck thus forcing the player to build a faster bridge or to use slower vehicles. Must the game do everything for the player? Shouldn't the player have some responsibility to provide the most efficient route? I would think that it would suffice for the pathfinder to simply look for the shortest route.

[romazoon]

to simply look for the shortest route.

while it sounds complicated to have penalties for slow bridge, i think there is a few corner case where it might be usefull.

I m thinking of highways, if you make some long brigde on your highways you might be happy that the fast vehicle takes the fast bridge, and the slow RVs stay on the slow bridge (if you care to make path shorter for slow bridge that is) allowing them to overtake each other where they normally can't.

Now a more usefull case is when there is two equal path in term of tiles to travel, but one of the two path has a slow bridge, you might be happy to not see the pathfinder send your vehicles "automaticly" via the slow bridge path because this way has no penalty over the other one.

[cirdan]

It also made sense when you could not upgrade town-owned bridges. And I think that taking the shortest route blindly would be worse; for instance, the road pathfinder currently tries to avoid level crossings, on the assumption that they are dangerous.

[HackaLittleBit]

to simply look for the shortest route.

while it sounds complicated to have penalties for slow bridge, i think there is a few corner case where it might be usefull.

I m thinking of highways, if you make some long brigde on your highways you might be happy that the fast vehicle takes the fast bridge, and the slow RVs stay on the slow bridge (if you care to make path shorter for slow bridge that is) allowing them to overtake each other where they normally can't.

Now a more usefull case is when there is two equal path in term of tiles to travel, but one of the two path has a slow bridge, you might be happy to not see the pathfinder send your vehicles "automaticly" via the slow bridge path because this way has no penalty over the other one.

On a highway (double lane one-way bridge) they could overtake.
That is not to difficult to do.(not sure however with MP mode.)

[HackaLittleBit]

Trains will happily choose a longer route over a sequence of short slow bridges rather than a direct route over a single faster bridge.

You have to give the trains orders!
If not they go haywire.
I took 2 trains a fast one and a slow one.
Orders were between depots.
Trunk behaves as it should I think.
With three bridges intact both trains will choose the fastest route possibility and go over bridge 1.
Destroy bridge 1 and only the fast train will choose bridge 2. slow train goes over slow bridge.
Destroy bridge 2 and both trains go over slow bridge.

Included save game.
Not sure if it will load though;-)(gcc 4.9.2)

[cirdan]

Hmm, scratch what I said, I misremembered some of the details about the bug. What happens in openttd is that a train will choose a longer route through a single, slower bridge over a shorter route over several faster bridges, under certain circumstances, as in the screenshot below (openttd trunk). The bridge to the north has a speed limit of 32 km/h (wooden), while the others have a speed limit of 48 km/h (concrete). The train has orders to go to each depot in turn, and will take the longer and slower route to do so.

[wallyweb]

Hmm, scratch what I said, I misremembered some of the details about the bug. What happens in openttd is that a train will choose a longer route through a single, slower bridge over a shorter route over several faster bridges, under certain circumstances, as in the screenshot below (openttd trunk). The bridge to the north has a speed limit of 32 km/h (wooden), while the others have a speed limit of 48 km/h (concrete). The train has orders to go to each depot in turn, and will take the longer and slower route to do so.

Interesting. I'm unsure as to how the pathfinder algorithm functions. Does it measure a series of hops and sum them as it calculates? If this is the case then I should think it would be faster to do one single "slow bridge" sum than to do several "fast bridge" sums. By the time the "fast bridge" route has been calculated, the "slow bridge" route has already been found and set out upon.

[HackaLittleBit]

@cirdan, I understand what is going on.

I was also thinking along the lines of wallyweb.
I am going to test.
Would be a nice feature. 10% difference between train max speed and bridgespeed low cost, more than 10 % very high cost.
Than you can make fast trains pass slow trains!

[Eddi]

Hmm, scratch what I said, I misremembered some of the details about the bug. What happens in openttd is that a train will choose a longer route through a single, slower bridge over a shorter route over several faster bridges, under certain circumstances, as in the screenshot below (openttd trunk). The bridge to the north has a speed limit of 32 km/h (wooden), while the others have a speed limit of 48 km/h (concrete). The train has orders to go to each depot in turn, and will take the longer and slower route to do so.

Interesting. I'm unsure as to how the pathfinder algorithm functions. Does it measure a series of hops and sum them as it calculates? If this is the case then I should think it would be faster to do one single "slow bridge" sum than to do several "fast bridge" sums. By the time the "fast bridge" route has been calculated, the "slow bridge" route has already been found and set out upon.

there is no timing condition on what is calculated "faster". the way these things work (simplified):

1. build a candidate list initially containing only the start tile, with a penalty of 0, all other tiles have a penalty of infinity
2. if the candidate list is empty, the destination is unreachable
3. remove the tile with the lowest penalty from the candidate list
4. for each neighbour of that tile, add the penalty for that neighbour to the current penalty
5. insert the neighbours back into the candidate list, if their penalty was lowered in the above step
6. if one of the neighbours is the destination tile, you are finished. otherwise continue with step 2.

the algorithm is guaranteed to find the route with the lowest penalty.

[HackaLittleBit]

@Cirdan Some solutions.

I checked some ottdcoop games with and without bridge cost calculation.
I did not notice any difference.

So here some possibilities for solving the problem.

Solution1:
A bridge has always two ramps.
So only apply DOUBLE cost for exit_ramp of bridge and use track direction for getting exit_ramp.
That way cost is applied when bridge is actually passed.
When track follower passes bridge_head without going over bridge normal track cost applies.

Solution2: Forget cost for passing bridges.

Solution3: Same as 1 but apply cost only when there actually is a wormhole. So no bridge-speed penalty on ramps.
(me like)

Solution4: Make bridge ramp penalty a optional feature.
I do think that it is a loss of attractiveness of the game when it starts thinking for you.(the player)
When player puts slow bridge,than that is his fault. bad luck!
Think of "flappy bird", it is addictive because you allways want to improve.


Here a link to read some posts from KUDr to get more a feeling of how he was(is) thnking.
Regards

P.S. You reduced path finding code in half!, yeahhhh.
Spring cleaning.

[Eddi]

if you hate the penalty so much, why don't you just set it to 0 in your games?

by that logic, we should remove the pathfinder altogether, and you have to put waypoints every 2 tiles so the trains don't get lost and go exactly where you want them to.

maybe all that playing flappy bird fried your brain?

[HackaLittleBit]

if you hate the penalty so much, why don't you just set it to 0 in your games?

I don't think you understand the issue here.
Custom bridge heads have more than one way to be passed.
So the issue here is solving the applied penalty!

Do you need more explanation?

[Eddi]

yes. why is it more difficult than in the follow-track-function for brigeheads: "if (track enters wormhole) add penalty;"?

[HackaLittleBit]

yes. why is it more difficult than in the follow-track-function for brigeheads: "if (track enters wormhole) add penalty;"?

That could be a solution indeed. In cirdans branch however vehicles do not enter wormhole on bridges of 2 tile length.
So it would require more code to catch that exception.
And extra code should be avoided there I think. I may be wrong.

[Eddi]

i still don't quite see your problem. you can know which trackbits lead into the wormhole from looking at the tile itself. no matter whether there is a wormhole or not

[HackaLittleBit]

@Cirdan
I came up with this piece of code to calculate bridge cost penalty only when crossing bridge.

Code: Select all

	int GetSpeedLimit (void) const
	{
		/* Check for on-bridge and railtype speed limit */
		TileIndex bridge_tile;
		RailType rt;

		if (!m_old.in_wormhole()) {
			/* Only consider bridge cost when actually entering wormhole. */
			bridge_tile = (m_flag == TF_BRIDGE ?  m_old.tile : INVALID_TILE);
			rt = m_old.get_railtype();
		} else if (IsTileSubtype(m_old.wormhole, TT_BRIDGE)) {
			bridge_tile = INVALID_TILE;
			rt = GetBridgeRailType(m_old.wormhole);
		} else {
			bridge_tile = INVALID_TILE;
			rt = GetRailType(m_old.wormhole);
		}

I am still trying to figure out what

Code: Select all

			cost += YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (1 + tf->m_tiles_skipped) / max_veh_speed;

exactly was meant to do.
Till now I get inconsistent results.
Could this not be changed in

Code: Select all

cost += (YAPF_TILE_LENGTH + max_veh_speed - max_speed) / YAPF_TILE_LENGTH * (1 + tf->m_tiles_skipped);

or

Code: Select all

cost += (max_veh_speed - max_speed) * (1 + tf->m_tiles_skipped);

?

[Eddi]

"YAPF_TILE_LENGTH" is the default penalty for one rail tile (100). treat this as the "base unit" for all pathfinder calculations. units are always multiplicative. you don't ever see "3m+5N" in physics.

"(1 + tf->m_tiles_skipped)" i suppose is the amount of tiles. this also should be multiplicative, as you want to get the same result as if you counted each tile individually

"(max_veh_speed - max_speed) / max_veh_speed" can be simplified to "1-v_1/v_2", so it calculates by which fraction the max speed is reduced

it's written the way it is, because moving the / to the end causes fewer rounding errors.

[HackaLittleBit]

I put all formulas in a worksheet for testing.
It shows that the formula used in trunk and Cirdan are the correct ones.

When I apply these lines of code, trains will choose the bridge that has speed limitations closest to max-speed of train.

Code: Select all

	if (n->m_num_signals_passed < m_sig_look_ahead_costs.size())
	{
		assert (!IsNodeCached(n));
		int max_speed = tf->GetSpeedLimit();
		int max_veh_speed = m_veh->GetDisplayMaxSpeed();
		/* Is max_speed applied? */
		if (max_speed < INT_MAX) {
			DEBUG(misc,0,"YTL %d	mVV %d	mV %d	ts %d", YAPF_TILE_LENGTH, max_veh_speed, max_speed, 1 + tf->m_tiles_skipped);
			int extra_cost = YAPF_TILE_LENGTH * (max_veh_speed - max_speed) * (1 + tf->m_tiles_skipped) / max_veh_speed;
			DEBUG(misc, 0,  "aC %d	C%d", abs(cost), cost);
			if (extra_cost < 0) {
				/* Train max_speed lower than speed limit gives reduced penalty. */
				cost += abs(extra_cost / 2);
			} else {
				/* Train max_speed higher than speed limit. */
				cost += extra_cost;
			}
		}
	}

They do not blindly choose any bridge that has speed limit above their own max-speed.
When trains go on track, bridge with higher speed limit than the train max-limit, they will be penalized also!
Albeit with half.
I show it here just for fun, realizing that YAPF is a balancing act.
With it, I think you can split of slow trains from the main line to a branch line.
To me it looks, that track always gives max_speed = INT_MAX.
Maybe there exist newGRF with speed limitations applied to track.
That would be nice to experiment.
I made it for myself just to try, and understand YAPF a bit better.
This will be my last post here about this subject.
There are people here that are much more knowledgeable about the workings of YAPF then me.

Have a nice weekend!

[Eddi]

When trains go on track, bridge with higher speed limit than the train max-limit, they will be penalized also!
Albeit with half.

it may be worth introducing a pathfinder penalty for that, similar to how shorter/longer platform penalty work.

[HackaLittleBit]

Known issues:
[*] Bridge speed limits are applied to any vehicle going through a bridgehead, even if it is not heading into or out of the bridge; I am not sure whether this is the behaviour that we want.

In cirdans second post he mentions that he is aware about pathfinder problems with bridges.
How would the following situation be solved? (Fair)

bridge2.png (266.61 KiB) Viewed 1809 times

I do not have a solution.
In this situation trains will always follow the red track.
Now vehicles are four times taxed when using a bridge with a little slower limit.

Normal track tax
1:/* If we skipped some tunnel/bridge/station tiles, add their base cost */
segment_cost += YAPF_TILE_LENGTH * tf->m_tiles_skipped;

A speed limit tax pathfinder
2: with GetSpeedLimit( etc etc

The actual slowing
3: and when the train is slowed in the train controller.

And extra slowing introduced with r21136 on top of that see:
(svn r21136) -Fix [FS#4213]: bridge speed limits should apply to all wagons of a vehicle, not just the head of the vehicle