miércoles, 9 de marzo de 2016

Proctofantasmista

Después de una ardua investigación me-aburro-etimológica de qué significa Proctofantasmista, deposito aquí mis conclusiones para que perduren eternamente.

El término lo usó Goethe en su obra Fausto para referirse a uno de los personajes. El original alemán decía Proktophantasmist. Juega con el griego pero no significa una mierda más allá de la disección que se quiera hacer del palabro.

Una primera autopsia podría arrojar estos resultados:

prokto / procto -> ano
phantasmist / fantasmista -> iluso 
(hay más opciones con este último pero elijo esta por sus connotaciones negativas)

Alguien podría decir a bote pronto que entonces significa "tonto del culo" y se estaría acercando bastante.

Goethe llamó "Proctofantasmista" a un personaje para relacionarlo con uno de sus detractores en la vida real: Christoph Friedrich Nicolai, un escritor de la época.

Se decía que el pobre Nicolai sufría una dolencia (intestinal, anal o del culo) que le hacía sufrir fuertes dolores y hasta alucinaciones. La localización del problema en la zona final del tubo digestivo o alrededores podría ser el motivo de usar el término procto. En cuanto a fantasmista, puede que Goethe lo usara, más que por las alucinaciones, por desvaríos o pulmonías varias surgidas de la pluma de Nicolai contra su persona.

También se comentaba en aquellos tiempos que Nicolai se sentaba sobre sanguijuelas para aliviar su malestar mientras escribía (otro argumento para procto). Esto podría no sólo arrojar más luz sobre el significado de nuestro vocablo sino también explicar alguna broma de sanguijuelas que hay en Fausto: «(...) y cuando las sanguijuelas se relaman en sus posaderas, se curará de los espíritus y del espíritu»

Así pues, si bien la traducción literal podría ser "tonto del culo", el sentido es más amplio, refiriéndose a una persona "ilusa" o "fantasiosa" que tiene afecciones ano-rectales y que... Va, sí, casi mejor "tonto del culo".

En alguna edición en inglés (no sé si en todas) tradujeron Proktophantasmist por A Rationalist, sustituyendo el nombre por el sentido o la función del personaje. Efectivamente, el personaje es un racionalista, o más bien un ilustrado, que pretende sin éxito doblegar al mundo con sus razonamientos. Esto contrastaría con la mentalidad de Goethe propia del Romanticismo y enfrentada a la Ilustración. (El Proctofantasmista decía algo así a los espíritus: «¿Pero cómo seguís ahí? ¿No os hemos explicado ya?»)

Llamarlo A Rationalist facilita la comprensión de la obra pero se carga el juego de Goethe con el misterioso y cachondo término.

Y bueno. Que "proctofantasmista" hay que decirlo más.

domingo, 18 de enero de 2015

Juegos artesanales

Anoche de madrugada me dio por continuar una partida que tenía empezada en Vagrant Story y saqué esta foto a la tele porque me hizo gracia la sugerente pose de Samantha:

A pesar de la mala calidad de la foto (por ahí tiene que haber mejores imágenes de este mismo momento), se aprecian detalles técnicos y artísticos muy interesantes.
De entrada el plano es la hostia. Este juego se las ingenia para que las secuencias se vayan deteniendo en puntos que te permitan leer los textos, pero con encuadres muy cinematográficos mientras la escena se mantiene "viva" gracias a movimientos leves de los personajes o a lentos travelings de cámara. 
También se aprecia que las texturas tienen pintada la iluminación a mano. Por ejemplo, toda la piel de Samantha es una textura bellísimamente pintada. Las luces y sombras de su cara me recuerdan algo a las de Anjelica Huston en La Familia Addams, aunque en el juego son más sobrias.
Vagrant Story salió en la última época de la primera PlayStation y técnicamente estaba a caballo entre esa generación y la siguiente, con las lógicas limitaciones de la resolución. Puede ser perfectamente el juego con la tecnología gráfica más potente de la época. Los contornos iluminados de los personajes según la procedencia de la luz en cada momento eran una proeza técnica impropia de aquellos tiempos.
Pero, como digo, el grueso de la iluminación se pintaba a mano, algo que se siguió haciendo con muy buenos resultados incluso para PlayStation 2 (tómese como ejemplo Metal Gear Solid 2).
Estos detalles de los encuadres tan estudiados mientras se leen los textos, o la iluminación pintada a mano en las texturas, son una pista de por qué los gráficos de los juegos japoneses sobresalían tanto en aquellos tiempos y por qué decayeron tanto al principio de la siguiente generación.
En los juegos japoneses había mucha artesanía. Se trabajaba mucho en cuidar cada detalle y no escatimaban esfuerzos en retocar pixel a pixel lo que hiciese falta para que quedara exactamente como ellos querían. (Lo mismo podría decirse de otros apartados como la jugabilidad, aunque no es el objeto de esta entrada.)
Esa forma de trabajar de los japoneses era perfecta para obtener buenos resultados porque controlaban (con mucho trabajo, eso sí) el contenido visual que podían abarcar aquellas máquinas. A los desarrolladores occidentales, por su mentalidad sobrecientífica, les cuesta asumir la manualidad y siempre han pretendido implementar motores que gestionaran todo de la forma más automática posible. Este enfoque apenas cabía en esas generaciones de máquinas y de ahí que los resultados de los japoneses fuesen, en general, apreciablemente mejores. Por supuesto que había tecnología en los trabajos de los japoneses, pero su complementación manual era tan alta que permitía marcar diferencias.

