Historia de la Simulación de la Física en los Videojuegos

- Francisco León

Engañando al ojo

La Fisica en los juegos ha sido fundamental desde los inicios de la industria en los años 70s.
Desde el clásico Pong hasta los complejos simuladores de vuelo usados por la Fuerza Aerea de los Estados Unidos.
Sin embargo, aunque la Fisica en los primeros juegos cumplía un papel fundamental, su aplicación fué muy limitada debido a la falta de hardware capáz de realizar extensos cálculos numéricos en tiempo real.

Por lo general la gran mayoría de juegos de arcade limitaban su funcionamiento a simulaciones discretas de autómatas finitos simplificados.
La secuencia de ejecución de las acciones de los agentes inteligenes se realizaban por turnos, y el dinamismo era casi nulo.

Algunos Juegos como Pacman y Mario Bros podían ofrecer la ilusión de dinamismo implementando simples rutinas de movimiento lineal.
El mismo principio de desplazamiento discreto fue usado por los juegos de carreras de arcade como Outrun, F1-racer y Pole-Position.
(muchos tendrán recuerdos nostálgicos de estos juegos de tragamonedas)

En estos juegos los carros son representados internamente en el programa como simples celdas que se desplazan en una gran matriz; esta matriz se visualizaba en el juego como la pista prediseñada que el usuario tendría que atravesar evitando los obstáculos (celdas ocupadas). En la pantalla estas celdas cobraban vida como imagenes pixeladas del escenario.

Para hallar  colisiones entre el carro del jugador y el escenario se verificaba de forma discreta si el carro se encuentra en la celda ocupada por otro carro o por un arbol.
Aqui, la fisica de newton nada tenía que ver: la aceleración se basaba en la rapidéz a la cual se desplaza la celda del carro entre las filas de la matriz, pero ante los ojos del jugador daba la ilusión de que se desplazaba a gran velocidad por una autopista en las playas de Miami.


Acrobacias

Solo hasta el final de los 80s una serie de juegos de carros de PC revolucionaron la simulación fisica en tiempo real:
La serie Test Drive, y el titulo más famoso de esta fué Stunt Racer para MS-DOS y Amiga:


Solo hasta la aparición de este juego las ecuaciones de Newton al fin salieron la luz a traves del monitor del computador.
Por primera vez, el jugador podía experimentar con la aceleración, fricción e inercia al momento de conducir el coche en una pista de superficies tridimensionales. Los jugadores podían diseñar rampas, obstaculos, curvas y cilindros para poner a prueba las acrobacias de los vehiculos.
Podías experimentar la fuerza centrifuga al momento de virar una curva a alta velocidad, y el vacio en el estomago por efecto de la aceleración de la fuerza de gravedad
al momento de realizar un salto parabolico entre rampas.
También al jugador le era posible conocer las diferencias de prestaciones entre los modelos de vehiculos deportivos de la epoca (Ferrari,Laborgini, Corvette, Acura, Audi)
de forma muy cercana a la realidad: Desde la acelearión, marchas y torque hasta la estabilidad del chasis vehiculo al momento de girar curvas.

Para mi, este juego ha sido mi principal fuente de inspiración como programador de videojuegos; Durante mis  primeros años de Universidad dediqué cierto tiempo en averiguar los algoritmos y modelos matemáticos usados en este juego.
Y aunque aun no tengo certeza de como los autores lo hicieron, por lo menos tengo algunas pistas:

• Los carros son simulados como particulas que experimentan la fisica newtoniana, cuerpos que experimentan aceleración e inercia.
• Mas estos no experimentan rotacion, aceleración angular ni torques.

Los modelos debieron simplificarse para brindar la ilusión de realismo con las limitaciones del hardware de la epoca.
El modelo de colisiones entre los carros y el escenario pudo implementarse mediante un BSP (Arbol binario de planos 3D), que permitía comprobar intersecciones entre regiones convexas (estructuras del escenario, recintos, supercifies) y las esferas que representan los vehiculos (jugando por horas en este juego uno se podía dar cuenta de que el carro era fisicamente mas pequeño de lo que se veía).

Aunque aun presentaba problemas de realismo debido a la simplificación del modelo fisico-matemático, hay que reconocer que fue un gran logro para la epoca.
Este juego ha dado las bases para otros titulos de consolas como Need For Speed, Nascar y Daytona Racer.


La sed de ultraviolencia exige Realismo
 

