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?
79
Respuestas:
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.
fuente
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:
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í.
fuente
De esta página :
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.
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í .
fuente
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.
fuente
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:
La IA se volverá cada vez menos sensible cuanto más haya, pero el jugador probablemente solo lo notará en casos extremos.
fuente