Las cosas cambiaron drásticamente con las máquinas que vinieron tras PlayStation 2. Los motores soñados de los occidentales por fin eran generosamente posibles. Ahora sí que se podían tratar modelados, texturas, iluminaciones y demás avituallamiento gráfico de forma automática, lo que producía unos resultados espectaculares.
Sin embargo, las técnicas artesanales de los japoneses ya se quedaban muy cortas. Esa forma de trabajar no lucía si era comparada con la occidental. Pintar texturas HD a mano para darles detalle o simular iluminación era una verdadera jodienda que además no lograba los resultados de los motores occidentales, los cuales, para mayor humillación, hasta permitían programar efectos artísticos que simulaban con solvencia el buen gusto.
Y así comenzó el declive de la era de los juegos triple A artesanales. Supongo que eso los hace aún más apetecibles y encantadores, especialmente tras sufrir algún arrebato de nostalgia propio de la edad. En teoría los juegos indies están en condiciones de recuperar la artesanía, pero debido a la sofisticación de las herramientas actuales no siempre se apuesta por ello pese al aspecto retro que tienen muchos.
Afortunadamente Vagrant Story sigue ahí.


jueves, 11 de septiembre de 2014

Problemas de frame-rate en Android por bucles for-each para ArrayList

Hablamos de Java, por supuesto. El uso de los bucles for-each en Android al recorrer colecciones ArrayList, fue un terrible quebradero de cabeza en el desarrollo de Boo & Marung que incluso provocó problemas de diseño. Mucha gente tiene dificultades para mantener estable la tasa de frames y nunca imagina que se debe a este asunto.

Un bucle for-each es un tipo de bucle para recorrer colecciones que es muy recomendable en las buenas prácticas de programación:
ArrayList<Enemigo> listaDeEnemigos;
...
for (Enemigo enemigo : ListaDeEnemigos) {
    enemigo.pintar()
    ...
}
El problema de este tipo de bucles para recorrer listas ArrayList en Android es que, al menos en las máquinas virtuales y versiones en las que yo lo he probado, ocasiona graves problemas de rendimiento si ejecutamos estos bucles frecuentemente.

Google reconoce en voz baja y parcialmente este problema:
With an ArrayList, a hand-written counted loop is about 3x faster (...) consider a hand-written counted loop for performance-critical ArrayList iteration.
Fuente: http://developer.android.com/training/articles/perf-tips.html#Loops

Pero Google se queda corto. El estropicio en aplicaciones en tiempo real es mayúsculo si se usan mucho estos bucles porque el consumo de memoria es tal, que el recolector de basura se dispara, provocando importantes problemas de rendimiento.

No me consta que esto ocurra en otras plataformas, sino solo en Android, por lo que no hay motivo para no usar este tipo de bucles en ellas; al contrario, es lo deseable.

El caso es que este asunto provocó en mi juego problemas de diseño porque ante la falta de estabilidad de los frames en los primeros prototipos, no pensé que se debía a este tipo de bucles y eso me hizo probar métodos cada vez más rebuscados de mejora del rendimiento.

Pero, ¿por qué pasa esto cuando se trata de ArrayList en Android? Ni idea. Son cuestiones de implementación de la máquina virtual por parte de Google que, espero, se solucionarán algún día, si es que no lo están ya.

Así pues, si tienes problemas en tus juegos en Android con la tasa de frames, y no sabes qué más hacer para mejorarla, fíjate si utilizas bucles for-each para recorrer colecciones ArrayList (con otras colecciones en teoría no hay problema). Si es así, prueba a cambiarlos por bucles clásicos:
ArrayList<Enemigo> listaDeEnemigos;
...
for (int i = 0, n = listaDeEnemigos.size(); i < n; i++) {
    Enemigo enemigo = listaDeEnemigos.get(i);
    enemigo.pintar()
    ...
}
Otros métodos para mejorar el rendimiento incluyen, por ejemplo, evitar crear y liberar objetos durante el juego en sí, dejando estas tareas para los momentos de carga de niveles. O utilizar un patrón de diseño Flyweight para aliviar el uso de memoria. Técnicas que, afortunadamente, sí se mueven en el ámbito de la lógica.

jueves, 3 de julio de 2014

Boo & Marung: lo que quiso ser y lo que es

Comento en esta entrada algunos aspectos jugables que definen a Boo & Marung, así como ciertas ideas iniciales que cambiaron o se desecharon.

Boo & Marung quiso ser un juego humilde desde el principio, sin más aspiraciones que la de satisfacer las ganas de realización de un aficionado como yo. Los mismos diseños visuales, de corte desenfadado e infantil, pretendían reflejar esto.

