Я работаю над игрой (используя Game Maker: Studio Professional v1.99.355), которая должна иметь как изменяемую пользователем геометрию уровня, так и поиск пути AI, основанный на физике платформера. Из-за этого мне нужен способ динамического определения того, какие платформы могут быть доступны с каких других платформ, чтобы построить граф узлов, который я могу передать A*.
Мой текущий подход, более или менее, таков:
Для каждой платформы рассмотрим каждую другую платформу на уровне.
Для каждой из этих платформ, если она явно недостижима (например, из-за того, что она выше максимальной высоты прыжка), не формируйте связь и переходите к следующей платформе.
Если связь кажется возможной, поместите экземпляр ai_character на стартовую платформу и (в рамках текущего шага) смоделируйте попытку прыжка.
3.a Повторите эту попытку прыжка для каждой возможной стартовой позиции на стартовой платформе.
Если эта попытка окажется успешной, запишите данные, необходимые для их репликации в режиме реального времени, и перейдите к следующей платформе.
Если нет, не формируйте ссылку.
Повторите для всех платформ.
Этот подход работает более или менее и создает структуру ссылок, которая при визуализации выглядит следующим образом:
связанные платформы (гиперссылка, потому что нет представителя)
В этом примере почти скрытое розовое привидение в правом нижнем углу пытается добраться до черно-белого ящика. Светло-голубые прямоугольники просто указывают, где находятся распознанные платформы, фактические платформы — это ряды серых прямоугольников. Линии связи имеют зеленый цвет в начале и красный цвет в пункте назначения.
Огромная и вопиющая проблема с этим подходом заключается в том, что для уровня всего 17 платформ (как показано выше) для создания графа узлов требуется больше секунды. Причина этого очевидна, желтый текст в центре экрана показывает нам, сколько времени ушло на построение графика: более 24 000 (!) смоделированных кадров, каждый с сопутствующими проверками на столкновение с каждым блоком — я буквально просто запускаю событие шага персонажа. в цикле while, так что все, что обычно делается для обработки движения платформера в кадре, теперь выполняется 24 000 раз.
Это, очевидно, неприемлемо. Если он так плохо масштабируется всего на 17 платформах, то это будет шутка на сотнях, которые мне нужно поддерживать. Черт возьми, при такой геометрической стоимости времени на это могут уйти годы.
Пытаясь ускорить процесс, я сосредоточился на другом важном числе отладки, счетчике тестов: 239. Если бы я просто пробовал все возможные комбинации начальной и конечной платформ, мне нужно было бы запустить 17 * 16 = 272 теста. Выяснив различные способы прогнозирования невозможности прыжка, мне удалось сократить количество дорогостоящих тестов на целых 33 (12%!). Однако чем больше исключений и особых случаев я добавляю в код, тем больше убеждаюсь, что реальная проблема заключается в коде симуляции прыжка, что, наконец, приводит меня к моему вопросу:
Как бы вы с полной достоверностью определили, может ли персонаж прыгать с одной платформы на другую, предпочтительно без необходимости моделирования всего прыжка?
Моя конкретная физика платформы:
Прыжки имеют фиксированную высоту, если только вы не попали в потолок.
Горизонтальное движение не имеет ускорения или инерции.
Допускается горизонтальное управление воздухом.
Дополнительная информация: я нашел это видео, в котором описана аналогичная проблема, но не дано хорошего решения. Это буквально единственный ресурс, который я нашел.
