¿Cómo puede un juego manejar a todos los personajes a la vez?

31

Esta pregunta es solo para obtener conocimiento sobre cómo un juego puede manejar tantos personajes a la vez. Soy nuevo en los juegos, así que te pido perdón por adelantado.

Ejemplo

Estoy creando un juego de defensa de torres en el que hay 15 ranuras de torres donde se construyen torres y cada torre expulsa proyectiles a una velocidad determinada; Digamos que cada segundo, cada una de las torres crea 2 proyectiles y hay enemigos que marchan en el campo de batalla, digamos 70 (cada uno con 10 tipos de atributos como HP, maná, etc., que cambiarán a medida que se mueven alrededor del campo de batalla).

Resumen

Conteo de
torres = 15 proyectiles creados por cada torre por segundo = 2
Número total de proyectiles creados por segundo = 30
unidades en el campo de batalla Conteo = 70

Ahora, ¿maneja el juego esos 30 proyectiles y 70 unidades al manejarlos en 100 hilos diferentes (que es demasiado para una PC) o 1 hilo que los mueve a todos, reduce su valor, etc. (que será un poco lento , Yo creo que)?

No tengo ni idea de esto, así que ¿alguien puede guiarme sobre cómo funcionará?

Nación del desarrollador
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
MichaelHouse
Agregando a las otras respuestas ... un ejemplo de algunos juegos masivos. Skyrim tuvo la mayor parte de la actualización de la lógica del juego en un solo hilo. La forma en que maneja esto tan bien es que los NPC distantes (NPC que están a millas de distancia) se aproximan de acuerdo con su calendario. La mayoría de los MMO actualizan la lógica del juego en un solo subproceso, PERO cada parte de un mapa existe en un subproceso o servidor diferente.
moonshineTheleocat

Respuestas:

77

Ahora, ¿cómo maneja el juego esos 30 proyectiles y 70 unidades al manejarlos en 100 hilos diferentes?

No, nunca hagas eso. Nunca cree un nuevo hilo por recurso, esto no escala en redes, ni lo hace en las entidades de actualización. (¿Alguien recuerda los momentos en que tenía un hilo para leer por socket en Java?)

1 hilo que los mueve a todos reduce su valor, etc.

Sí, para empezar, este es el camino a seguir. Los "grandes motores" dividen algo de trabajo entre hilos, pero esto no es necesario para comenzar un juego simple como un juego de defensa de la torre. Probablemente haya aún más trabajo para hacer cada tic que también harás en este hilo. Ah, sí, y la representación, por supuesto.

(que será un poco lento, creo)

Bueno ... ¿Cuál es tu definición de lento ? Para 100 entidades, no debería tomar más de medio milisegundo, probablemente incluso menos, dependiendo de la calidad de su código y el idioma con el que esté trabajando. E incluso si toma dos milisegundos completos, sigue siendo lo suficientemente bueno como para alcanzar los 60 tps (tics por segundo, sin hablar de fotogramas en este caso).

tkausl
fuente
34
Más como medio microsegundo, a menos que estés haciendo algo raro. Pero lo más importante, dividir el trabajo en varios subprocesos hará que todo sea peor , no mejor. Sin mencionar que el subprocesamiento múltiple es extremadamente difícil.
Luaan
13
+1 La mayoría de los motores de juegos modernos generan miles o incluso decenas de miles de polígonos en tiempo real, lo que es mucho más intenso que el seguimiento del movimiento de solo 100 objetos en la memoria.
phyrfox
1
"Un juego simple como un juego de defensa de torres". Hmm ... ¿alguna vez has jugado Defense Grid: The Awakening , o su secuela?
Mason Wheeler
44
"Nunca cree un nuevo hilo por recurso, esto no escala en la creación de redes ..." ¡ ejem, algunas arquitecturas muy escalables hacen precisamente esto!
NPSF3000
2
@BarafuAlbino: Eso es algo extraño que decir. Hay muchas razones válidas para crear más hilos que núcleos disponibles. Es una compensación de complejidad / rendimiento / etc. como cualquier otra decisión de diseño.
Dietrich Epp
39

La regla número uno de subprocesos múltiples es: no lo use a menos que necesite paralelizar en múltiples núcleos de CPU para obtener rendimiento o capacidad de respuesta. Un requisito "x e y debe ocurrir simultáneamente desde el punto de vista de los usuarios" aún no es razón suficiente para usar el subprocesamiento múltiple.