Cacho de una de las libretas que me acompañaron

Y desde luego ha quedado humilde; más de lo pretendido. Me hubiese gustado un juego más ágil, tipo Pac-Man, donde el lanzamiento del bumerán (¿algo que ver con el nombre del juego?) fuese más frenético, con personajes más grandes y espacios más pequeños, menos puzles y más acción. Sin embargo, esto fue cambiando poco a poco a lo largo del proyecto sin pretenderlo. Me gustaba el nuevo enfoque que le estaba dando aunque ahora pienso que los puzles son una salida más fácil que la acción. Eso sí, el "sigilo" ha ganado con el enfoque final.


También quería al principio unas escenas automáticas totalmente distintas al resto del juego, desde una perspectiva lateral y mezclando bitmaps y gráficos 2D vectoriales. Iban a incluir "líneas auxiliares" que, junto con el resto, vibrarían para dar la impresión de un dibujo hecho a mano. Esto fue descartado a mitad del proyecto por el inmenso trabajo que requería y por la poca calidad que yo era capaz de darle. Deshacerme de esta característica fue como soltar un lastre agobiante. Revitalizó el proyecto y me ayudó a descubrir que, a veces, es necesario renunciar a ideas que considerábamos básicas. Eventualmente podemos llegar a la conclusión de que eran incluso desacertadas.

Boceto del estilo descartado en las escenas

Este tipo de escenas más elaboradas se debía a que el juego iba a tener un trasfondo de aventura mucho más profundo y a la vez más explícito. No obstante, de esta idea de recrear animación a mano quedó una curiosa escena hacia la mitad del juego que comentaré en otra entrada dedicada a curiosidades y secretos.

Algo que sí tenía claro al comenzar, y que se ha mantenido hasta el final, es que quería un juego para tocarlo. Siempre he sido partidario de que los juegos aprovechen la plataforma en la que corren, y ya que iba a ser un juego para pantalla táctil, quería sacarle partido a eso. Boo & Marung no puede jugarse en condiciones si no es con pantalla táctil. Su diseño requiere de esta característica y creo que el juego se lleva muy bien con ella.


Aunque no lo parezca el juego realiza un trabajo considerable en la interpretación de las entradas. Analiza lo que hace el jugador cuando toca la pantalla para intentar averiguar lo que realmente pretende. Así, desliza los puntos tocados, si estos dan en sólidos, hacia zonas libres cercanas. O ajusta el trazado del bumerán a las paredes para que pase por sitios estrechos. O ignora la entrada si cree que el usuario se ha arrepentido a la hora de desplazar a Boo o de lanzar a Marung. Como digo, esto se ha intentado cuidar mucho y puedo garantizar que en las primeras versiones, haciendo caso de las entradas "a lo salvaje", la experiencia era muy inferior a la final.

Por cierto, me da vértigo mirar atrás y ver la evolución del juego desde sus primeros prototipos... Este era el aspecto tras unos 6 meses de desarrollo:

video

El juego iba a contar al principio con nada menos que ¡300 pantallas! Finalmente quedó en unas 75, creo que suficientes para la dificultad del juego.

A este respecto me hubiese gustado haber cuidado algo más la curva de dificultad. Llevaba un Excel donde registraba, entre otras cosas, la dificultad estimada de cada pantalla, para así cuidar la mencionada curva y sus oscilaciones, pero claro, sin un testeador que me diera su opinión, todo quedaba demasiado a mi criterio.

La duración es algo que precisamente por eso no tengo muy claro de cuánto supone para el jugador medio. Yo puedo terminar el juego cogiendo todas las gemas en poco más de una hora, pero claro, yo me sé todos los puzles y secretos xD.

Lo que sí he cuidado es que el juego fuese de más cantidad a menos; con ello quiero decir que cada nueva ambientación tiene menos contenido que la anterior. Esto fue deliberado porque me gusta que cuando juego me dé la sensación de que cada vez voy más rápido. Esto también ayuda a dinamizar el juego.

Otra de las ideas que tuve en consideración incluso antes de empezar, era la utilización de inteligencia artificial. Por supuesto, nada del otro mundo, pero sí algunas características típicas de los juegos: como un algoritmo de pathfinding o máquinas de estados finitos para los estados de los personajes, entre otras cosas.

Algo que contribuyó a enriquecer mucho el juego, y que en parte fue el causante del cambio de juego de acción a juego de puzles, fue el sistema de puertas-pulsadores-bloqueadores.


Junto con mis amigas las ovejas solares, las sunsheep, los puzles disponían de la base que necesitaban. Tenía una gran preocupación de que los puzles, al igual que el resto de reglas del juego, no funcionaran. Ha sido muy satisfactorio comprobar que sí han resultado: suponen limitaciones sin fisuras que el jugador debe superar de la manera prevista. Con una mecánica tan amplia como la que ofrece el juego (para mi nivel), esto ha sido un logro extraordinario.

