Frogger HD and numerical modeling of waves in the pond

After reading the article about CGA from SLY_G, I was unusually excited. He remembered his youth, IBM PC / XT and the frogger jr game, in which the frog had to cross the road, avoiding the wheels of wildly racing bikes. Then on the logs to jump to a quiet backwater. And so to death, which gave 4 pieces. Fry was given 666, but I'm not Max.
After crying about the irretrievably lost years, I decided to lose another couple of days and made a remake of the game for the iPad.

I decided to model the movement of water in the river in the correct way, through a difference scheme.
On the numerical algorithm for modeling lake waves and what happened, read on.
Yes! I forgot to say.
Those who can continue the sequence

TTFS E ...

reading will not be particularly interesting.

')


So, water. Numerically solving the Navier-Stokes equations on phones is still early. Therefore, I took the model, kindly seen in the article by the distinguished gentleman blind_designer . In the work of Blind Pugh, a one-dimensional algorithm is described. I expanded it to two-dimensional.

Model surface of the water.

Imagine a rectangular grid of size M * N. The grid lies on the ground, from each node sticks out along the spring with the initial length Lx0 [i, j]. The elasticity of a spring is determined by its coefficient kx [i, j].

We throw a light veil on the springs - this is the veil and will simulate the mirror of the reservoir.

Under the influence of external forces (the stone fell), the lengths of the springs Lx [i, j] may change. As we remember from life, the waves from an abandoned stone sooner or later calm down.

Therefore, we will get another array of spring viscosity mx [i, j]. If the spring viscosity is set equal to 0, the waves will never stop and will be reflected from the shores indefinitely.

