Иногда не заливает часть и оставляет дырку (если остров снизу)

[Pro100AlexHell]

Пример входных данных
https://prnt.sc/omlq1n

Вот результат
https://prnt.sc/omlpp2

Другой человек также сообщал о подобном (изза него и стал дебажить)
https://prnt.sc/oml5qx

Инпут был сгенерирован с помощью задания player.territory в LR.

Для дебага можно такой пресет поля использовать - добавить в game.py в Init
https://pastebin.com/YVhC70Wx

---

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

После этого дырки внизу - будут копиться.
Именно нижняя часть, отделенная от основной Territory - не имеет связности с ней, поэтому в графе по Boundary не находит пути для связи нижней дырки.

Далее - почему оно так, с подробностями.

Рассмотрим https://prnt.sc/omox6l
путь обозначенн крестиками

lp1 = начальная точка, рядом с которой ищется вариативный point

Вот примеры вариаций point (v1) и (v2)
https://prnt.sc/omoxqy
Они ищутся циклом

Рядом же с lp2 - находится всегда ближайшая точка - одна, вот этим кодом
start_point = self.get_nearest_boundary(lp2, boundary)

И если есть точка сверху от lp1 - она станет start_point
Это не проблема для островка - когда он сверху от основной территории

Зато это проблема, когда островок снизу
https://prnt.sc/omoyyd
тут обозначены lp1 и lp2

https://prnt.sc/omozwt
тут к ним добавлены - варьирующийся point (v1) и (v2)
и фиксированный start_point - который всегда находит верхнюю часть

и даже когда есть снизу остров: start_point никогда не будет на boundary нижнего острова, пока есть верхний

---

Варианты (по сути решать оргам):

1. Игнорировать баг, т.к. он не частый

2. Добавить цикл (разработчику который это пилит) для вариации соседа относительно lp2, и все, но это замедлит.. кому то может существенно - кто полагался на референс реализацию

3. Добавить цикл (см выше),
   а также оптимизить сам алг, например закешить перед вложенными циклами - при инициализации:
   Dict[point => list[neighbours] ] и поместить в него только point (которые lp1, lp2) имеющие соседей (neigbours список), и не помещать те, которые не имеют, хотя бы чтобы в цикле не перебирать много подвариаций рассмотрением 8 соседей

4. Варьировать иным способом,
   например чтобы для верхней точки - выбирал всегда верхнюю (как и было),
   но для диагональной точки - диагональную,
   чтобы когда lp2 будет такой (а там несколько возможных lp2) то выбирался диагональный - на острове снизу
   http://prntscr.com/omp68m
   т.е приоритет убрать от верхней в get_nearest_boundary
   с учетом что lp2 (точек линии) рядом с границей (boundary) несколько, то одна из них попадет на верхнюю, а другая на нижнюю

формально это реализуется в get_nearest_boundary через проверку X координаты у входной lp2:
if X делтся на 60 без остатка - отдать приоритет верхним (вверху, и по диагоналям)
else отдать приоритет нижним (внизу, и по диагоналям)

правда не уверен что на счет левого и правого :)
а если и их учитывать то делить уже на 120 нужно, т.к. 4х30 = 120
но низкая вер-ть что будет несколько lp1 или lp2 - рядом с boundary - и их будет аж 4 штуки, чтобы все возможные дырки рядом заполнить
.. можно левый и правый заигнорить
.. можно добавить деление на Y без остатка
т.е получатся 2 компоненты X % 60 и Y % 60 - от которых берется приоритет

можно бы и для lp1 тоже изменить на такую же логику, всетаки цикл лишний

---

Если "быстро" поменять функцию get_vert_and_horiz
чтобы в приоритете всегда был низ

def get_vert_and_horiz(point, width=WIDTH):
    x, y = point

    return [
        (x, y - width),
        (x, y + width),
        (x - width, y),
        (x + width, y),
    ]

получаем заливку без багов, но это в данном случае
http://prntscr.com/omq27q

на картинке почему так http://prntscr.com/omq7f8
т.к. находит по диагонали справа-сверху (приоритет)
(x + width, y + width)

если же под lp2 (каждым из диагональных) поставить еще свою землю - оно опять перестанет заливать т.к. будет находить уже снизу всегда, а верхний остров игнорится
https://prnt.sc/omq85t
http://prntscr.com/omq8bj

т.е эта быстрая замена безусловного приоритета - не поможет

---

Я думаю этот случай (ud1)
из этой же оперы (не факт)
https://www.youtube.com/watch?v=ttRmWiRktr0&feature=youtu.be

[SannikovDmitry]

Исправлено. Сейчас ок?

[Pro100AlexHell]

не понял где исправлено
master: Commits on Aug 1, 2019
и нет нового
на сервере чтоли исправлено?

[Pro100AlexHell]

вроде должно пофиксить все кейзы, но смысл что перебора стало уж очень много в смумарном алгоритме
хотя может и не важно
shortest_path = (edges + territory.len) * log(territory.len)
4 цикла это (lines.len ^ 2 / 2) * neighbours
итого примерно до N ^ 4, но по факту формула сложней
никаких N^5 или N^6 там нет в отличие от того что ранее оценивал, но ухудшилось всеравно