Technical: More flexible landscape array

Forum for technical discussions regarding development. If you have a general suggestion, problem or comment, please use one of the other forums.

Moderator: OpenTTD Developers

User avatar
Csaboka
Tycoon
Tycoon
Posts: 1202
Joined: 25 Nov 2002 16:30
Location: Tiszavasvári, Hungary
Contact:

Technical: More flexible landscape array

Post by Csaboka »

This suggestion is technical; I'd have posted it to the development forum if it was open for outsiders.

TTD stores six bytes of information for every tile on the map. The old code tries to put everything in there, sometimes using ugly methods (packing two or three pieces of information in a single byte), sometimes failing at all (that's why the grass grows faster under rails and roads: there wasn't enough space to store the phase of the growing grass, so it becomes fully grown immediately). Adding new properties for a tile is also extremely hard without adding new arrays, which increase the memory requirement by 64K each.

What I suggest here is a flexible storage of some part of the data. We could add a sixth landscape array, which contains pointers. This array is initialized with all NULLs. If it's non-NULL, it points to the head of a linked list whose every element contains an ID number and data of variable length. This linked list contains the extra data for the tile. This way no memory would be wasted for tiles not needing the extra info, and extending properties of tiles would be much easier.

For example, if I want to implement abandonedroads for OpenTTD, I'll need an extra _landscape6 array. This array would allocate 1 or 2 bytes of memory even for tiles that don't have road on them, and if someone wants to implement another property (correct growing on grass under roads, for example), he'll need a _landscape7 array and so on. On the other hand, if _landscape6 contains pointers only, 4 bytes per "standard" tile is wasted no matter how many extra properties tiles can have.

Or maybe there should be a continous block instead of a linked list, because AFAIK every malloc() call eats 8 bytes of additional data on top of the size requested. This would be a bit harder to change, but still flexible enough.
Bjarni
Tycoon
Tycoon
Posts: 2088
Joined: 08 Mar 2004 13:10

Post by Bjarni »

this post looked to developerlike to me that I moved it to OpenTTD developer forum
User avatar
Darkvater
Tycoon
Tycoon
Posts: 3053
Joined: 24 Feb 2003 18:45
Location: Hong Kong

Post by Darkvater »

