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