Monstruo errante: cómo deshacerse de los problemas en el mapa

Ya en el proceso de creación de The Witness se ha convertido en uno de mis juegos favoritos. Comencé a jugarlo desde el momento en que Jonathan Blow comenzó a desarrollarlo, y no podía esperar a su lanzamiento.

A diferencia del juego anterior de John Braid , la escala de recursos y programación de The Witness estaba mucho más cerca de los proyectos AAA que de los juegos independientes. Todos los que trabajan en tales proyectos saben que la cantidad de trabajo al elegir este camino aumenta significativamente. Había mucha más gente trabajando en The Witness que en Braid , pero como con cualquier proyecto de este nivel, hay muchos aspectos que requieren más atención de la que la administración del proyecto puede permitirse.

Por lo tanto, siempre quise encontrar tiempo libre para ayudar a crear The Witness a la hora de lanzar el juego. Entonces, un día, el Día de Acción de Gracias, John y yo nos sentamos y miramos la lista de cosas en la base del código que se beneficiarían de los esfuerzos adicionales de otro programador. Habiendo decidido la importancia relativa de los elementos de la lista, decidimos que la jugabilidad será más beneficiosa si realizamos mejoras en el código de movimiento del jugador.

Walkmonster en pared

En el contexto de The Witness , el objetivo del código de movimiento de un jugador es ser lo más discreto posible. El jugador debe sumergirse completamente en una realidad alternativa, y en esta experiencia de juego cada detalle es importante. Lo último que queríamos era que el jugador notara que estaba sentado frente a la computadora y moviendo la cámara virtual.

Por lo tanto, el código de movimiento del jugador debe ser absolutamente confiable. Si un jugador se aferra a las esquinas, se atasca en las paredes, cae al suelo, desciende de una colina sin la capacidad de regresar, etc., esto destruirá instantáneamente la ilusión de inmersión y le recordará al jugador que está dentro de un proceso de juego artificial que es interferido por un sistema poco confiable desplazamientos En algunas circunstancias, esto puede incluso tener consecuencias desastrosas para el jugador si no tiene la oportunidad de resolver el problema reiniciando el juego o volviendo a cargar el (probablemente muy antiguo) "guardar". Si juegas a menudo, debes haber encontrado problemas de este tipo y sabes a qué me refiero.

Después de nuestra discusión, comencé a trabajar en esta tarea. En primer lugar, decidí escribir herramientas integradas para trabajar con el código de movimiento del jugador, para que podamos analizarlo y observar su comportamiento actual. Después de abrir el proyecto, me encontré con un problema grave que ya conocía: ¿cómo debo nombrar el primer archivo de código fuente? Esta es siempre la parte más importante de cualquier proyecto ( como dijo una vez Bob Pollard sobre los nombres de grupos musicales y álbumes ). Si le da al archivo fuente un nombre adecuado, el trabajo posterior será claro y fluido. Elija el equivocado: puede destruir todo el proyecto.

Pero, ¿cuál es el nombre del sistema para garantizar la calidad del código de movimiento del jugador? Nunca he tenido que escribir código como este antes. Cuando pensé en esto, me di cuenta de que personalmente vi un ejemplo de dicho código solo una vez: cuando jugué la versión beta temprana de Quake . Contenía errores con la ubicación de los monstruos, y en la ventana de la consola se podían ver mensajes de error que indicaban que los monstruos, en lugar de crear en la superficie de la tierra, se crean, intersectando parcialmente con la geometría de los niveles. Cada mensaje de depuración comenzó con la frase "walkmonster in wall at ..."

Bingo! Es difícil encontrar un mejor nombre para el archivo de código que "walk_monster.cpp". Y estaba casi seguro de que a partir de ahora el código se crearía sin problemas.

Movimiento al punto

Cuando desee probar el sistema, lo más importante es probarlo realmente . Aunque esta regla parece simple, las personas que escriben pruebas a menudo no cumplen.

