Есть ли способ узнать, соответствует ли значение в 2D-массиве любому значению в другом 2D-массиве? - PullRequest
Новая
       7

Есть ли способ узнать, соответствует ли значение в 2D-массиве любому значению в другом 2D-массиве?

1 голос
/ 20 февраля 2020

Я создаю игру на линкорах в Javascript и React, и я застрял над этой проблемой на некоторое время, даже после большого Googling и StackOverflowing.

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

Вот что у меня есть для моих кораблей: 

placeShips = () => {
        // Logic to place boats randomly below

        // Checks required before placing a boat:
        // 1. Does the boat go off the board
        // 2. Does the boat overlap another boat
        // 3. If checks above pass then place boat


        let placedPosition = []
        let board = this.state.board.slice()
        let i
        for (i = 0; i < this.state.ships.length; i++) {
            // First randomly select coordinates for where the boat will start
            let xcoord = Math.floor(Math.random() * 10)
            let ycoord = Math.floor(Math.random() * 10)

            // Get positions in array where a boat will be
            let potentialBoat = []
            let newCoords

            let j
            for (j = 0; j < this.state.ships[i].getLength(); j++) {
                newCoords = [xcoord, ycoord + j]
                potentialBoat.push(newCoords)

Первое для l oop повторяется для каждого корабля, оставшегося в моем штате, и второй для l oop принимает длину корабля, получает предполагаемую координату ([[0, 1], [0,2]] для корабля длиной 2, например ) и сохраняет его в массиве потенциальный бот.

Моя идея состоит в том, чтобы использовать этот потенциал потенциальных массивов и посмотреть, существует ли какой-либо [xcoordinate, ycoordinate], который уже существует в массиве PlacePosition и, если это так, снова l oop для текущей лодки и получать новые координаты до они не пересекаются.

Возможно ли это? Или я должен переосмыслить всю мою реализацию? Спасибо!

1 Ответ

1 голос
/ 20 февраля 2020

Внутри l oop, когда вы создаете корабль, подумайте о создании строки, представляющей координаты. Например, для newCoords из 1, 3 создайте строку 1_3. Чтобы проверить местоположение, проверьте, существует ли эта строка в массиве (или множестве) местоположений проверенных кораблей. В конце внутреннего l oop, после того как все позиции по длине корабля будут проверены, объедините возможные местоположения в массив проверенных местоположений: 

placeShips = () => {
  const placedPosition = [];
  const board = this.state.board.slice();
  const validatedPositionStrings = []; // <---- Create this array
  for (const ship of this.state.ships) {
    const thisShipLength = ship.getLength();
    tryShip:
    while (true) {
      const thisBoatPossiblePositionStrings = [];
      // Generate ship positions until valid
      const xcoord = Math.floor(Math.random() * 10);
      const ycoord = Math.floor(Math.random() * 10);
      const potentialBoat = [];
      for (let j = 0; j < thisShipLength; j++) {
        // Then check to see if the below position is already in it
        const thisCoordinateString = `${x}_${y}`; 
        if (validatedPositionStrings.includes(thisCoordinateString)) {
          // Invalid
          continue tryShip;
        }
        thisBoatPossiblePositionStrings.push(thisCoordinateString);

        // If this point is reached, then this particular coordinate is valid
        // do whatever you need to do:
        const newCoords = [xcoord, ycoord + j];
        potentialBoat.push(newCoords);
      }
      // All positions for ship are valid
      // do something with potentialBoat here?
      // push positions to placedPosition?
      validatedPositionStrings.push(...thisBoatPossiblePositionStrings);
      break;
    }
  }
}

Это можно сделать меньше вычислительно сложный, используя Set вместо массива, но это, вероятно, не имеет значения, если нет очень большого количества итераций.

Также можно было бы искать в вашем массиве массивов, чтобы увидеть, если позиция уже размещен, но это потребует ненужного количества кода IMO.

Если возможно, вы можете рассмотреть возможность изменения структуры данных таким образом, чтобы вместо массива массивов у вас был только один объект, представляющий координаты, значения которых указывают корабль в этой позиции (и, возможно, другие атрибуты, необходимые для конкретной точки), например: 

{
  1_3: { ship: 'destroyer', 'attackedYet': 'false' }
  // ...

Такой объект, вероятно, будет легче найти и проработать, чем массив массивы пар XY.

...