A propósito de las ovejas, implementar su física fue un pelín complicado. No tanto por la aritmética de los vectores ni por la detección de colisiones, ¡sino por eso y todo lo demás que hubo que tener en cuenta! Para empezar había una importante cuestión de jugabilidad que había que resolver. Al principio las ovejas podían ocupar cualquier posición de la pantalla, no teniendo que acabar necesariamente centradas en una de las celdas invisibles en las que está dividido cada nivel. Este exceso de libertad complicaba innecesariamente la vida del jugador.

Si las mueven se ponen contentas, las muy jodías ^^
Con el proyecto bastante avanzado, supuse que el jugador sólo estaba interesado en que estos bichejos ocuparan celdas en su punto central. Entonces se me ocurrió la idea de hacer que cada celda fuese un "sumidero" y que todas las ovejas acabaran centradas en una celda cuando bajaran de un umbral de aceleración.

Otra de las cuestiones a considerar fue que las ovejas rebotaran con más fuerza contra las paredes cuando había un personaje cerca, para así evitar quedar atrapadas entre él y un bloque. O que escaparan de una puerta que se cierra. Mil detalles, como con todo.

Dicen los cánones que todo juego debe tener un valor que conseguir por el jugador, entiéndase por ello puntos, monedas y cosas así. Aunque no soy muy de seguir cánones, no quería pasarme de listo e incorporé esta idea, de lo cual me alegro. Opté por gemas en un homenaje onanista a Lucky Rain. Las gemas son uno de los pocos elementos de estado persistente del juego, es decir, si vuelves a una pantalla donde ya cogiste alguna gema, esa gema no aparece.

Not redeemable for cash

Otros elementos singulares fueron los electrificadores, necesarios para electrificar ovejas y aturdir así a ciertos tipos de enemigos. Veía necesario algo de este tipo aunque no sabía exactamente por qué. Ahora, aunque no tengan la contundencia de otros juegos, sé lo que son: powerups


La variedad de enemigos no fue algo que me preocupara mucho. Sabía que habría pocos tipos y así ha sido. Lo malo es que el aspecto también suele ser parecido, lo que incrementa la sensación de monotonía.


Y no sólo eso, sino que las animaciones también fueron reducidas al mínimo. Esto no estaba previsto. Es más, conseguí hacer un sistema de controladores de animación que no quedó mal, pero hacer gráficos seguía siendo un suplicio para mí y además ya me había quedado sin tiempo. Así que tuve que tirar de ingenio: lo único que dibujé de los enemigos (y del protagonista) fue la imagen anterior. A partir del gráfico de un personaje, roto e invierto bitmaps para generar las posturas (dos) y las orientaciones (ocho) que puede tener. Minimalismo minimalista.

En otra entrada lloraré más profusamente sobre lo desafortunado que es dedicar tiempo y energía a implementar sistemas que luego apenas puedes lucir por lo costoso que resulta crear recursos para ellos.

Casi al final del todo añadí algunos efectos de luces, chispas y animaciones sencillas del decorado (todo hecho a mano, como el resto). Me agradó comprobar que el sistema montado soportaba bien este tipo de añadidos, además de que el aspecto lo agradecía bastante.


En mis planes iniciales estaba crear tres o cuatro jefes finales para los que ya tenía algunas ideas. Pero a seis meses del final aún no tenía ninguno implementado, así que tuve que tomar otra dura decisión, sólo haría un jefe final. Para mí lo importante era demostrarme que podía "romper" la mecánica general del juego, establecer una excepción a las reglas del mismo, y para eso con uno bastaba. Sin embargo, reconozco que cabía refinar más la mecánica de este jefe y la interacción con él.

Del jefe no pongo imagen para dejar un halo de misterio que deje al público sin dormir... Bueno, sigue en la línea modesta del resto pero sí difiere más en aspecto y tamaño.

El juego guarda la partida automáticamente en uno de tres slots, hecho que se produce al abandonar una pantalla. Esta característica es muy típica de los juegos y no quería dejarla pasar, además de que es muy apropiada para un juego de smartphone.

Ya que he mencionado que es un juego de smarthphone, también tuve que tener en cuenta esto para anticiparme a interrupciones como llamadas que se reciben mientras juegas o jugadores que quieren salir del juego con mucha rapidez. Había que hacer el juego robusto ante este tipo de sucesos.

Diré también que la ayuda iba a consistir en secuencias animadas. De nuevo por la falta de tiempo, quedó en imágenes estáticas apoyadas por iconos y textos. Creo que son suficientes pero indudablemente lo otro habría quedado mejor.

Hay muchísimos aspectos sobre los que hablar, si he mencionado estos es por mencionar algunos, no porque sean los más importantes. En futuras entradas hablaré de forma más concreta de algún otro que me parece curioso, aunque siempre quedarán cosas sin mencionar de mis trabajadas libretas y mi refactorizado código.

viernes, 20 de junio de 2014

Pathfinding en Boo & Marung (y II)

Continuamos la entrada anterior y finalizamos la revisión del pathfinding de Boo & Marung, recurriendo de nuevo a detalles más técnicos de lo habitual. Descansaremos de esto en la próxima entrada.


Integración del origen y el destino

