Почему главная механика рисования в моей игре сделана на костыле и почему это оказалось правильным решением⁠⁠

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

Начну издалека. В игровой индустрии, одним из способов дать возможность не игровым персонажам "правильно" перемещаться по игровому миру, является построение специальной навигационной сетки. Из себя, она буквально представляет сетку в зоне которой они могут двигаться и по которой рассчитывают свой маршрут от точки А, к точке Б.
Причём, при расчёте маршрута, искусственный интеллект NPC, будет искать не самый короткий, с точки зрения расстояния, а самый "Дешёвый" с точки зрения затраты времени на прохождение пути. Объясню, что это значит. На сетке можно сделать зоны помеченные как "трудные" для перемещения, как пример, скорость движения в такой зоне будет снижена. То есть на карте может быть река и мост через эту реку. Так как река будет помечена как "трудный путь", а мост как "обычный", алгоритм просчёта пути оценит, что будет быстрее. Дойти до моста и перейти реку или пуститься вплавь, если мост далеко. Однако, если на пути нет таких зон, "дешёвый" и самый короткий обычно совпадают, что я и использовал. Выглядит навигационная сетка так:

Так причём тут рисование и нахождение пути для не игровых персонажей?
А дело в том, что линии которые рисует игрок, являются физическими объектами, которые реагируют на столкновения. И может случиться крайне не приятный момент, если такую линию нарисовать внутри стены. В самом лучшем случае, такую линию просто вытолкнет, а в худшем она начнёт дёргаться по всей локации, пытаясь высвободиться.

Самый простой способ, не допустить такое поведение, запретить рисовать внутри других физических объектов, прерывая или не давая начать рисовать.
Но тут есть две проблемы:
1) Так как рисование линий происходит путём добавления новых точек, а получаем мы такие точки не мгновенно, а если упрощённо, с периодичностью обновления экрана. То, когда мы получим новую позицию на экране, она может указывать на зону, где можно рисовать, но фактически, между предыдущей точкой и новой может находиться стена. А как мы оговорились ранее, внутри стен рисовать мы не хотим.
2) Игроку нужно нарисовать длинную сплошную линию, но он случайно заходит в запретную зону и рисование сразу прекращается, линия обрывается и её приходиться рисовать по новой. Как итог, игрок после пары попыток сдаётся и удаляет игру.

Понимая проблему, пришло и решение как обеспечить рисование правильной и непрерывной линии. Мы должны проверить, есть ли между предыдущей и новой точкой препятствие. Если такое есть, нам нужно выяснить, существует ли обходной путь.
Вот тут то и пригодился уже готовый, предназначенный для немного иных целей, но имеющий такой нужный нам функционал, механизм поиска пути по навигационной сетке.
Теперь нам осталось просто обратиться к алгоритму поиска пути с вопросом, есть ли между этими двумя точками доступный путь. Если он есть, добавляем точки полученного пути к нашей линии, если нет, находим точки где линия бы оборвалась. Причём, даже если наша новая точка находиться в недоступном для рисования месте, алгоритм всё ровно будет пытаться найти ближайшую точку в зоне, где рисование доступно и наша линия не прервётся. Выглядит это так:

То есть фактически, я даю команду алгоритму работающему с навигационной сеткой: Дай мне все точки по которым "Агент" прошёл бы этот путь, и если такой путь есть, просто добавляю полученные точки к рисуемой линии.
Вот так, всё оказалось очень просто!

Поиграть в игру, в которой реализована эта механика, можно тут:
Скачать: Google Play
p.s. Суть игры рисовать линии, что бы решать головоломки.
Спасибо, что прочитали!