90 degree tunnels

Got an idea for OpenTTD? Post it here!

Moderator: OpenTTD Developers

Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: 90 degree tunnels

Post by Alberth »

MagicBuzz wrote:In fact "anything" an be done with "any" langage".

The problem isn't a matter of langage nor even a problem that writting and maintaining more complex code in a langage than with another one.
There are differences in languages, some are stronger in one area, and less strong in another. C and C++ is one the most flexible languages, as the language doesn't limit you. At the down-side, it doesn't help you much either.
In the end however, the differences are minor. If you know your way around in a language, you can express pretty much express anything you want, with a varying degree of complexity. (If a language supports a feature that you need out of the box, it's a great language. If it doesn't support a feature you need, you first have to build a layer on top of the language to add the feature, then you can express it on top of that layer. Building that layer may be a complex problem in itself though.)

It's much like natural languages. Different languages have different vocabularies, but in the end, you can express all notions in natural language, using more or less words.
MagicBuzz wrote:The problem is a matter of "how it's done now".
Sort of.
The current solution is the current solution because it's in a sweet spot of the requirements. In other words, it works well, it is optimal in some way.
Much of the code is pretty well tuned for its function in OpenTTD. For example, the A* path-finder in the code is not a generic A* implementation that you find at the Internet. It once started as a generic implementation, and was subsequently extended and refined to get better performance for eg routing trains, ie all the slack has been taken out, so you can have more trains.

This means that it's very hard to beat the current solution, or to keep the same performance, but add more functionality (like having multiple layers). More functionality implies you have to do more work (namely everything that's extra), which will cost CPU time. That CPU time is thus not available for the old functionality, ie you loose performance wrt to the old functionality.
MagicBuzz wrote:The core of OTTD is about it's way to store and manage the map.
We can change the way it's coded, but this implies many changed in all features of the program.
The dominant data structure IS the map. Everything is connected to it. Add a few CPU cycles to the access, and you will immediately see a drop in performance, as it's accessed zillions times each second.

You can perhaps hide most of the changes, there is a set of functions that abstracts the map structure. On the other hand, that abstraction is very very thin to avoid performance losses.
MagicBuzz wrote:And for some benefits it may bring some enormous limitations.
You cannot get more CPU cycles than you have, so at some point you have to decide whether a feature is worth the cost in other areas of the game.
MagicBuzz wrote:You may have the same problems with any langage.
You do, until you invent a language that has free infinitely many CPU cycles.
That won't happen with the current computer technology.
Being a retired OpenTTD developer does not mean I know what I am doing.
User avatar
acs121
Tycoon
Tycoon
Posts: 1956
Joined: 03 Nov 2017 18:57
Location: Courbevoie, near Paris, France

Re: 90 degree tunnels

Post by acs121 »

Alberth wrote:
MagicBuzz wrote:snip snip
snip
While you have stated Minecraft uses the GPU instead of the CPU for rendering, why doesn't OpenTTD do the same thing ? Would it break AIs, GameScripts or NewGRFs ?
User avatar
MagicBuzz
Tycoon
Tycoon
Posts: 1354
Joined: 15 Feb 2003 17:32
Location: Vergezac, France

Re: 90 degree tunnels

Post by MagicBuzz »

Some answers :
- OTTD is cross plateform. As GPU is plateform specific, the code should implement many different APIs in order to provide GPU acceleration for any plateform.
- OTTD uses 2D only. Since the MMX instructions, most of the interesting graphic 2D oriented instructions are handled by CPU. GPU is worth only for 3D acceleration.
- Working with the GPU implies many CPU cycles to prepare and transfert the scenery to the GPU. This is a real wasting time (this applies to 3D too) and for 2D I'm pretty sure the gain is not much higher than the waste.


In fact, the only feature that could help with performances in OTTD should be multi-threading.
Most of the computer have now 2 or 4 cores, and even more.
Currently, OTTD mainly works in a single thread. As a result, modern processors are not fully exploited.

