¿Cómo hace Dwarf Fortress para rastrear tantas entidades sin perder rendimiento?

79

En Dwarf Fortress puedes tener cientos de enanos, animales, duendes, etc. en el juego en cualquier momento, cada uno con su propia IA compleja y rutinas de búsqueda de caminos. Mi pregunta es ¿cómo esto no produce una desaceleración notable? ¿Cada enano se ejecuta en su propio hilo?

RSH1
fuente
66
Interesante pregunta. Aunque no me gusta la forma en que está redactada, ya que sería una especulación responder esta pregunta como está redactada. De todos modos, es posible que hayas visto este artículo hablando con Tarn Adams. Donde cubren brevemente la búsqueda de caminos.
MichaelHouse
25
Es absolutamente produce notable desaceleración una vez que tenga una topología compleja y más de 100 túneles enanos.
Russell Borogove
3
Sí, DF en mi experiencia es increíblemente lento en el escenario que describe.
argentage
44
Destruye un hueco de escalera principal y observa cómo baja tu velocidad de cuadros como una roca por un momento, mientras que cada enano de repente se recupera al mismo tiempo.
Mooing Duck
2
Voy a intervenir y estoy de acuerdo en que DF no es el mejor ejemplo; de hecho, DF es bien conocido por sufrir problemas de rendimiento.
Robert S.

Respuestas:

110

Cualquier sistema que tuviera un hilo para cada uno de tantos caracteres se quedaría sin recursos muy rápidamente. Los subprocesos pueden darle acceso a núcleos de procesador adicionales, pero no hacen nada intrínsecamente más eficiente, y vienen con gastos generales.

La respuesta simple es ser eficiente sobre el procesamiento de cada entidad en el juego.

  • No procese cada entidad en cada cuadro.
  • Divida el procesamiento en cosas que necesita hacer con frecuencia y cosas que no necesita hacer con frecuencia.
  • Extienda los algoritmos de larga ejecución en múltiples marcos para que no bloqueen el procesamiento en otros sistemas.
  • Asegúrese de utilizar algoritmos eficientes y estructuras de datos.
  • Almacena en caché los resultados de cálculos caros si es probable que se vuelvan a usar.
Kylotan
fuente
2
+1 por esto, por explicar realmente lo que está sucediendo, en lugar de hablar sobre gráficos como yo. :)
Matt Kemp
44
Para ser justos, también le di +1 porque olvidé ese aspecto, y es muy cierto: elimine gfx de la ecuación y es como hacer que las computadoras sean 2x o 3x más rápidas al instante.
Kylotan
Escuché que DF ahora es multiproceso, pero al menos hasta hace poco, todo se hizo en un solo hilo. (Todavía puede ser, no estoy seguro)
Mooing Duck
@MooingDuck Todavía no lo es.
Tharwen
63

Dwarf Fortress no es de código abierto, y si bien hay muchas conjeturas e ingeniería inversa que pueden explicar cómo funciona todo, en cambio me centraré en algunas técnicas básicas para optimizar un roguelike 3D (no gráficos 3D, mundo 3D) del el mismo tipo.

Como es el caso con todos los videojuegos, hay mucho humo y espejos que crean la ilusión de complejidad a partir de reglas y sistemas simples. Estos van desde el uso de números aleatorios simples para un movimiento sin rumbo hasta la cocción previa de una malla de nodos de alto nivel para encontrar caminos.

Movimiento

Hablando de pathfinding, esto a menudo puede ser un problema muy difícil de resolver para espacios grandes como puede ser un mapa DF (hasta 768x768x64 IIRC), sin embargo, el problema puede simplificarse y acelerarse de esta manera:

  • Red de nodos previamente horneados: cuando se crea el mapa, el mundo se puede dividir en fragmentos, y cada fragmento puede tener sus salidas y entradas asignadas. Cuando se actualiza un fragmento, como cuando se construye un muro, solo es necesario actualizar la red de ese fragmento.
  • Búsqueda de ruta por etapas: ejecutar una ruta en todo el mapa, celda por celda, llevaría mucho tiempo, en su lugar, buscaría en la red de fragmentos más grande, que asigna toda la conexión entre fragmentos, y luego solo ejecutaría una ruta dentro de fragmentos moviéndose de un pedazo a otro. Esto hace 2 cosas por ti. Acelera la búsqueda de ruta al dividirla en muchas piezas más pequeñas, y también permite que la unidad cambie de dirección a lo largo de la ruta cuando se actualiza un fragmento. Volvería a recorrer la red grande si alguno de los nodos que necesita para actualizarse.
  • Dirección aleatoria: cuando no se mueve hacia una meta, la unidad solo necesita caminar sin rumbo. Muchos roguelikes simplemente mueven la unidad en una dirección aleatoria, lo que se siente poco natural. Se pueden usar varias técnicas de dirección, las simples favorecen moverse en línea recta y tienen cada vez menos posibilidades de moverse en las direcciones que irradian hacia atrás, lo que tendría solo un 1% de posibilidades. Por lo tanto, la unidad a veces invierte la dirección por completo, pero solo en raras ocasiones.

