The International Simutrans Forum

 

Author Topic: Map optimisation  (Read 2826 times)

0 Members and 1 Guest are viewing this topic.

Offline Ashley

  • Coder/Patcher
  • Devotee
  • *
  • Posts: 1288
    • entropy.me.uk
Map optimisation
« on: February 08, 2012, 07:49:37 PM »
How many bytes are needed to store an empty planquadrat_t object in memory? I am toying with the idea of replacing the 2D array which represents the world with a Quadtree representation, which is sparse and could thus save significantly on memory footprint (especially for maps without trees). Any map tile which does not contain an object or an artificial slope could thus be found without needing to specifically represent it in the world array. The height could be looked up using the same algorithm used to generate the map in the first place.

Only tiles containing specific objects, e.g. roads, buildings etc. would actually need a real planquadrat_t object, empty tiles would be generated on-the-fly via the access methods using derived data.

This could save quite some memory for large maps, which would benefit network games both in terms of memory footprint and data transfer.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4564
  • Languages: EN, DE, AT
Re: Map optimisation
« Reply #1 on: February 08, 2012, 08:36:41 PM »
Try starting simutrans with  '-debug 3 -sizes'. It should print some information about size of structures to the terminal:
Code: [Select]
Message: sizes: koord: 4
Message: sizes: koord3d: 5
Message: sizes: ribi_t::ribi: 1
Message: sizes: halthandle_t: 2

Message: sizes: ding_t: 16
Message: sizes: gebaeude_t: 48
Message: sizes: baum_t: 24
Message: sizes: weg_t: 40
Message: sizes: stadtauto_t: 88

Message: sizes: grund_t: 32
Message: sizes: boden_t: 32
Message: sizes: wasser_t: 32
Message: sizes: planquadrat_t: 24

Message: sizes: ware_t: 12
Message: sizes: vehikel_t: 120
Message: sizes: haltestelle_t: 960

Message: sizes: karte_t: 6936
Message: sizes: spieler_t: 4096
This is for a 32bit executable, for a 64bit executable the sizes are much bigger.

The size of one tile is at least one planquadrat_t + one grund_t = 56 bytes.

About your quadtree idea: what about ships crossing (otherwise empty) sea or airplanes flying over empty plains? Then the structure must be updated very often to store the vehicles there.

I tried some time ago a different approach: do not use virtual methods in grund_t classes (-3bytes), store the ground 'kartenboden' directly in planquadrat (-4bytes).

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9438
  • Languages: De,EN,JP
Re: Map optimisation
« Reply #2 on: February 08, 2012, 09:57:36 PM »
If the ground in planquadrat_t is never br├╝ckenboden_t, tunnelboden_t or fundament_t then one could incoporate the ground there. Also an extra case for kartenboden as part of planquadrat_t would probabaly require to derive boden_t from both planquadrat_t and grund_t, not a very nice construction.
 
Those sizes are specific for 32 Intel; x64 uses considerably more, since it pack and aligns data differently (around the then 8 byte pointers). ARM also gives different numbers, as two byte integer must be aligned on even address. The virtual functions do save some bytes; if those were not there, then one would need to save the way slope at least, which would increase the structure to the next 4 byte size, i.e. 38 bytes. (Why were the virtual function pointer 3 bytes ??? )
 
About sparse maps: This may save a little memory. But not much, since any tile with a tree or a special slope needs a ground. Also memory is not as much of a concern as time routefinding, which would be very expensive with sparse map compared to looking up tiles in a linear array. And even a 4096*4096 map require "only" 896 MB for the map, in contrast to about 1,1 GB required for trees ...

I think not saving empty ground may help to reduce savegame size (and thus transfer times for network games.) But in memory I thin the cons will outweight the pros.

Offline Spike

  • *
  • Posts: 1361
  • First Simutrans Developer and Graphics Artist
Re: Map optimisation
« Reply #3 on: February 08, 2012, 10:06:16 PM »
Is this good: koord3d: 5 ?
I wonder a bit, but there might be good reasons behind it. I just want to know what they are :)

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9438
  • Languages: De,EN,JP