But changing a mono-thread program to a multi-thread program is like to change a train into 200 cars with mad drivers running everywhere in the wild : it takes a lot of work to decide wich feature could work on which thread and how to synchronize everyone… In a city, there are trafic lights… and trafic jams. Not in the subway.
User avatar
acs121
Tycoon
Tycoon
Posts: 1956
Joined: 03 Nov 2017 18:57
Location: Courbevoie, near Paris, France

Re: 90 degree tunnels

Post by acs121 »

MagicBuzz wrote:Some answers :
- OTTD is cross plateform. As GPU is plateform specific, the code should implement many different APIs in order to provide GPU acceleration for any plateform.
- OTTD uses 2D only. Since the MMX instructions, most of the interesting graphic 2D oriented instructions are handled by CPU. GPU is worth only for 3D acceleration.
- Working with the GPU implies many CPU cycles to prepare and transfert the scenery to the GPU. This is a real wasting time (this applies to 3D too) and for 2D I'm pretty sure the gain is not much higher than the waste.


In fact, the only feature that could help with performances in OTTD should be multi-threading.
Most of the computer have now 2 or 4 cores, and even more.
Currently, OTTD mainly works in a single thread. As a result, modern processors are not fully exploited.

But changing a mono-thread program to a multi-thread program is like to change a train into 200 cars with mad drivers running everywhere in the wild : it takes a lot of work to decide wich feature could work on which thread and how to synchronize everyone… In a city, there are trafic lights… and trafic jams. Not in the subway.
No, OpenTTD isn't 2D. It is 2D isometric, halfway between 2D and 3D.
User avatar
MagicBuzz
Tycoon
Tycoon
Posts: 1354
Joined: 15 Feb 2003 17:32
Location: Vergezac, France

Re: 90 degree tunnels

Post by MagicBuzz »

Yes, 3D isometric IS 2D.

There is no 3D graphic engine in OTTD.
It uses only 2D graphic instructions.
User avatar
acs121
Tycoon
Tycoon
Posts: 1956
Joined: 03 Nov 2017 18:57
Location: Courbevoie, near Paris, France

Re: 90 degree tunnels

Post by acs121 »

MagicBuzz wrote:Yes, 3D isometric IS 2D.

There is no 3D graphic engine in OTTD.
It uses only 2D graphic instructions.
Then as for an answer, platforms are none of a problem. Specific versions can be developed for each platform.
While for the cores, i don't think changing OpenTTD to two cores instead of one would resolve any problem.
The real problem isn't during the game, really. It's outside of it. I have save files that weigh 28978 Ko. And this, while they contain 2k trains, 3k RVs, 1k ships and 2k aircraft, all them moving at the same time, and i have no problem playing it on my computer.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: 90 degree tunnels

Post by Alberth »

NewGRFs have vast possibilities to change graphics based on data from the game. To get performance, you need the NewGRF interpreter and the graphics engine at the same device. So if you want to move rendering to the GPU, you need to move the NewGRF interpreter to the GPU too. The NewGRF interpreter can likely be done, but to run it you also need the information of the game, since NewGRFs use that information. That mostly implies you need to move half the openttd data to the GPU too.

Of course the other option is to break all newgrfs by throwing away a lot of the possibilities, so you need less information to be present at the GPU.

A third option is to spread the control between the GPU and the CPU, that has been tried, and it hardly improved matters, while making everything a whole lot more complicated, afaik.


With resepct to 2.5D: Indeed, isometric (or rather, dimetric, true isometric projection is different from what OpenTTD does) looks like 3d-ish, but it's really just flat weirdly shaped 2d images drawn partly on top of each other, ie the engine sprites you see everywhere are literally painted as you see them, at exactly the right position, so it looks like there is depth. Pretty nice for a technique that's 30 or so years old :)
Being a retired OpenTTD developer does not mean I know what I am doing.
User avatar
acs121
Tycoon
Tycoon
Posts: 1956
Joined: 03 Nov 2017 18:57
Location: Courbevoie, near Paris, France

Re: 90 degree tunnels

Post by acs121 »

