New map features

[cirdan]

So, everyone is aware of these little things we all would love to have in OpenTTD, such as custom tunnelheads and bridgeheads, signals in tunnels and bridges (or at least tunnelheads and bridgeheads), and so on, that are high in many people's wishlist but are not implemented in OpenTTD, for whatever reasons.

Well, recently I became frustrated enough that some of them were not available so as to attempt to code them myself and, after quite a bit of effort, I am beginning to get results, so I am posting this ongoing work for others to benefit (and help test).

So far, these are the main new features provided by the patch:

• Parallel tracks of different railtypes on the same tile
• Custom road bridgeheads
• Custom rail bridgeheads, including signals

There are also some other minor improvements, such as the owner/closest town stored for road bridges, plus an assortment of minor cleanups and performance enhancements.


UPDATE:

I have now created my own fork of openttd, available here. I regularly cherry-pick (almost) all commits made to openttd trunk, so you can expect any feature or bugfix in openttd to be forward-ported. It has full backwards savegame compatibility and can also load openttd savegames (the ability to load openttd trunk savegames may lag behind slightly). This is a list of features it has, compared to the last commit picked from openttd:

• Parallel tracks of different railtypes on the same tile
• Custom road bridgeheads
• Custom rail bridgeheads, including signals
• Signals in tunnels
• Allow to overbuild airports
• Multiple docks per station

...plus several bug fixes and lots of performance improvements and code cleanups.

Please report any bug you find in this thread.

[cirdan]

This is the first version of the patch; it should apply cleanly against r23877. It brings custom road bridgeheads, custom rail bridgeheads including signals and parallel tracks of different railtypes on the same tile.

Testing is more than welcome, since I have touched a lot of things in the code and it is unlikely that my own checks have uncovered all the bugs. Expect it to be rough around the edges, and do not be surprised if it crashes or otherwise behaves unexpectedly. Please do report what you find.

The patched program should load savegames from trunk, but patched savegames will not load in trunk, of course. And I cannot make any promise regarding savegame compatibility, at least for now: Future patches are unlikely to load savegames made with this one.

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.
• The land information tool does not give an accurate description of rail tiles with two different railtypes.
• There are some graphical glitches with custom bridgeheads, especially those heading north, and with the building tools. None of them should affect gameplay.

[Jacko]

wow those look really cool
I see what you mean by graphics glitch

[Level Crossing]

That's amazing!

Let's see what the devs say about this.

[bokkie]

Probably that they won't review such a large patch Let's hope Cirdan has a patch queue, otherwise this patch is 'doomed' to be used for personal use (and maybe patchpacks) only.

Other than that: good luck, obviously you've already put in a lot of work

[Eddi]

you probably want to talk with michi_cc, who had something similar in the works.

[cirdan]

Probably that they won't review such a large patch Let's hope Cirdan has a patch queue, otherwise this patch is 'doomed' to be used for personal use (and maybe patchpacks) only.

If that thing you call a "patch queue" is what we call a branch in git, then yes, I keep a branch for the patch, consisting of "only" 332 smaller patches.

Other than that: good luck, obviously you've already put in a lot of work

You can say that again. It's been quite a few months of work. And the patch was ready in december, against an older revision of trunk, but then infrastructure counts were merged and rebasing was a nightmare and set me back for some more weeks.

[Lord Aro]

Custom bridgeheads:
+ patch queue/git branch =

suggest that you upload the git branch so the devs can review the patches individually

[FLHerne]

Diagonal tracks for different railtypes!
That little thing just bugs me. How does the railtype upgrade tool work on those though?

[cirdan]

suggest that you upload the git branch so the devs can review the patches individually

There you go. Apply with 'git am'.

How does the railtype upgrade tool work on those though?

Not too well, I'm afraid. That is, the convert tool, when applied to a tile with two different railtypes, converts both tracks to the target type. This is the current behaviour in trunk, so you don't really lose anything, although you would probably want a way to selectively convert only one of the tracks, since this is now possible. I'm aware of this, but I think that it is a further improvement that could be done later.

[supermop]

Could the tool work more like the rail tool itself? Or maybe 'building' monorail over rail has the same effect as the convert tool? Or is that out of the scope of the patch?

[Michi_cc]

Warning: HUGE patch

Indeed. There are two things I though after seeing that the combined diff is ~1.3MB. First one was "Who the hell would ever review that?" and the second was "Maybe the chosen approach is, ehh, suboptimal".

Of course, I just took some very tiny peeks so far, so I don't have any idea if the approach really is in any way suboptimal or not. Maybe you can write a few words about your chosen design.

In my own map array rewrite experiments, I only need about 470KB of diff to arrive at multiple railtypes with multiple owners on one tile. I can't show any custom bridgeheads so far, because I've focused a lot more on the ground work with the intention to someday for example even have proper signals on bridges and tunnel (not like in some those current signals-in-tunnel hack patches). Who knows how big my patch would grow till that