En nuestro caso particular, es muy fácil imaginar que estamos probando el código de movimiento de un jugador sin probarlo realmente. Aquí hay un ejemplo: puedes analizar el volumen de colisiones y superficies sobre las que puedes moverte en el juego, buscar pequeñas superficies, huecos, etc. Una vez eliminados todos estos problemas, podemos decir que ahora el jugador puede moverse y caminar con seguridad alrededor del mundo.

Pero, de hecho, probamos los datos, no el código. Es muy probable que haya errores en el código de movimiento que conduzcan a un mal comportamiento incluso con datos de alta calidad.

Para evitar esa trampa, quería que el sistema de prueba estuviera lo más cerca posible del comportamiento de la persona que realmente controla el movimiento del personaje en el juego. Comencé escribiendo dos procedimientos que se convertirían en los componentes básicos de tales pruebas.

El primer procedimiento es más cercano a las acciones humanas reales. Esta es una llamada de actualización que se conecta al sistema de procesamiento de entrada de The Witness y le pasa los eventos sintetizados del teclado y el mouse. Es capaz de hacer cosas simples que una persona puede hacer: mirar a su alrededor, ir hacia un punto, mirar un punto, etc. El procedimiento realiza estas acciones simplemente emulando la interacción del usuario con el teclado y el mouse, por lo que estaba seguro de que al procesar la entrada de The Witness todo se hará exactamente como se hizo durante las pruebas. En los siguientes artículos hablaré más sobre este sistema y su uso.

El segundo procedimiento es un paso que no se utiliza en este nivel. Esta es una función llamada DriveTowardPoint , que recibe dos puntos en el mundo y, causando un sistema de colisión existente de un jugador, intenta moverse sin problemas de un punto a otro. Llevando a cabo el regreso, transmite información sobre el intento: qué obstáculos encontró en el camino y si logró llegar al punto final.

Esta función no es tan confiable como un método de prueba con entrada sintetizada, ya que elimina parte de la prueba del sistema de movimiento del jugador. Por ejemplo, cualquier condición errónea asociada con la ubicación del jugador en caso de problemas con el sistema de colisión no afectará las pruebas con esta función. Sin embargo, considero que este nivel de prueba es valioso porque puede probar vastas áreas mucho más rápido, porque no requiere la ejecución de todo el ciclo del juego, es decir, puede usarse con mucha más frecuencia en todo el mundo, y no solo en pruebas separadas .

También vale la pena señalar que esta función no transmite datos de entrada física; por ejemplo, las velocidades no están indicadas para el punto de partida. Esto se debe a que The Witness no es un juego de acción, por lo que el jugador tiene pocas propiedades físicas significativas. Los jugadores no pueden saltar, correr en las paredes, activar el tiempo de bala. Puede admitir tales comportamientos utilizando sistemas que describiré más adelante, pero agregan niveles de complejidad que no eran necesarios en nuestro proyecto.

Sea como fuere, después de implementar DriveTowardPoint podría comenzar a resolver la primera tarea del sistema: determinar dónde puede moverse el jugador a The Witness Island.

Explorando rápidamente árboles al azar

¿A dónde pueden ir los jugadores? Parece una pregunta simple, pero te sorprenderá saber cuántos juegos se lanzaron cuando el equipo de desarrollo no sabía la respuesta real. Si esto es posible, quería que The Witness fuera uno de esos pocos juegos en los que los desarrolladores antes del lanzamiento sabían exactamente dónde podía y no podía obtener un jugador, sin sorpresas.

Esto hace que el enunciado del problema (pero probablemente no sea su solución) sea muy simple: si hay una función DriveTowardPoint que determina de manera confiable si el jugador puede moverse en línea recta entre dos puntos, cree un mapa de cobertura que muestre dónde puede estar el jugador.

Por alguna razón, sin escribir una sola línea de código, por alguna razón pensé que sería mejor usar Rapidly Exploring Random Tree . Para aquellos que no están familiarizados con este algoritmo, les explicaré: este es un proceso muy simple en el que registramos todos los puntos que visitamos con referencia al punto del que vinimos. Para agregar un punto al árbol, tomamos un punto objetivo aleatorio en cualquier parte del mundo, seleccionamos el punto más cercano a él, ya en el árbol, e intentamos llegar desde este punto al objetivo. El lugar donde terminamos se convierte en el próximo punto de muestreo.