No cubriré los conceptos básicos de la búsqueda de caminos. La mayoría de los roguelikes usan A *, pero existen otros métodos para desollar al gato. Mmmm Cat cuero ..

Tareas personales

Una de las principales cosas que hace que las unidades de DF exploten y se sientan vivas es su lista de objetivos personales. En verdad, muchos juegos roguelike tienen esto en un nivel básico. Esencialmente, cada unidad tiene una lista de deseos (y para sus dormitorios, tareas que podrían tomar y que está pidiendo que se hagan) y elegirán según su personalidad (estadísticas).

Algunas tareas tienen requisitos. Hacer una falda de cuero requiere que el dorf esté en tal o cual tienda que tiene X artículos. Entonces, todos se verifican y se agregan como tareas a su lista. Simple como eso.

Dado que la mayoría de las veces una unidad estará en tránsito, las verificaciones de lo que están haciendo las unidades pueden ser muy rápidas, solo unas pocas unidades elegirán en un momento dado, por lo que, en general, no hay desaceleración incluso para cientos o miles de unidades Y recuerde, en DF todo, desde abejas hasta trogloditas y árboles, son unidades.


Al hacer una investigación adicional, está claro que, de manera divertida, el DF está haciendo un trabajo terrible de encontrar caminos en general. No está dividiendo el mapa en trozos, está dividiendo el mapa en segmentos o áreas que están conectadas (lo cual es mejor que nada seguro), por lo que mi evaluación anterior es incluso menos un ejemplo de cómo funciona el DF de lo que pensaba. :) Lo que no quiere decir que DF sea nada menos que sorprendente por un millón de otras razones.

Esto demuestra que lo importante en un juego es el juego. Ni gráficos, ni gran programación, ni gran escritura, ni buena música, ni siquiera la interfaz; nada más es incluso un 1% tan importante como el juego en sí.

DampeS8N
fuente
1
1024X1024X32? Vertical es 128 o 256, creo. Es mucho más grande que 32.
Lawton
@Lawton Creo que soy incorrecto sobre el tamaño máximo, pero la altura no es tan incorrecta. Lo estoy corrigiendo. Cargué el juego y el embarque en el que estoy tiene solo 45 niveles de altura. Más podría ser 'simulado' pero no tengo acceso a ellos para cavar o construir.
DampeS8N
@ DampeS8N Acabo de cargar un mapa medio sin modificaciones y pude ver de +16 a -156, alrededor de 180 niveles. Los mapas de 40 niveles son la excepción, no la regla. Incluso si solo puede cavar 40 de ellos debido a que está bloqueado por un acuífero o lava, no es relevante, porque el área debajo todavía está poblada de diversión simulada.
Lawton
@Lawton, mi mapa solo me permite recorrer 45 niveles. Son absolutamente variables, pero no pude encontrar fácilmente los números de cada mapa accesible. También puede depender de qué versión del juego estamos usando. Al final, no es tan importante para mi respuesta.
DampeS8N
Es un puesto antiguo, pero las profundidades en la fortaleza enana dependen de las capas sedimentarias. Al igual que la corteza terrestre es más gruesa en algunos lugares. DF no es completamente geológico correcto pero el hombre lo estudia como un profesional: D.
Madmenyo
50

De esta página :

Bueno, [la búsqueda de caminos] se ve increíble desde mi punto de vista, ya que hay una tonelada métrica de personajes que lo hacen todos a la vez.

TA: Los enanos mismos se mueven principalmente con A *, con la antigua heurística de distancia de la calle. La parte difícil es que realmente no puede llamar A * si no saben que pueden llegar allí con anticipación, o terminará inundando el mapa y matando al procesador.

