Hi!
I have been playing TTD and OpenTTD for long. One of the features I would like to see is the possibility to build underground. It is a feature that has been asked for long. So, if nobody is working on it, I would start a patch for it (just building infrastructure: no pathfinders). I have two questions:
Is anybody already working on it? No need to waste unnecessary time.
I need to add three pointers to the Tile or TileExtended (tile above/tile underground + another). What is better? Add them 1) to Tile, 2) to TileExtended or 3) to a new struct? I'm thinking of Tile, which is the one that has more information, but I'm not sure. I'll take Expresso's idea instead.
(My) main ideas/goals to start are:
Brute force. It's not nice but it will end up consuming double memory and increasing CPU usage
Extend the Tile struct but not change it dramatically: adding an uint32 as Expresso suggested (can be done with an uin24 if needed)
Simple GUI
Add markers to several tiles to mark border tiles between surface and underground (see pictures)
Each company keeping a "working currently at height..." number (also clients). Town, water,... owners won't. It can change in the future.
Make procs check at the beginning at which height the company is working and apply changes to tile at that height (creating/deleting a new tile if necessary)
Split it into small patches: if I leave this patch unfinished (as it probably will be), at least make it possible another person to use some of the code
Drop most of the new code into separate files (underground*.h...) declaring things static. Details will be decided later. I want the starting draft be reviewed as soon as possible. So if I make any big mistake, I can correct it at the beginning
I've started writing it and it doesn't seem so difficult (at least the GUI part; I suppose the building rail/roads as well). The difficult part is depots, stations, vehicles and pathfinders. But this comes after building the basic infrastructure.
Any idea (even possible problems that may arise) is welcome.
Attachments
Sarnton Transport, 29th Jul 1976.png (543.72 KiB) Viewed 797 times
Same picture showing underground tiles
Sarnton Transport, 20th Jun 1976.png (408.24 KiB) Viewed 797 times
Last edited by J0anJosep on 14 Dec 2011 18:35, edited 1 time in total.
The split between Tile and TileExtended is due to performance reasons. It's easier to go to x * 8 than to go to x * 9 for a CPU. Something similar will happen if you add extra pointers. So I'd suggest using a tertiary array. Anyhow, for 64 bits OpenTTDs this will increase the map size by almost a factor 4.
As far as I know nobody is actively working on the issue. However, there have been people that worked on making the tile array more extendable.
A while ago I posted an idea which basically comes down that every tile which comes down to more then one layer is stored in a separate memory pool and the map array gets a new tile class which basically stores an index in that memory pool.
You don't need to expand the map array and memory usage is expanded as needed. Each tile could effectively safely store such an offset and you'd still have bits to spare.
A memory pool is not so nice for performance, but you don't end up consuming rediculous amounts of memory just to store the map. You could ofcourse also use a flat array, which you grow or shrink as the need arises... but that still isn't nice on performance.
Another option could be to cut the map array up into lines or collums and storing each layer as a separate tile. To compensate for searching through 2048 tiles, each line could keep track of where a block of 64 tiles starts on a line; of course this tracking information should not be stored in the actual map data itself, but instead it should be tracked separately.
Rubidium wrote:The split between Tile and TileExtended is due to performance reasons. It's easier to go to x * 8 than to go to x * 9 for a CPU. Something similar will happen if you add extra pointers.
Idea of linked lists by pointers abandoned. I don't know much about how computers work. Adding an uint32 to Tile it would make it 16*x (64 bits). Would that be tolerable in terms of efficiency? (ie: x8 is a shift of 3 bits; do computers detect that x16 is a shift of 4 bits?)
planetmaker wrote:You'll need that per client. Not per company.
Thank you. I would never have realised this.
Yexo wrote:Michi_cc has create a set of patches that change how tiles are stored. ... Perhaps this can help you already?
It helps. I have looked at it and I was about to use it, because in case of adding bits to tiles (for storing extra information) it is more flexible than the Tile/TileExtended way. But after Expresso's suggestion and after coding a while, I think it is irrelevant which I use.
Expresso wrote:A while ago I posted an idea which basically comes down that every tile which comes down to more then one layer is stored in a separate memory pool and the map array gets a new tile class which basically stores an index in that memory pool...
... A memory pool is not so nice for performance ...
... Another option could be to cut the map array up into lines or columns...
Just some thoughts, I hope it helps.
Your post has helped a lot. Now I've read some of your (and other users) posts on the topic. I found out there has been a long discussion about it. Nobody seems to start coding even with a simple idea. I'll do it. In fact, your idea of a separate memory pool adding an integer to the tiles to reference underground tiles is the best. And I'll take it. I think someone should have listened and started coding your idea long enough...
...A memory pool isn't nice, ok. But we'll have to start somewhere (allowing duplicating memory, processor usage...).
...To cut the map array into lines or columns? Do you want to put me off? :-/ Too complicated for me, sorry.
I'll post a draft on Friday with the basic GUI and how to deal with landscaping while underground.
Another idea is to cut the map array in a bunch of lines. Each line contains a number of tiles relative to the map width. However, tiles could have a variable size (from one byte up to whatever memory allows). To compensate for the search nightmare this becomes, a separate array keeps track where each tile on the line starts in memory.
The advantage of this approach is that reading from and writing to the map can be done by an independent thread, allowing the program to continue. It also allows for tiles to become as large as needed, instead of the current max of 9 bytes (72 bits).
The disadvantage to this is that you need to copy all data and accessing the map array isn't a simple operation anymore.
The line could then expand or shrink as needed, without the rest of the game needing to take note.
Come to think of it... why not put the map array in sqlite?
edit: removed "simple", as the idea isn't simple at all
I've had some problems writing the code. Just to say I assumed a byte is 4 bits... Wrong! ... I noticed that yesterday... But, well, the idea was to see how difficult would be to adapt OpenTTD with underground structures.
I have to say, the idea of developing an underground mode doesn't look to me as interesting as at the beginning. Whatever approach used, it will consume lots of resources...
On the other hand, it is not difficult to adapt it, just lengthy. Most of the code should be rewritten, but no great changes are needed (just having tileindexes and a way to decide whether to look on the _m array or the _mu array). Also, the same approach used in underground could be used to allow signals/stations over bridges.
This patch tries to show the main idea (it is messy and uncommented, but I don't have time this week to do so). It allows seeing (more or less) the underground and buy tiles.
PD: moving some functions to tile members and declaring so many functions static is just to speed up the process of writing the patch, it isn't necessary.
Expresso wrote:Another idea is to cut the map array in a bunch of lines. Each line contains a number of tiles relative to the map width. However, tiles could have a variable size (from one byte up to whatever memory allows). To compensate for the search nightmare this becomes, a separate array keeps track where each tile on the line starts in memory.
The advantage of this approach is that reading from and writing to the map can be done by an independent thread, allowing the program to continue. It also allows for tiles to become as large as needed, instead of the current max of 9 bytes (72 bits).
The disadvantage to this is that you need to copy all data and accessing the map array isn't a simple operation anymore.
The line could then expand or shrink as needed, without the rest of the game needing to take note.
Come to think of it... why not put the map array in sqlite?
edit: removed "simple", as the idea isn't simple at all
As soon as you start down the routes of variable size tile records, you might as well just use a heap, as performance will be poor regardless.
Using a separate thread for map read/writes is frankly infeasible, as this introduces major synchronisation issues, and excessive context switching, which will kill performance stone dead.
A database such as sqlite again has major performance overheads.
If I were to attempt to implement something like this, I'd leave the existing map array more or less as it is, and add a field/extra array pointing to a separate pool/intermediary layer. Rather like the way routing restrictions are stored in TTDP. I believe that Oscar Eisemuth also started working on code to do this sort of thing for TTDP.
Ohh, that is code mentioned that I didn't touched since 5 years.
Basicly it's a 256x256 index ptr array that points to a continues stream of feature structures.
Each entry has an height above ground, a feature (like rail map) and a word of data.
In memory you have some kind of stream for each tile with holes.
###### ###### ###
To insert something you need to maybe move some data around, if the ratio between holes and user data is good, you have to move only a couple of bytes. Otherwise you need a big mem move. Or move the tile data elsewhere. (optimize). If nothing helps a new memory page is requested by the system
So it can store a true 3D representation of transport game.
Notice the ratio ptr to user data isn't bad for small map.
-edit-
For bigger maps and more levels I would design:
- a quad tree like structure, so a map is in logical cells, that have locks for read and full write. Nearby tiles are close in memory.
- changes on the map can be async only if it isn't a player action or influences other cells. Reads like the drawing code can work async.
- I would have a height entry, so I won't need to store for each feature the extendedheight.
TTDPatch dev in retirement ... Search a grf, try Grf Crawler 0.9 - now with even faster details view and new features...
Eddi wrote:my guess would be a beta in about 5 years from now...
I have a slight feeling of déja vu on this remark.
JGR: there are other means then mutexes in order to guarantee data integrity. Queues could be made for read and write commands. Performance impact would still be more then acceptable, though. That being said, have you got a better idea on how to store dynamic size tiles with as little as possible performance loss?
Expresso wrote:JGR: there are other means then mutexes in order to guarantee data integrity. Queues could be made for read and write commands. Performance impact would still be more then acceptable, though. That being said, have you got a better idea on how to store dynamic size tiles with as little as possible performance loss?
A read/write queue system implies that the write queue and read queue must not simultaneously refer to the same location, unless further expensive serialisation is added. It also implies that for read operations, the "main" thread will be idle until the queued operation returns (and therefore a good fraction of the time), and hence logically it is better to have multiple threads and one map-handler worker thread, which makes the synchronisation problem even worse.
Furthermore you underestimate the performance hit of an inter-thread queue. Context-switching and queue CAS/locking operations are not cheap.
As for storing dynamic size data, basically a heap with a suitable hash tree/something like that to point to each item, is the first thing that comes to mind.
With about 4 years no post, and only a first patch that doesn't work (as in, it is non-functional in providing more build levels), it's quite safe to say the project was never alive.
Being a retired OpenTTD developer does not mean I know what I am doing.
I've been looking through the forum at various discussions about this. I have not yet looked at the code, even briefly, to determine the amount of work it would take, and still have concluded that it would probably be a rather large amount of work.
I have some interest in contributing some of my time to, at least, making some changes to move things in the right direction towards making this possible. I certainly will not claim that I could have a patch next week/month/year so we can all build subways and underground bus stations. I do believe that I can get something started here, though.
It would seem that the first stage of this would be to figure out how underground building would work. We already have some underground building (tunnels) but, according to other discussions I have read, it's not really underground building at all. The vehicle just sort of disappears into one end and emerges from the other end after some time. So, perhaps a logical first step would be to change that? If more complex underground networks of tunnels could be built, including intersections and the changing of levels, it seems that things would be moving in the proper direction toward making this possible.
So, thinking ahead just slightly, the next step would probably be to allow for the creation of stations underground. Underground bus stations, truck stations, and train stations need to be possible, and it needs to be possible to join them to above-ground stations. An above-ground station, something like "subway entrance" could be added, but realistically any above-ground station could be joined in the beginning, making the underground stations usable for more than simple transfers. It seems reasonable that underground stations would have no direct interaction with the towns/industries above unless they are somehow joined with an above-ground station of some sort. It would also seem that this may possibly simplify some things, as the underground stations would not really be considered when it comes to distribution of freight/passengers. It also seems to address the issue of stations existing on more than one level, as additional station connections would need to be made at each level, probably with a greatly reduced station spread.
The other major thing that needs to be considered is how exactly we build underground. Currently there is no kind of alternate view which would allow this AFAIK. The layers of subterranean construction would be somewhat relative to the ground height. It would seem to me that, if I was building an underground network of tunnels for some reason, I would rather "peel away" a specific elevation and see all above-ground roads and structures at and below that elevation, while making everything above that level invisible. It seems that perhaps an additional transparency setting could be added, something like "above N meters" with a selector for N. The actual building would be done using new construction tools for tunnels with descending/ascending ramps in various directions, intersections, and underground stations. However, this may not be the best solution, so some feedback on this would probably be useful.
Moving on, there is very little I can say before looking over the code for this. I believe it is all written in C, which is good for me since I have a lot of experience in C programming. At this point, I am more interested in knowing how receptive the maintainers of this project would be to patches for this type of functionality. There are also a few parts of this which some of them may be able to implement far more easily than I could. The transparency settings I mentioned, for instance, may be fairly easy to implement for someone that has worked on the rendering system before. It seems that many people have already created and contributed graphics for many vehicles appropriate for this, so most of that type of work could already be complete also.
So, before I ramble any more about this and before I start looking through sources, I'm just going to wait and see what kind of response I get from this.
I did see that thread, and there were a few things that made me not look too much into it (yet). I may look at what he has done there after examining the current code more. It looked, mostly from the naming, like what was done there was just a 4-layer hack. It seems that a proper 3-D implementation, replacing the old tunnel system, etc. would be preferable to that.