Habíamos obtenido un grafo a partir de las esquinas de los bloques que nos permitiría bordear obstáculos aplicando un algoritmo A*. Mostramos de nuevo el grafo proyectado sobre el mapa:


Pero lo normal será que tanto el origen como el destino de un actor no coincidan con estas esquinas. Incluso puede que el actor no esté centrado en una casilla al recibir la orden de desplazarse.

Supongamos primero el caso general. El actor está centrado en una casilla y recibe la orden de desplazarse a un destino, el cual siempre estará centrado en una casilla. En la siguiente imagen el origen es el cuadro verde y el destino el rojo.


Estamos tratando, pues, el caso en el que no se pueda ir directamente de un punto a otro, algo que averiguamos con el algoritmo de conectividad.

Lo que se hace es tratar estas dos celdas como dos nuevos nodos del grafo, en el cual los integramos. El origen sólo tendrá arcos de salida y comprobaremos si puede conectarse a cualquiera de los nodos (esquinas) que ya existen.


Lo mismo hacemos con el destino teniendo en cuenta que sus arcos serán de entrada. En este ejemplo sólo conecta con un nodo esquina.


A esta acción de incluir nuevos nodos en el grafo la llamo integración y a la posterior de quitarlos la llamo desintegración. Podríamos copiar el grafo, integrar los nuevos nodos y luego desechar todo el conjunto en lugar de desintegrar los nodos añadidos, pero por la estrategia que he seguido de minimizar los objetos creados y desechados durante el juego, opté por modificar de nuevo el grafo para dejarlo otra vez sólo con las esquinas, algo que no es muy costoso.

De esta manera tenemos el grafo completo:


El grafo será procesado por el algoritmo A* para devolver la lista ordenada de nodos con el recorrido más corto:


Quiero recalcar que aunque la detección de esquinas y la construcción del grafo principal se hace al cargar cada nivel, la integración y desintegración de orígenes y destinos se hace durante el juego.

Veamos ahora el caso que dejamos pendiente, en el que el actor no está centrado en una casilla, quizá porque se le ordena ir a otro sitio cuando estaba realizando un desplazamiento. Sea de nuevo la casilla verde el origen (descentrada) y la casilla roja el destino:


Calculamos la ruta suponiendo que el actor está centrado en la casilla más cercana, que es la que hay un poco arriba y a la izquierda del origen:


Pero luego, una vez obtenido el resultado, modificamos la primera casilla a visitar según sea lo más apropiado, y siempre teniendo en cuenta que no haya bloques sólidos cercanos que nos impidan ese recorte. En el ejemplo sería más apropiado que la primera casilla del desplazamiento sea la de la arriba a la derecha:


De hecho en Boo & Marung se emplea una heurística algo más anticipativa que hace que el desplazamiento inicial se dirija incluso más a la derecha.

Para cuando estaba implementando todo esto, ya se me había quitado el complejo a la hora de hacer ajustes posteriores a los cálculos teóricos. En los meses que pasaron entre Lucky Rain y el inicio de este juego, me metí entre pecho y espalda libros y artículos de Inteligencia Artificial aplicada a juegos con ejemplos más o menos reales. En todos los casos eran necesarios este tipo de ajustes posteriores.

Una cosa es hacer un ejemplo para explicar un algoritmo de IA y otra es que esa solución tenga que convivir con otros aspectos de un juego real. Esos ajustes posteriores se extendían además a elementos dinámicos, como puertas que se pueden cerrar en cualquier momento, enemigos en la ruta, etc.

Lo importante es que los ajustes no sean costosos y que estén desacoplados del sistema que ajustan, para que así sean fácilmente tratables.

Pues bien, llegados a este punto en el que tenemos una lista de celdas a las que ir desplazándonos en orden, el movimiento en sí de una a otra (el "subproblema" del que hablamos en la entrada anterior) se hace con aritmética de vectores. De alguna forma es la parte inversa al problema inicial. Si partíamos de la necesidad de traducir el espacio del juego a un espacio algebraico en el que calcular la solución más fácilmente, ahora necesitamos traducir esa solución al espacio del juego y aplicarla.

Por mencionar algún aspecto concreto, dado un vector de trayecto de un actor, un método de ese vector como el siguiente lo modificaría para dirigirse del origen al destino en incrementos de "magnitud" (que representaría la velocidad).
public Vector dirigir(Vector vOrigen, Vector vDestino, float magnitud) {
        set(vDestino).restar(vOrigen);
        normalizar().multiplicar(magnitud);
        return this;
}
El trayecto debería aplicarse en cada frame hasta alcanzar el destino. Esto de nuevo necesita ajustes o supervisiones para evitar, por ejemplo, pasarnos si estamos muy cerca del punto final.


El algoritmo de conectividad

Para finalizar, comentaré algo sobre el algoritmo de conectividad. Es muy versátil porque me ayudó a determinar la distancia entre dos celdas, saber si eran conectables (esto es, si no tenían obstáculos entre ellas y había un pasillo suficientemente ancho entre ellas), si un actor tenía a otro a la vista, etc.