¿Por qué?

Multithreading es difícil. No tiene control sobre cuándo se ejecuta cada subproceso, lo que puede ocasionar todo tipo de problemas imposibles de reproducir ("condiciones de carrera"). Hay métodos para evitar esto (bloqueos de sincronización, secciones críticas), pero estos vienen con su propio conjunto de problemas ("puntos muertos").

Por lo general, los juegos que se ocupan de una cantidad tan baja de objetos como unos pocos cientos (sí, esto no es mucho en el desarrollo de juegos) generalmente los procesan en serie cada tic-tic lógico usando un forbucle común .

Incluso las CPU de teléfonos inteligentes relativamente más débiles pueden realizar miles de millones de instrucciones por segundo. Eso significa que incluso cuando la lógica de actualización de sus objetos es compleja y toma alrededor de 1000 instrucciones por objeto y tic, y está apuntando a unos generosos 100 tics por segundo, tiene suficiente capacidad de CPU para decenas de miles de objetos. Sí, este es un cálculo excesivamente simplificado del reverso del sobre, pero le da una idea.

Además, la sabiduría común en el desarrollo de juegos es que las lógicas de los juegos rara vez son el cuello de botella de un juego. La parte crítica del rendimiento es casi siempre los gráficos. Sí, incluso para juegos 2D.

Philipp
fuente
1
"La regla número uno de subprocesos múltiples es: no la use a menos que necesite paralelizar en múltiples núcleos de CPU para obtener rendimiento o capacidad de respuesta". Podría ser cierto para el desarrollo del juego (pero incluso lo dudo). Cuando se trabaja con sistemas en tiempo real, la razón principal para agregar subprocesos es cumplir con los plazos y por simplicidad lógica.
Sam
66
@Sam El cumplimiento de los plazos en los sistemas de tiempo real es un caso en el que necesita múltiples subprocesos para la capacidad de respuesta. Pero incluso allí, la simplicidad lógica que aparentemente alcanzas a través del enhebrado a menudo es traicionera, porque crea una complejidad oculta en forma de puntos muertos, condiciones de carrera e inanición de recursos.
Philipp
Desafortunadamente, muchas veces he visto la lógica del juego empantanar todo el juego si hay problemas de búsqueda de caminos.
Loren Pechtel
1
@LorenPechtel También he visto esto. Pero generalmente era solucionable al no hacer cálculos de ruta innecesarios (como recalcular cada ruta en cada tic), almacenar en caché las rutas solicitadas con frecuencia, usar la búsqueda de rutas de varios niveles y usar algoritmos de búsqueda de rutas más apropiados. Esto es algo en lo que un programador experto generalmente puede encontrar un gran potencial de optimización.
Philipp
1
@LorenPechtel Por ejemplo, en un juego de defensa de torres, podrías usar el hecho de que normalmente solo hay un puñado de puntos de destino. Por lo tanto, podría ejecutar el algoritmo de Dijkstra para cada destino para calcular un mapa de dirección que guíe todas las unidades. Incluso en un entorno dinámico en el que tiene que volver a calcular estos mapas en cada cuadro, esto aún debería ser asequible.
CodesInChaos
26

Las otras respuestas han manejado los hilos y el poder de las computadoras modernas. Sin embargo, para abordar la pregunta más importante, lo que está tratando de hacer aquí es evitar situaciones "n al cuadrado".

Por ejemplo, si tienes 1000 proyectiles y 1000 enemigos, la solución ingenua es simplemente compararlos entre sí.

¡Esto significa que terminas con p * e = 1,000 * 1,000 = 1,000,000 cheques diferentes! Esto es O (n ^ 2).

Por otro lado, si organiza mejor sus datos, puede evitar mucho de eso.

Por ejemplo, si enumeras en cada cuadrado de la cuadrícula qué enemigos hay en ese cuadrado, entonces puedes recorrer tus 1000 proyectiles y simplemente verificar el cuadrado en la cuadrícula. Ahora solo necesita verificar cada proyectil contra el cuadrado, esto es O (n). En lugar de un millón de cheques por cuadro, solo necesitas mil.

Pensar en organizar sus datos y procesarlos de manera eficiente debido a esa organización es la mayor optimización individual que puede hacer.