Bjarni wrote:this post looked to developerlike to me that I moved it to OpenTTD developer forum
Csaboka wrote:I made a suggestion today about the inner working of OpenTTD, which was moved to OpenTTD development by Bjarni. The only problem is that I can't post things there, so I can't post to my own forum anymore. Please put it back to Suggestions.
I am not even here.
OpenTTD Development would be nice to be posted into for things like this, but if it became open, people would post the silliest ideas like: "I want a 3D openTTD where I can drive the trains" and the such :(

We/I'll ask Owen tonight if we could open the forum, and then just play moderator and move all silly-suggestions to the suggestions topic.

I like your idea though. I didn't know what AbandonedRoads was, so I looked it up. Basically you would need L6 to remember when was the last time a vehicle was on a tile (non-town roads), right?
TrueLight: "Did you bother to read any of the replies, or you just pressed 'Reply' and started typing?"
<@[R-Dk]FoRbiDDeN> "HELP, this litte arrow thing keeps following my mouse, and I can't make it go away."
User avatar
Csaboka
Tycoon
Tycoon
Posts: 1202
Joined: 25 Nov 2002 16:30
Location: Tiszavasvári, Hungary
Contact:

Post by Csaboka »

Darkvater wrote:Basically you would need L6 to remember when was the last time a vehicle was on a tile (non-town roads), right?
Yes, this is the basic idea. In TTDPatch, I stored the time since the last traffic and not the date of it, but this doesn't make a difference.
User avatar
orudge
Administrator
Administrator
Posts: 25134
Joined: 26 Jan 2001 20:18
Skype: orudge
Location: Banchory, UK
Contact:

Post by orudge »

I have opened the OpenTTD Development forum, something I was planning on doing anyway (for a trial period at least). Any inappropriate posts, just move them (don't delete them) elsewhere.
TBOT
Route Supervisor
Route Supervisor
Posts: 441
Joined: 30 Jul 2003 18:36
Location: The Codecave

Post by TBOT »

On large maps the pointers would waste quite an amount of memory. Take for example the case of 1024x1024 maps, that would be 4 MB of memory wasted just for the pointers, where the useful data might not exceed a few kb's (depending on what your doing with it of course).
So I think you should think carefully about whether a good 'static' implementation would exceed the size of the memory you waste with pointers.
"Peace cannot be kept by force. It can only be achieved by understanding." - Albert Einstein
Mek
TTDPatch Developer
TTDPatch Developer
Posts: 417
Joined: 13 Apr 2004 13:35
Location: Eindhoven, Netherlands
Contact:

Post by Mek »

TBOT wrote:On large maps the pointers would waste quite an amount of memory. Take for example the case of 1024x1024 maps, that would be 4 MB of memory wasted just for the pointers, where the useful data might not exceed a few kb's (depending on what your doing with it of course).
So I think you should think carefully about whether a good 'static' implementation would exceed the size of the memory you waste with pointers.
but with just 5 new features that need a landscape array, you would need a lot more memory with a static implementation....
User avatar
Csaboka
Tycoon
Tycoon
Posts: 1202
Joined: 25 Nov 2002 16:30
Location: Tiszavasvári, Hungary
Contact:

Post by Csaboka »

At first, it will seem to be only a waste of memory, but the more extra data is needed, the less the overhead will be. People will want more and more features, so the amount of extra data needed will surely increase.

On the other hand, we could extend the flexible format to the landscape data already there (maybe except owner, height and type data, because these are present for every tile). This would make the handling of landscape data more logical by getting rid of bitmasking, at the cost of slightly slower data access. And rewriting the existing code would take some time as well.

For example, the status of grass is currently stored differently for empty tiles, rail tiles and road tiles. It isn't even stored for bridges and trees, so putting these things on the map will make the grass grow immediately. In the new format, there'd be a GRASS_STATE field for every tile that needs it, making it easier to handle.

IMO TTD has many bad solutions because of the limits of memory available. We should make the code more logical,readable and extendable even if it means making it a bit slower.
User avatar
Darkvater
Tycoon
Tycoon
Posts: 3053
Joined: 24 Feb 2003 18:45
Location: Hong Kong

Post by Darkvater »

TBOT wrote:On large maps the pointers would waste quite an amount of memory. Take for example the case of 1024x1024 maps, that would be 4 MB of memory wasted just for the pointers, where the useful data might not exceed a few kb's (depending on what your doing with it of course).
So I think you should think carefully about whether a good 'static' implementation would exceed the size of the memory you waste with pointers.
I don't see how this would be problem. People that will play 1024x1024 maps, are not going to play it on their P90 with 32MB of ram. That will never run with any decent speed. 4MB extra for a 16x as big map on a (semi)-modern machine is peanuts.

I'll just move this back :lol:
TrueLight: "Did you bother to read any of the replies, or you just pressed 'Reply' and started typing?"
<@[R-Dk]FoRbiDDeN> "HELP, this litte arrow thing keeps following my mouse, and I can't make it go away."
fortis
Engineer
Engineer
Posts: 5
Joined: 28 May 2004 09:54
Contact:

Post by fortis »

I'd have to agree with Csaboka, this will solve a lot of problems with expanding the current game, instead of all the current hacks. I'd doubt we'd see much slower speeds, on the systems that should be running the 1024x1024 maps, as dark pointed out, it's not targeted at P90s, especially when pasky or who ever starts working on the 16/24 bit graphics.
User avatar
dominik81
OpenTTD Developer
OpenTTD Developer
Posts: 768
Joined: 16 Aug 2003 12:55
Location: Bonn, Germany

Post by dominik81 »

I'd rather see the whole memory usage reworked than extending the current system. That would certainly cause a new savegame format, but it would bring many benefits. The current usage is way too limited, e.g. when you look at bridges. A more dynamic format could allow bridges over each other and much more.
"There's a readme that comes with the source. I suggest you read it."
- Korenn
User avatar
Korenn
Tycoon
Tycoon
Posts: 1735
Joined: 26 Mar 2004 01:27
Location: Netherlands
Contact:

Post by Korenn »

dominik81 wrote:I'd rather see the whole memory usage reworked than extending the current system. That would certainly cause a new savegame format, but it would bring many benefits. The current usage is way too limited, e.g. when you look at bridges. A more dynamic format could allow bridges over each other and much more.
this is exactly what's needed, but it will be a colossal job.

But I like the pointer idea, you could store ALL data this way, then it would be only one extra memory call per tile, with lots of potential for extensions.
Bjarni
Tycoon
Tycoon
Posts: 2088
Joined: 08 Mar 2004 13:10

Post by Bjarni »

we really need this. It will make options, such as signals in tunnels and on bridges possible. It would also make turnable tunnels and underground stations possible
Still, it's a lot of work, both altering the code to pointerstyle and each of this features, but I think it's worth it
User avatar
Csaboka
Tycoon
Tycoon
Posts: 1202
Joined: 25 Nov 2002 16:30
Location: Tiszavasvári, Hungary
Contact:

Post by Csaboka »

That's how I think it should work:

The old _map_owner and _map_type_and_heights arrays should stay since these data are needed for every tile, and looking up them would be faster this way. The other arrays should be replaced by an _extra_data array of pointers. These pointers are either NULL, or point to a data chunk that looks like this:

<ID><DATA><ID><DATA>...<ID><DATA><0>

where the (at least two bytes long) ID uniquely identifies the lenght and structure of the following data. Finding a property by ID would need a linear search, inserting or deleting data would need a realloc(). Since these things will be implemented as functions, the conversion of the code should be done in three parts. First we make dummy search, insert and delete functions that in fact read from the old landscape arrays. Then we can start rewriting the code to use the new functions gradually, since we get the same data in both ways. After finishing all the code conversion, we change the dummy functions to real ones, and voila: we have a more flexible and easily extendible landscape.
User avatar
Csaboka
Tycoon
Tycoon
Posts: 1202
Joined: 25 Nov 2002 16:30
Location: Tiszavasvári, Hungary
Contact:

Post by Csaboka »

If everything goes well, my last exam will be on Wednesday. After that, I'll have a lot of free time until September, so I can work on this idea. If, of course, you devs agree with it. If anyone has problems or questions about the format I suggested in my previous post, go ahead and let's start discussing it.

If you agree with the format, I suggest these functions for using new landscape data:

void *GetPropByXY(int x,int y,PROP_ID prop)
Returns a pointer to the property data from the tile identified with the given ID. If there's no data assigned to the property, it returns NULL.

void *GetPropByXYDef(int x,int y,PROP_ID prop,void *default)
The same as above, except that if it doesn't find the property then adds it to the tile, with the default values given in the fourth parameter.

void SetPropByXY(int x,int y,PROP_ID prop,void *data)
This one is only needed for the temporaly stage when we access landscape data both ways. The dummy getter functions malloc() a data block filled with the data in the new format, while SetPropByXY translates the new format data back to old format, stores it in the landscape arrays, then free()-s the temporary memory block. This is an ugly solution, but needed only temporarily. In the new-style landscape data management, changes can be done directly on blocks returned by getter functions, all setter functions can be deleted from the code.

void DelPropByXY(int x,int y,PROP_ID prop)
Deletes data assigned to the given property from the given tile. If there's no such property, the function returns silently without doing anything.

void *GetPropByTile(void *tile,PROP_ID prop)
void *GetPropByTileDef(void *tile,PROP_ID prop,void *default)
void SetPropByTile(void *tile,PROP_ID prop,void *data)
void DelPropByTile(void *tile,PROP_ID prop)
Similar to the above, except they operate on a pointer taken directly from _extra_data.

PROP_ID is defined as either an uint_16 or an uint_32, and every value has an according symbolic name like PROP_GROUND_STATE or PROP_FENCE_STATE. The starting set of PROP_ID values can be created by using Marcin's TTD internals file. This file can be also used for the dummy functions needed for the temporary stage. I'd gladly write both the final and the dummy functions (the final ones will be pretty easy anyway) and start converting the code to the new style, but it hasn't any sence if others don't agree with using this format. I'm also open for suggestions to improve this system.

PS: I don't know how frequently I can access Internet in the summer holiday, so I may be lagging behind the SVN releases. I hope this wouldn't hurt so much with this kind of work (changing code already present without changing its function).
DjArcas
Engineer
Engineer
Posts: 65
Joined: 24 May 2004 14:02
Contact:

Post by DjArcas »

TBOT wrote:On large maps the pointers would waste quite an amount of memory. Take for example the case of 1024x1024 maps, that would be 4 MB of memory wasted just for the pointers, where the useful data might not exceed a few kb's (depending on what your doing with it of course).
So I think you should think carefully about whether a good 'static' implementation would exceed the size of the memory you waste with pointers.
Speaking as a console developer - when writing games, you should ideally allocate the maximum amount of something at startup time. Linked lists are evil, and lead to nasty fragmentation. Not to mention that they are a *b***** to debug.

I would lean towards simply choosing a sensible number of bytes for tiles in the future, and sticking with that. 256? *shrugs*

But please please please stay away from allocating RAM at runtime in a game!
The largest multiplayer games in the world - ever.
http://www.projectorgames.net
msalters
Engineer
Engineer
Posts: 34
Joined: 16 Jun 2004 19:21

Post by msalters »

I'm also a software engineer, worked on non-gaming embedded systems. Games have the advantage that it is more acceptable to have hiccup now and then, I worked on communications systems where timing was somewhat more important.

Anyway, linked lists are pretty much the classical case of objects that do not fragment memory. Fragmentation occurs when memory alloactions differ in size. Typically this happens with strings. Still, I wouldn't use them here.

The problem is not storing data for every tile. For that, an extra array is most efficient. The problem is storing properties for a small number of tiles (sparse). One should definitely use a PROP_ID for this that also identifies the property size, and properties should be fixed-size. This speeds up logic. E.g. use the lowest 4 bits for the size,

Code: Select all

size_t size = sizeof(PROP_ID) * (aPROP_ID & 0xf) 
. (The sizeof is for alignment). This still leaves at least unique 4096 properties, assuming we don't alias PROP_ID's of different sizes (ie when PROP_ID >> 4 is also unique).
After the PROP_ID we can then store the property data.

Only then do we have to deal with the hard stuff, finding properties for a given x/y pair. Basically, there are two solutions: linked lists of properties and concatenated properties. In the first case, each property has a pointer to the next property. In the second, we continue with a new PROP_ID after the propery data of the previous.
We can also use mixed forms, by reserving a special PROP_ID PROP_CONTINUE_IN_NEXT_BLOCK or so. In that case, we concatenate properties in a block until we have space for one last 4-byte property. If we then add it, we allocate a new memory block, add a pointer property in the previous block, and continue in the new block.

This last form is pretty good, because we can then use uniform 32-byte block (hardly any fragmentation) yet still use variable-length properties.

The last point we need to address is the 'first property'. For simplicity, I suggest we initially stick with a [N][N] pointer array. One could perhaps save a few bytes by using an array of arrays, and allocating only those nested arrays for which there are really properties. This saves quite a few bytes near the edges, but it becomes complicated quite soon.
DjArcas
Engineer
Engineer
Posts: 65
Joined: 24 May 2004 14:02
Contact:

Post by DjArcas »

I meant 'memory allocation leads to fragmentation'

Just take me outside and shoot me. :)
The largest multiplayer games in the world - ever.
http://www.projectorgames.net
msalters
Engineer
Engineer
Posts: 34
Joined: 16 Jun 2004 19:21

Post by msalters »

While we're at it, perhaps we can speed things up by merging the arrays. With modern caches, we can benefit from locality of reference by keeping all data of a single tile close together. There is no need on a 32-bits architecture to limit our arrays to 64 Kb. In fact, this may be sub-optimal for a number of CPUs (especially those with 64Kb cache, where speed matters most)
pasky
OpenTTD Developer
OpenTTD Developer
Posts: 90
Joined: 25 Apr 2004 15:14
Location: Czech Republic
Contact:

Post by pasky »

I, for one, would wholehearthly welcome blasting off all those horrible map12345lohi bitpacking and just use array of struct { byte owner; byte type; void *data; }, data varying by type. But I think that's not going to happen ;-).
The flush toilet is the basis of Western civilization. -- Alan Coult
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 10 guests