Перебор Соседних Клеток — забавные формулы

Не только в играх вроде «Го» или «Жизнь» — но и в создании фильтров для изображений — часто нужно для клетки или точки (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-ю (себя, то есть центр, нужно выводить последним — если вы ещё не загуглили про «улитку», то загуглите)