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

DjArcas
Engineer
Engineer
Posts: 65
Joined: 24 May 2004 14:02
Contact:

Post by DjArcas »

pasky wrote: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 ;-).

yes Yes YES YES. Try and move away from the mode of coding that assembler games had to be 10 years ago, and move towards a much more readable, flexible methodology. Especially for new things :)
The largest multiplayer games in the world - ever.
http://www.projectorgames.net
Vurlix
OpenTTD Developer
OpenTTD Developer
Posts: 122
Joined: 07 Mar 2004 01:54

Post by Vurlix »

Implementation of the new map data format is going well. And no, i'm not using linked lists -- those would make the game unplayably slow. I'm using bit structs, which are equally flexible and do not sacrifice any speed.
http://sf.net/projects/openttd/
Post all your patches and feature requests here.
msalters
Engineer
Engineer
Posts: 34
Joined: 16 Jun 2004 19:21

Post by msalters »

Vurlix wrote:Implementation of the new map data format is going well. And no, i'm not using linked lists -- those would make the game unplayably slow. I'm using bit structs, which are equally flexible and do not sacrifice any speed.
Actually, bitstructs are pretty horrible nowadays. Modern CPUs don't like the bitshifting; with caches and high-bandwith buses it's better to use a few more bits. What you certainly shouldn't do is mix unrelated data, that causes cache poisoning. That's the effect of stuffing your cache with unneeded bits. E.g. if you've got two 256x256 arrays of 4 bits, it's better to store them as two 32K byte arrays with two elements per byte then one 64K array of one-byte structs. In the first case, it would fit in a Celeron's L1 data cache.

Of course, the best action in early development is to just ignore the bitfields. If something is too slow, retry it with bitfields enabled and hope it doesn't slow even more. You just don't know anymore.
User avatar
Celestar
Director
Director
Posts: 574
Joined: 02 Jul 2004 10:56
Contact:

Post by Celestar »

I agree with you about that performance issue, in fact most integer operations are fastest on word-sized stuff, however there's the problem of memory usage and especially bandwidth usage in multiplayer. Every time a new player joins the game, the entire map needs to be transmitted. Now what happens if they're playing via 56k? They'd be waiting like 30 minutes for the game to begin if we put anything in int32s. There needs to be some balance

Celestar
User avatar
lucaspiller
Tycoon
Tycoon
Posts: 1228
Joined: 18 Apr 2004 20:27

Post by lucaspiller »

I was thinking the same thing. The maps are big enough as it is for multiplayer but just wait until it is the year 2046 on a 1024x1024 map and a 56k player joins. Maybe in a later version certain things could be left out and maybe disabled. Trees must take up quite a bit of space so what if they were disabled? Another thing could be the different road types, they don't affect gameplay so why not just stick with the basic ones. Also maybe instead of marking each tile, tiles that are the same (e.g. big flat areas) are all marked together. Hmmm, how about if when you have a multiplayer game there are certain maps you have to choose from and teraforming is disabled - that should save quite a bit of bandwidth shouldn't it.

Anyway those are my thoughts about it, in reality they would probably be more trouble than they are worth though.
msalters
Engineer
Engineer
Posts: 34
Joined: 16 Jun 2004 19:21

Post by msalters »

Celestar wrote:I agree with you about that performance issue, in fact most integer operations are fastest on word-sized stuff, however there's the problem of memory usage and especially bandwidth usage in multiplayer. Every time a new player joins the game, the entire map needs to be transmitted. Now what happens if they're playing via 56k? They'd be waiting like 30 minutes for the game to begin if we put anything in int32s.
We already link in a zlib compression library. If you compress stuff, the overhead of int32s is minimal if not negative. Most lossless compression algorithms work by replacing fixed-length structures like int16 or int32 by variable-length bitstrings, where the highest-frequency values get the shortest strings.
Remember, CPUs are high-bandwidth so it's better to use a few more bits and avoid costly shifting. WAN connections, even ADSL, are in comparison low-bandwidth. There it's better to use compressed formats. Packed-bit representations are an attempt at manual compression, identical for every tile whether it holds a house, rail or bridge. zlib uses variable-length strings and is thus more efficient, besides being automatic.
User avatar
Wolf01
Tycoon
Tycoon
Posts: 2016
Joined: 24 Apr 2004 10:43
Location: Venezia - Italia
Contact:

Post by Wolf01 »

