Волновой алгоритм для нескольких маршрутов

@Rayne · Регистрация: 11.07.2009

Студворк — интернет-сервис помощи студентам

Задача самая рядовая: допустим, есть стратегическая игра, нужно организовать движение группы машин из точки А в точку Б.
Спрашивал на форумах игроделов, говорят что подход вроде ~"если клетка пересекается с другим маршрутом, и сейчас занята - то подождать" не подходит совершенно.
Думаю что обязательно на карту кроме пройденных\непройденных\непроходимых точек добавятся ещё динамические - занятые\незанятые
Но как быть если например до точки Б единственный путь - через тоннель, у которого ширина позволяет пройти только одной машине? Как тут обойтись без "подождать"? или на том форуме имели ввиду что нельзя активное ожидание создавать ... к сожалению не помню ссылку.

@insideone · 04.01.2012, 15:39

Каждые N мс пересчитывать для каждой машины маршрут с учетом текущих препятствий (в т.ч. другие машины). Не?

@Rayne · 06.01.2012, 02:36 **[ТС]**

не, это худшее что можно сделать.
Можно например для 10 объектов по очереди строить маршруты с 1 по 10, у каждого следующего в препятствие войдут маршруты предыдущих, и спокойно запускать. Как-бы нормально на относительно свободной местности, проблемы будут когда появится очередь, две машины проезжают тоннель шириной в 2 клетки, что остальным делать.

Попробовать сравнить длины маршрутов, вот только что идея пришла, если одна машина получила слишком длинный маршрут - то видимо что-то не так, она нашла как проехать - но по огромному обходному пути, из-за перекрытого другими движения, и она попадёт в очередь пока не освободят дорогу. Только вот как поймать этот момент?

Попроще сделаю пока ... покажу что получится, может у кого ещё идеи возникнут

@insideone · 06.01.2012, 08:54

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

murderer · 07.01.2012, 10:56

две машины проезжают тоннель шириной в 2 клетки, что остальным делать.

Найти полный путь без учёта пересечений с другими маршрутами для каждого юнита и пусть они толкаются пока всё само сабой не утрясётся. Кажется в большинстве стратегий так и делают.

Добавлено через 1 минуту
insideone
Так делали на денди. Сейчас это уже примитивно будет выглядеть.

@insideone · 08.01.2012, 18:09

Сообщение от murderer

Так делали на денди. Сейчас это уже примитивно будет выглядеть.

По-моему на денди вообще никак не делали. Там нет стратегий где возможно групповое перемещение. По крайне мере я таких не помню.

@Ales'hon'ne · 10.01.2012, 17:17

Как вариант - запрещать пересечение маршрутов только если расстояние от старта до точки пересечения у этих маршрутов одинаково. Тогда все спокойно разъедутся.

murderer · 10.01.2012, 20:07

Объединяя сообщения от Ales'hon'ne и insideone предлагаю следующее: Выделить группы юнитов с пересекающимися путями и установить для каждой группы лидера. Далее повторяем алгоритм для лидеров и формируем группы второго порядка, у которых будет свой лидер и т.д. рекурсивно. Но я сильно сомневаюсь, что это будет вменяемо работать.

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Rayne 76 / 62 / 23 Регистрация: 11.07.2009 Сообщений: 730

	Волновой алгоритм для нескольких маршрутов 03.01.2012, 14:01. Показов 1558. Ответов 7 Метки нет (Все метки) Задача самая рядовая: допустим, есть стратегическая игра, нужно организовать движение группы машин из точки А в точку Б. Спрашивал на форумах игроделов, говорят что подход вроде ~"если клетка пересекается с другим маршрутом, и сейчас занята - то подождать" не подходит совершенно. Думаю что обязательно на карту кроме пройденных\непройденных\непроходимых точек добавятся ещё динамические - занятые\незанятые Но как быть если например до точки Б единственный путь - через тоннель, у которого ширина позволяет пройти только одной машине? Как тут обойтись без "подождать"? или на том форуме имели ввиду что нельзя активное ожидание создавать ... к сожалению не помню ссылку. 0

@insideone 3687 / 964 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	04.01.2012, 15:39
	Каждые N мс пересчитывать для каждой машины маршрут с учетом текущих препятствий (в т.ч. другие машины). Не? 0

@Rayne 76 / 62 / 23 Регистрация: 11.07.2009 Сообщений: 730
	06.01.2012, 02:36 [ТС]
	не, это худшее что можно сделать. Можно например для 10 объектов по очереди строить маршруты с 1 по 10, у каждого следующего в препятствие войдут маршруты предыдущих, и спокойно запускать. Как-бы нормально на относительно свободной местности, проблемы будут когда появится очередь, две машины проезжают тоннель шириной в 2 клетки, что остальным делать. Попробовать сравнить длины маршрутов, вот только что идея пришла, если одна машина получила слишком длинный маршрут - то видимо что-то не так, она нашла как проехать - но по огромному обходному пути, из-за перекрытого другими движения, и она попадёт в очередь пока не освободят дорогу. Только вот как поймать этот момент? Попроще сделаю пока ... покажу что получится, может у кого ещё идеи возникнут 0

@insideone 3687 / 964 / 114 Регистрация: 10.01.2010 Сообщений: 2,550
	06.01.2012, 08:54
	Как вариант - рассчитывать маршрут для машины-лидера, а остальные машины цеплять к ней (следуй за лидером). Лидер - тот кто впереди. Естественно при таком раскладе остальные машины всегда будут плестись сзади. Чтобы машины-последователи не кучковались можно к каждому маршруту давать смещение для каждой машины в отряде, такое чтобы не было толкучки. Другими словами есть лидер, а сзади слоты в форме разряжённого куба\пирамиды которые раздаются присоединённым в отряде. 0

@Ales'hon'ne 159 / 152 / 50 Регистрация: 03.08.2011 Сообщений: 299 Записей в блоге: 14
	10.01.2012, 17:17
	Как вариант - запрещать пересечение маршрутов только если расстояние от старта до точки пересечения у этих маршрутов одинаково. Тогда все спокойно разъедутся. 0

murderer 4190 / 1838 / 221 Регистрация: 06.10.2010 Сообщений: 4,124
	10.01.2012, 20:07
	Объединяя сообщения от Ales'hon'ne и insideone предлагаю следующее: Выделить группы юнитов с пересекающимися путями и установить для каждой группы лидера. Далее повторяем алгоритм для лидеров и формируем группы второго порядка, у которых будет свой лидер и т.д. рекурсивно. Но я сильно сомневаюсь, что это будет вменяемо работать. 1