Алгоритм для нахождения оптимальных маршрутов для продовольственного распределения в игре

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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