Transport Tycoon Forums

The place to talk about Transport Tycoon
It is currently Sun Dec 17, 2017 12:24 am

All times are UTC




Post new topic  Reply to topic  [ 38 posts ]  Go to page 1 2 Next
Author Message
PostPosted: Wed Jun 02, 2004 10:44 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Nov 25, 2002 4:30 pm
Posts: 1202
Location: Tiszavasvári, Hungary
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.


Top
   
 Post subject:
PostPosted: Wed Jun 02, 2004 3:08 pm 
Offline
Tycoon
Tycoon

Joined: Mon Mar 08, 2004 1:10 pm
Posts: 2088
this post looked to developerlike to me that I moved it to OpenTTD developer forum


Top
   
 Post subject:
PostPosted: Wed Jun 02, 2004 3:39 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Feb 24, 2003 6:45 pm
Posts: 3053
Location: Hong Kong
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."


Top
   
 Post subject:
PostPosted: Wed Jun 02, 2004 4:09 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Nov 25, 2002 4:30 pm
Posts: 1202
Location: Tiszavasvári, Hungary
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.


Top
   
 Post subject:
PostPosted: Wed Jun 02, 2004 10:53 pm 
Offline
Administrator
Administrator
User avatar

Joined: Fri Jan 26, 2001 8:18 pm
Posts: 23816
Skype: orudge
Location: Banchory, UK
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.

_________________
Owen Rudge
owenrudge.net | Owen's Transport Tycoon Station | Owen's Locomotion Depot | The Transport Tycoon Wiki


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 12:08 pm 
Offline
Route Supervisor
Route Supervisor

Joined: Wed Jul 30, 2003 6:36 pm
Posts: 441
Location: The Codecave
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


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 12:13 pm 
Offline
TTDPatch Developer
TTDPatch Developer
User avatar

Joined: Tue Apr 13, 2004 1:35 pm
Posts: 417
Location: Eindhoven, Netherlands
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....


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 12:38 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Nov 25, 2002 4:30 pm
Posts: 1202
Location: Tiszavasvári, Hungary
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.


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 1:26 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Feb 24, 2003 6:45 pm
Posts: 3053
Location: Hong Kong
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."


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 1:35 pm 
Offline
Engineer
Engineer

Joined: Fri May 28, 2004 9:54 am
Posts: 5
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.


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 3:58 pm 
Offline
OpenTTD Developer
OpenTTD Developer
User avatar

Joined: Sat Aug 16, 2003 12:55 pm
Posts: 768
Location: Bonn, Germany
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


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 10:47 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Fri Mar 26, 2004 1:27 am
Posts: 1628
Location: Netherlands, Enschede
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.

_________________
Creator of the Openttd Challenge Spinoff, Town Demand patch
The path to riches, a report on playing on a daylength server on ultra hard mode.


Top
   
 Post subject:
PostPosted: Thu Jun 03, 2004 11:09 pm 
Offline
Tycoon
Tycoon

Joined: Mon Mar 08, 2004 1:10 pm
Posts: 2088
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


Top
   
 Post subject:
PostPosted: Fri Jun 04, 2004 8:52 am 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Nov 25, 2002 4:30 pm
Posts: 1202
Location: Tiszavasvári, Hungary
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.


Top
   
 Post subject:
PostPosted: Sun Jun 13, 2004 9:04 pm 
Offline
Tycoon
Tycoon
User avatar

Joined: Mon Nov 25, 2002 4:30 pm
Posts: 1202
Location: Tiszavasvári, Hungary
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).


Top
   
 Post subject:
PostPosted: Mon Jun 14, 2004 1:00 pm 
Offline
Engineer
Engineer

Joined: Mon May 24, 2004 2:02 pm
Posts: 65
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


Top
   
 Post subject:
PostPosted: Wed Jun 16, 2004 8:02 pm 
Offline
Engineer
Engineer

Joined: Wed Jun 16, 2004 7:21 pm
Posts: 34
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:
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.


Top
   
 Post subject:
PostPosted: Thu Jun 17, 2004 7:51 am 
Offline
Engineer
Engineer

Joined: Mon May 24, 2004 2:02 pm
Posts: 65
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


Top
   
 Post subject:
PostPosted: Thu Jun 17, 2004 10:17 pm 
Offline
Engineer
Engineer

Joined: Wed Jun 16, 2004 7:21 pm
Posts: 34
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)


Top
   
 Post subject:
PostPosted: Fri Jun 18, 2004 1:16 pm 
Offline
OpenTTD Developer
OpenTTD Developer

Joined: Sun Apr 25, 2004 3:14 pm
Posts: 90
Location: Czech Republic
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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 38 posts ]  Go to page 1 2 Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000-2017 phpBB Limited

Copyright © Owen Rudge/The Transport Tycoon Forums 2001-2017.
Hosted by Zernebok Hosting.