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

[cliva]

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

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

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

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

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

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

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

Изменено 8 декабря, 2022 пользователем cliva

[dmitryartist]

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

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

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

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

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

[cliva]

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

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

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

Вот более расширенный пример:

поверх графа красными стрелками проложено дерево

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

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

Изменено 5 декабря, 2022 пользователем cliva

[dmitryartist]

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

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

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

Изменено 6 декабря, 2022 пользователем dmitryartist

[cliva]

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

[cliva]

Добавил перенос графа из запущенного превью прямо в редактор, может пригодиться если нужно спроектировать большой уровень:

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

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

[ViGaCi]

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

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

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

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

[ReviveR200]

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

Изменено 8 декабря, 2022 пользователем ReviveR200

[cliva]

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