Por lo general, este algoritmo se usa para buscar rutas: alternativamente para puntos aleatorios, siempre seleccionamos el mismo punto que el objetivo. Esto inclina la exploración del espacio hacia el punto objetivo, y esto es lo que se requiere cuando nuestra única tarea es lograr el objetivo. Pero en este caso, quería crear un mapa completo de los lugares en los que el jugador podría caer, así que solo uso muestras aleatorias.

Después de implementar este algoritmo (afortunadamente, es muy simple y no requirió mucho tiempo), vi que hizo un trabajo de bastante alta calidad al explorar el espacio (los caminos se muestran por caminos blancos, y las líneas rojas verticales indican los lugares donde el algoritmo colisionó con un obstáculo) :


Sin embargo, después de observar su comportamiento, me di cuenta de que, de hecho, no necesito tal algoritmo. Por ejemplo, incluso después de muchas iteraciones, apenas puede explorar las habitaciones similares a las que se muestran a continuación, a pesar de la densa cobertura de las áreas exteriores. Esto se debe a que simplemente no puede seleccionar puntos suficientemente aleatorios dentro de las habitaciones:


Si pensara en esto antes de comenzar a trabajar, entendería que la ventaja de algoritmos como Rapidly Explorando Random Tree es que exploran efectivamente espacios de alta dimensión. De hecho, esta suele ser la razón principal de su uso. Pero The Witness no tiene espacios de alta dimensión. Tenemos un espacio bidimensional (sí, distribuido en una variedad compleja, pero este sigue siendo un espacio bidimensional).

En este espacio de baja dimensión, las ventajas de Explorar rápidamente el árbol aleatorio son débiles, y su inconveniente es de vital importancia para mi tarea: el algoritmo está diseñado para la búsqueda más eficiente de rutas a pares de puntos conectados en el espacio, y no para la búsqueda eficiente de todos los puntos accesibles de este espacio. Si tiene una tarea así, de hecho, Explorar rápidamente el árbol aleatorio tomará una gran cantidad de tiempo para resolverlo.

Así que rápidamente me di cuenta de que necesitaba buscar un algoritmo que efectivamente cubriera completamente los espacios de baja dimensión.

Relleno de inundación 3D

Cuando realmente pensé en elegir un algoritmo, se hizo evidente que, de hecho, necesitaba algo como el viejo relleno bidimensional, que se usa para rellenar áreas del mapa de bits. Para cualquier punto de partida, solo tenía que llenar todo el espacio, verificando exhaustivamente todas las formas posibles. Desafortunadamente, por muchas razones, la solución para The Witness será mucho más complicada que para un mapa de bits bidimensional.

Primero, no tenemos un concepto claro de la conexión finita de un punto. Todo el espacio es continuo. Esto es para un píxel, podemos enumerar fácilmente 4 lugares posibles a los que se puede llegar desde un punto determinado y verificar cada uno de ellos por turno.

En segundo lugar, no hay un tamaño fijo de posición en el espacio, como un píxel en un mapa de bits. Las superficies sobre las que se mueve el jugador, y los obstáculos pueden estar en cualquier lugar, no tienen un tamaño topológico máximo o mínimo, y tampoco están vinculados a ninguna cuadrícula externa.

En tercer lugar, aunque el movimiento a través del espacio The Witness puede considerarse localmente como un movimiento a lo largo de un plano, el espacio en sí mismo es en realidad una variedad cambiante y profundamente interconectada, en la que las áreas transitables del jugador están directamente sobre otras áreas (a veces puede haber varios niveles ubicados uno encima del otro) . Además, hay conexiones que varían según las condiciones del mundo (puertas abiertas / cerradas, ascensores que suben / bajan, etc.).

