Логика программирования: как проверить соседей в сетке?

Question

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

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

EDIT: Я забыл упомянуть, что я использую двумерный массив.

Answer 1

Вот простой способ получить соседнюю позицию, не беспокоясь о сторонах:

int leftX = (x - 1 + width) % width;
int rightX = (x + 1) % width;
int aboveY = (y - 1 + height) % height;
int belowY = (y + 1) % height;

Возможно, это не самый эффективный способ сделать это, но он сохраняет каждый расчет в одном простом выражении.Это, конечно, при условии, что вы хотите обернуть его.Если вы этого не сделаете, у вас будет , чтобы сделать что-то условно:

if (x > 0)
{
    // Use x - 1
}
if (x < width - 1)
{
    // Use x + 1
}

Answer 2

Что это за двумерный массив?Возможно, некоторые объекты, которые имеют состояние, такие как «Занято» и «Пусто» или что-то подобное?В этом случае введите новое состояние, такое как «Край» и «Угол», и создайте двумерный массив на 1 ячейку больше в каждом направлении.Тогда программа проверки соседей может просто использовать простую логику +/-, а затем при обработке набора соседей можно игнорировать любые ребра.

Answer 3

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

При условии, что центральная ячейка (где вы ) равна (x,y) и что вы также хотите проверить диагонали.
Ваша сетка [0, W [на X, и [0, H [на Y (в основном W x H, начиная с (0,0))

  for (i=-1 ; i<2 ; i++)    
    for (j=-1 ; j<2 ; j++)
      if (i !=0 && j != 0)
  {
     rx = x + i;
     ry = y + j;

     if (rx >= 0 && ry >= 0 && rx < W && ry < H)
     {
       // I'm in
     }
     else
     {
       // I'm out
     }

  }

Это можно оптимизировать для (i, j), например, i начинается с 0, если x равно 0.

Если вам не нужны диагонали, вам нужно только проверить (x-1,y) (x+1,y) (x,y-1) и (x,y+1),

  for (i=-1 ; i<2 ; i+=2)
  {
     // check (x+i, y)
     // check (x, y+i)
  }

Answer 4

Как насчет того, чтобы выделить нужные вам биты? Что-то вроде isOccupied(x,y) метода, который возвращает false для значений за пределами:

  public boolean isOccupied(int x, int y) {
    if (!inXRange(x) || !inYRange(y))
      return false;
    return occupied[y][x]; // or [x][y] depending on row/col major preferences
  }

Тогда метод подсчета соседей будет довольно простым:

  public int countNeighbours(int x, int y) {
    int neighbours = 0;
    for (int dx = -1; dx <= 1; ++dx) {
      for (int dy = -1; dy <= 1; ++dy) {
        if (((x != 0) || (y != 0)) && isOccupied(x, y))
          neighbours += 1;
      }
    }
    return neighbours;
  }

Answer 5

Часто (если не всегда) приходится жертвовать скоростью или памятью; Некоторое время назад мне пришлось реализовать решатель судоку на Java, и было быстрее назначить каждой ячейке список групп ячеек. Поэтому вместо того, чтобы каждый раз проверять границы, мне просто приходилось выполнять итерации по каждой группе, а затем по каждой ячейке в каждой группе. Проверка была сделана один раз для создания групп.

Что-то вроде:

class Neighbors {
   ArrayList<Point> pList = new ArrayList<Point>();
}

...

int[][] grid = new int[10][10];
Neighbors[][] n = new Neighbors[10][10];

for (int x=0; x<10; x++) {
   for (int y=0; y<10; y++) {
      grid[x][y] = (y*10)+x;  // 0..99
      n[x][y] = new Neighbors();
      for (int nx=x-1; nx<=x+1; nx++) {
         for (int ny=y-1; ny<=y+1; ny++) {
            if (!(x==nx && y==ny) && nx>=0 && ny>=0 && nx<10 && ny<10) {
               n[x][y].pList.add(new Point(nx,ny)); // add valid neighbor
            }
         }
      }
   }
}

тогда для любой заданной точки: х, у

for (Point p : n[x][y].pList) {
   // grid[p.x][p.y]  is a neighbor of grid[x][y]
}

Ну, мое решение было немного более сложным, но принцип тот же. Если ваша сетка представляет собой двумерный массив объектов, соседями на самом деле могут быть объекты в grid[nx][ny] вместо точек для прямого доступа к объектам.

В конечном итоге вам нужно будет проверить x>=0, y>=0, x<SIZE_W и y<SIZE_H, но это решение выполняет проверку только один раз, поэтому, на мой взгляд, оно весьма эффективно, когда часто запрашивает соседей для каждого ячейка сетки. Если вам нужно часто менять размер сетки, то это решение нужно будет адаптировать.

Другим подходом будет заполнение массива в каждом направлении значением флага ignored (например, ноль, -1 и т. Д.) И просто выполнить обычную проверку, игнорируя такие ячейки:

int pad_size = 1;  // how many neighbors around x,y
int size_w = 10+(pad_size*2);
int size_h = 10+(pad_size*2);
int[][] grid = new int[size_w][size_h];

for (int x=0; x<size_w; x++) {
  for (int y=0; y<size_h; y++) {
     if (x<pad_size || x>=size_w-pad_size || y<pad_size || y>=size_h-pad_size) {
        grid[x][y] = -1;  // ignore
     } else {
        grid[x][y] = ((y-pad_size)*10)+(x-pad-size);  // 0..99
     }
  }
}

тогда для любой заданной точки: х, у

for (int nx=x-pad_size; nx<=x+pad_size; nx++) {
  for (int ny=y-pad_size; ny<=y+pad_size; ny++) {
     if (-1!=grid[nx][ny] && !(nx==x && ny==y)) {
        // grid[p.x][p.y]  is a neighbor of grid[x][y]
     }
  }
}

Answer 6

Как уже упоминалось, левый сосед [x, y] равен [x, y-1], а правый сосед [x, y + 1] и т. Д. Однако вы также должны проверить, что y> = 1, иначе вы выйдете за пределы. Точно так же у должен быть меньше, чем размер массива. Вы можете сделать это с помощью оператора if или, альтернативно (не рекомендуется), вы можете обработать ArrayIndexOutOfBoundsException.