Asignación de tareas

En un RTS donde los trabajadores tienen la tarea, por ejemplo, construir un muro, ¿cómo deciden los trabajadores qué muros construir?

El jugador decide qué muros se construirán y dónde, pero no asignan trabajadores individuales a cuadrados de muros individuales. En muchos juegos de RTS, los trabajadores simplemente realizan tareas que están cerca de ellos, pero en mi RTS quiero usar la realización estratégica de tareas explícitas en cuadros específicos como la estrategia principal, por lo que no quiero que los trabajadores tontos se agrupen en algún lugar y dejen más tareas. lejos no hecho.

Yo uso el ejemplo de construcción de muro; Podría ser la extracción de piedra, hacer un camino, recoger madera o lo que sea. La clave es que el usuario elige dónde, pero no quién.

Los trabajadores solo pueden trabajar en cuadrados adyacentes a cuadrados accesibles; los cuadrados en los que trabajan pueden ser intransitables hasta que se complete el trabajo.

Se les dice a los trabajadores 1 y 2 que extraigan los cuadrados A, B, C y D.

Pueden mover un cuadrado por partida de juego, y extraer un cuadrado requiere 10 ticks.

¿Cómo se decide qué trabajador mina cada cuadrado?

Parece evidente que 1 debería extraer A y 2 extraer C.

1 está a 4 casillas de distancia de A, por lo que habrá terminado de extraerlo en 14 ticks. ¿Dónde debería ir después y por qué?

¿Y si hubiera otro cuadrado, E, que se extraería directamente sobre B?

¿Cuál es la lógica que utiliza un trabajador para decidir dónde proceder a continuación?

Marque el nodo de recursos como ocupado, o limite el número de trabajadores por los que puede utilizar un árbol. Si se asigna un trabajo para reunirse en cierto punto, lo que realmente le está diciendo es que coseche el árbol más cercano disponible.

Dos caminos principales para esto: un enfoque realista sería evaluar y marcar los recursos de recursos antes de que lleguen. Para evitar problemas de colas extraños, brinde a los trabajadores un rango de visión para evaluar los árboles. Esto le permite al trabajador acercarse a un nodo de recursos en particular mientras camina hacia el parche. Esto da un limitado acerca de la optimización.

Sin embargo, muchos RTS (SC y SC2) no tienen trabajadores que evalúen un nodo hasta que lleguen. Esto dirige a los trabajadores a deambular hasta encontrar un nodo de recursos. Esto permite una mayor recompensa de habilidad / optimización (¿Alguna vez viste divisiones de trabajadores increíbles?) Sin embargo, la mayoría de tus jugadores solo van a boxear todo, hacer clic y se molestarán de que todos vayan primero a la misma ubicación.

La implementación exacta variará en función de cómo se agrupan los recursos. En AoE, los árboles y los peces son extensiones continuas, por lo que los recolectores pueden terminar bastante lejos a medida que avanza el juego. Pero en juegos como SC y Red Alert los recursos se encuentran en parches discretos. Entonces, un trabajador solo tiene que mirar alrededor de ese parche en particular.

EDITE después de su edición: no se preocupe demasiado por las ineficiencias de los trabajadores. Cualquier RTS que se me ocurra tiene ineficiencias laborales. Cosas como las divisiones de los trabajadores surgen de que el jugador es mejor manejando a sus trabajadores que el juego. Creo que puede estar tomando una perspectiva de programadores en esto y no diseñadores. El problema de la izquierda de la marca de verificación se puede solucionar simplemente ajustando números y haciendo que los nodos se puedan cosechar en un número discreto de viajes. Las ineficiencias de los trabajadores son evidentes para usted, porque conoce el sistema detrás de ellas. Sin embargo, si sus probadores de juego no lo notan, no se demoren demasiado.

Solución y pensamiento:

Solución: puede hacer que los nodos de recopilación se coloquen en una cola cuando se hace clic en ellos, luego, cuando un trabajo sube a la parte superior de una cola, encuentre el valor de la cola de tareas ponderado para los trabajadores y luego encuentre el vecino más cercano con el mejor valor de cola de tareas ponderado ( valor de la cola).

En su ejemplo, podría tener el valor de cola óptimo en 0 (lo que implica que no hay tareas actuales). Agregue 1 al valor de la cola para cada cuadrado que tendrían que viajar (tiempo de viaje) y 10 para cada tarea (tiempo para hacer la tarea). Elimine 1 del valor de la cola de cada trabajador por cada unidad de tiempo que pase (si el valor inicial de la cola es 10, después de 3 unidades de tiempo el valor de la cola sería 7). Luego, se encuentra el vecino más cercano (en el caso de que varios trabajadores tengan valores de cola equivalentes) para encontrar el trabajador que debe hacer esa tarea.

