O (1) сложность структуры поиска данных для 2D координатной сетки JavaScript

Question

Проблема

Я пытаюсь реализовать структуру данных для представления карты плиток в p5.js, но в JavaScript я не могу создать двумерный массив заданного размера, которыйбыло бы идеально для поиска в постоянном времени.

В настоящее время это просто простой одномерный массив, который хранит все объекты мозаики в порядке от верхнего ряда до нижнего ряда.Реализация показана ниже.

Я хотел бы получить решение для захвата объекта мозаики по определенной координате без необходимости поиска по каждой плитке, пока объекты мозаики x и y не совпадут с тем, что я ищу.

Вот моя реализация сетки:

this.tiles = [];

for(x = 0; x < this.canvasWidth; x += this.tileWidth) {
  for(y = 0; y < this.canvasHeight; y += this.tileHeight) {
    var tile = new Tile(x, y, this.tileWidth, this.tileHeight)
    this.tiles.push(tile);
  }
}

Методы, которые я пробовал

Я пытался реализовать это с помощьюсловарный тип структуры, которая отображала объект координат на объект мозаики, чтобы я мог создать объект координат при поиске, но я не мог понять это.

Answer 1

Вместо этого используйте массив массивов, внешний массив с индексом x, а внутренний индекс с индексом y, а значения внутреннего массива - это плитки:

this.tiles = [];
for(x = 0; x < this.canvasWidth; x += this.tileWidth) {
  const xArr = [];
  for(y = 0; y < this.canvasHeight; y += this.tileHeight) {
    var tile = new Tile(x, y, this.tileWidth, this.tileHeight)
    xArr.push(tile);
  }
  this.tiles.push(xArr);
}

Тогда, например,

this.tiles[3][6]

будет относиться к Tile с x из 3 и y из 6.

Это зависит от x и y, начиная с 0в твоем вопросе.Если они не начинаются с 0, рассмотрите возможность использования Map из Map с (если структура прямоугольная) или (если структура не прямоугольная) объекта с ключами, которые представляют x и y координаты, например,

{
  "3_4": <tile correspoding to x of 3, y of 4>
}

Если структура прямоугольная, вы также можете продолжать использовать массив массивов, если сначала добавите в поиск начальные значения x и y, хотяэто может быть немного сложнее для чтения.