Best practice for level storage?

[Smoking_mirror]

In the past I’ve used 2d arrays (a list of (lists of (lists))) for creating level maps for games. And in sparse arrays, where much of the game level is empty I’ve used dictionaries.

Now dictionaries have many advantages, being able to access them easily, using get() etc…
But I’m sure that there are more efficient i.e. quicker methods for storing that data.

The data I want to store for each tile of my map is terrain type (1-16 values) and height (0 to 8 values).

I also need to process those values when displaying the level (get neighbors and choose the correct tile from a tile set.) My tile sets have 16 possible variations (0000, 0001, 0011, 0111 etc…)

kind of like this:

So I wonder if it might be more efficient to just process them when generating the level and save the variations as a hexadecimal value in the array and read it directly when loading the level, rather than processing the tile values to get the variation needed by the tile set.

My question is:
Does python have any good tools for dealing with arrays of hex numbers? Will this improve performance vs just saving the terrain types and height values as a tuple in a dictionary?

[Monster]

This is less a “level” aspect. What you want is an sufficient way to handle your terrain.

I can’t tell you a best practice, but some thoughts that might help you.

First of all you should know what your model should look like (a 3D mesh is a special form of a model - in most cases just part of a game model). As far as I understand you want to model your terrain somehow.

What is a terrain?
From your description I guess you want to cover a large area with a mesh. I will exclude any assets on top of the terrain. That would be too much for now.

What are you going to do with the terrain?
I guess you want to show it … at least parts of it
You might want to move around on top of the terrain … at least a part
You might want to change the terrain e.g. dig a hole, form a hill. Maybe not.

What is the most time critical operation?
showing and moving. This will constantly happen.

So these operations have to be really fast.

Creating the terrain at each frame is slow. So we should create it once and leave it until we need to change it.
A good way is to create one or more 3D meshes and let the BGE perform visualization and physics.

So we have another not-so-often performed operation: create a 3D terrain object.

How to create a 3D terrain object?
As we can’t generate new meshes, we can use an existing mesh and manipulate it’s vertices. This is not very fast. But what is the bottleneck?

A) large number of vertices. So reducing the number of vertices would speed up the process
B) calculating the attributes of a vertex

I think this is what you are referring to with your thread.

B) should be very fast as it will performed for each single vertex (A).

So you are right with your list and dictionary idea. But why?
The reason is that both objects allow a very fast access by key. Lists expect an ordinal number and dictionaries any unique key.
If you have the key the access to the data is very fast.

But terrain causes some problems:
A) it is huge … so you need quite a lot of keys
B) you do not need all keys at the same time, just the keys for the model under operation
C) there are gaps between the keys which might require new keys in-between (e.g. your grid is 1m x 1m, but you look at an ant)

Lists and dictionaries have another problem:
D) you need to know the data beforehand the be placed in that data-structure.

I guess all of that is known to you. Otherwise you would not ask.

But there are some tricks you could work with:

• split your model into smaller more efficient parts. Organize terrain parts in an hierarchy. Rough terrain information at the root, fine details at the leaves. This allows you to fill the gaps between the grid cells, but you still focus on a specific region.
• use fast generation algorithms to create a base model (on-the-fly data) by given indices (like the list/dict access).
• store only differences to the generated on-the-fly data, this reduces the amount of data a lot (but also the flexibility).

Such things would allow you to model planet-size terrain in cm-granularity as you do not need to keep every cm² in you database. It also allows you to see terrain from a distance (e.g. plane, spaceship). From that distance you do not need the high density and you can present a low resolution terrain (only process what you can see - approach).

I remember some threads regarding fast real-time generation: perlin-noise (input is a coordinate … it gives you the high).
Due to the possible amount of “moderated data” you might think of an fast way to access the data you need. e.g. organizing in a tree structure. It is not so fast as indexed data, but O(log(n)) is very fast.

Just some ideas.

[Mobious]

If your maps are fairly large, I would recommend using NumPy arrays to handle them while in memory. They should be both faster and more memory efficient than using regular lists.

As for the tile data, you can fit each tile in one byte with room to spare (16 types * 9 height values = 144 <= 256). I would just use regular Python integers for this as you easily do bit-wise operations on them. Here are a couple example functions you might use:

def get_tile_type(intValue):
    # tile type is stored in the first 4 bits
     return intValue & 0x0F

def get_tile_height(intValue):
    # tile height is stored in the last 4 bits
     return intValue >> 4

For the tile variations, it really depends if you want to trade a lot of memory for a small performance gain. If you chose to store the tile variations, you’ll end up having to use 2 bytes per tile, double what you were using before (16 type * 9 height values * 16 variations = 2404 > 256). The performance gain is that you won’t have to calculate the tile variation by looking at the 4 adjacent tiles. If you need to do this very frequently during gameplay it might be worth it. Otherwise I wouldn’t bother.

When saving maps to disk, you should obviously just write the raw binary to save space. The Struct module is useful for this.

