Алгоритм поиска лучших маршрутов раздачи еды в игре

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

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

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

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

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

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

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

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

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

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