La idea es sencilla, se trata de dibujar una línea entre dos celdas pero en unidades de celdas completas. Básicamente es un algoritmo de dibujado de rectas típico de Informática Gráfica.

La novedad para mí es que lo implementé desde cero según mi criterio. Imaginemos que tenemos estas dos celdas para determinar su conectividad:


Primero se obtiene el rectángulo de celdas más pequeño que las abarca:


Determinamos el lado más largo y el más corto para establecer el número de segmentos y la longitud de los mismos que necesitaremos para conectar ambos extremos mediante celdas. En este ejemplo bucólico y pastoril salen tres segmentos de dos celdas cada uno (en otros casos la solución es más irregular). El origen y el destino forman parte del primer y último segmento respectivamente.


Es muy rápido preguntar en las pocas celdas resaltadas si hay una sólida. En cuanto encontremos una dejamos de preguntar puesto que se trata de dos puntos no conectables. Nótese que el algoritmo también ofrece fácilmente una aproximación de la distancia entre los extremos, aunque yo he preferido la distancia real.

Sin embargo, esta solución tal cual podría hacer que se considerasen conectables puntos por cuya ruta de conexión el actor no cabe o por la que sencillamente no puede "ver", como se muestra aquí:


Por ello es necesario ensanchar la recta dentro del rectángulo (no hace falta fuera), a modo de antialiasing, y hacer comprobaciones también en esa ampliación que en la siguiente imagen mostramos con casillas azules.


El dibujo no pretende reproducir exactamente los resultados reales del algoritmo de conectividad, sólo mostrar la idea general en la que se basa. La determinación de las celdas a ampliar se hace por vecindad de las amarillas iniciales.

Si todas las celdas resaltadas están libres, garantizamos que un actor que tuviera que desplazarse de una celda a otra, cabe por esa ruta. Lo mismo si estamos preguntando si un actor orientado hacia otro, puede ver a ese otro. Como dije en la entrada anterior, el ensanchamiento es generoso, puede que demasiado, porque un obstáculo cercano podría invalidar la visibilidad entre dos actores, exigiendo que el espacio entre ellos estuviese ampliamente despejado. Pero este enfoque es razonablemente bueno para los pocos y rápidos cálculos que requiere.

Reitero que siempre necesitaremos hacer ajustes y comprobaciones posteriores durante el desplazamiento para tener en cuenta puertas que se cierran y otros actores.

Todas las operaciones de este algoritmo son muy rápidas de hacer y no tiene muchos pasos, por lo que su empleo es continuo durante el juego con un coste bastante asumible.


Conclusiones

Para mí resulta bonito investigar algoritmos sencillos de Inteligencia Articial que sean razonablemente eficientes para el problema que han de resolver. He aprendido que tras las bases teóricas normalmente hay que aplicar ajustes posteriores. Esos ajustes no sólo suelen ser necesarios, sino que a menudo facilitan el diseño del algoritmo principal, dejando para una fase posterior el tratamiento de casos especiales.

La construcción del grafo para el algoritmo A* mediante las esquinas de los bloques, fue una idea que se me ocurrió hace muchísimos años y que ahora he tenido la oportunidad de comprobar. La implementación del algoritmo de conectividad fue más reciente. Se me ocurrió en un bar mientras asentía a mis acompañantes como un autómata; mi mente estaba en estas ideas que acabé apuntando en una servilleta de papel. Todo esto es una muestra de lo que me gustan esta clase de temas.

Por eso explico así las cosas, dando las ideas básicas más que detallando el código, porque así es como yo quisiera encontrar las claves del desarrollo de videojuegos cuando busco ayuda. (Salvo, claro está, que se trate de un problema de implementación concreto.)

En Boo & Marung lo pasé muy bien haciendo estas cosas aunque hubo momentos en los que temí por mi salud mental por abarcar tantos aspectos diferentes.

Por supuesto, todo es mejorable y estoy abierto a comentarios y críticas, así como a ofrecer más detalles a quien me los pida ;)

Escribo estos artículos porque necesito expresar mi agradecimiento a la comunidad en Internet que tanto me ha ayudado sin saberlo, aportando soluciones en foros que luego son leídas por gente como yo. Esto es una humilde aportación para quien la considere útil y hasta para quien no, porque son caminos que se ahorrará explorar.


miércoles, 18 de junio de 2014

Pathfinding en Boo & Marung (I)

Este artículo es más técnico que otros. Avisaré de esta característica al principio de cada entrada.

En Boo & Marung se hace un uso intensivo de un algoritmo de pathfinding. Se trata de una implementación del algoritmo A*, concretamente del algorítmico que encontré en la versión inglesa de Wikipedia. No quise buscar más.



La forma en que los actores (como yo los llamo) hacen uso de esto en las escenas y en sus estados requeriría otra entrada. Aquí sólo hablaré de aspectos más relacionados con el algoritmo en sí y con la representación del espacio del juego para este fin.

La acción de encontrar un camino en el laberinto que conforman los bloques de cada nivel, lo llamé "pacificar", derivada de path, en su acepción de ruta, que en inglés de mi barrio se pronuncia como "paz". Pues eso, se trataba de encontrar la paz... Jajajaja...
(¬ _¬)


