[patch] train collision cache

madman2003 · Post by **madman2003** » 02 Jun 2007 11:44

The basic idea is this:

- Use 2 bits in the map array to store if there are 0, 1, 2, 3 or more trains on a tile

- More than 1 > do collision checking, in normal situations this only happens when you have diagonal track and two trains pass eachother.

- When leaving and state 3 is active, it will check if it's actually number 3 (somewhat expensive, but very rare).

- Also handle bridges and tunnels (toggle the other side as well, since trains actually remain on the ramp tile as far as the game is concerned).

GOAL: Improve performance of trains, sorry this was unclear.

NOTE: This could use testing now, try to load your old savegames (preferably with a lot of trains) and let it run at max speed for a few minutes. Play with it. If it asserts, please provide assert messsage and savegame. Post your experiences, even if they are good. Multiplayer experience is also good.

madman2003 · Post by **madman2003** » 02 Jun 2007 12:03

With profiling i have a rough estimate of reduction:

(FindTrainCollideEnum and GetVehicleFromPos are the functions i look at)

Previously it used ~13% of cpu time, this was reduced to ~1%.

I included the savegame, which is from openttdcoop(iirc), you'll probably need their grf pack.

When looking at real cpu usage, that went from ~45% to ~35%.
This is just to give you an idea, don't quote me on this

Nickman · Post by **Nickman** » 02 Jun 2007 14:09

Looks like a nice reduction

kaan · Post by **kaan** » 02 Jun 2007 16:07

First of all I would like to say that even though I don't know what it all means, then I like what I do understand in there.
One thing might be improved though.
As I remember it then GetPrevVehicleInChain is somewhat expensive performance wise because vehicle is a linked list, not a double linked list.
This means that it iterates over all vehicles in the train until it finds the vehicle that has u as ->next.

I think this might be better

Code: Select all