En la decada de los 90s ocurre una gran revolución tanto estética como tecnológica en el desarrollo de videojuegos. Viniendo de una era ochentera dominada por nintendo donde la regla para los  juegos fué una estética infantilizada y abstracta traida del tierno mundo de las  caricaturas de TV y cuentos de hermanos Grimm, de repente aparecen mounstruos ciberneticos que sumergen a los jugadores en un ambiente post-apocaliptico cargado de sadismo, masacres y crueldad. Si señores,  hablamos del fenomeno DOOM.

John Carmack,  un brillante programador de apenas 20 años, introduce el concepto de Shooter en Primera Persona gracias al desarrollo de su tecnología en ambientes virtuales 3D inmersivos. Sin su aporte aun estaríamos jugando muñequitos en perfil que corren y corren en un escenario colorido y pixelado a la Mario. Por primera vez, un adolecente de 12 años podría sentir la sensación casi real de tener una escopeta en sus manos y volarle los cesos a drogadictos en un callejon obscuro, virtualmente. Para muchos adolecentes este juego fue un catalizador donde podrían desahogar todas sus frustaciones ocasionadas por el bulling hacia ellos en los colegios, la incomprensión de sus padres por no cumplir sus expectativas, y la visión de un futuro sombrío que amenaza con desastres ambientales, plagas, colapsos económicos y guerras.

El genero de la ultraviolencia vino acompañado de increibles avanzes tecnológicos que permitieron reproducir lo que antes era exclusivo de los militares y la industria Hollywoodense en un PC doméstico. Por primera vez, podrías internarte en la guarida del demonio y luchar con engendros alienigenas armado de metralleta, bombas, rockets y toda clase de armas de energía directa. Juegos como Quake y DukeNukem 3D te enseñaban la importancia de la fisica para dominar la trayectoría balística a la hora de lanzar granadas hacia un recinto con el fin de exterminar el maximo número de zombies. El jugador ahora podía tocar las paredes, sumergirse en el agua y lanzar proyectiles como si estuviera viviendo la experienca de un Marine en carne propia.

Esta sed de realismo motivo el desarrollo de modelos matemáticos mas precisos y dinámicos en las simulaciones físicas. Si bien antes los algoritmos y modelos matemáticos trataban de engañar al ojo con burdas aproximaciones debido a las limitaciones de los computadores de la epoca, ahora los desarrolladores concentraron sus acciones en implementar los principios de la mecanica clásica y la robótica en las simulaciones interactivas en tiempo real.

Inspirados por los Destruction Derbi  y peliculas como MadMax y la Carrera de la Muerte 2000 , el programador Patrick Buckland y el artista Neil Barnden decidieron crear un juego de carreras donde el objetivo sea chocar a otros vehiculos hasta hacerlos volar en pedazos. Nace Carmageddon, el primer juego realista de vehiculos donde estos experimentan toda la complejidad de los fenomenos fisicos dinámicos. Es a partir de Carmageddon donde se define el funcionamiento estandar en los proximos motores físicos. Solo hasta ese momento las colisiones entre objetos toman un papel primordial: los vehiculos podían volcarse y sufrir deformaciones por los choques. También entró en juego el diseño estructural fisico de los vehiculos: estos ahora estaban compuestos de ruedas conectadas al chasis mediante suspensiones. Algunos vehiculos poseían extensiones unidas por visagras que funcionaban como mazos de batalla para la destrucción de cualquier cosa que se atravesara en el camino: otros vehiculos, semaforos, PEATONES ( daban puntos por atropellar gente).

Antes de dedicarse a los videojuegos, Patrick desarrollaba aplicaciones de simulación y control automatizado en procesos médicos quirurgicos. Diseño los sistemas para el control de brazos robóticos encargados de cortar tejidos y reacomodar organos en cirugías de alta precisión. Sus herramientas de simulación le permitiá a los médicos estimar a  el efecto colateral de un procedimiento y desarrollar diferentes estratégias.

Desde esta experiencia en mecatrónica se inspiró para desarrollar con precisión quirurgica la tecnología capaz de representar un nivel de destrucción nunca antes visto en los videojuegos.  Con su trabajo se establecieron las bases del algoritmo fundamental de toda simulación física, el cual consiste en lo  siguientes principios:

