Перейти к содержанию

алгоритм Дейкстры | Поиск пути на взвешенном графе


Рекомендуемые сообщения

Что это такое можно узнать на вики

Если кратко - алгоритм поиска пути на взвешенном графе, взвешенный - означает что каждое ребро имеет свою стоимость перехода

Достаточно специфичная штука для всяких навигационных систем, однако и для игр вполне может пригодиться, допустим есть патрулирующий по точкам враг и нужно чтобы он отреагировал на посторонний звук и как можно быстрее прибежал на место происшествия, подключать для такой задачи pathfinder на мой взгляд не совсем удобно, и даже не красиво, ибо вот враг только что патрулировал строго по точкам, а как только прозвучала тревога - начал движение по произвольной траектории.
Или как вариант реализации поиска пути для платформера
giphy.gif

Весом для рёбер я сделал их длину для более наглядной демонстрации применения
Реализовывать весь алгоритм ивентами для меня было бы пыткой, поэтому основную работу повесил на подключаемый скрипт

Исходник - dijkstra.c3p

Обновлённый с комментариями в коде и копированием графа в редакторdijkstraUpdate.c3p
Копирование:

giphy.gif

Есть идеи для улучшения и повышения полезности этого исходника..
одна из таких идей сделать прямой перенос графа из запушенного превью в проект и наоборот, но не знаю доберусь ли, по идее просто json поковырять)  готово

Изменено пользователем cliva
Ссылка на комментарий
Поделиться на другие сайты

17 часов назад, cliva сказал:

Есть идеи для улучшения и повышения полезности этого исходника

18 часов назад, cliva сказал:

//Скучные, нудные и никому не интересные просчёты, возможно не самая лучшая реализация

Как раз наоборот, лично мне было бы очень интересно почитать твои комментарии и понять что там в джаваскрипте написано и в целом было бы здорово если бы ты чуть подробнее освятил эту связку события+код на JS. Я ровно год назад делал этот алгоритм но чисто на событиях, и помню очень намучался, особенно с массивам, а JS код у тебя очень аккуратненько смотрится, хоть ничего и не понятно и даже ни одного массива в проекте нет, как такое может быть 0_0))

Ссылка на комментарий
Поделиться на другие сайты

@dmitryartist Окей, найду как-нибудь время на усовершенствование и комментирование кода)

Если очень кратко - то в js написан код который превращает граф в дерево (в графе могут быть петли, а в дереве нет) причём конец каждой ветки - наикратчайший путь до этого конца
Для примера:
image.png

"А" в данном примере - корень дерева, то есть стартовая точка, теперь можно ткнуться в любую точку на дереве и найти наикратчайший путь двигаясь в обратном направлении по стрелкам

Вот более расширенный пример:
image.png
поверх графа красными стрелками проложено дерево

На счёт связки ивенты+код - наверное сделаю отдельную тему, уже заметил, что люди очень редко пользуются таким мощным инструментом

Массивов в самом проекте нет, ибо все массивы внутри кода, там с ними намного приятней работать)

Изменено пользователем cliva
Ссылка на комментарий
Поделиться на другие сайты

22 часа назад, cliva сказал:

На счёт связки ивенты+код - наверное сделаю отдельную тему, уже заметил, что люди очень редко пользуются таким мощным инструментом

Реквестирую полноценный курс на тему "Основы JS в construct 3"! Будет здорово, если в формате как курсы Сайлера, в текстовом виде со скриншотами событий/кусков кода, и ещё небольшими домашними заданиями в каждой части. Цену ставь как 3 или даже 4 Сайлеровских курса, это всё-таки не для новичков, а для тех кто хочет углубить свои знания в констракте. Я буду первый твой ученик))

Изменено пользователем dmitryartist
Ссылка на комментарий
Поделиться на другие сайты

@dmitryartist Запрос принят, пока продумываю структуру, с курсами Сайлера не знаком, потому будет чистая импровизация, постараюсь приблизиться к формату лучших статей с хабра, курс будет общедоступным, так как на форуме есть запрет на торговлю, но сделаю донатную ссылку для альтруистов это, кажется, не запрещено

Ссылка на комментарий
Поделиться на другие сайты

Добавил перенос графа из запущенного превью прямо в редактор, может пригодиться если нужно спроектировать большой уровень:
giphy.gif
Также прокомментировал весь код в js, но людям не разбирающимся в js сильно понятнее не станет, ибо это достаточно непростой алгоритм для комментирования, особенно учитывая то что я привык мыслить абстракциями, а для объяснений куда лучше подходят реальные примеры, а не абстракции
Исходник -  dijkstraUpdate.c3p

Для того чтобы работало копирование - в настройках должен быть снят этот флажок

image.png

Ссылка на комментарий
Поделиться на другие сайты

А как сделать следующую механику:

IMG_20221207_213019.jpg

  1. Тапом по экрану создаются точки.
  2. По нажатию на кнопку происходит генерация связей между точками.

Правила генерации связей:

  •  каждая точка соединена линиями минимум с одной, максимум с четырьмя ближайшими точками.
  • линии не могут пересекаться друг с другом.
Ссылка на комментарий
Поделиться на другие сайты

Надо как-то прописать ИИ, который будет думать, сколько именно точек надо объединять. Если поставить точку в правый верхний угол, то соединять с 4 точками или только с крайними и одна по середине? Или нижняя слишком далеко и до неё не нужно?

Screenshot_20221208-130303_Browser.png

Изменено пользователем ReviveR200

Сижу с телефона, исходник не посмотрю / не отправлю.

Ссылка на комментарий
Поделиться на другие сайты

@ViGaCi На ивентах, мог и в код запихнуть, но там нужно было бы вводить функцию проверки пересечений, а мне лень)
Да и думаю на ивентах понятнее получилось, кнопка Q - проставить рёбра, R - сбросить рёбра
Исходник - dijkstraUpdateForVGC.c3p

Ссылка на комментарий
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.
Примечание: Ваш пост будет проверен модератором, прежде чем станет видимым.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Восстановить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
×
×
  • Создать...