No sé si esta es definitivamente la forma en que evita "inundar el mapa" , pero la forma habitual de hacer esto en los juegos es usar una alteración a A * llamada Hierarchical Path-Finding A * , o HPA *. La idea es dividir la cuadrícula en muchos menos pero más grandes fragmentos, luego use A * para encontrar la mejor ruta desde cada fragmento a sus fragmentos vecinos. Puede usar esto para construir un gráfico mucho más pequeño sobre el cual ejecutar A * para cada unidad.

Pathfinding jerárquico

También puede agrupar esos fragmentos en fragmentos aún más grandes, que es de donde proviene lo "jerárquico".

Este algoritmo solo encuentra caminos casi óptimos, pero para juegos como Dwarf-Fortress generalmente está bien. Todavía se garantiza encontrar un camino si existe; y cuando no hay un camino, solo se inundará el gráfico más pequeño, ahorrando una enorme cantidad de tiempo.

También hay una abstracción de HPA * que trata con unidades que pueden atravesar un terreno pero no otros (como los acantilados, que las unidades aéreas pueden atravesar pero las unidades terrestres no pueden) . Se llama HAA * , y hay un artículo muy accesible que lo explica aquí .

Puede leer más sobre varios algoritmos de búsqueda de rutas aquí .

BlueRaja - Danny Pflughoeft
fuente
3
Este video del desarrollador de RimWorld me pareció muy esclarecedor. Es un juego similar, aunque solo en 2D. Explica los conceptos básicos detrás de la búsqueda de caminos y los beneficios de separar el mapa en regiones. youtube.com/watch?v=RMBQn_sg7DA
Sire
18

En todo caso, es todo lo contrario: todo se ejecuta en un hilo y ahora está llegando al punto en que eso se está convirtiendo en el factor de bloqueo (¡la última vez que lo revisé!)

La razón por la que es rápido es que no hay gráficos sofisticados. Es engañoso, pero lo principal que ralentiza las cosas es dibujar cosas (piense más de dos tercios de un cuadro en los títulos AAA). Como la fortaleza enana es bastante básica, dedica el resto de ese tiempo a hacer cosas interesantes.

Matt Kemp
fuente
8
Un punto de datos a favor de esto es la reescritura de OpenGL desde hace un tiempo, que recuerdo trajo un aumento masivo de la velocidad de fotogramas. Entonces, incluso haciendo los gráficos de sprites simples que DF ha tenido un impacto eficiente.
millimoose
3
+1 Gráficos de tira = cantidad masiva de tiempo libre para la informática de juego
Laurent Couvidou
2
Vale la pena señalar que los gráficos de DF son tan exigentes como cualquier juego 2D independiente moderno. Hay muchas texturas, incluso si son pequeñas y simples, y se pueden distribuir en monitores Full HD de bienes raíces. No hay efectos de partículas llamativos o lo que sea, pero el trabajo en bruto de "pintar todos estos píxeles" todavía está presente y, debido a la cantidad de llamadas de dibujo necesarias para los pequeños tamaños de mosaico, en realidad es un gran desafío realizar.
DampeS8N
Puede parecer una respuesta tonta al principio, pero esto es correcto, imagine lo que se puede hacer con una potencia de GPU de 4-12 gb y GPU de 4-12 tflops si no necesita dibujar primitivas complejas, desenvolturas, texturas, transformar vectores 3d en una matriz 2D de píxeles, sombreadores, etc.
Felype
10

No sé cómo se codifica el DF, pero la cantidad de IA realmente no me impresiona porque lo que la gente suele supervisar es que la IA no necesita precisión . Es perfectamente viable hacer la mayoría de las cosas solo cada pocos segundos. También es viable usar cálculos imprecisos. La imperfección ahorra mucho rendimiento . Puede ejecutar la rutina de toma de decisiones de 100 unidades cada 100 ms, o puede ejecutarla por 1000 unidades por segundo, tomará la misma cantidad de tiempo de CPU pero bueno ... tiene 10 veces las unidades.

Aquí hay un ejemplo simple de cómo se pueden manejar muchas unidades de lote:

int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

La IA se volverá cada vez menos sensible cuanto más haya, pero el jugador probablemente solo lo notará en casos extremos.

API-Bestia
fuente
Hay mucho que decir para avanzar en pilas de tareas que no son precisas a nivel de marco. Los juegos AAA a menudo marcan el tiempo explícitamente en cada departamento individual en porcentajes de marcos para que un departamento no pueda pisar los dedos de los demás departamentos. Si el método para animar el balanceo de los árboles basado en la velocidad y dirección del viento es lento, se procesarán menos árboles en lugar de consumir el presupuesto de otros equipos.
DampeS8N