Which would be more CPU efficient?

Questions & Answers
1

Hello everyone,

I’m trying to make a game which makes the floor based on tile info which can be read from a text file, so that it passes that data into a multidimensional array (which then will be built as the actual level floor).

I’ve thought of two ways of doing this, both seem fine, but I don’t know which would be most CPU efficient:

First of all, my first idea was to store the floor data into a three dimension array (I’m using c sharp so that is already implemented), so then, the first two dimensions would be the x and y coordinates of the floor, and with the third dimension, I would be able to store data such as: height, which kind of tile is, moving cost to get to that tile…
so the 5,12,1 of my map array would hold for example, the value of the tile located at the square 6,13 (the arrays start counting at zero), and then the third dimension, would hold for example, another value telling a type of data from that tile, the height from above the ground for example.

I was writing all that down, to organize myself in which to start working first, when an idea came into mind: Instead of using a 3d array, i could just use a 2d array, and instead of holding integer values, it could hold another kind of variable made by myseld (which i could create in a new class) which could hold all of the properties on that square, so they could have different variable types. So now, i could call the [3,2].height, instead of the [3,2,1] value for that square.

Now that I look at it, i see the second method better, but I was wondering, would that increase the CPU cost of my script? (I care about that because I’m already planning on a path finding system in that kind of tile-based maps, so the whole thing might be a lot CPU consuming, I have to optimize things as much as I can).

4

The class/struct should also give a “locality” speed-up. CPUs have a few Megs of high-speed and super high-speed (called L2/L1) “cache” (think of it as a file cabinet, your desk, and the page you are currently holding.)

With the class method, when you look up tile (3,7)'s gold, it’s like you grab the tile (3,7) sheet (which corrosponds to the class/struct.) You’ll probably look up the silver and brass next, which also is on the tile (3,7) sheet you’re holding, so great.

With the array method, you have a sheet for gold in tiles (3,0) through (3,100). For the silver look-up now, you have to put that down and look for the row-3 silver sheet.

Of course, if you really do scan all gold in a row, parallel arrays has the advantage. But, classes are so much easier to work with.

2

I would recommend you use the second method - it makes much more sense to store your information as a class held at the position in the array - especially if you decide you need even more information about that tile - which I bet you will over time and that information may be something apart from an int or a float.

For me I follow this paradigm:

  • Indices should be about addressability - how do I find something I want with reference to some logical construct (e.g. x & y coordinates in your case), then how do I navigate from one thing to its neighbour etc. Your 2d array works well for this.
  • Contents should be descriptive and extensible - a class is perfect for this it can hold named variables of multiple different types.

What will happen is that your memory footprint for the structure will change, rather than being some contiguous block you will end up with classes instantiated at different locations - but it shouldn’t hurt performance too much on execution.

There’s one further consideration you could make and that is about sparsity - if many of your locations would be empty then:

  • Not allocating a class for that location will save memory

If your array was very sparse then actually you could use a different structure from an array and just write a function to get the information at a location given x and y. You might use a dictionary for instance… But that’s a bit more advanced and not the right solution if most of your tiles are populated.

3

Using the second method won’t increase CPU cost. However, as Mike mentioned, it will change your memory footprint.
If you find that you’re running into performance issues with that data structure, try to use structs instead of classes.

The following link proposes the use of structs over classes when creating many instances that hold data because it saves memory. However a class is much more flexible.

Heres my tip: create an intercace ITile which consists of methods like “GetTileType”, “GetTileHeight”, etc, allowing you to access the data. Structs and classes can both implement interfaces, so you can decide later on which way you want to go.
Interfaces can also inherit, so you get the flexibility you might want, even if you use structs.