complete idea on underground/above ground construction

[Expresso]

The basic idea is to allow full freeform underground and above ground construction.

** Idea for user interface **

You open up rail/road construction as usual and click on the tunnel or bridge.
An additional window appears that basically contains the following: A button for going up a level, for going down a level, for having the track/road slope down a level, for having the track/road slope up a level.
Tunnel entrance/exits are achieved by placing a rail against a sloped peace of land.
Bridgeheads are achieved by simply going down to ground level.
Roads/rails on ground level keep behaving as normal.
Want to dig somewhat deeper? simply slope down. Want to construct a lower level? Press the button for the lower level. Further construction works as usual, with the exception that it's now not anymore on ground level.

I'm bad at mockups, so that's why I do it by text.

** idea for internal representation **

The problem here is that all those tiles need to be stored somewhere, without consuming an infinite amount of memory and without giving a performance hit.

So, it's probably best to add another tile type: the tile stack.The tile stack is a tile on the normal map array that contains a reference to a tilestack for the requested tile. All tilestacks are stored in a memory pool, as to not consume more memory than needed. Tilestacks contain either 4, 8 or 16 tiles on top of one another, possibly connected to more tilestacks (in case someone is so insane as to need more levels on top of one another). These tiles function exactly the same as ground level tiles. A tilestack is a sorted list of tiles and height level pairs. At the beginning and end of each tilestack a reference to the previous and next tilestack is contained - to aid with sorting. No tunnel or bridge in a tile, means no tilestack for that tile - saves memory and cpu cycles.

I hope this brain dump is actually useful to someone.

[acs121]

Very good idea, but maybe it lacks a button in transparency options to have an "underground view".

[Gwyd]

Two questions (only one of which I care about):
How would stations be handled? Can you build them on any level? What are the graphical implications of this?
And how would this work with old gamesaves?

[Karn]

Apart from technical questions, this idea has large impact on game balance. It suggests extremely flexible building in air. Which implies we could move everything into several layers of air. Limiting factor in OpenTTD is land and this would remove any challenge from gameplay. You could simply avoid congested land by another layer of air.

[acs121]

I honestly think players are quite smart, and they will want to avoid congested land for the simple and good reason that it is congested, or that there already are infrastructures above.
This would lead to the creation of subway networks, underground S-Bahn networks, or big 34-track stations with its ugly junction hidden of course.

[Expresso]

First, I'd like to suggest that underground and air constructs be more expensive to maintain (as they are in real life).

Second, for old savegames there would obviously need to be a conversion scheme (there are already several in the current loading scheme). A problem occurs here in the (now new super expensive) maintenance costs. A setting or a cheat could automatically be enabled when such an older savegame is loaded that keeps the old costs, in order to not make the companies on the map instantly go bust.

Third, stations should be able to be built on any level, however, the further away from ground level, the less cargo (including passengers and mail) it receives. I think that special stations need to be drawn for bridges and tunnels and that the game should consider the bounding box of buildings on lower levels

[acs121]

So it would have a 3D acceptation model with a sphere shape instead of a square shape ?

[Expresso]

So it would have a 3D acceptation model with a sphere shape instead of a square shape ?

I never mentioned a spheroid. I just said that the further away from ground level the station would be, the less goods it would get. Where exactly does this say that the station acceptation range would be a sphere?

I'll elaborate (an example): When you build a station on ground level, it gets 100% of the cargo it would normally get. If you build it one level above ground level, it would get 95%, two levels 90%, etc. Same goes for underground. This is what I meant and I thought I had explained clear enough.

If you need to be 7 levels above ground level to build your station, because of a bunch of high-rises below, you get a whopping 35% reduction in passenger count (for example).

[acs121]

So it would have a cubic shape instead of a square shape for the acceptation zone ?

[Expresso]

For internal game logic, it would still be a flat square. However, since the further away you get from ground level, the less cargo you get, for the player it would seem cubic.

[Gwyd]

I have to agree with Karn here: why build actually complex junctions when I can just fly stuff over eachother? OpenTTD Coop style players would have a field day

[Expresso]

Because building above or under ground level becomes really expensive and it's also really expensive to maintain. If building one junction would completely drain their coffers and keep it empty.

I've considered an alternative, but I do not like it. How about a maximum of 4 levels on top of one another?
- Air level
- ground level
- sub level 1
- sub level 2

That would also simplify the internals. This would also make complex junctions still pretty much a requirement for the coop players. But I think this would make a lot of players very unhappy and probably break some savegames out there.

[Alberth]

The problem here is that all those tiles need to be stored somewhere, without consuming an infinite amount of memory and without giving a performance hit.

Memory is mostly irrelevant, performance is the only relevant factor here.

You mostly get performance by minimizing memory access, and by localizing the access you cannot avoid. In that way, you get maximum profit of the L1 and L2 cpu caches. To get an idea on their speed, getting data from the L2 cache is about 10x as slow as data from the L1 cache, and data from main memory is at least 10x slower than data from the L2 cache.

The current implementation is a single array of tiles, where the address of the tile is computed, so the first memory access is already reading proper tile information needed for moving the train. That information is not much bigger than a stored pointer. In other words, by the time you have loaded the pointer to the tile-stack, the current implementation has already seen all tile information, and is working on the next tile.

The pointed-to address is likely not in the L1/L2 caches, and this likely also holds for your other stack-segments in the sorted list (ie you're quite likely to work at very slow main-memory speed). I don't know how you intend to find the tile at the correct level, but pretty soon you're at least doubling or tripling the amount of memory accesses, in particular at random points in the pool, ie outside the L1 and L2 caches, so you're likely waiting eons (in cpu ticks) for main memory.

The additional access immediately translates to 1/2 or 1/3 of the number of trains that you can run in the game before you hit the CPU limit. You'd have to implement it for a real test though. openttdcoop has a few nice test-cases for you

You have a nice idea, and it would work if you're not in a hurry, but here, every memory access counts, and jumps to possibly far-away locations are quite deadly for speed, you can do a lot of L1 access compared to main memory access.


This is basically why there is no multi-level implementation yet. A single flat array of tiles is so fast, it's hard or perhaps impossible to find anything which is even close to comparable in performance.
I don't think a new data structure will suffice, it may need a different way of computing paths, without killing the deterministic properties that we have now.

[acs121]

I have to agree with Karn here: why build actually complex junctions when I can just fly stuff over eachother? OpenTTD Coop style players would have a field day

Welp, while their junction right now are crazily completely insane, i seriously wonder what they would do it they had multiple levels to build on.
We would have a density as high as... heck.