Graph Pathfinder (Dijkstra's Algorithm)

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

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

Управление

Основные режимы

• Кнопка "Поиск путей" - переход в режим поиска пути
• Кнопка "Конструктор" - переход в режим конструктора графа
• Клавиша Esc - возврат в режим бездействия из любого режима

Режим конструктора

• Клавиша 1 - подрежим "Создание вершин" (клик левой кнопкой мыши создаёт вершину)
• Клавиша 2 - подрежим "Создание рёбер" (клик на двух вершинах создаёт ребро между ними)
• Клавиша 3 - подрежим "Удаление сущностей" (клик удаляет вершину или ребро)

Режим поиска пути

• Левый клик мыши - выбор стартовой и конечной вершин для поиска пути

Как пользоваться

Начало работы

При запуске приложения вы находитесь в режиме бездействия. Для начала работы выберите один из режимов:

Создание графа (Режим конструктора)

1. Нажмите кнопку "Конструктор" в интерфейсе
2. Выберите подрежим создания вершин (1), кликайте левой кнопкой мыши для размещения вершин
3. Перейдите в подрежим создания рёбер (2), кликните на две вершины для создания ребра между ними
4. Для удаления вершин или рёбер используйте подрежим удаления (3)
5. Для выхода из режима конструктора нажмите Esc

Поиск пути

1. Нажмите кнопку "Поиск путей" в интерфейсе
2. Выберите стартовую вершину кликом мыши
3. Выберите конечную вершину кликом мыши
4. Программа автоматически построит и подсветит кратчайший путь, найденный с помощью алгоритма Дейкстры
5. Для выхода из режима поиска нажмите Esc

Технические детали

• Движок: Unity 6000.2.2f1
• Самописные решения:
  • Shafir FSM (https://github.com/JafarovJafar/shafir-fsm.git)
  • Shafir MonoPool (https://github.com/JafarovJafar/shafir-monopool.git)
• Сторонние решения:
  • UniTask (https://github.com/Cysharp/UniTask.git?path=src/UniTask/Assets/Plugins/UniTask)
• Корректный порядок отрисовки (сначала ребра, потом путь, следом вершины) реализован при помощи Render Feature
• Обводка на вершинах сделана при помощи шейдера

Возможные улучшения

• Добавление других алгоритмов поиска пути (A*, Bellman-Ford)
• Режим сравнения разных алгоритмов
• Сохранение/загрузка графов (JSON/XML)
• Настройка произвольных весов рёбер
• Анимация процесса поиска по шагам

---

Если этот проект был вам полезен, не забудьте поставить звезду ⭐ репозиторию!