The numerical equation for the springs is quite simple (Hooke's law with dissipation)

for (int i=0; i<n; i++) { float x = Lx[i] - Lx0[i]; float acceleration = -kx[i] * x - mx[i]*Wx[i]; Lx[i] += Wx[i]*dt; Wx[i] += acceleration*dt; } 

Here the array Wx [i, j] is the vertical speed of each spring. It's simple - the spring acceleration is equal to the coefficient of elasticity multiplied by the displacement. And speed is an integral of acceleration. And the offset is an integral of speed. The time step dt = 1, entered for severity.

If you leave the solution in this form, then each spring will swing by itself, regardless of the neighboring springs. In life is not so, between the neighbors there is a connection. We describe this relationship through the diffusion equation or (for designers) through a filter with a width of 9 springs. The filter spreads the speed of each spring to 4 neighbors in each direction of the light, which creates the effect of a wave.

Watch the cycle

  float spread = 0.025; // do some passes where springs pull on their neighbours for (int iki = 0; iki < 4; iki++) { // 4        //     for (int j = 0; j < ny; j++) { for (int k = 1; k < nx-1; k++) { int i = k + j*nx; lp[i] = spread * (Lx[i] - Lx[i-1]); Wx[i - 1] += lp[i]; rp[i] = spread * (Lx[i] - Lx[i + 1]); Wx[i + 1] += rp[i]; } } for (int j = 0; j < ny; j++) { for (int k = 1; k < nx-1; k++) { int i = k + j*nx; Lx[i - 1] += lp[i]; Lx[i + 1] += rp[i]; } } //    y for (int j = 1; j < ny-1; j++) { for (int k = 0; k < nx; k++) { int i = k + j*nx; lp[i] = spread * (Lx[i] - Lx[i-nx]); Wx[i - nx] += lp[i]; rp[i] = spread * (Lx[i] - Lx[i + nx]); Wx[i + nx] += rp[i]; } } for (int j = 1; j < ny-1; j++) { for (int k = 0; k < nx; k++) { int i = k + j*nx; Lx[i - nx] += lp[i]; Lx[i + nx] += rp[i]; } } } 

The lp [] and rp [] arrays are temporary, you optimize the algorithm yourself for your abilities.
nx is the number of nodes along the x axis, ny is the number of nodes along the y axis.

All clear? In my opinion, quite, go ahead, to visualize.

Visualization

You can draw a three-dimensional surface. And I have long gone from the realism of OpenGL and show the waves in a flat picture. As if the view from a helicopter hovering over the lake. Picasso would do the same. We take the texture, with the parties proportional to our grid.
Not bad, if it is similar in color to the water in the pool.



Texture example. Pizhzhenno at zeptolabov.

The texture is turned into a two-dimensional array of rawData pixels, each pixel is 4 bytes or RGBA components.

  myUIImage = [UIImage imageNamed:@"ground_2"]; n = nx*ny; CGImageRef image = [myUIImage CGImage]; NSUInteger width2 = CGImageGetWidth(image); NSUInteger height2 = CGImageGetHeight(image); CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB(); bytesPerPixel2 = 4; bytesPerRow2 = bytesPerPixel2 * width2; NSUInteger bitsPerComponent = 8; rawData = malloc(height2 * width2 * 4); CGContextRef context = CGBitmapContextCreate(rawData, width2, height2, bitsPerComponent, bytesPerRow2, colorSpace, kCGImageAlphaPremultipliedLast | kCGBitmapByteOrder32Big); CGColorSpaceRelease(colorSpace); CGContextDrawImage(context, CGRectMake(0, 0, width2, height2), image); CGContextRelease(context); 

We are ready for modeling.
There is an initial picture - rawData [i, j].
There is a current height of the water surface at each point - Lx [i, j].
There is a vertical velocity of the surface of the water at each point - Wx [i, j].

It remains to draw a texture perturbed by the speeds. We will form a new image in the pixel [] array.

 -(void) renderWater { size_t width = nx*2; size_t height = ny*2; size_t bytesPerRow = 4*width; memset(pixel, 0, bytesPerRow*height); float zz = -1.9; for (int j=0;j<height;j++) { for (int k=0;k<width;k++) { int i2 = (int) (k*4 + j*bytesPerRow); int k4 = k/2; int j4 = j/2; int s1 = k%2; int s2 = 2-s1; int s3 = j%2; int s4 = 2-s3; int i4 = k4 + nx * j4; float h2 = Lx[i4] - Lx0[i4]; h2 = (Wx[i4]*s2*s4 + Wx[i4+1]*s1*s4 + Wx[i4+nx+1]*s1*s3 + Wx[i4+nx]*s2*s3) / 4.0; int a = 255.0*h2*h2*0.15; if (a>255) a = 255; float x2 = (k4>0 && k4<nx-1) ? Lx[i4-1] - Lx[i4+1] : 0; float y2 = (j4>0 && j4<ny-1) ? Lx[i4-nx] - Lx[i4+nx] : 0; int k2 = k+zz*x2; int j2 = j+zz*y2; if (k2<1) k2 = 0; if (k2>width-1) k2 = (int) width-1; if (j2<1) j2 = 0; if (j2>height-1) j2 = (int) height-1; int byteIndex = (int) ((bytesPerRow2 * j2) + k2 * bytesPerPixel2); int red = rawData[byteIndex]; int green = rawData[byteIndex+1]; int blue = rawData[byteIndex+2]; pixel[i2+0] = red; pixel[i2+1] = green; pixel[i2+2] = blue; pixel[i2+3] = 255-a; } } CGColorSpaceRef colorSpace=CGColorSpaceCreateDeviceRGB(); CGContextRef context=CGBitmapContextCreate(pixel, width, height, 8, bytesPerRow, colorSpace, kCGBitmapByteOrder32Big |kCGImageAlphaPremultipliedLast); CGImageRef image=CGBitmapContextCreateImage(context); CGContextRelease(context); CGColorSpaceRelease(colorSpace); UIImage *resultUIImage=[UIImage imageWithCGImage:image]; CGImageRelease(image); water.image = resultUIImage; } 

At each point, the offset from the initial image is calculated and interpolated to the current one. Interpolation is needed for the program to work on the iPhone 4S. To do this, I halved the size of the texture in each direction and 4 times increased the speed of the algorithm. On the sixth iPhone it is not necessary to do this, it copes with a grid of 160 by 284.

Plus, depending on the speed of water at this point, I change the transparency of the texture from 0 to 255.

Everything. This cycle works well even on the old iPhone 4S at 20 frames per second.

Conclusion

The simulation result can also be seen in two applications for the iPad and two more for the iPhone.


Haken application.


Frogger app.

All good weekend and blessed memory to our ancestors.