+	/* Only the first may trigger it */
+	if (u == u->first) {

Or maybe this

Code: Select all

+	/* Only the first may trigger it */
+	if (IsFrontEngine(u)) {

madman2003 · Post by **madman2003** » 02 Jun 2007 17:46

@kaan: That is already changed in my local copy, i still need to work on strange cases like trains crossing each other. Once that's done i'll post another patch.

madman2003 · Post by **madman2003** » 03 Jun 2007 10:27

Updated patch, what this doesn't do, is handle trains riding circles in themselves.

Any comments so far?

Besides the fact that the counting algoritm isn't perfect (i know that).

madman2003 · Post by **madman2003** » 03 Jun 2007 10:56

I did some testing, good news is that the extra checks don't seem to have much performance impact. Bad news, is the cpu usage comparison of the first test was wrong (visual details were different), diffirence is more in the order of 41% vs 35%. So i hope noone quoted me on that

(this is why profiling is more important)

madman2003 · Post by **madman2003** » 03 Jun 2007 16:04

This should work for crossings, loops (including those with crossings in them).

Counting algoritm is fixed as far as i know (despite the old comment).

Please test, there are fprintf's in the code which could be usefull if you want to debug.

madman2003 · Post by **madman2003** » 03 Jun 2007 17:59

Some fixes, some comment. Not perfect yet.

madman2003 · Post by **madman2003** » 03 Jun 2007 22:19

Simplified version.

madman2003 · Post by **madman2003** » 04 Jun 2007 05:40

I forgot to cache if a train is crossing, otherwise you do quite a few last car checks.

SyncViews · Post by **SyncViews** » 04 Jun 2007 06:29

There is an edit button so you don't have to post 7 times running...
Also update the 1st post so I don't go and try to compile the wrong thing again lol... *gets updated patch this time...*

madman2003 · Post by **madman2003** » 04 Jun 2007 19:36

SyncViews wrote:There is an edit button so you don't have to post 7 times running...
Also update the 1st post so I don't go and try to compile the wrong thing again lol... *gets updated patch this time...*

I will update the patch in the first post, as i have done now.

Bjarni · Post by **Bjarni** » 05 Jun 2007 09:12

I just looked at this and decided to play a bit with it. I made the following modification to rail_map.h

Code: Select all

ShowCostOrIncomeAnimation(TileX(t) * 16, TileY(t) * 16, (_m[t].type_height & 0x0F) * 8, GetOccupancy(t));

in SetOccupancy(). This means that it will have to be aware of GetOccupancy() (they are in the wrong order) and include functions.h.
Now a cost animation is printed on every tile that changes the train counter. If currency is set to punds, then the price will be the content of the counter. This makes a quick test a bit easier.

I did find some issues. Crashing two trains into each other can set the counter to 0 before it's done cleaning up the trains because the counter is decreased one for each vehicle that's removed. If a train has more than one vehicle in the tile, then it's substracted more than once.

Road crossings... now the road vehicle crash if the train is in the tile. It's good to test if there is a train by using the counter (fast) before checking if there is a collision, but the need for a collision check is still needed as a road vehicle and a train could be on the same tile without touching each other. The check should be (in that order)

Code: Select all

if (GetOccupancy(tile) > 0 && VehicleFromPos(tile, v, EnumCheckRoadVehCrashTrain) != NULL)

Also I think the crossing train detection code can be made even simpler. Once a train front enters a tile where the train counter is more than 0, then it should loop though it's own consist to check if the tile is present. If it is, then set the crossing bool, else increase the counter for the tile.

DecreaseOccupancy() should assert if it is called when the count is already 0, not just do nothing. This should never happen, so just returning without doing anything is a bad solution that can hide bugs.

madman2003 · Post by **madman2003** » 05 Jun 2007 10:52

In my local copy i have two functions now, one for tileenter and tileleave.
I have begun adding asserts in places were they are needed.

The proper roadveh crash stuff has been readded.

Good catch about the crash stuff.

I found out an issue in the savegame stuff, it also increases the counter inside depots, which aren't handled by a normal game.

I'll look at the possibility of simplifying the code further.

I will make some changes this evening.

kaan · Post by **kaan** » 05 Jun 2007 15:07

I would just like to say that I am full of admiration for your hard work on this non-trivial patch

madman2003 · Post by **madman2003** » 05 Jun 2007 19:32

Fixed quite a few bugs, it's nearing an end, please give final comment please.

Bjarni · Post by **Bjarni** » 05 Jun 2007 20:42

for TrainEnterTile():
/* Check the entire train for cross points */.. about this check. Isn't it good enough to just loop though the train to see if (v->tile == gp.new_tile)? This would be easier to read and should be faster than making a vector of the train every time this happens.

If the train is crossing (still first if), then wouldn't it be possible to just set v->u.rail.crossing_self = true and then return?

*u in the argument... we usually call vehicles for *v

the function ends with return... there is no need to place return as the last line in a void function.

for TrainLeaveTile():
DEBUG(misc, 2, "[UpdateTrainCache] The last wagon of a car is somewhere it isn't registered"); <-- this sounds like a reason to assert to me.

I think it's possible to simplify this function some more. Checking if the train is crossing could just be if the tiles are matching, then set the crossing bool and break. No need to check if it is crossing in more than one place since the only change it will do is to set the bool again.

if the crossing bool is set after this, then loop though the train to see if gp.old_tile is present for any of the vehicles in the train to see if it can be cleared... or maybe it should be done in revered order (if the tile isn't present, then we know that the train wasn't crossing at that tile). Maybe both can be done during the same loop.

Add more comments on the idea behind the vector and the sort.

For the crashing into road vehicles: join the two ifs into one with && (it should still be on two lines though)

PossibleRailDepot() should be named IsRailDepot() (and we already have that function in rail_map.h)

That's what I found this time. I just read the diff and didn't actually apply it this time, so more stuff might show up.

madman2003 · Post by **madman2003** » 05 Jun 2007 20:58

Bjarni wrote:for TrainEnterTile():
/* Check the entire train for cross points */.. about this check. Isn't it good enough to just loop though the train to see if (v->tile == gp.new_tile)? This would be easier to read and should be faster than making a vector of the train every time this happens.

Decent idea, i'll look at it.

If the train is crossing (still first if), then wouldn't it be possible to just set v->u.rail.crossing_self = true and then return?

*u in the argument... we usually call vehicles for *v

Maybe for the TrainEnterTile.

the function ends with return... there is no need to place return as the last line in a void function.

Ok

for TrainLeaveTile():
DEBUG(misc, 2, "[UpdateTrainCache] The last wagon of a car is somewhere it isn't registered"); <-- this sounds like a reason to assert to me.

It's already gone, just didn't notice it for this diff.

I think it's possible to simplify this function some more. Checking if the train is crossing could just be if the tiles are matching, then set the crossing bool and break. No need to check if it is crossing in more than one place since the only change it will do is to set the bool again.

if the crossing bool is set after this, then loop though the train to see if gp.old_tile is present for any of the vehicles in the train to see if it can be cleared... or maybe it should be done in revered order (if the tile isn't present, then we know that the train wasn't crossing at that tile). Maybe both can be done during the same loop.

As far as i know, i do need to know how many crossings there are, so i can put the vehicle in normal mode again.

Add more comments on the idea behind the vector and the sort.

For the crashing into road vehicles: join the two ifs into one with && (it should still be on two lines though)

Ok.

PossibleRailDepot() should be named IsRailDepot() (and we already have that function in rail_map.h)

This function also checks for IsTileType(t, MP_RAILWAY), it would be ugly having to do that a lot in the code itself (since it's also called on bridges for example). For other things, such double functions exist as well.

That's what I found this time. I just read the diff and didn't actually apply it this time, so more stuff might show up.

End message

madman2003 · Post by **madman2003** » 06 Jun 2007 14:52

I think i've got the bugs worked out now.

The question is, can this be committed if nothing turns up soon?

Transport Tycoon Forums

[patch] train collision cache

[patch] train collision cache

Who is online