Не только в играх вроде "Го" или "Жизнь" - но и в создании фильтров для изображений - часто нужно для клетки или точки (x, y) перечислить её "соседей". Либо только четырех (по горизонтали и вертикали), либо все восемь (с диагоналями).

Можно не задумываясь написать массивчик с 4-мя или 8-ю парами смещений, вроде
[(-1, 0), (0, 1), (1, 0), (0, -1)] - а можно ли вместо него жахнуть какую-нибудь формулу? Давайте попробуем для утренней разминки ума в понедельник :)

В этой статье будет несколько 2-3 строчных примеров кода - уж извините пожалуйста :) зато она довольно короткая.

Типичная ситуация

Итак, допустим мы задали массив со "смещениями" соседей относительно текущей клетки, хотя бы вот в том виде что выше:

neighbors = [(-1, 0), (0, 1), (1, 0), (0, -1)]

Обычно встречается одна из двух необходимостей (или обе) - либо нам нужно перебрать этих самых "соседей" в цикле:

# let x, y be current cell coordinates
for dx, dy in neighbors:
  paint_it_black(x+dx, y+dy)

во всех примерах с циклом вы можете заменить paint_it_black на print и проставить x=0; y=0 вначале чтобы увидеть "чистые смещения".

Либо нужно получить координаты i-го соседа:

def get_neighbor(x, y, i):
  return x + neighbors[i][0], y + neighbors[i][1]

и вот нам интересно, можно ли обойтись без массива neighbors - ибо кажется, что особенно в варианте с 8 соседями он и выглядит громоздко и попутать можно чего-то невзначай - а проверять потом визуально.

Что если соседей... девять, включая себя?

Рассмотрим этот случай чисто для подготовки к следующим - он гораздо проще, ведь нам нужно перебрать квадрат 3x3 - например так:

for i in range(9):
  paint_it_black(x + i % 3 - 1, y + i // 3 - 1)

def get_neighbor(x, y, i):
  return x + i % 3 - 1, y + i // 3 - 1

В общем, пользуемся тем что частное и остаток от деления на 3 для чисел 0..8 возвращают естественно "строку" и "столбец": dx=i%3-1, dy=i//3-1.

Но как быть с 8-ю?

В случае перебора в цикле, конечно, можно использовать вариант для 9-ти и проверять отдельным условием что это не центральная точка. Ну выглядит омерзительно :)

И конечно для "занумерования" соседей в функции get_neighbor просто не годится такое "выкалывание" точки. Номера должны идти по порядку!

Однако - мы ведь перебираем в цикле 9 значений из которых одно нам не нужно. Что будет если перебирать начиная с числа следующего за "ненужным"? Это можно написать по-разному но общий принцип такой - добавим к номеру соседа пятёрку (т.к. нам нужно пропустить четвертого - себя) - и возьмём остаток от деления на 9 - ну и конечно помним что теперь перебирать на одного меньше (ведь 9м окажемся мы сами).

for i in range(8):
  i = (i+5) % 9
  paint_it_black(x + i % 3 - 1, y + i // 3 - 1)

def get_neighbor(x, y, i):
  i = (i+5) % 9
  return x + i % 3 - 1, y + i // 3 - 1

Когда принцип понятен, можно записать и короче

for i in range(8):
...   paint_it_black(x + (i+5)%3-1, y + (i+5)//3%3-1)

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

Что делать с 4-мя?

Посмотрите на тот случай с 9-ю, ведь в нём нужные нам "ортогональные" соседи идут через одного. Это даёт нам очень простую мысль - запишем тот же код, но используя индекс с удвоенным шагом:

for i in range(1, 9, 2):
  paint_it_black(x + i % 3 - 1, y + i // 3 - 1)

Элементарно, Ватсон! Для того чтобы их занумеровать в функции, нужно поступить чуть иначе - "смасштабировать" индекс:

def get_neighbor(x, y, i):
  i = i * 2 + 1
  return x + i % 3 - 1, y + i // 3 - 1

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

Что же, на помощь приходит школьная формула - ведь использование синусов-косинусов позволяет нарисовать круг или получить из полярных координат декартовы - это примерно то что нужно!

for i in range(4):
  a = i*math.pi/2
  paint_it_black(x + round(math.sin(a)), y + round(-math.cos(a)))

Ну и для get_neighbor(...) аналогично.

Дополнение: в комментарии предложена хорошая идея - аналогичная в смысле математики но более красивая в исполнении - если язык программирования поддерживает комплексные числа (например в Go они зачем-то прямо-таки стандартный тип) - то можно получать 4-х соседей просто возводя мнимую единицу в степень равную номеру соседа:

def get_neighbor(x, y, i):
  return x + round((1j**i).real), y + round((1j**i).imag)

Можно вообще представлять пару координат (точку, клетку) одним комплексным числом.

Заключение

Я вовсе не призываю использовать эти "хитроумные" формулы вместо упомянутого массива с парами "смещений". Это уж по вкусу - и по настроениям в команде. Кому что проще кажется. К слову, иногда с формулами можно попасть впросак - в частности в PHP функция round из последнего примера может округлять не только в положительный ноль но и в отрицательный. Сравнению это не помешает, но склеив из двух координат строковый ключ для ассоциативного массива я, конечно, поймал занятный баг (который отчасти и подтолкнул к рассмотрению других способов - и в общем написанию данной статьи).

В качестве упражнения попробуйте:

• переделать функцию с синусами-косинусами так чтобы она работала с 8 соседями

• переделать её же так чтобы работала с 9-ю (себя, то есть центр, нужно выводить последним - если вы ещё не загуглили про "улитку", то загуглите)