Alberth wrote:NewGRFs have vast possibilities to change graphics based on data from the game. To get performance, you need the NewGRF interpreter and the graphics engine at the same device. So if you want to move rendering to the GPU, you need to move the NewGRF interpreter to the GPU too. The NewGRF interpreter can likely be done, but to run it you also need the information of the game, since NewGRFs use that information. That mostly implies you need to move half the openttd data to the GPU too.

Of course the other option is to break all newgrfs by throwing away a lot of the possibilities, so you need less information to be present at the GPU.

A third option is to spread the control between the GPU and the CPU, that has been tried, and it hardly improved matters, while making everything a whole lot more complicated, afaik.


With resepct to 2.5D: Indeed, isometric (or rather, dimetric, true isometric projection is different from what OpenTTD does) looks like 3d-ish, but it's really just flat weirdly shaped 2d images drawn partly on top of each other, ie the engine sprites you see everywhere are literally painted as you see them, at exactly the right position, so it looks like there is depth. Pretty nice for a technique that's 30 or so years old :)
You shall note that even very popular games, such SimCity 4 also use 2D isometric. However, the map array is much more complicated in SC4 than OpenTTD, or the said Minecraft. OpenTTD has 12 slope types IIRC (correct me if i'm wrong), and SC4 is "dynamic terrain" - it has a ton more elevation types and others.
User avatar
JGR
Tycoon
Tycoon
Posts: 2557
Joined: 08 Aug 2005 13:46
Location: Ipswich

Re: 90 degree tunnels

Post by JGR »

Alberth wrote:NewGRFs have vast possibilities to change graphics based on data from the game. To get performance, you need the NewGRF interpreter and the graphics engine at the same device. So if you want to move rendering to the GPU, you need to move the NewGRF interpreter to the GPU too. The NewGRF interpreter can likely be done, but to run it you also need the information of the game, since NewGRFs use that information. That mostly implies you need to move half the openttd data to the GPU too.
I can't see how it would be practical or advantageous to turn NewGRFs into GPU shader programs.
Other than returning what sprite and bounds to use, NewGRFs don't do any actual rendering.
Running NewGRFs as they are now, but doing sprite blitting/culling/etc and palette operations in the GPU would be a plausible thing to do.
Having the GPU (pre-)loaded with sprites/textures and receiving a command list for each frame is fairly traditional and well-understood.
That said it still probably wouldn't be worth the bother as blitting sprites in the CPU is acceptably cheap.
acs121 wrote:You shall note that even very popular games, such SimCity 4 also use 2D isometric. However, the map array is much more complicated in SC4 than OpenTTD, or the said Minecraft. OpenTTD has 12 slope types IIRC (correct me if i'm wrong), and SC4 is "dynamic terrain" - it has a ton more elevation types and others.
Typically, SimCity maps have significantly fewer tiles than OpenTTD ones. Therefore it's reasonable for each individual tile to be more complicated/expensive.

OpenTTD is fairly atypical in how large the maps are (measured in tiles).
acs121 wrote:There are things you can code with Java you can't code in C++.
See Minecraft for example. Coded in Java, thus allowing a HUGE map size and an even more complicated map array, this using as much RAM as a game with over 5k vehicles in OpenTTD.
At no point does Minecraft store or simulate the entire map. It is procedurally (i.e. deterministically) generated as you move around, only deltas are saved.
This is not a suitable mechanism for a game like OpenTTD.
For what it's worth, Microsoft did re-write Minecraft in C++ for better performance.
lukasz1985 wrote:Java eats a lot more memory than C/C++ for a single object. I saw a video somewhere about it. So the map size would be very limited.
Java has flat (primitive type) arrays, this wouldn't be a problem.
Ex TTDPatch Coder
Patch Pack, Github
User avatar
acs121
Tycoon
Tycoon
Posts: 1956
Joined: 03 Nov 2017 18:57
Location: Courbevoie, near Paris, France

Re: 90 degree tunnels

Post by acs121 »

JGR wrote:snip
The SC4 maps, even for big cities, sure aren't very big... expecially when compared to OpenTTD : using a certain patch, your map can reach 16,384 x 16,384 tiles. Mathematically, you can use 268,435,456 tiles. And imagine you could have one cave layer, just one for convenience. That would make 536,870,512 usable tiles. Imagine storing that into a single .sav file. What if i told you my last save file is 34 778 Ko ?
This, and you not knowing how Minecraft really works... for the first generated tiles, they sur are generated when going near them. But once you modify the already generated, it is stored in the save.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: 90 degree tunnels

Post by Alberth »

MagicBuzz wrote:In fact, the only feature that could help with performances in OTTD should be multi-threading.
Most of the computer have now 2 or 4 cores, and even more.
Currently, OTTD mainly works in a single thread. As a result, modern processors are not fully exploited.

But changing a mono-thread program to a multi-thread program is like to change a train into 200 cars with mad drivers running everywhere in the wild : it takes a lot of work to decide wich feature could work on which thread and how to synchronize everyone… In a city, there are trafic lights… and trafic jams. Not in the subway.
Had no time yesterday to answer this one, so with a day delay:

Multi-threading only works if you can do stuff in parallel. Basically this boils down to being able to compute different parts independently, where the input data is fixed or is easily accessible and the order of getting results from the various computations has no influence on the final answer.

Unfortunately this does not hold for OpenTTD.

Let's take train-movement as example. The simulation-engine has one big central data structure, namely the map. Trains that move read the map for deciding where to go, and update the map with block reservations.

So what happens if you try to compute tha path of several trains at the same time, one thread for each train for example?
1. Path-finding is mostly "inspect a tile, do a small update, inspect next tile, do a small update, inspect .." etc, for a few hundred tiles or so (for one train). You constantly need map access to move the computation forward. If nothing writes to the map, this is easy, but trains do update the map with new blocks claimed and old blocks released at least.
2. Without protection at all, if you write to data that other threads read, the written data in the map is not consistently updated between threads (especially if different threads run at different CPUs). Threads may read old data, they may read partly updated data, or read the true updated data, The partly updated data is simply invalid, you never want that to happen (it will crash the program randomly).
3. The standard solution to deal with a data structure that is both being read and written from different threads, is by giving exclusive access to that data structure using a semaphore. Basically, a semaphore can give one thread exclusive access, it does its thing, and then releases the semaphore for the next thread. (Much like one train can use a block at a time.)

4. That solves the read/write problem, but creates two new problems.
- One is that your multi-threading is now a complicated form of single threading. As explained before, a thread needs constant map access to do a computation. If you fold a semaphore around the access, at most 1 thread can access the map, all others are blocked. It's like having eg ten people at a table with one fork on the table to eat. Only 1 person can use the fork at any time. Effectively, you have 1 person eating, and all others are waiting for the fork. It's just as fast (if not faster) to have each person eat in turn.
For the map data, still only a single train is being computed (or several at an equally slower rate), so there is no significant gain at all, you only added a complex multi-threading thing around it.

- The second problem is that the input data is now not fixed any more. Tile information may change at any moment (from another thread). This means that inspecting a tile has lost its meaning, since right after you looked at it, it may (or may not) change, so a computation may or may not use obsolete data, and produce incorrect results (two threads read the same tile after each other, both conclude the tile is free, and both reserve that tile for their train).
You can check the final result or so to avoid collisions, but that makes path-finding more expensive (you have to check after you found a path), and it doesn't solve the MP game problem, where two different computers are going to have to compute the exact same result each and every tick for half a day or whatever how long you play the game.
In particular, a very old single core computer and a 16-core monster in one MP game should work. Discarding paths based on timing of thread execution is a sure-fire way to desync in less than a few seconds.

You can come up with a few variations on the theme, but you either get results that vary on each run, or you lock down so much that you loose any significant gain.
This is why OpenTTD still uses single threading for path finding. It's simply the fastest solution that meets all requirements.
Being a retired OpenTTD developer does not mean I know what I am doing.
rowdog
Engineer
Engineer
Posts: 67
Joined: 24 May 2017 12:51
Location: East Texas

Re: 90 degree tunnels

Post by rowdog »

Alberth wrote:This is why OpenTTD still uses single threading for path finding. It's simply the fastest solution that meets all requirements.
Maybe we're barking up the wrong tree here. Instead of trying to do parallel pathfinding we could try to pull everything else out of the pathfinding thread. e.g. we could use another thread to calculate cargo production and other such tasks so as to free up the pathfinding thread to spend more time pathfinding.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: 90 degree tunnels

Post by Alberth »

Could be, although I wouldn't be surprised if production update for a few thousand industries (large map!) does not even show a blip in cpu usage.
It's basically moving 10 numbers or so, practically nothing.
Being a retired OpenTTD developer does not mean I know what I am doing.
Kruemelchen
Transport Coordinator
Transport Coordinator
Posts: 287
Joined: 18 Feb 2017 17:47

Re: 90 degree tunnels

Post by Kruemelchen »

I guess you could run cargo-dest in its own thread, or anything that doesn't alter the map array like the GUI? But I don't know if this would actually lead to any big gain, the bottleneck would still be the main thread (map array operations / pathfinding).

About underground layers, you could basically create another 'underground layer array' that only stores actual infrastructure, which means the size of the array would be min. 0 bytes plus overhead for the actual array. Then you would switch inside the game to an 'underground view' where nothing else than the underground would be rendered (except a 'shadow' of stations/buildings for orientation) so you wouldn't need to update any graphics, even though the pathfinder etc would still need to be run (like SimCity does with underground view). However, this would only allow for 1 (ideally flat) underground layer, which is better than nothing but eh.

As an alternative, you may allow for an actual tile inside the map array to store a pointer to additional data which could be 'concatenated' to store infrastructure for several different heights. This wouldn't 'quadruple' the size of the map array unless all the map is filled with 'tunnels' and 'bridges' (which would then be stored tile-wise and not as 'wormholes', thus allowing curves etc.)
However, pathfinding would be more costly as it would need to search for paths on different heights (if interconnected).

I don't know if cirdans new map features goes any way into that direction ...?
User avatar
acs121
Tycoon
Tycoon
Posts: 1956
Joined: 03 Nov 2017 18:57
Location: Courbevoie, near Paris, France

Re: 90 degree tunnels

Post by acs121 »

Kruemelchen wrote:I guess you could run cargo-dest in its own thread, or anything that doesn't alter the map array like the GUI? But I don't know if this would actually lead to any big gain, the bottleneck would still be the main thread (map array operations / pathfinding).
Actually, CargoDist also takes a huge ton of RAM during the game, and thus, i think you could effectively run Cargodist on a second thread. Or maybe we're barking up the wrong tree again ?
User avatar
Expresso
Tycoon
Tycoon
Posts: 1760
Joined: 09 Aug 2004 00:14
Location: Gouda, the Netherlands

Re: 90 degree tunnels

Post by Expresso »

iirc cargodist already has its own thread, as it can become quite cpu intensive.
User avatar
acs121
Tycoon
Tycoon
Posts: 1956
Joined: 03 Nov 2017 18:57
Location: Courbevoie, near Paris, France

Re: 90 degree tunnels

Post by acs121 »

Expresso wrote:iirc cargodist already has its own thread, as it can become quite cpu intensive.
...you know OpenTTD is entirely single-thread, right ?
User avatar
JGR
Tycoon
Tycoon
Posts: 2557
Joined: 08 Aug 2005 13:46
Location: Ipswich

Re: 90 degree tunnels

Post by JGR »

acs121 wrote:
...you know OpenTTD is entirely single-thread, right ?
See https://github.com/OpenTTD/OpenTTD/sear ... pe=Commits
Ex TTDPatch Coder
Patch Pack, Github
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: 90 degree tunnels

Post by Alberth »

acs121 wrote:
Expresso wrote:iirc cargodist already has its own thread, as it can become quite cpu intensive.
...you know OpenTTD is entirely single-thread, right ?
Only if you have a computer that doesn't know how to do multi-threading.
Being a retired OpenTTD developer does not mean I know what I am doing.
Post Reply

Return to “OpenTTD Suggestions”

Who is online

Users browsing this forum: No registered users and 10 guests