Алгоритм нахождения лучших маршрутов для раздачи еды в игре

Question

Я разрабатываю игру по строительству города и попал в проблему.

Представьте себе Цезарь III игровой механики Сьерры: у вас есть много городских кварталов с одним рынком в каждом.На расстоянии есть несколько зернохранилищ, связанных с ориентированным взвешенным графом.Разница в том, что люди (в данном случае автомобили) - это единицы, образующие пробки (весовые коэффициенты на графике).

Примечание: в серии игр Ceasar люди собирали пищу и складировали ее в нескольких больших зернохранилищах, тогда как на многих рынкахнебольшие магазины) брали еду из зернохранилищ и доставляли ее гражданам.

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

Пример карты

Предположим, что желтым округам нужно 7, 7 и 4 яблока соответственно.В голубоватых амбарах соответственно 7 и 11 яблок.

Предположим, что вес ребер пропорционален их длине.Тогда решение должно быть чем-то вроде серых чисел, обозначенных по краям.Например, первый район получает 4 яблока из 1-го и 3 яблока из 2-го амбара, в то время как последний район получает 4 яблока только из 2-го амбара.

Здесь вертикальные дороги сначала заняты по максимуму, а затем оставшиеся рабочие отправляются по диагональным путям.

Вопрос

Какой практичный и очень быстрый алгоритм я должениспользовать?Я просматривал некоторые статьи ( Игры с заторами: Оптимизация на соревнованиях и т. Д.), Описывающие игры с заторами, но не смог получить общую картину.

Answer 1

Вы хотите разобраться в проблеме Max-flow . Похоже, что в этом случае это двудольный граф, который должен облегчить визуализацию.

Answer 2

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

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

Answer 3

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

Answer 4

Я согласен с Ларри и Мэтмиком, похоже, эта проблема является специализацией сетевого потока.

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

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

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

Редактировать: Хотел бы также указать, что ссылка mathmike на Википедию также говорит о проблеме максимального потока с пропускной способностью вершин , где каждый из ваших зернохранилищ можно представить как вершины с конечной емкостью.

Answer 5

Может быть интереснее иметь динамику, которая моделирует поведение, которое приводит к хорошему разумному решению, а не находить идеальное решение для управления поведением. Предположим, вы планируете каждую поездку индивидуально. Если вы водитель и вам нужно добраться из пункта А в пункт Б, как вы туда доберетесь? Вы могли бы рассмотреть несколько вещей:

1. Я знаю о типичных условиях движения в этот час, и я постараюсь найти пути вокруг дорог, которые обычно заняты. Вы можете смоделировать это как усредненное значение трафика в разное время, так как автомобилисты не обязательно имеют точную информацию о текущем трафике, но могут изучать и выявлять тенденции во времени.

2. Мне не нравятся длинные, запутанные маршруты с большим количеством поворотов. При планировании поездки вы можете оштрафовать тех, у кого много краев.

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

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

Answer 6

Стоит отметить, что ваша игра непрерывна. Если у вас есть решение X в момент времени t, и происходит небольшое изменение (например, игрок строит другую дорогу, или один из городов набирает больше населения), решение, которое алгоритмы Max Flow дают вам , может сильно измениться , но вы, вероятно, хотели бы, чтобы решение в момент времени t + 1 было похоже на X. Совершенно другое решение на каждом временном шаге нереально (1 новая дорога строится в южном конце карты, и все маршруты автоматически пересчитывается).

Я бы использовал какой-то алгоритм для расчета начального решения (или когда происходит значительное изменение, например, землетрясение разрушает 25% дорог), но большую часть времени обновляет его только постепенно : значение, определение какая-то форма действительного преобразования решения (например, 1 город пытается получить 1 еду из другого зернохранилища, чем сейчас) - вы пытаетесь обновить (имитировать ожидаемую загруженность) и сохраняете обновленное решение, если оно лучше, чем существующее решение. Выполняйте этот шаг N раз после каждого игрового хода или некоторой единицы времени.

Он эффективен в вычислительном отношении (не нужно запускать полный Max Flow каждую секунду) и даст вам более реалистичные, плавные изменения в поведении.