Los preparativos

Lo primero fue construir estructuras de datos adecuadas para la representación del grafo.
Desarrollé Boo & Marung sin motores ni librerías de terceros, todo desde cero, con la lógica excepción de las librerías estándar más básicas de Java y Android. En las de esta plataforma encontré una interesante estructura para guardar pares clave-valor llamada SparseArray, que es más eficiente que HashMap cuando la clave es un entero. La utilicé para representar listas de nodos y arcos.

A partir de ahí construí interfaces y clases que culminaron con la clase Grafo. La representación básica consistió en una lista de nodos, cada uno con otra lista de semiarcos, que es como llamé a cada par nodo-coste al que estaba ligado un nodo concreto.

Aunque quizá no sea lo más acertado, la misma clase Grafo implementa el algoritmo que devuelve la lista de nodos para llegar de un nodo a otro con el menor coste posible.

Como curiosidad decir que la implementación recursiva del paso final que ordena los nodos que forman el camino, resultó más rápida que una versión iterativa para el tamaño medio de los grafos.

Otro ejemplo de búsqueda de eficiencia que resultó infructuosa, fue que comencé implementado como heurística la distancia Manhattan. Esto no sólo introducía un margen de error apreciable, sino que no merecía en absoluto la pena porque el ahorro computacional era ínfimo. Acabé implementando sin más complicaciones el cálculo de la distancia real tirando de la raíz cuadrada que aún sigue siendo tan temida por algunos.


Representación del espacio del juego

El verdadero problema era la representación del espacio de juego, o más bien su traducción como grafo. ¿Qué eran los nodos y qué eran los arcos en el espacio del juego?


La imagen anterior da una pista sobre los candidatos a ser nodos gracias a que en este nivel se aprecia la "cuadrícula": los candidatos son las casillas en las que se divide.

No quiero profundizar en esta idea ahora pero no toda la resolución de un juego tiene que ser la misma para todos sus aspectos. En Boo & Marung los actores se mueven en transiciones suaves y en este sentido la resolución es la de la pantalla, pero el cálculo de las rutas tiene menos resolución.

He hablado de "candidatos" porque no todas las casillas serán un nodo del grafo, sólo algunas pocas. He visto enfoques en libros y foros que no me han gustado. En esas representaciones el grafo es una bestialidad de nodos y arcos porque casi que cada punto libre del juego se trata como un nodo. En Boo & Marung no sólo se reduce el número de posibles nodos al cuadricular el espacio en celdas, sino que al cargar cada nivel se determinan las celdas realmente útiles para ser los nodos del grafo.

A partir de aquí llamaré "mapa" al espacio del juego, al escenario, y "celda" a sus casillas.

Las celdas útiles son las que permiten bordear cualquier obstáculo. Como en este juego todos los obstáculos se componen de rectángulos (realmente cuadrados), es fácil determinar que esas celdas son las que hay en las esquinas. Las geometrías de otros juegos pueden requerir otros métodos.

En esta imagen vemos un ejemplo de mapa con obstáculos:


Como hemos dicho, no todas las celdas serán nodos del grafo sino sólo las esquinas, marcadas en azul:


Se puede observar que las esquinas de algunas formas coinciden con las de otras, esas esquinas sólo cuentan como un nodo. Otras quedan fuera del mapa y podemos ignorarlas.

Ya tenemos los nodos de nuestro grafo. Podremos sortear los obstáculos gracias a estos nodos porque cualquier celda del mapa es accesible desde alguno de ellos, y cualquier nodo es visible desde algún otro.

Ahora nos falta determinar los arcos. Para ello hice un algoritmo que llamo "de conectividad" y del que hablaré específicamente más adelante. Por ahora nos vale con saber que ese algoritmo dice si entre dos celdas hay un segmento de recta que no toca a ningún bloque.

Este sería el arco válido que conecta dos nodos, proyectado sobre el mapa.


No es una recta, realmente, como la que se aprecia en la imagen, si la mostramos así es por simplificar el dibujo. La verdadera recta, siempre que sea oblicua, la ensanchamos haciéndole una especie de antialiasing porque no nos basta con que los nodos sean conectables, sino que además el actor debe caber por ese "pasillo". Es un ensanchamiento muy generoso porque exige caminos muy anchos, pero por la propia geometría del juego no es ningún problema y nos permite una implementación fácil. En el siguiente ejemplo vemos un arco que no es válido, puesto que una de las X que representan el ensanchamiento de la línea toca un bloque:


Esta sería la configuración completa del grafo:


Los arcos son bidireccionales por lo que en realidad hay dos para cada pareja de nodos conectados, un arco en cada sentido. No he querido resaltar ese aspecto en los dibujos para no sobrecargarlos más. También en los dibujos hay arcos que se han pintado encima de otros, algo que tampoco he querido diferenciar.

Aún así salen muchos menos nodos y arcos que si hubiésemos considerado todas las celdas libres o si hubiésemos seguido otros métodos de interpretación del espacio. No es la solución óptima, estoy seguro, pero sí es razonablemente optimal.