Tim B
fuente
1
Como alternativa a almacenar toda la cuadrícula en la memoria solo para rastrear algunos elementos, también puede usar árboles b, uno para cada eje, para buscar rápidamente posibles candidatos para colisiones, etc. Algunos motores incluso hacen esto por usted "automáticamente "; especifica regiones de impacto, solicita una lista de colisiones y la biblioteca se la proporciona. Esta es una de las muchas razones por las que los desarrolladores deberían usar un motor en lugar de escribir desde cero (cuando sea posible, por supuesto).
phyrfox
@phyrfox Ciertamente, hay varias formas diferentes de hacerlo, dependiendo de su caso de uso, lo que es mejor variará sustancialmente.
Tim B
17

No cree hilos por recurso / objeto sino por sección de la lógica de su programa. Por ejemplo:

  1. Hilo para actualizar unidades y proyectiles - hilo lógico
  2. Hilo para renderizar la pantalla - Hilo de GUI
  3. Subproceso para la red (por ejemplo, multijugador): subproceso IO

La ventaja de esto es que su GUI (por ejemplo, botones) no necesariamente se atasca si su lógica es lenta. El usuario aún puede pausar y guardar el juego. También es bueno para preparar tu juego para multijugador, ahora que separas el gráfico de la lógica.

Tomáš Zato - Restablece a Monica
fuente
1
Para un principiante, no recomendaría usar hilos gráficos y lógicos separados, ya que a menos que copie los datos requeridos, representar el estado del juego requiere acceso de lectura al estado del juego, por lo que no puede modificar el estado del juego mientras lo dibuja.
CodesInChaos
1
No dibujar con demasiada frecuencia (por ejemplo, más de 50 veces por segundo) es algo importante y esta pregunta era sobre el rendimiento. El programa de división es lo más simple para obtener un beneficio de rendimiento real. Es verdad que esto requiere cierto conocimiento sobre hilos, pero adquirir ese conocimiento vale la pena.
Tomáš Zato - Restablece a Mónica el
Dividir un programa en varios subprocesos es lo más difícil para un programador. La mayoría de los errores realmente molestos provienen de subprocesos múltiples y es una gran cantidad de problemas y la mayoría de las veces simplemente no vale la pena . Primera regla: verifique si tiene un problema de rendimiento, LUEGO optimice. Y optimice justo donde está el cuello de botella. Tal vez un solo hilo externo para un cierto algoritmo complejo. Pero incluso entonces debes pensar cómo avanzará la lógica de tu juego cuando este algoritmo tarde 3 segundos en terminar ...
Falco
@Falco Usted está supervisando las ventajas a largo plazo de este modelo, tanto para el proyecto como para la experiencia del programador. Su afirmación de que es más difícil pensar realmente no puede abordarse, eso es solo una opinión. Para mí, el diseño de la GUI es mucho más aterrador. Todos los lenguajes evolucionados (C ++, Java) tienen modelos multiproceso bastante claros. Y si realmente no está seguro, puede usar el modelo de actor que no sufre de errores principiantes de subprocesos múltiples. Sabes que hay una razón por la cual la mayoría de las aplicaciones están diseñadas como lo propuse, pero no dudes en discutirlo más.
Tomáš Zato - Restablece a Mónica el
4

Incluso Space Invaders manejó docenas de objetos interactuando. Mientras que decodificar un cuadro de video HD H264 involucra cientos de millones de operaciones aritméticas. Tiene mucha potencia de procesamiento disponible.

Dicho esto, aún puedes hacerlo más lento si lo desperdicias. El problema no es tanto el número de objetos como el número de pruebas de colisión realizadas; El enfoque simple de verificar cada objeto uno contra otro cuadra el número de cálculos requeridos. Probar colisiones de 1001 objetos de esta manera requeriría un millón de comparaciones. A menudo, esto se soluciona, por ejemplo, no verificando la colisión entre proyectiles.

pjc50
fuente
2
No estoy seguro de que Space Invaders sea la mejor comparación para hacer. La razón por la que comienza lento y se acelera a medida que matas enemigos no es porque fue diseñado de esa manera, sino porque el hardware no pudo manejar la representación de tantos enemigos a la vez. en.wikipedia.org/wiki/Space_Invaders#Hardware
Mike Kellogg
¿Qué pasa, cada objeto mantiene una lista de todos los objetos que están lo suficientemente cerca como para que puedan chocar con ellos en el siguiente segundo, actualizado una vez por segundo o cada vez que cambian de dirección?
Random832
Depende de lo que estés modelando. Las soluciones de partición espacial son otro enfoque común: dividir el mundo en regiones (p. Ej., BSP, que quizás tenga que hacer de todos modos con fines de representación, o quadtree), luego solo puede colisionar con objetos en la misma región.
pjc50
3