Re: Map optimisation
« Reply #4 on: February 08, 2012, 10:31:17 PM »
Becuse by this I could reduce ding_t to 16 and grund_t to 24 bytes. Before those were 4 bytes larger. There are very few structures that only use koord3d without any other information.

Offline Spike

  • *
  • Posts: 1361
  • First Simutrans Developer and Graphics Artist
Re: Map optimisation
« Reply #5 on: February 08, 2012, 10:39:44 PM »
Why are my Simutrans Iron Bite ding_t 12 and my grund_t 20 bytes  :o
I'd say it's the compiler but who knows that magic ....

Code: [Select]
Message: sizes:    koord: 4
Message: sizes:    koord3d: 5
Message: sizes:    ribi_t::ribi: 1
Message: sizes:    halthandle_t: 2

Message: sizes:    ding_t: 12
Message: sizes:    gebaeude_t: 32
Message: sizes:    baum_t: 16
Message: sizes:    weg_t: 32
Message: sizes:    stadtauto_t: 68

Message: sizes:    grund_t: 20
Message: sizes:    boden_t: 20
Message: sizes:    wasser_t: 24
Message: sizes:    planquadrat_t: 12

Message: sizes:    freight_t: 12
Message: sizes:    vehikel_t: 88
Message: sizes:    haltestelle_t: 888

Message: sizes:    karte_t: 6320
Message: sizes:    spieler_t: 4040

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9438
  • Languages: De,EN,JP
Re: Map optimisation
« Reply #6 on: February 08, 2012, 11:25:53 PM »
ding has a minimum size of 8 bytes (koord3d 5, plus 2 bytes and two nibbles) It also needs a virtual function table (4 bytes)

grund_t should have 16 bytes (dingliste_t 6, koord3d 5, flag 1, image_id 2, another two bytes) and a virtual function pointer (4 bytes).

But in MSVC the sizes are larger in debug mode. This is the sizes Dwachs reported. Your numbers come from MinGW.

Thus the 4069^2 world only consumes 512 MB and the trees only 768 MB with optimized builds.

EDIT: Now I remember. MSVC could not use standard library with more closer packed structures.
« Last Edit: February 08, 2012, 11:49:16 PM by prissi »

Offline Ashley

  • Coder/Patcher
  • Devotee
  • *
  • Posts: 1288
    • entropy.me.uk
Re: Map optimisation
« Reply #7 on: February 09, 2012, 12:02:31 AM »
I hadn't considered the implications for route-finding, or that vehicles are stored in the structure of the world ground array. I think route-finding may be capable of optimisation in the general case using quadtrees but I'd have to look into that (may be an interesting project in and of itself, I am studying data structures on my university course at the moment).