how proceed the work for the landscape array?
}T{Reme [Q_G]
Route Supervisor
Route Supervisor
Posts: 389
Joined: 04 Feb 2004 23:24
Contact:

Post by }T{Reme [Q_G] »

Well.. I guess this is a nice idea... It's a combination of linked lists and struct arrays... it's a work in progress and can be much more optimized and more features added and other things.. but works for what I need it to do, and pretty fast too. The basic idea is to have a linked list of an array of pointers to what you need to store.... default is 64 but can be changed. Every piece is accessible with just pop(data) returning an index and push(index) returning a pointer. As for networking you can send the client a chunk at a time, thus slowly letting it load the map while playing. (current visible portion first). As for what to stuff in the array... that's up to you :)
Attachments
dill.zip
(1.57 KiB) Downloaded 250 times
Siggy not gonna work unless someone allows javascripting...
nilsi
Transport Coordinator
Transport Coordinator
Posts: 268
Joined: 20 Nov 2002 16:20
Location: Dresden, Germany

Post by nilsi »

I see some things a little bit different here.
In my opinion saving memory is much more important than
avoiding some bit shift operations.
On modern x86 hardware the memory access is the bottleneck,
certainly not a few processor cycles.
Processor speed grows much faster than
memory access speed.
Torrasque
Engineer
Engineer
Posts: 94
Joined: 19 Aug 2004 13:33
Contact:

Post by Torrasque »

nilsi: I think this is an old topic, the new map array is already fixed.
You can find some info there : http://wiki.openttd.org/index.php/MapRewriteDesign
User avatar
Wolf01
Tycoon
Tycoon
Posts: 2016
Joined: 24 Apr 2004 10:43
Location: Venezia - Italia
Contact:

Post by Wolf01 »

uhmmm, i think that the release of 0.4.0 is close... or maybe 0.3.5 with the new landscape array...

Good work Celestar and Matthijs!
User avatar
Magic_Pixel
Engineer
Engineer
Posts: 80
Joined: 29 Jul 2004 07:56
Location: Tulcea/Bucharest, Romania
Contact:

Post by Magic_Pixel »

You can see the actual progress of the new_map implementation here: http://wiki.openttd.org/index.php/MapRewriteProgress
...maintainer of Romanian OpenTTD translation...
User avatar
Darkvater
Tycoon
Tycoon
Posts: 3053
Joined: 24 Feb 2003 18:45
Location: Hong Kong

Post by Darkvater »

Wolf01 wrote:uhmmm, i think that the release of 0.4.0 is close... or maybe 0.3.5 with the new landscape array...

Good work Celestar and Matthijs!
I say, what about the others? :roll:
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
Wolf01
Tycoon
Tycoon
Posts: 2016
Joined: 24 Apr 2004 10:43
Location: Venezia - Italia
Contact:

Post by Wolf01 »

Darkvater wrote:
Wolf01 wrote:uhmmm, i think that the release of 0.4.0 is close... or maybe 0.3.5 with the new landscape array...

Good work Celestar and Matthijs!
I say, what about the others? :roll:
Yes, also you and Tron, Celestar and Matthijs have done more patches, but also your work is useful

so, good work to who is working to the new map array, i'm waiting impatient!
matthijs
Engineer
Engineer
Posts: 76
Joined: 25 Jun 2004 15:20
Location: Enschede, Netherlands
Contact:

Post by matthijs »

Wolf01 wrote: Yes, also you and Tron, Celestar and Matthijs have done more patches, but also your work is useful
I am thankful for your kind words, but you are giving me too much credit ;-) I haven't done any real big patches yet, just some smaller stuff until now. Though I have been working on the new map design a lot (mainly arguing with Tron and Darkvater ;-p), there are "Bigger" devs than me.

So, I will gladly pass on the thanks to those who deserve it a little more :-)
Also, I will add my own thanks, not so much for the new features you guys introduced as well as for the nice people you are and for how good it is to work together :-)

Matthijs
User avatar
Celestar
Director
Director
Posts: 574
Joined: 02 Jul 2004 10:56
Contact:

Post by Celestar »

Currently working on the map array: (alphabetical order :))

blathijs (matthijs)
celestar
darkvater
tron

Currently working on the new network:

dominik81
Truelight

and octo_ is working on the newgrf implementation

We could use more manpower :wink:

Celestar
User avatar
bociusz
Traffic Manager
Traffic Manager
Posts: 131
Joined: 24 Jul 2004 11:04
Location: Hungary
Contact:

Bug

Post by bociusz »

Celestar!

You made a little mistake SVN/branch/map/tunnelbridge_cmd.c (r458)
On line 921 you wrote "brdge_land.h" instead of "bridge_land.h"

If you can't see it click here:
http://svn.openttd.com/cgi/viewcvs.cgi/ ... idge_cmd.c
You'll see it in the green line.
User avatar
Celestar
Director
Director
Posts: 574
Joined: 02 Jul 2004 10:56
Contact:

Post by Celestar »

Whoops yeah. thanks.

Celestar
Post Reply

Return to “OpenTTD Development”

Who is online

Users browsing this forum: No registered users and 9 guests