Dadas las dificultades descritas, es muy simple encontrar su propia opción de implementación para el llenado, que como resultado se llenará de áreas que se cruzan, faltan rutas importantes, información errónea sobre conexiones en lugares complejos de la variedad. Al final, el algoritmo será demasiado engorroso de usar, porque para tener en cuenta los cambios en el estado del mundo, debe volver a ejecutarse.

No pensé en ninguna buena solución de inmediato, así que decidí comenzar con experimentos simples. Utilizando el código de árbol aleatorio de exploración rápida que escribí, cambié la selección de puntos objetivo de aleatorio a muy controlado. Cada vez que se agrega un nuevo punto al árbol, indico que los puntos están a una unidad de distancia a lo largo de las direcciones principales desde el punto que se considerará el punto objetivo futuro, como sucede en un simple relleno bidimensional.

Pero, por supuesto, si no tiene cuidado, esto creará un ciclo de muestreo inútil. El punto se ramificará en los 8 puntos vecinos a su alrededor, pero estos 8 puntos intentarán nuevamente volver al punto de partida, y esto continuará para siempre. Por lo tanto, además de la selección controlada de puntos objetivo, necesito una restricción simple: cualquier punto objetivo que no esté dentro de una cierta distancia útil mínima desde un punto objetivo existente no se tendrá en cuenta. Para mi sorpresa, estas dos reglas simples crean un relleno bastante exitoso:


No está mal para un experimento bastante simple. Pero el algoritmo sufre de lo que yo llamo el "eco límite". Este efecto se puede ver en la siguiente captura de pantalla tomada durante el estudio del mapa:


En áreas sin obstáculos, el algoritmo funciona bien mediante el muestreo a distancias relativamente iguales. Pero cuando la intersección llega al borde, crean puntos que están "fuera de la cuadrícula", es decir, no están alineados de acuerdo con el patrón de muestras, según el cual el algoritmo llena el área abierta vecina. La razón por la que los puntos "en la cuadrícula" no crean una teselación excesivamente densa es porque cada nuevo punto que intenta regresar a uno de los anteriores encuentra el punto anterior allí y se niega a volver a contarlo. Pero al crear nuevos puntos en el borde, están completamente desalineados, por lo que nada puede evitar que regresen al espacio ya explorado. Esto lleva a la creación de una ola de muestras sesgadas, que continúa hasta que alcanza una línea aleatoria de puntos en otro lugar, lo suficientemente cerca como para que el algoritmo pueda encontrarla coincidiendo con el frente móvil de los puntos.

Aunque esto no parece ser un problema grave, en realidad es crítico. El objetivo de estos algoritmos es concentrar las muestras en áreas donde es más probable que produzcan resultados productivos. Cuanto más tiempo pasemos muestreando y volviendo a muestrear grandes áreas abiertas, menos tiempo dedicaremos a marcar las caras de esta área, que es la información que necesitamos. Como estamos tratando con un espacio continuo, y solo un número infinito de muestras puede describir su forma real, la proporción de muestras significativas a insignificantes es, literalmente, una medida de la efectividad del algoritmo para crear una superficie aceptable para un jugador.

Sin embargo, hay una solución simple para este problema en particular: necesita expandir la distancia a la cual los dos puntos se consideran "bastante cercanos". Al hacerlo, reduciremos la densidad de muestreo en lugares que no son importantes para nosotros, pero también perderemos la densidad de muestreo en lugares que son importantes para nosotros, por ejemplo, las áreas alrededor de las fronteras que queremos verificar cuidadosamente para detectar la presencia de "agujeros".

Muestreo direccional localizado

Probablemente porque comencé con el árbol aleatorio de exploración rápida, mi cerebro suplantó todas las demás ideas, excepto la idea de proximidad. Todos los algoritmos anteriores usaban proximidad para su tarea, por ejemplo, para determinar un nuevo punto que debe considerarse a continuación, o para seleccionar un punto desde el cual comenzar a llegar a un nuevo punto objetivo.