Could the issue of trees be solved using some kind of deterministic procedural generation? E.g. individual tree locations are not stored, rather parameters which determine tree generation are stored which ensure the same pattern is generated dynamically when querying a certain grid square? The same level-of-detail approach employed in representing the map as a quadtree could be applied to storing information about trees too, since large forests require less detail than individual/lone trees do (in the same way that large tracts of flat land require less information than e.g. heavily terraformed terrain.

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotees (Inactive)
  • *
  • Posts: 1559
  • Languages: EN,ES,CAT
Re: Map optimisation
« Reply #8 on: February 09, 2012, 01:18:20 AM »

 I've been thinking about those trees too in the past, specially since for Simutrans3D I'd like to remove the individual tree concept, because it adds too much items in the map (maybe individual trees can still be allowed, but forests won't be implemented that way). your level of detail approach suits perfectly on that, and it whould be great to implement it, since it whould boos simutrans 2D performance too.

 Also, a LOD for cities can be created too, you don't need lots of detail on a city on the max zoom level, but I might be wrong here. Maybe also zoomed out views should just display "snapshots", with a approximate static layout of the city.
 
 Terrain will be managed as a octree in simutrans3D, but just at the 3D vertex structure level. At the game engine level, I don't know if it's a good idea, as prissi points out. The currrent array allows for constant time access to any tile of the map, and many algorithms lookup it, I guess (don't know those parts of the game, really).
« Last Edit: February 09, 2012, 01:56:10 AM by Markohs »

Offline Spike

  • *
  • Posts: 1361
  • First Simutrans Developer and Graphics Artist
Re: Map optimisation
« Reply #9 on: February 09, 2012, 09:46:53 AM »
Save the trees!

I know, Germans are crazy treehuggers, but the trees always have been something special to me. They were simulated life in an otherwise quite plain and technical world. I don't know the current state of the code, but the trees have been real simualted life which is born, bears offspring, and some day dies.

It made me sad to see the option added to have no trees on a map by default, and it makes me sad to degrade the trees to purely decoration, simplified to a few billboard graphics  :-[

In my home town there is a movement going to preserve trees which are about to be taken taken down by the DB AG to make building a new central train station easier. To understand this you need to know that these trees survived two world wars, and that people who were freezing in cold winter did not touch htese trees because they felt them to be important, more important than sitting in a damaged home and freeze. And now DB AG wants to kill those trees almost without a real need - trees which have seen 6 generations of citizens grow up and die, which survived one revolution and two world wars ...

If you can read German or want to try google translate, here is a link for starters:

http://www.bei-abriss-aufstand.de/

I _strongly_ will try to hinder all movements to kill the trees in Simutrans. The "no trees" option was made when I was away, and couldn't do anything about it, but now I'm here and I will.
« Last Edit: February 09, 2012, 10:30:52 AM by Memzeron »

Offline Markohs

  • DevTeam, Coder/patcher
  • Devotees (Inactive)
  • *
  • Posts: 1559
  • Languages: EN,ES,CAT
Re: Map optimisation
« Reply #10 on: February 09, 2012, 10:01:23 AM »
Noone wants to remove the trees, only optimizing the way they are stored and displayed. :)

The idea is imo, just storing the information about "forests". Their location, approximate density and shape, and just not storing/displaying them one by one, but in a group fashion, so they can be displayed in one pass, and don't use so much memory. :)

But of course, maybe a option to plant a single tree can be allowed, but as a exception.

Offline Isaac.Eiland-Hall us

  • Benevolent Dictator
  • Administrator
  • *
  • Posts: 3645
  • PanamaCityPC.com/support/
    • Facebook Profile
  • Languages: EN
Re: Map optimisation
« Reply #11 on: February 09, 2012, 10:27:57 AM »
Question that may alleviate some concern: If the trees are *displayed* in an optimized fashion, would they still grow/spread/die organically in the same way? If so, perhaps it's not so bad. :)

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9438
  • Languages: De,EN,JP
Re: Map optimisation
« Reply #12 on: February 09, 2012, 02:57:18 PM »
The problem with storing forest is, that tree are cutted during waybuilding and trees can spawn. Thus this is not simple.

In networksgames, trees are saved without their positions inside the tile, to save lot of size during transfer (The "no tree" option was more to allow manual adding forest later, to get more manageable maps for networkgames.)

An idea was a "forest_t" object, to have one one object on a tile, even with multiple trees. This could save a little memory (and even time) during season change and would require less memory. But it would require display in dig to be virtual, what would make it slower.

But Simutrans is tied around the idea that everything is on a tile. Thus introducing global objects might be clever for 3D but is defying the relatively strict objects of simutrans.

Offline wlindley us

  • Devotee
  • *
  • Posts: 960
    • Hacking for fun and profit since 1977
  • Languages: EN, DE
Re: Map optimisation
« Reply #13 on: February 09, 2012, 03:17:36 PM »


How about coding a Forest as an industry with many fields, and zero or very low production of Wood?

Offline isidoro

  • Devotee
  • *
  • Posts: 1128
Re: Map optimisation
« Reply #14 on: February 09, 2012, 10:41:11 PM »
Save the trees!
[...]
In my home town there is a movement going to preserve trees which are about to be taken taken down by the DB AG to make building a new central train station easier.
[...]

We're living bad times...  We, the People, are being asked to do a lot of things and sacrifices to save the world, our world.  The question is if life is deserved to be lived in the world they want us to save...

It is time to peacefully, but firmly, just say no...