• Los objetos están compuestos de un Modelo de Colisiones el cual representa la superficie geométrica de este, y el Modelo de Cuerpo Rigido el cual define las propiedades dinámicas de este tales como posición, orientación , velocidad, aceleración, masa y distribución de inercia (usado en la dinámica de rotaciones).
• Los objetos pueden interactuan entre si aplicandose fuezas entre ellos, ya sea por colisiónes elásticas o por estás enlazados mediante alguna articulación (visagras, eslabones, resortes).
• Las simulaciones se ejecutan de forma ciclica, calculando el estado de los cuerpos durante intervalos discretos de tiempo. Los pasos de una simulación fisica interactiva son estos:
  
        1) Calculo de sumatoria de fuerzas iniciales: gravedad, torques, y otras fuerzas inducidas por controladores.
  
        2) Con estas fuerzas se estiman las trayectorias que estos cuerpos realizarán en el siguiente intervalo de tiempo integrando las ecuaciones de movimiento newtonianas.
  
        3) Se calculan los punto de contacto entre las superficies de los modelos de colisión mediante intersecciones geométricas. Se aplican algoritmos avanzados que permiten determinar el punto y el vector de tangencia que separa dos objetos de superficie convexa. Los objetos concavos se representan como un conjunto de objetos convexos.    
     Estos algoritmos de colisión detectan también la distancia y eje de separación entre cuerpos lo que permite estimar el tiempo de colición dadas las trayectorias estimadas en el paso anterior. Con el dato de tiempo estimado de colisión cada cuerpo reajusta su posición evitando atravesar como un fantasma un muro por efecto de un desplazamiento grande durante un intervalo de tiempo.
  
     4) Con estos puntos de contacto se definen las restricciones de movimiento que tendrán los cuerpos al colisionar con otros. Se plantea un sistema de ecuaciones diferenciales que pretende satisfacer el estado de los cuerpos cuando se aplican fuerzas de otros simultaneamente (colisiones y fricción), y este sistema se resuelve iterativamente con métodos de penalización cuando los cuerpos no satisfacen las restricciones aplicando fuerzas de reacción durante microintervalos de tiempo. Se usan metodos numéricos como resolución matricial con multiplicadores de Lagrange,  o aplicación de impulsos basado en proyecciones Gauss-Seiddel. Este ultimo ofrece solucines aproximadas pero requieren menos tiempo de cómputo lo que lo hace atractivo para simulación en tiempo real.
     
     5) Adicionalmente se usa el mismo sistema de penalización para resolver las restricciones de movimiento causadas por las articulaciónes mecánicas. Aqui algunas articulaciones aplican fuerzas motorizadas (como en el caso del torque de vehiculos).
     
     6) Finalmente, con los impulsos finales calculados durante la resolución de restricciones se ajustan los parámetros en las ecuaciones de movimiento y se entregan las posiciones y orientaciones de los cuerpos rigidos al subsistema gráfico.

La batalla de los Middleware de Efectos Fisicos:


Durante la década de los 90s algunos ingenieros brillantes desarrollaron algoritmos de detección geométrica de colisiones para usos en inteligencia artificial y robótica. Esto haría posible que los robots salieran de los laboratorios a la movilidad de un campo de batalla evadiendo obstaculos hacia sus objetivos (Terminators?).

Los algoritmos de colisión y simulación fisica lograron tal nivel de optimización que permitieron su aplicación en simulaciones de tiempo real en PCs ordinarios. La industría de los videjuegos llegó a su apogeo y brindo un futuro brillante de grandes dividendos a aquellos especialistas que fueran capaces de aplicar estos algoritmos para las grandes compañias.

Es en este momento cuando muchos desarrolladores se enfocan en brindar mayor realismo en los juegos sin engaños visuales artificiosos. Entonces en Europa se crean compañías como Havok, MathEngine e Ipion:

Havok, ubicada en Dublin, recluta a los ingenieros más talentosos para el desarrollo de un middleware de fisica que sería licenciado a los estudios de videojuegos. Aquellos que trabajaron en Carmageddon fueron llamados a engrosar las filas de esta compañía irlandesa. Despues de un duelo de titanes, Havok gana la partida absorbiendo a Ipion.

Por otro lado, MathEngine desarrolla el Karma engine que fue usado en Unreal Tournament 2003-2004. Hasta este momento estaba claro que los middle-ware de fisica solo eran accesibles para las grandes compañías de videojuegos que contaban con el capital para pagar el millonario precio de sus licencias. Pero un ingeniero de MathEngine, Russel Smith, decide revelar la formula secreta mediante un proyecto de software libre:

Open Dynamics Engine (ODE). Su intención era acelerar la investigación y desarrollo en esta area, y con este aporte brindo la oportunidad a desarrolladores independientes y académicos de experimentar con la simulación física. Con la liberación de este software, otros realizaron sus aportes desarrollando un novedoso algoritmo optimizado para la solición de restricciones basandose en la aplicación de impulsos projectados Gauss-Seiddel: este algoritmo se conoce como QuickStep, y se caracteríza por su escalabilidad (lineal) de acuerdo con el número de restricciones y cuerpos del problema. En contraste, otros métodos usados por Havok como el matricial de multiplicadores de lagrange escalaban cuadráticamente y al mismo tiempo consumían mucha mas memoría. Ahora empezaba la batalla por ofrecer resultados en el menor tiempo posible.

Es entonces cuando Adam Moravanszky y Mathias Müller deciden formar su propia compañía llamada Novodex, y utilizan los algoritmos de ODE para la construcción de su propio middleware. Contratan al brillante programador Pierre Terdiman (autor de Opcode) el cual trabajó en la optimización los algoritmos del simulador físico escrito por Adam, y al mismo tiempo ofrece su aporte con algoritmos de colisión geométrica muy eficientes. Esto lleva a Novodex a ocupar el liderazgo en los middleware de fisica demostrando su eficiencia computacional con resultados sorprendentes.

Las grandes corporaciones quieren acaparlo todo

Durante el 2003, una companía fabricante de semiconductores centra su atención en los middleware fisicos; La compañía estadounidence AGEIA decide absorver Novodex y construir la primera tarjeta procesadora de efectos fisicos PPU. Pensaban que así como las tarjetas de video permitieron liberar la carga computacional para el procesamiento de gráficas 3D, entonces una PPU podría liberar a la CPU del intensivo procesamiento geométrico usado en la simulación fisica. Más sin embargo, esta compañía no pudo preveer los inconvenientes de la comercialización de esta tarjeta dirigida a los jugadores Hardcore.

Para ese entonces, los jugadores abandonaron el PC y retornaron al mundo de las consolas de Sony y Microsoft. Ahora las consolas cosecharon los frutos del progreso tecnológico cultivado por el libre desarrollo en los PC de escritorio, y el hardware de AGEIA no tuvo lugar en esta revolución XBOX-PSX.

Es entonces cuando AGEIA decide involucrar a los desarrolladores Indie mediante un modelo de licenciamiento más accequible. Hasta el punto de ofrecer licencias gratuitas a estos desarrolladores con el fin de estimular la compra del hardware por parte de los jugadores de PC. Durante este tiempo, un modesto estudio colombiano: Inmersion Games, desarrolla un Tech-demo conocido como Cell-Factor que demuestra el potencial tecnológico del hardware PhysX. La combinación mágica de la PhysX con los asombrosos efectos gráficos del Reality Engine llama la atención de otro gigante en la industria: EPIC games. Este gigante adquiere el capital tecnológico e intelectual de la compañía autora del RealityEngine para constituir el motor de Unreal 3 2007. Este motor estableció un nuevo estándar tecnológico demostrando su impacto con juegos como Gears of War.

Sin embargo, AGEIA no tuvo tanta suerte con la venta del hardware. Desafortunadamente la pericia de programadores como Pierre Terdiman había tenido tan buenos resultados que la versión de software ejecutada en un moderno procesador Intel Pentium 4 con Hypertreading mostraba un rendimiento superior al ofrecido por la PhysX. Esto desmotivo a los jugadores de la compra de la AGEIA cuyo precio no bajaba de los $300. Quizas la PPU realizaba un buen trabajo, pero las limitaciones de transmisión de datos de la PPU hacia la CPU  a través del bus de datos en las board añadía retardos y problemas de sincronización con los gráficos.

Durante este tiempo Havok formó alianzas con ATI para el uso del procesamiento vectorial de las GPU en las simulaciones fisicas. Esta tecnlogía llamada Havok FX, permitió usar otra GPU ATI para el procesamiento geométrico requerido por las simulaciones físicas de cuerpos deformables y partículas.  Mediante una tecnología llamada Close-to-Metal, ahora se resolvió el problema de transmisión de los calculos realizados por una GPU hacia la otra, y esto hizo posible que se sincronizan de forma óptima el renderizado y la física. NVIDIA no se quedó atrás y se unió al proyecto desarrollando una tecnología similar llamada SLI para la sincronización de varias tarjetas de video mediante un veloz canal de datos, superando en rendimiento a su rival ATI. Aunque este proyecto fue cancelado trajo consigo el fenómeno de GPGPU, o Procesamiento Computacional massivo en paralelo mediante el uso del Hardware de video.