Voy a estar en desacuerdo con algunas de las otras respuestas aquí. Los hilos lógicos separados no solo son una buena idea, sino que son muy beneficiosos para la velocidad de procesamiento, si su lógica es fácilmente separable .

Su pregunta es un buen ejemplo de lógica que probablemente sea separable si puede agregarle lógica adicional. Por ejemplo, puede ejecutar varios subprocesos de detección de aciertos ya sea bloqueando los subprocesos en regiones específicas del espacio o haciendo una exclusión mutua de los objetos involucrados.

Probablemente NO desee un subproceso por cada posible colisión, solo porque es probable que esto bloquee el programador; También hay un costo asociado con la creación y destrucción de hilos. Es mejor hacer una cierta cantidad de subprocesos alrededor de los núcleos del sistema (o utilizar una métrica como la anterior #cores * 2 + 4), luego reutilizarlos cuando finalice su proceso.

Sin embargo, no toda la lógica es fácilmente separable. A veces, sus operaciones pueden alcanzar todos los datos del juego a la vez, lo que haría que el enhebrado sea inútil (de hecho, dañino, porque necesitaría agregar controles para evitar problemas de enhebrado). Además, si varias etapas de la lógica dependen mucho unas de otras en órdenes específicas, tendrá que controlar la ejecución de subprocesos de manera que se garantice que no se obtengan resultados dependientes de las órdenes. Sin embargo, ese problema no se elimina al no usar hilos, los hilos simplemente lo exacerban.

La mayoría de los juegos no hacen esto simplemente porque es más complejo de lo que el desarrollador promedio de juegos está dispuesto / capaz de manejar para lo que generalmente no es el cuello de botella en primer lugar. La gran mayoría de los juegos están limitados por GPU, no por CPU. Si bien mejorar la velocidad de la CPU puede ayudar en general, generalmente no es el enfoque.

Dicho esto, los motores de física a menudo emplean múltiples hilos, y puedo nombrar varios juegos que creo que se habrían beneficiado de múltiples hilos lógicos (los juegos Paradox RTS como HOI3 y otros, por ejemplo).

Estoy de acuerdo con otras publicaciones en que probablemente no tendrías necesidad de emplear hilos en este ejemplo específico, incluso si pudiera ser beneficioso. El subproceso debe reservarse para casos en los que tiene una carga de CPU excesiva que no se puede optimizar mediante otros métodos. Es una tarea enorme y afectará la estructura fundamental de un motor; no es algo que puedas abordar después del hecho.


fuente
2

Creo que las otras respuestas pierden una parte importante de la pregunta al enfocarse demasiado en la parte de la pregunta.

Una computadora no maneja todos los objetos de un juego a la vez. Los maneja en secuencia.

Un juego de computadora progresa en pasos de tiempo discretos. Dependiendo del juego y la velocidad de la PC, estos pasos generalmente son 30 o 60 pasos por segundo, o tantos / pocos pasos como la PC pueda calcular.

En uno de esos pasos, una computadora calcula lo que hará cada uno de los objetos del juego durante ese paso y los actualiza en consecuencia, uno tras otro. Incluso podría hacerlo en paralelo, usando hilos para ser más rápido, pero como veremos pronto, la velocidad no es una preocupación en absoluto.

Una CPU promedio debe ser de 2 GHz o más rápida, lo que significa 10 9 ciclos de reloj por segundo. Si calculamos 60 timesteps por segundo, que las hojas 10 9 ciclos / 60 ciclos de reloj = 16666666 de reloj por el tiempo de paso. Con 70 unidades, todavía nos quedan unos 2,400,000 ciclos de reloj por unidad. Si tuviéramos que optimizar, podríamos ser capaces de actualizar cada unidad en tan solo 240 ciclos, dependiendo de la complejidad de la lógica del juego. Como puede ver, nuestra computadora es aproximadamente 10,000 veces más rápida de lo necesario para esta tarea.

Peter
fuente
0

Descargo de responsabilidad: mi tipo de juego favorito de todos los tiempos está basado en texto y escribo esto como un programador de mucho tiempo de un antiguo MUD.

Creo que una pregunta importante que debes hacerte es esta: ¿Necesitas hilos? Entiendo que un juego gráfico probablemente tenga más uso de MT, pero creo que también depende de la mecánica del juego. (También podría valer la pena considerar que con las GPU, las CPU y todos los demás recursos que tenemos hoy en día son mucho más potentes, lo que hace que sus preocupaciones sobre los recursos sean tan problemáticas como podría parecerle; de ​​hecho, 100 objetos son prácticamente cero). También depende de cómo defina 'todos los personajes a la vez'. ¿Quieres decir exactamente al mismo tiempo? No lo tendrá como Peter lo señala con razón, así que todo de una vez es irrelevante en sentido literal; solo aparece de esta manera.

Suponiendo que irá con hilos: definitivamente no debe considerar 100 hilos (y ni siquiera voy a analizar si es demasiado para su CPU o no; me refiero solo a las complicaciones y la practicidad de la misma).

Pero recuerde esto: el enhebrado múltiple no es fácil (como señala Philipp) y tiene muchos problemas. Otros tienen mucha más experiencia (por mucho) que yo con MT, pero yo diría que también sugerirían lo mismo (a pesar de que serían más capaces que yo, especialmente sin práctica de mi parte).

Algunos argumentan que no están de acuerdo con que los hilos no son beneficiosos y algunos argumentan que cada objeto debe tener un hilo. Pero (y de nuevo, todo esto es texto, pero incluso si considera más de un hilo no necesita, y no debe considerarlo para cada objeto), ya que Philipp señala que los juegos tienden a recorrer las listas. Pero, sin embargo, no es solo (como sugiere, aunque me doy cuenta de que solo responde a los parámetros de tan pocos objetos) para tan pocos objetos. En MUD soy programador porque tenemos lo siguiente (y esta no es toda la actividad que ocurre en tiempo real, así que tenlo en cuenta también):

(El número de instancias varía, por supuesto, mayor y menor)

Móviles (NPC, es decir, personaje no jugador): 2614; prototipos: 1360 Objetos: 4457; prototipos: 2281 habitaciones: 7983; prototipos: 7983. Generalmente, cada habitación tiene su propia instancia, pero también tenemos habitaciones dinámicas, es decir, habitaciones dentro de una habitación; o habitaciones dentro de un móvil, por ejemplo, el estómago de un dragón; o habitaciones en objetos, por ejemplo, ingresas un objeto mágico). Tenga en cuenta que estas salas dinámicas existen por objeto / sala / móvil que realmente las tiene definidas. Sí, esto es muy parecido a la idea de instancias de World of Warcraft (no la juego, pero un amigo me hizo jugarla cuando tenía una máquina Windows, por un tiempo), excepto que la tuvimos mucho antes de que existiera World of Warcraft.

