Post by pmjobin on May 16, 2008 15:46:30 GMT -5
Today, I played a quick game of one of my favorite Genesis underdog, The Ooze. Seeing the green slime in action made me wonder about how they could achieve dynamic fluid simulation on the very limited Genesis hardware. So I started to think and this is what I came up with.
Sorry for the academic tone of the text, it's copy'n'pasted from a .txt file I just finished writing about the matter. ;D
-------
THOUGHTS ON THE OOZE DYNAMIC FLUID ALGORITHM
by Pierre-Marc Jobin
May 16th, 2008
This document is a recollection of my thoughts on a SEGA Genesis game titled
The Ooze. In this game, the player takes control of a puddle of slime and must
wade his way through vast environements while fighting off enemy creatures. The
Ooze character requires some basic form of computational fluid dynamics (CFD)
which represents a lofty technical challenge due to the very limited processing
power of the SEGA Genesis hardware. What follows is a short description of an
algorithm to simulate and render the slime fluid. It is based solely on cursory
observations of the gameplay and not on the actual game code which I haven't
reversed as of yet.
The algorithm can be naturally separated in two parts: simulation and rendering.
According to my observations, the simulator is based on a gradiant flood fill
and the renderer on a cellular automaton.
The simulation algorithm encompasses the calculations performed to detect
collisions with enemies and the external world and also to move the fluid in a
realistic manner. The simulation step overlaps a gradiant grid (centered on the
Ooze head) to the tilemap. The weights of the grid are established so that slime
particles near the head are "cheaper" to allocate than those which are further.
The ratio between different weights is not important as such, but their
numerical order is. This is a sample gradient map where the head is represented
as 0.
7 6 6 5 6 6 7
6 5 4 3 4 5 6
6 4 2 1 2 4 6
5 3 1 0 1 3 5
6 4 2 1 2 4 6
6 5 4 3 4 5 6
7 6 6 4 6 6 7
The ooze puddle consists of a certain number of particles which the player
accumulates by making physical contact with them. The simulation algorithm
basically allocates those particles to free gradient grid slots by order of
increasing weight until every particle is allocated. A grid slot is free if
no physical obstacle lies on the corresponding tilemap tile. If an ennemy
bullet or a damage tile is present on the grid slot, the particle counter is
decremented but the grid slot stays free (in other word, the particle is sent
to the void). During each update frame where a change in the slime structure
must be evaluated, a certain subset of particles (proportional to the viscosity
of the fluid) are reallocated to new grid slots. The reallocation moves
particles allocated to costly slots back to cheaper ones. As deceptively simple
as this simulation algorithm may seems, it should provide sufficient realism
while being very cheap to calculate.
The renderer task is to generate a smooth, liquid-like, puddle of slime from
the gradient grid which only tells wether a given grid slot is occupied or
free. The most intuitive way to perform this step is to create a cellular
automaton. The state of each cell in the automaton depends solely on the state
of it's direct neighbours. Said otherwise, the graphic design used to represent
cell X depends on the state of cells marked with * and maybe even on the
tilemap tile below X.
. . . . .
. * * * .
. * X * .
. * * * .
. . . . .
Sorry for the academic tone of the text, it's copy'n'pasted from a .txt file I just finished writing about the matter. ;D
-------
THOUGHTS ON THE OOZE DYNAMIC FLUID ALGORITHM
by Pierre-Marc Jobin
May 16th, 2008
This document is a recollection of my thoughts on a SEGA Genesis game titled
The Ooze. In this game, the player takes control of a puddle of slime and must
wade his way through vast environements while fighting off enemy creatures. The
Ooze character requires some basic form of computational fluid dynamics (CFD)
which represents a lofty technical challenge due to the very limited processing
power of the SEGA Genesis hardware. What follows is a short description of an
algorithm to simulate and render the slime fluid. It is based solely on cursory
observations of the gameplay and not on the actual game code which I haven't
reversed as of yet.
The algorithm can be naturally separated in two parts: simulation and rendering.
According to my observations, the simulator is based on a gradiant flood fill
and the renderer on a cellular automaton.
The simulation algorithm encompasses the calculations performed to detect
collisions with enemies and the external world and also to move the fluid in a
realistic manner. The simulation step overlaps a gradiant grid (centered on the
Ooze head) to the tilemap. The weights of the grid are established so that slime
particles near the head are "cheaper" to allocate than those which are further.
The ratio between different weights is not important as such, but their
numerical order is. This is a sample gradient map where the head is represented
as 0.
7 6 6 5 6 6 7
6 5 4 3 4 5 6
6 4 2 1 2 4 6
5 3 1 0 1 3 5
6 4 2 1 2 4 6
6 5 4 3 4 5 6
7 6 6 4 6 6 7
The ooze puddle consists of a certain number of particles which the player
accumulates by making physical contact with them. The simulation algorithm
basically allocates those particles to free gradient grid slots by order of
increasing weight until every particle is allocated. A grid slot is free if
no physical obstacle lies on the corresponding tilemap tile. If an ennemy
bullet or a damage tile is present on the grid slot, the particle counter is
decremented but the grid slot stays free (in other word, the particle is sent
to the void). During each update frame where a change in the slime structure
must be evaluated, a certain subset of particles (proportional to the viscosity
of the fluid) are reallocated to new grid slots. The reallocation moves
particles allocated to costly slots back to cheaper ones. As deceptively simple
as this simulation algorithm may seems, it should provide sufficient realism
while being very cheap to calculate.
The renderer task is to generate a smooth, liquid-like, puddle of slime from
the gradient grid which only tells wether a given grid slot is occupied or
free. The most intuitive way to perform this step is to create a cellular
automaton. The state of each cell in the automaton depends solely on the state
of it's direct neighbours. Said otherwise, the graphic design used to represent
cell X depends on the state of cells marked with * and maybe even on the
tilemap tile below X.
. . . . .
. * * * .
. * X * .
. * * * .
. . . . .