[Smoking_mirror]

@ Monster
Thanks for the long reply. There’s some good stuff in there.

@ Mobius
Thanks also, that’s exactly the kind of thing I was looking for.
I think I need to check out bitwise operators…

[sdfgeoff]

Premature optimization is the root of all evil.

[Mobious]

“Premature” is the key word. If you can clearly see the direction you’re currently going in is going to cause problems in the future, you absolute should start making improvements sooner rather than later. It’s much easier to write good code the first time than it is to write bad code and then completely refactor it later.

It’s also important to make the distinction between optimization and simply writing good code. I don’t know what Smoking_mirror is working on, but to me it sounds like he’s just trying to figure out the best way to code his project, not that he already has functioning code that he wants to make more efficient. Unless you’re making a simple prototype, taking the time to plan out how your code should function and be structured and then implementing it efficiently is absolutely worth it in my experience.

[BluePrintRandom]

“Premature” is the key word. If you can clearly see the direction you’re currently going in is going to cause problems in the future, you absolute should start making improvements sooner rather than later. It’s much easier to write good code the first time than it is to write bad code and then completely refactor it later.

It’s also important to make the distinction between optimization and simply writing good code. I don’t know what Smoking_mirror is working on, but to me it sounds like he’s just trying to figure out the best way to code his project, not that he already has functioning code that he wants to make more efficient. Unless you’re making a simple prototype, taking the time to plan out how your code should function and be structured and then implementing it efficiently is absolutely worth it in my experience.

yeah, otherwise…

[Monster]

This is not a pre-optimization.

It is an investigation to find a sufficient architecture that fulfills certain requirements. This means first you nee to find the right requirements, which is not that easy. Th danger is when they change later on and the architecture does not fit or even counters them. That is the evil.

the idea to skip “optimization” is to define the needed operations with a naive implementation with the goal to exchange it later with a better fitting one. This is a good strategy as it creates a working prototype first and “improve it later”. On the other side it always requires a later change. I’m not sure if that really works on larger projects. The restructuring work increases really much (see Blender). If you choose a good architecture for your prototype you might get less work later on (if it is a bad choice it will be more work).

[Raiderium]

If I understand it correctly, you have tiles of ground that connect to each other in different ways. However, the map data is unaware of this connectivity, instead simply specifying where ground is and isn’t (or something similar), and an algorithm is necessary to select the right tile to use. And your question is, “should the map data include the results of that algorithm to speed up loading”.

Is that roughly correct?

Well, personally, I’d stick with what you’ve got. Most tile-based games involve some form of neighbour-checking algorithm, and it helps to be able to dynamically update the tiles, for instance to add a random map feature. Aside from that, storing the precise tile numbers would inflate map file size, and it’s unlikely that you’ll gain any meaningful performance, unless your hard drive is significantly faster at sequential reads than your CPU is at executing a small Python function.

This is humorous, because with Python, it might be.

In Python, your reasoning should always begin and end with convenience, not performance. Python does not value performance. The entire language is designed to sacrifice performance in the name of convenience, and then work backwards from there to salvage whatever performance it can. So should you, if you wish to get the full benefit of working with it.

However, when it does come time to optimise, the typical way to lose performance is to forget basic facts of computer science. For instance, appending to a list becomes more and more costly as the list grows, a problem that can obliterate any algorithm’s performance with ease, yet people I know frequently forget to account for it. (People like meee.) Mobious suggested NumPy; I will second that. NumPy numeric arrays are less convenient, but in exchange they’re much, much faster. You’ll get a massive speed boost from it. It’s like upgrading to an SSD from a hard disk.

The typical way to waste time while optimising is to treat Python like a low-level language, and start unrolling loops, creating register-like variables in the hopes that the interpreter will optimise accesses to them, modifying algorithms to be cache-friendly, or use bitwise operations. All of these are so much chaff before the wind.

But let’s put all that aside and consider this darling little calculation:

Let x be the execution time saved by optimising an inner loop in Python.
Let y be the execution time lost to Python’s fantasmagorical overhead.
Let w be how much you care about performance, from 0 (don’t care) to 1 (care immensely).
Let z be how much you care about sticking with Python, from 0 (don’t care) to 1 (care immensely).

If w > z, switch to a different language immediately, or reduce w. The other variables don’t actually matter, they’re just there to add flavour.

[Monster]

For instance, appending to a list becomes more and more costly as the list grows

While it strongly depends on the implementation.

Adding to list is typically not costly. A cost intensive operation is inserting into a list (position base index).
But there are list implementation that can have efficient inserting (e.g. linked lists). Typically it comes with additional costs at other place.

I fully agree that Python is not designed for speed efficiency. This is no big deal. In common projects the most costs are result of inefficient design. You will much more benefit from understandable code than fast, but cryptic code (that might not even do hat you need).

[Smoking_mirror]

Thanks guys, It’s not so much that I want to optimize, but that I want to use the best tools for the job.