Realmente el algoritmo de conectividad devuelve la distancia entre dos celdas o -1 si las celdas no son conectables con los criterios que manejamos. Esto nos permite determinar si dos celdas son conectables y al mismo tiempo nos proporciona la distancia para asignarle ese coste al arco.

El algoritmo de conectividad además facilita el no tener que usar el algoritmo de pathfinding, porque la primera comprobación entre un origen y un destino dados, es si son directamente conectables. En caso afirmativo ya tenemos el camino: una línea recta. Este subproblema de recorrer una línea recta, ya sea para ir directamente al destino o para ir de un nodo a otro, lo comentaré más adelante.

En la próxima entrada hablaré también de cómo integrar en el grafo el origen y el destino concretos de un actor, así como de otros aspectos relacionados con el pathfinding de este juego.


lunes, 16 de junio de 2014

Terminar el desarrollo de un videojuego

Comienzo una serie de entradas sobre el desarrollo de Boo & Marung, con las que sólo pretendo exponer impresiones personales abiertas a la crítica.

Esta primera entrada la dedico al descubrimiento (para mí) de que el desarrollo de un videojuego amateur tiene una fase diferenciada que podría llamarse fase de terminación, especialmente si el concepto jugable es también parte de lo creado.

Empecé mi juego estimando que tardaría un año en hacerlo, con un margen de seis meses más si la cosa se complicaba mucho. Al llegar al año y medio de desarrollo, y después de descartar multitud de características en el camino, aún estaba en una fase muy temprana. Entonces hice una estimación más seria de lo que quedaba, extrapolando lo realizado en ese año y medio, y salió que necesitaría al menos dos años más. Se me vino el mundo encima.




Muchos proyectos de juegos hechos por aficionados acaban abandonándose. Me atrevería a decir que la mayoría. Creo que esa tasa de abandono es superior en el caso de estos videojuegos frente a otro tipo de software. Yo mismo he protagonizado muchos de esos abandonos.

La complicación no viene de que falte una especificación de requerimientos, eso podemos hacerlo. Viene de que no hay una definición del problema, que es con lo que todo proyecto software debería comenzar.
¿Problema? Pero yo no tengo ningún problema. Sólo quiero hacer un juego divertido, bonito, sencillo pero profundo, explorar distintos apartados del desarrollo...
Esa definición difusa no se satisface en el fondo con una traca de requerimientos que no llevan ninguna dirección, porque no atacan ningún problema concreto ni son realistas.

Distinto es un entorno empresarial, donde la productividad y la calidad son imposiciones que ayudan a fijar un camino. Tampoco van descaminados los requerimientos de proyectos más mecánicos que se basan en conceptos propios o ajenos, porque el problema queda definido: repetir algo determinado con ciertas variantes; a partir de ahí los requerimientos surgen con relativa facilidad y con más sentido.



La excesiva libertad con la que se encuentra el desarrollador aficionado se vuelve en su contra. Intenta solucionar un problema que no tiene definido disparando en todas direcciones, abriendo demasiadas posibilidades y complicándose la vida.

En otro tipo de software la terminación es algo que ocurre automáticamente al completar todas las tareas pendientes. En los videojuegos de aficionados es algo que hay que acometer como una fase en sí misma. Hay que forzarla.

La fase de terminación es una revisión de requerimientos que va más allá de un mero enfoque evolutivo. Después de todo, cosas como un prototipo sirven para evaluar si cumplimos los requerimientos que satisfacen un problema, y recordemos que nuestra peculiaridad es que no conocemos el problema.

Aunque estemos de acuerdo en que esta fase existe (muchos no lo estarán), abordarla es complejo. No consiste específicamente en recortar requerimientos, sino en conducirlos para que se integren, de una vez por todas, en la solución que estamos conformando. La fase de terminación convive con todas las demás, idealmente desde el principio, y va tomando más importancia a medida que nos acercamos el final. Lo curioso es que la solución alcanzada nos revela por fin el problema que teníamos.



Tras los primeros dieciocho meses de desarrollo de Boo & Marung, y la estimación terrorífica de que necesitaba al menos dos años más, decidí finalizar el juego en nueve meses. Para ello quité más características, cambié otras, dividí las tareas en apartados, las prioricé de más a menos necesarias y asigné un tiempo a cada apartado; cuando se cumpliera ese tiempo, daría por terminado el apartado en cuestión quedase lo que quedase. Y si sobraba tiempo lo dedicaría a adelantar el siguiente apartado, nunca a rescatar tareas ya desechadas. Lo cumplí a rajatabla y me sorprendió lo bien que esta vez había afinado en la planificación comparándola con la disparatada estimación inicial.

El juego tiene carencias y queda algo lejos de lo que quería hacer al principio, pero para mí era vital terminarlo. Ahora tengo más experiencia y haría ciertas cosas de otra manera, empezando por un concepto más sencillo. Pero soy consciente de que seguiré sin poder definir bien el problema y que por tanto la fase de terminación tendrá que venir de nuevo al rescate.