Entonces, para su ejemplo, suponiendo que los nodos de recolección salgan de la cola de tareas en orden alfabético (AD) y no se realice ningún movimiento mientras la cola aparece:

(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.

Lo malo de hacerlo así: altamente computacional.

Pensamiento:

¿Cómo manejará tu juego el bloqueo de los recursos? es decir, si existe una cuadrícula 4x4 donde cada nodo es un recurso, ¿pueden los trabajadores obtener los 4 nodos internos? De lo contrario, asegúrese de que los trabajadores no solo estén inactivos tratando de llegar a ellos, sino que tal vez les asignen una tarea diferente y asignen a uno de los trabajadores que reúne uno de los nodos externos a los internos una vez que el nodo externo esté completo (coloque en una cola de tareas para el trabajador).

intente tener un sistema de peso, que si el árbol está siendo recolectado, calcule algún tipo de penalización de apilamiento y también algún tipo de bonificación de distancia. (cuánto tiempo se tarda en llegar desde el punto A-> B con la madera, y así sucesivamente. Luego puede hacer un algoritmo que verifique la madera más cercana, y verifique su peso, y luego compare si es deseable y luego use el que tenga el peso más bajo.

Por supuesto, esto requiere algunos ajustes. Pero la idea es simple.

Cada trabajo debe tener a) una importancia b) estado de asignación (# de trabajadores asignados)

Un trabajador podría entonces decidir el trabajo que le da la mayor "recompensa" por vez. La recompensa se calcula por la importancia dividida por el número de trabajadores asignados dividido por el tiempo que necesita invertir (caminar y hacer el trabajo). Si su trabajador puede especializarse en trabajos (por ejemplo, cortar madera), en realidad preferirán tareas que puedan realizar de manera eficiente. Por supuesto, los trabajos solo deben asignarse si pueden continuarse en el momento adecuado (por ejemplo, los recursos necesarios deben estar disponibles).

Para evitar que se deshagan algunos trabajos durante mucho tiempo (por ejemplo, porque está muy lejos). La importancia debería aumentar con el tiempo. En el caso de la cosecha, la importancia también debe depender de la cantidad de recursos de ese tipo disponibles / necesarios en este momento (por ejemplo, unidades producidas divididas por la unidad solicitada en un período determinado).

Para evitar que los trabajadores cambien su trabajo rápidamente, permítales cambiar solo su trabajo actual, si la recompensa mejora significativamente (por un umbral dado). También puede aplicar los costos duplicados para la caminata inicial al trabajo, al calcular los valores de recompensa por tiempo. Además, debe permitir volver a calcular el trabajo óptimo de los trabajadores uno después del otro, no todos al mismo tiempo.

Además, agregue algo de aleatoriedad a las recompensas calculadas. Esto causará una mejor distribución de los trabajadores a diferentes trabajos (de esta manera no solo "todos" van a hacer el mismo trabajo). Pero, este efecto ya se reduce recalculando en serie el siguiente trabajo óptimo para un trabajador y adaptando el número de trabajadores ya asignados (más trabajadores en el mismo trabajo reducen la recompensa esperada).

El algoritmo tal vez deba adaptarse un poco, si sus trabajos solo pueden asignarse a un trabajador. Si este es el caso, haga lo siguiente: Un trabajador elige el trabajo con la mayor recompensa por tiempo (importancia dividida por el tiempo individual necesario). Si otro trabajador puede hacer el mismo trabajo con una recompensa esperada más alta por tiempo, inicia al trabajador asignado actualmente. El nuevo trabajador "desempleado" intenta encontrar otro trabajo. En su ejemplo, esto podría ser así:

• "C" tiene una importancia muy alta. Y el trabajador 1 se asigna a "C", incluso él está más lejos.
• El trabajador 2 se asigna a continuación y tiene una recompensa más alta por "C" (menos caminar). Entonces, saca al trabajador 1 del trabajo y se asigna a sí mismo a "C". Esto no costó tiempo, ya que todavía estamos dentro del mismo segmento de tiempo de simulación. Por lo tanto, el usuario no verá esta reasignación del trabajo.
• El trabajador 1 está buscando otro trabajo. El trabajador 1 no saca al trabajador 2 de "C", ya que su recompensa por tiempo no es mejor. Entonces se le asigna a "A" o "B" (dependiendo de la importancia). Nuevamente, esto todavía está dentro del mismo intervalo de tiempo de simulación.