I don't want to demotivate you, but a 323-strong patch series, is, as Germans say, "eine Menge Holz". Maybe that's what it takes in the end, but I'd advise you to try looking for opportunities to cut down on the patch.

-- Michael Lutz

[cirdan]

Could the tool work more like the rail tool itself? Or maybe 'building' monorail over rail has the same effect as the convert tool? Or is that out of the scope of the patch?

It is not that it is out of the scope of the patch, it is simply that I'd rather address it later. First we should make sure that two railtypes per tile work and that the code has no bugs, and then we can discuss how to extend the existing tools to cope with the new possibilities.

Warning: HUGE patch

Indeed. There are two things I though after seeing that the combined diff is ~1.3MB. First one was "Who the hell would ever review that?" and the second was "Maybe the chosen approach is, ehh, suboptimal".

That is possible. I've been working on this patch for long, and I still consider it a work in progress (although some parts are already quite stable). I still have some ideas to better organise the sequence of patches, but I didn't want to hold the patch any longer because I thought it would be good to expose it for public review and, more importantly, to receive wider testing.

Of course, I just took some very tiny peeks so far, so I don't have any idea if the approach really is in any way suboptimal or not. Maybe you can write a few words about your chosen design.

As it usually happens, it all started with an underestimation. I thought that the main problem with not having two railtypes per tile, custom bridgeheads, custom tunnelheads, etc. was the constraints of the current map array, which makes it awkward to do any significant change because it is the result of unplanned expansion on top of the legacy TTD implementation and, as such, has a fairly inefficient representation. So I though that designing a new map array, better packed and planned in advance would go a long way into implementing all those things that I wanted.

Well, I was wrong. Rewriting the map array allowed me to implement two railtypes per tile very easily (in only 5 patches), but that was it. Custom bridgeheads and tunnelheads, although they badly required the map array rewrite as well, were still very far away. Adding custom road bridgeheads required lots of changes in the pathfinders and the vehicle controllers. Adding custom rail bridgeheads required additional changes in the signal code. And custom tunnelheads is something that, while taken into account into the new map array, still hasn't seen any actual work. If I had known how much work it would take to get here, I probably wouldn't have undertaken the task.

I'm attaching the map array I designed and which is (mostly) implemented in my patch. The file is gzipped as HTML files cannot be directly uploaded.

In my own map array rewrite experiments, I only need about 470KB of diff to arrive at multiple railtypes with multiple owners on one tile. I can't show any custom bridgeheads so far, because I've focused a lot more on the ground work with the intention to someday for example even have proper signals on bridges and tunnel (not like in some those current signals-in-tunnel hack patches). Who knows how big my patch would grow till that

In my patch sequence, having two railtypes per tile is achieved in patch 143/332, and the diff is 800K, which is closer to what you get. And there's a lot of code shuffling between files and changes that are there to make things easier down the road.

As for proper signals on tunnels and bridges, this is something that I've thought about. My map array rewrite has room for true signals on bridges, given some constraints, although I haven't coded them yet. For proper signals in tunnels, I'm afraid that we'll have to settle with a hackish implementation, if any, because a tile can have several tunnels underneath and there is no way we can store signal information for an arbitrary number of levels in the map array, especially not if we ever implement custom tunnelheads (which would reduce the available bits for tunnel data) or more height levels (which would increase the possible number of height levels under a tile).

(On a side note, my map array rewrite completely frees 2 bits per tile for all tiles, which could be used for storing more height levels.)

I don't want to demotivate you, but a 323-strong patch series, is, as Germans say, "eine Menge Holz". Maybe that's what it takes in the end, but I'd advise you to try looking for opportunities to cut down on the patch.

Believe me, I don't like bloat, either. But I truly think that this is what it takes. Note, however, that I am very keen on having patches as small as possible, so I may split what could be one single patch into four or five patches, to make my life easier when rebasing; this could partly explain the sheer number of patches. Also, there are a number of patches whose only purpose is to clean up code which I could very well not touch (the ship controller, for instance--ship code could really use some caring). So the 332 patches may not be as bad as it seems.

If you feel like reviewing some patches, though, I suggest that you try reviewing the first ten patches or so in the sequence. They are mostly optimisations and code cleanups (one of them just fixes a typo), and they should be fairly uncontroversial and improve the codebase whether the rest of the sequence is applied or not.

[Michi_cc]

I'm attaching the map array I designed and which is (mostly) implemented in my patch. The file is gzipped as HTML files cannot be directly uploaded.

