Назначение задач

В РТС, где перед рабочими стоит задача, например, возвести стену, как рабочие решают, какие стены возводить?

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

Я использую пример стены здания; это может быть добыча камня, строительство дороги, сбор дров или что-то еще. Главное, что пользователь выбирает где, а не кто.

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

Рабочим 1 и 2 говорят шахты на квадратах A, B, C и D.

Они могут сдвинуться на один квадрат за игровой тик, а добыча квадрата занимает 10 тиков.

Как вы решаете, какой рабочий шахты какой квадрат?

Кажется очевидным, что 1 должен добывать А, а 2 - добывать С.

1 находится на расстоянии 4 квадратов от A, поэтому закончим майнинг за 14 тиков. Куда мне идти дальше и почему?

А что, если был еще один квадрат - E -, который будет добыт непосредственно над B?

Какую логику использует работник, чтобы решить, что делать дальше?

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

Для этого есть два основных пути: Реалистичным подходом было бы оценить и отметить ресурсные метки до их прибытия. Чтобы предотвратить странные проблемы с очередями, предоставьте работникам диапазон видения для оценки деревьев. Это позволяет работнику приблизиться к конкретному узлу ресурса при переходе к патчу. Это дает ограниченную возможность оптимизации.

Однако многие RTS (SC и SC2) не имеют рабочих, которые оценивают узел до тех пор, пока не прибудут. Это заставляет рабочих бродить, пока не найден ресурсный узел. Это позволяет получить больше навыков / оптимизаций, (Вы когда-нибудь видели отличные рабочие расколы?) Однако, большинство ваших игроков просто собирают все, щелкают и раздражаются, что все они сначала идут в одно и то же место.

Точная реализация зависит от того, как сгруппированы ресурсы. В AoE деревья и рыбы представляют собой непрерывные пространства, поэтому собиратели могут оказаться довольно далеко по ходу игры. Но в играх типа SC и Red Alert ресурсы расположены в отдельных патчах. Поэтому работнику нужно только осмотреть этот конкретный патч.

РЕДАКТИРОВАТЬ после редактирования: не переоценивайте чрезмерную неэффективность работы. Любая RTS, о которой я могу думать, имеет неэффективность работника. Такие вещи, как разделение рабочих, возникают из-за того, что игрок лучше управляет своими работниками, чем игра. Я думаю, что вы, возможно, смотрите на программистов, а не на дизайнеров. Одиночный тик слева можно обойти, просто подправив числа и имея узлы, которые можно собирать в дискретном количестве поездок. Неэффективность работника очевидна для вас, потому что вы знаете систему, стоящую за этим. Однако, если ваши игровые тестеры этого не замечают, не задерживайтесь слишком долго.

Решение и мысль:

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

В вашем примере вы могли бы иметь оптимальное значение очереди равным 0 (что подразумевает отсутствие текущих задач). Добавьте 1 к значению очереди для каждого квадрата, который им нужно будет пройти (время в пути) и 10 для каждой задачи (время для выполнения задачи). Удалите 1 из значения очереди каждого рабочего за каждую проходящую единицу времени (если начальное значение очереди равно 10, то через 3 единицы времени значение очереди будет равно 7). Затем вы найдете ближайшего соседа (в случае, если несколько рабочих имеют эквивалентные значения очереди), чтобы найти работника, который должен выполнить эту задачу.

Итак, для вашего примера, если предположить, что узлы сбора выскочат из очереди задач в алфавитном порядке (AD), а движение не будет выполнено, когда очередь выскочит:

(values in format [total] = [preexisting value] + [current task distance])
A Pops: 
    queue value of 1: 4 = 0 + 4 
    queue value of 2: 19 = 0 + 19
    Assigned to 1.
B Pops:
    queue value of 1: 24 = 14 + 10 (distance to B from A) 
    queue value of 2: 9 = 0 + 9
    Assigned to 2.
C Pops:
    queue value of 1: 25 = 14 + 11
    queue value of 2: 20 = 19 + 1 
    Assigned to 2.
D Pops:
    queue value of 1: 36 = 25 + 11
    queue value of 2: 41 = 20 + 21
    Assigned to 1.

Недостаток в том, чтобы делать это так: очень вычислительно.

Думал:

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

попробуйте использовать некоторую систему весов, чтобы, если дерево собиралось, вычислили какой-либо штраф за суммирование, а также некоторый бонус за расстояние. (сколько времени нужно, чтобы добраться из точки A-> B с дровами и т. д., затем вы можете сделать какой-нибудь алгоритм, который проверяет наличие ближайшего дров, проверяет его вес, а затем сравнивает, желательно, а затем использовать тот, с самым низким весом.

конечно это требует некоторой тонкой настройки. но идея проста.

Каждая работа должна иметь а) важность б) статус назначения (количество назначенных работников)

Затем работник может выбрать ту работу, которая дает ему наибольшее «вознаграждение» за раз. Награда рассчитывается по значимости, деленной на количество назначенных работников, деленное на время, которое он должен инвестировать (ходьба и выполнение работы). Если ваш работник может специализироваться на рабочих местах (например, рубка леса), он на самом деле предпочтет задачи, которые он может эффективно выполнять. Разумеется, задания следует назначать только в том случае, если они могут быть продолжены в нужный момент (например, необходимые ресурсы должны быть доступны).

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

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

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

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

• «С» имеет очень большое значение. И рабочий 1 присваивает себе «С», даже если он ушел.
• Работник 2 назначается следующим и получает более высокую награду за «С» (меньше ходьба). Таким образом, он отстраняет работника 1 от работы и присваивает себе «С». Это не стоило времени, так как мы все еще находимся в том же временном интервале моделирования. Таким образом, пользователь не увидит это переназначение задания.
• Затем работник 1 ищет другую работу. Рабочий 1 не выбивает рабочего 2 из «С», так как его награда за время не лучше. Поэтому он назначен на «А» или «Б» (в зависимости от важности). Опять же, это все еще в том же временном интервале моделирования.