Pull request: integer representation for private car route data

[freddyhayward]

I have been working on storing private car routes as 8-bit integer values rather than 40-bit koord3d values. This is possible because the values always correspond to a neighbouring tile, and my implementation stores this as relative to the road's position rather than the absolute location of the tile.
I was initially concerned that this might negatively affect performance when accessing and converting them for individual private cars, but my testing confirmed that there is no such impact. I timed calls to private_car_t::hop_check over 1000 steps on a bridgewater-brunel save, and both implementations totaled roughly 1050ms.
The main benefit of my implementation is reduced memory and file size usage. Testing a bridgewater-brunel save, my implementation reduced memory usage by roughly 500MB and file size by roughly 50MB.
The reason why this is not currently listed as a pull request is that private cars now behave differently to the original implementation, which was not my intention at all. Connecting to a current server with clients built from this branch causes an immediate loss of synchronisation. I am currently trying to work out why this is the case. I believe it is likely related to the use of koord3d::invalid to mark the ends of routes and koord3d() to mark invalid or absent routes, and my implementation failing to properly account for these usages.
The branch can be found here: https://github.com/freddyhayward/simutrans-extended/tree/koord3d-neighbours
Edit: see new reply below...

[jamespetts]

Interesting - thank you for this. I shall look forward to further refinement of this.

[Vladki]

I do not see a big problem in changing the behavior of private cars. They are stupid anyway Although the stupidity may not be affected by your patch - it is imho something about how pathfinder deals with congested roads.

[freddyhayward]

it is imho something about how pathfinder deals with congested roads.

I guess this is partly my fault. I did not consider how infrequently the routes would be updated, therefore overreacting to travel time based congestion.

I do not see a big problem in changing the behavior of private cars. They are stupid anyway

This may be true, but I want to be sure that I have not introduced additional problems.

[freddyhayward]

This pull request is now open ready to be merged: https://github.com/jamespetts/simutrans-extended/pull/338. I have solved all known inconsistencies in behaviour. Thankfully, these were all caused by logic errors rather than inherent flaws in the design. Testing again, the memory savings are closer to ~300-400MB rather than 500MB, and I could not replicate any meaningful reduction in file size. Still, the memory usage reduction alone remains significant and worthwhile in my opinion.

[jamespetts]

Thank you for this. Can I check whether you have tested performance with all the bug fixes applied? This does appear to be potentially performance critical.

I am currently investigating a possible bug shown on the Bridgewater-Brunel server in which there appears to be much, much less inter-city private car traffic than expected even in cases where cities are linked with good roads and have had enough time to refresh their routes. I am not able to reproduce this in a minimal test case, so will need to work on the server saved game for testing, which is likely to be a long and difficult task. Whilst that is in progress, I am reluctant to merge a patch that affects private car routing, so there may be some delay before I can review this.

Thank you very much for your work on this, however.

[freddyhayward]

Can I check whether you have tested performance with all the bug fixes applied?

I had not before your reply, but have just done so and found that performance in hop_check remains identical to the current implementation.

Whilst that is in progress, I am reluctant to merge a patch that affects private car routing, so there may be some delay before I can review this.

I understand the reluctance, but it really should not be an issue because I have confirmed through testing that private car routing works identically across the two implementations.

[jamespetts]

Splendid, thank you. Now incorporated.