If I understand that right, the only think that really changed map array-wise is an additional byte per tile (and a lot of bit reshuffling).This is what I'd call the easy solution (talking about algorithmic complexity here, not code size ). The problem with this is that it will invariably end again at the same situation we are now: no more free map bits.

I've been exploring the solution of allowing an arbitrary number of Tile structs per TileIndex, basically resulting in "infinite" map storage. So a random tile of the map could e.g. consist of MP_GROUND + MP_ROAD + MP_BRIDGE_SURFACE + MP_RAIL + MP_SIGNALS (this of course involves significant bit shuffling as well). As a nice side effect the complexity of e.g. the pathfinder is actually reduced, because a road vehicle for example would simply follow only MP_ROAD tiles, no exceptions for anything.

-- Michael Lutz

[cirdan]

I'm attaching the map array I designed and which is (mostly) implemented in my patch. The file is gzipped as HTML files cannot be directly uploaded.

If I understand that right, the only think that really changed map array-wise is an additional byte per tile (and a lot of bit reshuffling).

Err, no, there is a lot of bit reshuffling, but the amount of storage needed is kept constant at 9 bytes per tile. Actually, there are two fewer bits required, since 2 bits in mth are always 0 (4 bits on non-tropical climates).

This is what I'd call the easy solution (talking about algorithmic complexity here, not code size ). The problem with this is that it will invariably end again at the same situation we are now: no more free map bits.

I'm afraid that this situation will eventually arise no matter what, unless, of course, we design a scheme in which the amount of storage per tile is dynamic. But I don't think such a scheme would be feasible performance-wise.

I've been exploring the solution of allowing an arbitrary number of Tile structs per TileIndex, basically resulting in "infinite" map storage. So a random tile of the map could e.g. consist of MP_GROUND + MP_ROAD + MP_BRIDGE_SURFACE + MP_RAIL + MP_SIGNALS (this of course involves significant bit shuffling as well). As a nice side effect the complexity of e.g. the pathfinder is actually reduced, because a road vehicle for example would simply follow only MP_ROAD tiles, no exceptions for anything.

...until you consider level crossings, which must be treated as both rail and road. As I said before, I'm afraid that such a system would impose a severe performance penalty. I'm willing to be proven wrong, though.

I understand that my new map array is not a revolutionary solution to the traditional OpenTTD map array problem: it simply does the same thing as before but in a better way. It greatly simplifies some code paths (you can't imagine how many lines of code I deleted when merging clear and tree tiles), it does allow to implement quite a few new things (such as custom bridgeheads) and it won't make the switch more difficult when the ultimate map array design is discovered.

[Eddi]

...until you consider level crossings, which must be treated as both rail and road. As I said before, I'm afraid that such a system would impose a severe performance penalty. I'm willing to be proven wrong, though.

well, the idea would be that a level crossing tile would consist of MP_GROUND + MP_ROAD + MP_RAIL. then the road pathfinder will only ever look at the MP_ROAD part, and the rail pathfinder will only ever look at the MP_RAIL part. the only immediate performance hazards are a) cache misses, because the map is not reserved "en bloc", and b) the lookup of the right tile by coords (x,y,z) and tile type. afair the code wasn't really optimized, last time i heard of it, so performance can't be judged properly

[Expresso]

NOTE: I'm typing this on a semi-public terminal.

Is my understanding correct in that this new map array comes with 3 new features. Can't you provide 4 patches, one providing the skeleton (just the new map array), one with the custom bridgeheads, one with the custom tunnel entrences and one with two railtypes on one tile) and make individual topics for each? That will keep discussion focussed.

[cirdan]

Is my understanding correct in that this new map array comes with 3 new features.

Well, it does more than that, but you are right in that there are three main new features.

Can't you provide 4 patches, one providing the skeleton (just the new map array), one with the custom bridgeheads, one with the custom tunnel entrences and one with two railtypes on one tile)

The patch does not implement custom tunnelheads (although the new map array design allows for them). As for the other features, you can already do that. The patch sequence I posted here can be split as follows:

• patches 1-10: misc cleanup
• patches 11-44: savegame afterload cleanup
• patches 45-65: preparatory work for the new map array
• patches 66-138: new map array proper
• patches 139-143: allow two railtypes per tile
• patches 144-178: rework vehicle controllers
• patches 179-188: store closest/owner town for road bridges
• patches 189-193: misc cleanup
• patches 194-267: prepare pathfinding for custom bridgeheads
• patches 268-286: custom road bridgeheads
• patches 287-332: custom rail bridgeheads

and make individual topics for each? That will keep discussion focussed.

I do not oppose this idea, but I think that it would be thread-spamming as of now, since there does not seem to be a lot of discussion.

[maquinista]

Awesome patch, It's very interesting.

You need some new sprites for foundation tiles. They will fix the road glitch.

[cirdan]

Thanks, maquinista! I will try to integrate them in the patch.