Gracias a la tecnología GPGPU, Havok en compañía de Lucas Arts trabajan en una tecnología de modelamiento molecular y elementos finitos para la simulación de deformación y destrucción de diferentes materiales. Ahora los arboles podrían ser destrozados en astillas, los metales doblarse, y las fibras romperse. Otra compañía, NaturalMotions desarrolla para Lucas la tecnología Euphoria la cual brinda control kinematico de acciones de los personajes. Ahora los personajes podían reaccionar ante el escenario fisicamente mediante sistemas de equilibrio y cinemática inversa. Este desarrollo se hace notable en el juego Star Wars - The Force Unleashed.

Esto llama la atención de otro gigante fabricante de chips: Intel adquiere Havok. Para este momento AGEIA experimenta el fracaso en la venta del harware PhysX, y NVIDIA ve una oportunidad en absorber esta compañía para desarrollar un producto similar que funcione en el hardware de sus tarjetas de video. Ahora NVIDIA se reivindica como compañía lider en el procesamiento asistido por GPU (GPGPU) mediante el desarrollo de la tecnología CUDA. Reescribe los algoritmos de la PhysX en el nuevo lenguaje de procesamiento concurrente, logrando un poder nunca antes visto en el procesamiento de efectos fisicos. Ahora los gamers solo tendrían que adquirir un solo hardware de NVIDIA para tener el potencial de graficos y fisica al mismo tiempo.

Ahora la disputa por el poder de simulación es dominada por 3 grandes fabricantes de procesadores: Intel, NVIDIA y posteriormente AMD que adquirere a ATI.

El legado.

De esta acelerada revolución tecnológica en los campos de simulación física, algunos desarrolladores ex-empleados de Havok y AGEIA deciden trabajar en proyectos de software libre para experimentar con ideas novedosas y crear una comunidad de aprendizaje.

En el año 2005, Erwin Coumanns, un ex-empleado de la Havok, decide crear el proyecto de software libre llamado Bullet Physics Engine. Crea una página de foros para conformar una comunidad de desarrolladores aficionados al tema de simulación física. A diferencia de ODE, El proyecto Bullet conformó una comunidad más activa y dinámica  involucrando a notables científicos como Gino van den Bergen y Christer Ericcson autores de uno de los libros más fundamental de algoritmos de detección de colisiones:
Real-Time Collision Detection:
http://www.amazon.com/exec/obidos/tg/detail/-/1558607323?tag=realtimecolli-20
Se sabe que estos autores participaron en el desarrollo del motor de fisica de God of War.

Otros desarrolladores como Pierre Terdiman y Nathanael Presson también realizaron sus aportes al proyecto Bullet con algoritmos altamente eficientes para la detección de colisiones. Nathanael Presson, desarrollador de juegos de la PS2, incorporó los algoritmos para la simulación de cuerpos deformables mediante elementos finitos y arboles binarios dinámicos que pueden actualizar su estado en tiempo real ajustandose a superficies que cambian de forma continua.

La tecnología de Bullet physics ha sido incorporada en el software de diseño 3D Blender (del cual Erwin Coumanns es también co-autor). Este software CAD permite crear videojuegos con herramientas visuales incorporando efectos de fisica dinámica, efectos de ropa para la animación de personajes y cuerpos deformables.

Desde entonces, la simulación fisica dejó de ser una tecnología reservada para grandes compañias con un gran capital financiero. Ahora desarrolladores indie, académicos y programadores entusiastas pueden aprender y explorar con esta tecnología.



Para más información recomiendo revisar la siguiente literatura:

Bullet Physics : http://www.bulletphysics.com
Lista de material de referncia, libros y frameworks :
http://www.bulletphysics.com/Bullet/phpBB3/viewtopic.php?f=6&t=63
http://www.gamedev.net/community/forums/topic.asp?topic_id=475753

Creación de carmageddon: http://www.edge-online.com/magazine/the-making-of%E2%80%A6-carmageddon
Historia de PhysX :
http://www.moravanszky.com/article.php?mode=thread&order=0&sid=41&thold=0
http://www.gamer20.com/features/91

El blog de Pierre Terdiman: http://www.codercorner.com/blog/


Entrevista con havok senior: http://www.enn.ie/story/show/279616

Anailisis de physics engines: http://www.gamedev.net/community/forums/topic.asp?topic_id=320274