Pero después de pensar en la tarea durante algún tiempo, me di cuenta de que todo se está volviendo más lógico, si pensamos no solo en la proximidad, sino también en la dirección . Entonces se vuelve obvio, pero si trabajaste en tareas similares, entonces sabes que es fácil caer en la trampa del pensamiento de mente estrecha y no ver el panorama general, incluso si resulta ser más simple. Eso es exactamente lo que me pasó.

Cuando cambié mi visión de las cosas, el enfoque correcto para el muestreo parecía obvio. Cada vez que quería expandir mi exploración del espacio desde un punto, solicité la existencia de puntos cercanos en el entorno local. Sin embargo, en lugar de utilizar la distancia a estos puntos para la investigación, los clasificaré por sus direcciones (antes de eso solo usé ocho direcciones principales, pero quería experimentar con otros núcleos).

En cualquier dirección en la que no "veo" el punto, recorro la distancia especificada y agrego un punto en cualquier lugar donde me detuve (independientemente de si encontré algo o no). Si veo un punto en una de las direcciones, me muevo allí y compruebo si puedo llegar allí. Si puedo, entonces solo agrego un borde visible para que el usuario pueda ver fácilmente que los puntos están conectados. Si no puedo, entonces agrego un nuevo punto en el punto de colisión, definiendo el límite del obstáculo.

Este método de muestreo funcionó bien. Nos permite controlar con mucha precisión el muestreo utilizando parámetros convenientes personalizables, guardar todos los puntos necesarios y evitar teselaciones innecesarias, lo que conduce a un llenado de espacio muy rápido:


Dado que el algoritmo busca a lo largo de las direcciones, y no solo usa la proximidad, está protegido de los ecos de límites y limita el muestreo excesivo solo a los límites que necesitamos:


Además, el algoritmo no se ve afectado por transiciones de estado o problemas con múltiples complejos. Solo se trata de puntos, y estos puntos pueden estar en cualquier lugar, y se pueden agregar otros nuevos en cualquier momento. Si ya compiló un mapa del área con la puerta cerrada, luego de abrir la puerta, solo necesita colocar el único punto de investigación en el otro lado de la puerta y ordenar el algoritmo para continuar expandiendo este mapa, después de lo cual se conectará correctamente y examinará correctamente toda el área fuera de la puerta.

Además, en cualquier momento, puede cambiar los parámetros básicos y el sistema continuará funcionando. ¿Desea realizar un muestreo de área con mayor densidad? Simplemente baje la distancia predeterminada. Esto ya se puede hacer en el proceso de construcción del mapa, y el algoritmo comenzará a tomar muestras con una densidad más alta sin la necesidad de restablecer los resultados anteriores (lo que puede llevar algún tiempo).

Verificación rudimentaria de bordes

El algoritmo predeterminado ya muestra los bordes con bastante cuidado, porque las intersecciones crean puntos adicionales que no están incluidos en el patrón de muestreo, pero no necesariamente los verifica con el cuidado necesario, ya que no realiza ninguna acción especial cuando encuentra obstáculos. Me di cuenta de que, dado que sabía qué puntos se crearon durante las colisiones, los dos puntos de colisión detectados están conectados por un borde y podemos solicitar un muestreo adicional para tratar de encontrar más puntos límite en el vecindario.

No investigué activamente este enfoque, pero creé un método rudimentario para probar esta teoría, y me pareció prometedor. Después de tomar dos puntos de colisión conectados por un borde, me desplazo al punto medio del borde e intento dibujar el exterior perpendicular al borde. Si no cruza el borde a una distancia muy corta, supongo que el borde es más complejo y agrego un nuevo punto objetivo para continuar la búsqueda en esta área.

Incluso este esquema simple crea muestras densas de muy alta calidad a lo largo de la frontera sin tomar muestras innecesarias de áreas abiertas vecinas. Aquí hay un área con varios bordes, pero sin marcar bordes:


Y aquí está la misma área con bordes de verificación:


No importa cuán satisfecho esté con este resultado, me sorprendió la falta de algoritmos significativamente mejores para el muestreo de bordes, e intentaré elegir algunos métodos más en el futuro.

Victorias rápidas

