[RFD] Multi-Layer Rectangle based grid

[Steve]

Rather than hijack the nice /\ thread, i'll make a nice new one that we can discuss options in. All pictures i've posted elsewhere are attached again below.

The basic idea is there are different 'layers' of landscape, with different sizes of grids for different objects. In my pictures, the towns have a grid and the track/roads get a grid that is 4 times smaller. Whilst thinking about how our cities will look in-game, i'm not entirely sure this ratio is perfect. It could be that we shrink the town grid, to allow better building placement, allowing more compact cities, allowing more space on the map.

I also don't know where the landscape fits in. Shall it be roughly the same as city tiles? Or shall we make it bigger, so that we can store much bigger maps in memory?

Now, i made this thread, to help answer some of these questions. So we need input from engine designers, to know how small we can make the landscape grid and how big we can make the map. As well as idea people, to see how big in relation to each other, the grids need to be, to create an effective and exciting gaming experience.

Something i've just been thinking:
Can we cut down on memory needed for the maps by making bigger tiles when we need them? I'll explain: We have a nice big flat desert. Rather than knowing the individual height of all the points in that large area, can we just store one height, and all those tiles who use it?

[Zuu]

First, this topic should be pretended with [RFD], which stands for Request For Discussion.

Secondly I don't know much on memory usage of diffrent datatypes etc.

Thirdly, I think that two many diffrent grids can be confusing, so if we can keep the number of grids without consuming to much memory I think it would be good.

[uzurpator]

Having Snap-Points only on the tile edges and forcing the player to build track elements on a single tile would simplify the code.

[Steve]

Would it? I'm guessing not by much. Knowing where to track the track will be just as easy and such a system would still need collision detections, which wouldn't differ much from a more point system. But i'll point out i wouldn't know the exact details there.

[Hellfire]

Can we cut down on memory needed for the maps by making bigger tiles when we need them? I'll explain: We have a nice big flat desert. Rather than knowing the individual height of all the points in that large area, can we just store one height, and all those tiles who use it?

For this to be possible, we would need a hierarchy in the map. For the old code of TE (by Rein), I once suggested the use of super tiles. Super-tiles are a group of 16x16 tiles. Accessing the map is done through the super tiles.
Examples:

• If some rough data about the map is needed, then the info in the super tile will suffice.
• Rendering: the map is cut-off by super tiles, instead of by normal tiles.
• Rendering: OpenGL supports "precompiling" rendering data. This could be done per-supertile. This means that a supertile will only have to be recompiled if something changed on it.

The setting you suggest could be achieved by introducing new, simple super tiles which can store just one height, instead of 256 heights.

[Steve]

The only problem being, if you then change too many gradients, breaking all the super tiles, your computer would run out of memory and die?

[uzurpator]

Hellfire - display lists are _slow_ to compile. Even if they allow fast rendering - they are not really useful for something that may change really fast.

Take a look at the proto below. It uses vertex arrays compiled into display list.
-
+
zoom in/out
[
]
rotate

[Hellfire]

Hellfire - display lists are _slow_ to compile. Even if they allow fast rendering - they are not really useful for something that may change really fast.

So they are only useful for things that are static but have to be drawn a lot, like vehicles and objects.

What should I look for in the prototype?

[uzurpator]

zoom in/out to check the performance drop when recompiling the list.

BTW - once I have some time the proto will use vertex-buffer-objects - so it should get helluva quicker.

[Hyronymus]

Is it me or does + zoom out? Runs nice with rotating and zooming IMO.

[PJayTycy]

We are going way OT here.

Or maybe not...

The original question was : should we have different grids for different types of objects?

Now it has changed to a discussion about the surface-height datastructures. What some games do, is render all points close to the viewer, but for points further away, render the terrain with less detail (ie: only draw 1 corner-point for every 4*4 corner-points, then 1 for every 8*8, ...). This is mostly done to cut down the memory used by the gfx card to display the landscape, not to increase drawing speed.

Having Snap-Points only on the tile edges and forcing the player to build track elements on a single tile would simplify the code.

