3D playing field in C++

user_10873199 0
Viewed 154

Im very new to C++ and I'm having a hard time creating a 3D playing board. Size of the board can increase throughout the course of the game.

My first idea was to use nested vectors. vector<vector<vector<int>>> board

Idea was, that it would be easily accesible (board[z][y][x]) and I wouldnt have problems with dynamic allocation. However I heard that it's not a good idea to nest vectors, because it breaks "cache friendliness". Instead, I should use 1d vector and "fake" dimension using math.

I think this means to create vector of size (x * y * z). In that case, when I want to "go" to nested_vector_board[0][1][0] I use board[x]. In case I want to go to nested_vector_board[1][1][0], I use board[x * y + x].

Is my understanding correct? What should I do in case of resizing of the board? For example, if I want to make the board wider, it seems I need to manually shift all the data. Even more importantly, is there a better, simpler way to do it?

I will welcome any advice and thank you very much in advance!

vector memory-management c++
3 Answers

If you don't know what your access pattern will be you can not choose an optimal solution. In addition if you have no working solution you can not measure your performance and can only guess what will be the best solution and you will probably guess wrong.

I suggest to implemnt your own 3D Board class with a clear interface and check if your trivial solution is good enough. If it is too slow you can swap the implementation for a better suited one.

Here is an example, how you could implement your board:

#include <iostream>
#include <unordered_map>
#include <map>

template <class ValueType>
class board_3d {
public:
    using key_t = std::tuple<size_t, size_t, size_t>;
    using value_t = ValueType;

    ValueType& operator[](key_t key) {
        return m_data[key];
    } 

    const ValueType& operator[](key_t key) const {
        return m_data[key];
    } 

private:
    std::map<key_t, ValueType> m_data;
};

int main()
{
    board_3d<int> my_board;
    my_board[{0,0,0}] = 5;
    return 0;
}

std::map is probably not what you want in the end. The access is O(log n). To optimise you can use std::unordered_map with O(1) access or any implemtation using vectors. You can also add a resize function, that takes care of the copying of the data from the old to the new storage.

user_70420110

I think you could use a sparse representation:

std::map<int, std::map<int, std::map<int, int> > > board;

You can use square brackets to reference a value in this map:

board[x][y][z] = 13;

However, this structure might messy and inefficient, so you can pack x, y and z to a composite key and use it in std::unordered_map.

struct XYZ_Key {
  int32_t  x;
  int32_t  y;
  int32_t  z;
  bool operator==(const XYZ_Key& o) const {
    return (x == o.x) && (y == o.y) && (z == o.z);
  }

  size_t hashCode() const {
    return ((((11 + x) * 7) + y) * 5) + z) * 3;
  }
};

std::unordered_map<XYZ_Key, int, decltype(std::mem_fn(&XYZ_Key::hashCode)) >  board;
user_17365960

To avoid nested vectors, how about building a 2D grid of pointers on the stack, of fixed size (set to the upper limit on board size) with single vectors holding all the data? Something like this (here implemented with smart pointers):

#include <iostream>
#include <vector>
#include <memory>

int main() {
    const int MAXSIZE = 512
    int width = 5;
    int height = 5;
    int depth = 5; 
    std::unique_ptr<std::vector<int>> grid[MAXSIZE][MAXSIZE];
    for (int i = 0; i < width; ++i) {
       for (int j = 0; j < height; ++j) {
          grid[i][j] = std::make_unique<std::vector<int>>();
          for (int k = 0; k < depth; ++k) {
              grid[i][j]->push_back(k);
          }
       }
    }
    //To iterate over all the contents:
    for (int i = 0; i < width; ++i) {
        for (int j = 0; j < height; ++j) {
            for (int k = 0; k < depth; ++k) {
                std::cout << grid[i][j]->at(k) << " ";
            }
            std::cout << " // ";
        }
        std::cout << std::endl;
    }
    return 0;
}

You might have to use a std::shared_ptr instead depending on how the game works. My understanding is that this kind of structure allows for more efficient memory access than the nested vector approach; perhaps the downside is having to allocate the larger grid all at once?

user_115475760
Related