Scripts: 868 (actualmente) (curiosamente nuestro comando de estadísticas no muestra cuántos prototipos tenemos, por lo que agregaré eso). Todos estos se llevan a cabo en áreas / zonas y tenemos 103 de ellos. También tenemos procedimientos especiales que se procesan en diferentes momentos. También tenemos otros eventos. Entonces también tenemos enchufes conectados. Los móviles se mueven, realizan diferentes actividades (además del combate), tienen interacciones con los jugadores, etc. (También lo hacen otros tipos de entidades).

¿Cómo manejamos todo esto sin demora?

  • sockets: select (), colas (entrada, salida, eventos, otras cosas), buffers (entrada, salida, otras cosas), etc. Estos son encuestados 10 veces por segundo.

  • personajes, objetos, habitaciones, combate, todo: todo en un bucle central en diferentes pulsos.

También (mi implementación basada en la discusión entre el fundador / otro programador y yo) tenemos un extenso seguimiento de listas vinculadas y pruebas de validez del puntero y tenemos más que suficientes recursos gratuitos en caso de que realmente lo necesitemos. Todo esto (excepto que hemos expandido el mundo) existió hace años cuando había menos RAM, potencia de CPU, espacio en el disco duro, etc. Y de hecho, incluso entonces no tuvimos problemas. En los bucles descritos (las secuencias de comandos causan esto al igual que los reinicios / repoblaciones de área al igual que otras cosas) se están creando, liberando, etc., monstruos, objetos (elementos) y otras cosas. Las conexiones también son aceptadas, encuestadas y todo lo demás que cabría esperar.


fuente