I don't really see the benefit in that. Why would this simplify the code? It only adds more validation-checking.

[uzurpator]

PJayTycy.

But lessens memory usage. With let us say - 16 snap points we have 240 possible combinations - so all trackage combos can be stored in a single byte - per element. With no restriction to single tile we need info on begin/end of the track and localisation (8 bytes at last, probably 16).

With 25 snap points spread evenly we need 600 elements - or two bytes.

[PJayTycy]

Yes, it would reduce memory if we store tracks like that (1 byte per section instead of 8 bytes). The disadvantage is we don't have acces to a track-tree to do pathfinding etc...

[Steve]

You presume A LOT about how we'd store the data. From my method we could use a starting position, then 2 more variables for tiles across, tiles down. If we limit that to 60 ish maximum per track (6 large tiles), that's 120 ish including negative values, 7 bits. x2.. and a bit more.

No idea where you get 16 bytes from!

[PJayTycy]

No idea where you get 16 bytes from!

start_X * 4 bytes
start_Y * 4 bytes
stop_X * 4 bytes
stop_Y * 4 bytes


In your example, you would store the start_X and start_Y, that's 8 bytes.
We can store the horizontal and vertical length in 1 byte each without any problems (-128...127). So, this would need 10 bytes total.

The point where uzurpators method apparently cuts down on memory usage, is the fact that we don't have to store some starting point, but just describe the track config on each cell. The problem is, we always have to store that info, for each cell, even if there is no track on it.

In uzurpator's method we will need to set a maximum on the number of tracks on one cell. Let's say we choose 5 (low estimate). So we would need 5 bytes memory for each cell (wheter there is track on it or not). On a 1024*1024 map, this would be 5 MiB.

In a method where you only store the tracks themselves, if we use 10 bytes per track, 5 MiB would be enough memory to store +/- 500 000 track elements. That's 1 element / 2 cells.

=> I don't think the memory usage is very different.

[SHADOW-XIII]

4 bytes for each coordinate ?
I think 2 bytes is enough (or even 1 wuld be good, however then we have to have 8 snappoints) ... the X,Y position of a titile and X,Y position of 'snap-point' in title are two diffirent things

[uzurpator]

PJayTycy.

Come to think of it - you are right. Storing tracks as seperate entity will save on memory. Also - with 4 byta positioning it is possible to use very fine track grid. Almost freeform grid...

[Hellfire]

Storing tracks as seperate entity will save on memory. Also - with 4 byta positioning it is possible to use very fine track grid. Almost freeform grid...

And even better: long straight pieces of track can be stored as one single record in the track data.

[Steve]

That's not always true. If you only leave so many bytes for length, a really long piece of track will need to be split up.

[PJayTycy]

That's not always true. If you only leave so many bytes for length, a really long piece of track will need to be split up.

True, but in the prototype I made, I set a max length of 20. Here we would have a max length of 128 * sqrt(2). There are a couply of reasons I put a max of 20 in the prototype:

=> If you lay a straight piece of track, maybe sometime later, you'll still want to create a junction in the middle of it. We would need to split up the existing track etc...
=> For signaling, we can use one section as blocked / not blocked unit (like the TTD tiles).
=> For the 3D part, if we design 1 3D model + texture for a track section, it only looks good if it isn't stretched very much (+/- 25% would be a max). We can add more models for shorter lengths ofcourse.
=> Such a section is always straight, also in the Z-direction. Having 1 piece of track spanning 10+ tiles that is completely straight without following the ground will look odd.


When I was talking about 4+4 bytes for snappoint positioning, that's for each snappoint on the map, not inside 1 cell. If we have 16*16 points in each cell, this would limit the max map size to +/- 268000000 * 268000000, which should certainly be enough.


Shadow, it's more memory-efficient if we store the X,Y position of the snappoint on the map instead of a X,Y position of a tile + X,Y position of the snappoint on the tile. And besides, it's not difficult to "find" the tile of the starting point, just divide the snappoint coords by the choosen value (5, 9, 16, ...).