For the landscape I’m using blocks which are offset from the center (the center of the tile is bottom left or each one). Each block has a physical mesh, and UV which can be moved to create alignments of texture on the physical mesh. I’m using nodes and object color to do the UV scroll rather than actually messing with UV scrolling.

The physical mesh looks like this:

While the texture mask looks like this:

By comparing 3 neighbors to the center tile you can get which tile to use.
Thanks to Blender Artist Nines for reminding me about this, as it’s something I had read but forgotten about.

First I check the square to the right, (1,0) offset from the current square. If it is valid (contains a color or height or feature or whatever) I add one to the base number. Next is the square to the top right (1,1) which will add 2, next the square immediately above the one I’m working on (0,1) which will add 4 to the score, and finally the home square (0,0) which will add 8. Because of the way binary numbers work, these 4 values will add up to a number between 0 and 15. So I just name my tiles “tile_0” to “tile_15”. Saving this data would be as simple as saving an integer.

for x in range(-1,mapsize):
    for y in range(-1,mapsize):
        main_tile = level_dict.get((x,y),[0,0])
                                                  
        search_array = [(1,0,1),(1,1,2),(0,1,4),(0,0,8)]
        
        tile_number = 0
        
        for n in search_array:    
            key = (x+n[0],y+n[1])
            tile = level_dict.get(key,0)
                                
            if tile ==1:                        
                tile_number += n[2]
                              
        tile_name = "tile_{}".format(tile_number)
                                                        
        tile_object = own.scene.addObject(tile_name,own,0)
        tile_object.worldPosition = [x,y,0.0]

And that’s pretty much the whole of the code for building the map, at least height wise. There is more to it when I start working with the textures too.

But you can see above I’m getting the info (tile) from a dictionary (level_dict). This is fine if I only need it for the level building data, but the game is going to be a grid based, turn based strategy. I’ll also be using the level data as the graph for an A* search algorithm, line of sight calculations, AI strategy maps and much more. If I can use an efficient method of storing/handling that data it will help with all those functions. For instance it may be better to have multiple arrays, each storing one type of data rather than a single array/dictionary with data about pass-ability, height, occupied, damaged, high priority etc… since only one will be used by a particular function at a time.

I know any code written in Python is never going to be as fast as it could be in another language, but making the right choices in python can often result in a function which is twice as fast as it would be otherwise.

I don’t think I am going to save the connectivity data though, since the way the tiles connect visually is different from how they connect for movement or sight calculations.

EDIT:
Here’s a blendfor anyone who is interested.
It’s still just a prototype, so lots of work to do yet, such as making sure there’s only a single physical mesh for each tile and making the base texture non-transparent.

[sdfgeoff]

With your sixteen tiles, be aware there are actually far fewer: only 5 - and some rotations. If you look at CaveFly, you’ll see the first thing I do is build up a dictionary of tiles based on their shape and a rotation. This means I need to manage far fewer actual objects and their textures (I have their textures based on the global co-ordinates so that solves some problems as well to do with alignment.

As for storing the map, you need to figure out what data you need to get from it. You need things like:

• What sort of tile at each node
• Sitelines
• Movement mesh

The easiest to work with in most cases is a simple binary one ignoring all actual elevations:

1 1 1 1 1 1 1 
1 0 0 1 1 0 1
1 0 0 0 0 0 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1

This is what I used for cavefly.
Then to place the pieces, you look at groups of four, offset slightly.
All easy. You conly do that once, so you don’t need to worry about speed there.

Now, sitelines and navmesh. We need to acces that lots of times and it needs to be fast. Using the bitmap we have may be innefficient. For instance with pathfinding: If you have large open spaces, you should be able to combine them.
What we need to do is to conver this into … a mesh representation. Our 10-empty space map (ie 10 node navmesh) can be simplified to just three in a ‘C’ shape. We do this only once at load time, so we don’t have to worry too much about our meshing speed.
Then our meshing is faster.

So how can we store this mesh?
Simple, create a class, for example:

class node
    def __init__(self, x, y):
        self.nodes = list() #in format (node, distance)
        self.x = x
        self.y = y
    def addLink(self, n)
        self.nodes.append([n, self.getDistanceTo(n)])
    def getDistanceTo(self, n, order=2):
        if (order == 1):
            return abs(self.x - n.x) + abs(self.y - n.y)
        elif (order == 2):
            return sqrt((self.x - n.x)**2 + (self.y - n.y)**2)

With this simplified mesh we can (in theory) do our pathfinding nice and fast, we even have the distance to adjacent nodes without having to do any computation.

Can we optimize our sitelines? To be honest, I have no idea about how to calculate this from a mesh like we have generated here. It’s easy enough with the bitmap, but is there a better way? Sorry, I’m not sure.
The trick is to figure out what data you can generate and store easily at load time, and in what format it should be in for it to be useful.

Maybe that’s given you some ideas.