Перебор Соседних Клеток — забавные формулы
Не только в играх вроде «Го» или «Жизнь» -, но и в создании фильтров для изображений — часто нужно уметь найти для клетки или точки (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(...) аналогично.
Заключение
Я вовсе не призываю использовать эти «хитроумные» формулы вместо упомянутого массива с парами «смещений». Это уж по вкусу — и по настроениям в команде. Кому что проще кажется. К слову, иногда с формулами можно попасть впросак — в частности в PHP функция round из последнего примера может округлять не только в положительный ноль, но и в отрицательный. Сравнению это не помешает, но склеив из двух координат строковый ключ для ассоциативного массива я, конечно, поймал занятный баг (который отчасти и подтолкнул к рассмотрению других способов — и в общем написанию данной статьи).
В качестве упражнения попробуйте:
переделать функцию с синусами-косинусами так чтобы она работала с 8 соседями
переделать её же так чтобы работала с 9-ю (себя, то есть центр, нужно выводить последним — если вы ещё не загуглили про «улитку», то загуглите)
