3D игровое поле в C ++ - PullRequest
Новая
       14

3D игровое поле в C ++

3 голосов
/ 16 марта 2020

Я очень плохо знаком с C ++, и мне трудно создавать 3D игровую доску. Размер доски может увеличиваться на протяжении игры .

Моей первой идеей было использование вложенных векторов. vector<vector<vector<int>>> board

Идея заключалась в том, что это было бы легко доступно (board[z][y][x]), и у меня не было бы проблем с динамическим распределением c. Однако я слышал, что вкладывать векторы не очень хорошая идея, потому что это нарушает «дружелюбность кеша». Вместо этого я должен использовать 1d вектор и «поддельное» измерение, используя математику.

Я думаю, что это означает создание вектора размера (x * y * z). В том случае, когда я хочу "go" для nested_vector_board [0] [1] [0], я использую board [x]. В случае, если я хочу go для nested_vector_board [1] [1] [0], я использую доску [x * y + x].

Верно ли мое понимание? Что мне делать в случае изменения размера платы? Например, если я хочу сделать доску шире, мне нужно вручную сдвинуть все данные. Что еще более важно, есть ли лучший, более простой способ сделать это?

Буду рад любым советам и заранее большое спасибо!

Ответы [ 3 ]

2 голосов
/ 16 марта 2020

Если вы не знаете, каким будет ваш шаблон доступа, вы не сможете выбрать оптимальное решение. Кроме того, если у вас нет рабочего решения, вы не можете измерить свою производительность и можете только догадываться, какое решение будет лучшим, и вы, вероятно, догадаетесь неправильно.

Я предлагаю реализовать собственный класс 3D 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, вероятно, не то, что Вы хотите в конце. Доступ O (журнал N). Для оптимизации вы можете использовать std::unordered_map с доступом O (1) или любую реализацию с использованием векторов. Вы также можете добавить функцию изменения размера, которая заботится о копировании данных из старого в новое хранилище.

1 голос
/ 16 марта 2020

Я думаю, вы могли бы использовать разреженное представление: 

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

Вы можете использовать квадратные скобки для ссылки на значение на этой карте: 

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

Однако эта структура может быть грязной и неэффективно, поэтому вы можете упаковать x, y и z в составной ключ и использовать его в 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;
0 голосов
/ 16 марта 2020

Чтобы избежать вложенных векторов, как насчет построения двумерной сетки указателей в стеке фиксированного размера (установленного в верхний предел размера платы) с одиночными векторами, содержащими все данные? Примерно так (здесь реализовано с помощью умных указателей): 

#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;
}

Возможно, вам придется вместо этого использовать std::shared_ptr в зависимости от того, как работает игра. Насколько я понимаю, такая структура обеспечивает более эффективный доступ к памяти, чем метод вложенных векторов; возможно, недостатком является необходимость выделять большую сетку одновременно?

...