Incluso habiendo invertido solo un poco de tiempo en el desarrollo y creando un código bastante simple, he logrado que Walk Monster ya esté creando resultados bastante adecuados que puedan detectar problemas reales en el juego. Aquí hay ejemplos de problemas que encontré durante el desarrollo del algoritmo:


Las pendientes a los lados de esta plataforma no deben ser transitables, pero el jugador puede caminar sobre ellas. Esto sucedió porque en el código de movimiento del jugador hay una pobre forma patológica de procesar la geometría oblicua. Ahora sé que está allí, y lo corregiré cuando se trata de garantizar su fiabilidad.


Se suponía que el Testigo era un juego contemplativo, pero preguntándose por qué parece que hay una piedra, aunque no lo es, no era uno de sus koans. Como puede suponer, este problema surgió porque alguien dejó la cantidad de colisión en el juego después de eliminar la geometría que lo denota. Esto puede suceder fácilmente, y es muy bueno que tengamos una herramienta que pueda reconocer rápidamente tales errores para que las personas no tengan que hacerlo.



Se suponía que estos objetos eran rocas intransitables, pero Walk Monster descubrió que esto no sucedió. Peor aún, Walk Monster descubrió que, por alguna razón, el camino es solo de una manera (de la captura de pantalla de izquierda a derecha), pero esto no debería ser así. Me aseguré de que el jugador realmente pueda hacer esto (lo logré). ¡Es muy interesante observar la ocurrencia de tales errores!

Preguntas abiertas

Cuando ve buenos resultados que pueden desarrollarse aún más, es inspirador. Como dije, si elige un nombre adecuado para los archivos de origen, ¡todo irá como un reloj! Pero todo este trabajo se completó en unos pocos días, por lo que está lejos de ser exhaustivo y se ha hecho mucho improvisado por completo. Si tengo suficiente tiempo para el desarrollo adicional de estos sistemas, entonces vale la pena responder varias preguntas.

Primero, ¿qué procesamiento posterior debe hacerse con los datos para que sea más fácil de visualizar? Será difícil para las personas descubrir una red no procesada de puntos y bordes, pero si mejora la descripción de los datos, esto probablemente dificultará la evaluación de áreas transitables difíciles a primera vista.

En segundo lugar, ¿cómo se pueden mejorar los patrones de muestreo alrededor de las fronteras para garantizar que se encuentre el número máximo de "agujeros"? ¿Existen buenas maneras de caracterizar la reducción de figuras en una red, y existen esquemas de teselación de alta calidad que maximicen la probabilidad de cruzar y atravesar estas figuras?

Tercero, ¿qué patrones de muestreo son mejores para llenar espacios, regulares o aleatorios? Puedo cambiar fácilmente los criterios para elegir puntos objetivo para crear patrones más aleatorios, pero no está muy claro si vale la pena hacerlo y, de ser así, qué tipos de patrones aleatorios serán mejores.

Cuarto, ¿qué otra información queremos obtener de los mapas de áreas transitables si ya hemos aprendido cómo construirlas? Por ejemplo, es muy simple expandir un sistema existente con funciones tales como buscar rutas o mapas de distancia, de modo que el usuario pueda seleccionar un punto y solicitar la ruta más corta entre él y algún otro punto, o ver un mapa de calor de la distancia entre un punto y otros puntos del mapa. ¿Serán útiles tales consultas? ¿Qué otras consultas puedo usar?

Por el momento, las visualizaciones de las áreas transitables de Walk Monster son más que suficientes para mostrar que el código de movimiento del jugador es bastante malo. Planeé pasar a crear un sistema para tarjetas de prueba nocturnas utilizando el método de simulación de entrada del usuario, pero es obvio que ya tenemos suficientes problemas para resolver sin este paso. Por lo tanto, el siguiente paso será aumentar la confiabilidad del código de movimiento del jugador. Y mientras estoy trabajando en esto, me gustaría comprobar si es posible aumentar la velocidad de ejecución en uno o dos órdenes de magnitud, porque mientras el trabajo de Walk Monster se ralentiza mucho por el sistema de frenos de colisiones.