My version is simple attempt of moving the game from PC to mobiles but with one important feature - or rather without - no 3D api in use ( neither JSR184 nor Mascot nor OpenGL/ES ). I just wanted to prove that current generation phone can handle simple raycaster engine. Obviously, there are number of devices which will never support this simple technology due to poor J2ME implementation but also there are many ( especially Sony Ericssons ) which do it really good.
Walls shading is very first feature I have added. Then game was using fillRect() to draw each vertical line. It worked fast but it looked nothing like old Wolfenstein! What I did need was texturing. So the hardest part of implementation was about to come. But let me first to tell about how my raycaster engine works as it’s bit different than one made by Id Software.
Raycaster engine I have made is well optimized for mid-end mobile devices. It has a few assumptions like:
- walls are always perpendicular
- block of single wall piece can never be different length which means it’s always cube
To optimize the engine I came out with several ideas which seem to work quite well:
- Each piece ( let’s assume it’s square because we look at the map from top-view ) has for edges and they are marked. This way we know which edges must be checked and drawn. It’s something like simple backface culling ;)
- The map is splitted into several areas to limit the number of edges to check.
- I implemented “viewing rect”. Viewing rect is the area which is desgnated by 3 factors:
* Camera position
* Left edge of viewing angle
* Right edge of viewing angle
Viewing rect limits the area which must be computed and drawn. Also by having these 3 factors it’s possible to find corresponding sectors of map which also should be included into computation process.
After designing map model it became important to find the best way of checking ray intersection point with nearest edge. This is the place which differs pretty much from original Wolfenstein3D.
First by the FOV angle all the vertices are sorted and only ones whichshould be checked becomes a part of sorted array.:
final int p_fov = player_angle + FOV_HALF;
final int m_fov = player_angle - FOV_HALF;
final int view_x = player_x + ( ( Maths.sin( m_fov ) << VIS_SHIFT ) >> FP );
final int view_z = player_z - ( ( Maths.cos( m_fov ) << VIS_SHIFT ) >> FP );
final int view_x_2 = player_x + ( ( Maths.sin( p_fov ) << VIS_SHIFT ) >> FP );
final int view_z_2 = player_z - ( ( Maths.cos( p_fov ) << VIS_SHIFT ) >> FP );
final int vis_player_x = player_x + ( ( Maths.sin( player_angle ) << VIS_SHIFT ) >> FP );
final int vis_player_z = player_z - ( ( Maths.cos( player_angle ) << VIS_SHIFT ) >> FP );
final int r_x1 = Math.min( Math.min( Math.min( view_x, view_x_2 ), vis_player_x ), player_x );
final int r_x2 = Math.max( Math.max( Math.max( view_x, view_x_2 ), vis_player_x ), player_x );
final int r_y1 = Math.min( Math.min( Math.min( view_z, view_z_2 ), vis_player_z ), player_z );
final int r_y2 = Math.max( Math.max( Math.max( view_z, view_z_2 ), vis_player_z ), player_z );
int num = 0;
final int v_num = vertices.length;
for ( int i = 0; i < v_num; i += 4 )
{
final int v_x1 = vertices[ i ];
final int v_y1 = vertices[ i + 1 ];
final int v_x2 = vertices[ i + 2 ];
final int v_y2 = vertices[ i + 3 ];
if (
( v_x1 > r_x1 && v_x1 < r_x2 && v_y1 > r_y1 && v_y1 < r_y2 ) ||
( v_x2 > r_x1 && v_x2 < r_x2 && v_y2 > r_y1 && v_y2 < r_y2 )
)
{
sortedVertexBuffer[ num ] = i;
num ++;
}
}
Looks pretty complex but it isn’t at all and moreover it’s a very fast method. This code can be launched every single frame and won’t affect overall performance. This is also where “viewing rect” is implemented. Of course not entire map is being checked but only sectors. How to find sectors? Simply, by checking of each point of viewing rect and finding at which area it is placed. In worst case we’ll have to check for sectors . Still looks scary? So now think that we do not have to check every single edge but only visible ones and those at which camera looks! Practically there are about 10 to 20 edges to check every frame. This is number which every midrange device can handle and will not cause much of performance problem.
From code above you may see that I use lot calls for sin() and cos(). There are just pre-computed arrays and every calculations is being sped up by avoiding of multiplications and using bit shifting instead.
When edges and vertices are sorted we can start to shoot rays. From each pixel lying along screen x-axis we need to shoot one ray and check on which edge it stops and how far it is from an eye. The engine shoots the ray from camera position and ( since we know exact maximum viewing distance which is constant ) uses simplified intersection check between two lines. Why is it simplified? Because we know that all the edges are always perpendicular. This assumption cut downs all the calculations to minimum. Also, there are some special cases which can be handled by even more reduced code.
How the engine checks the distance? Let’s say we have one vertical edge.
The camera shoots a ray which intersects the edge. What we need to know is the y-position of our ray at x-edge point. Using linear equation the engine finds coordinate:
cx = ( ( ( dz ) << FP ) / factor_a ) + player_x;
The equation above uses factor_a variable which is:
factor_a = ( ( ( ray_z - player_z ) << FP ) / ( ray_x - player_x ) );
This gives to more divisions, which cost CPU cycles but engine tries to reduce their number to very minimum. Since we know x-edge position then it’s time to find a distance. There are two ways of how we do it. Less accurate and ( in this case ) slower ( but tricky and it’s good to know it as it lets to not use square root, also games uses it for sorting sprites ):
public static int approx_distance( int dx, int dy )
{
int min, max;
if ( dx < 0 ) dx = -dx;
if ( dy < 0 ) dy = -dy;
if ( dx < dy )
{
min = dx;
max = dy;
}
else
{
min = dy;
max = dx;
}
// coefficients equivalent to ( 123/128 * max ) and ( 51/128 * min )
return ((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) +
( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 );
}
or more accurate and faster:
d = ( ( dy << FP ) / cos );
‘cos’ is value of cosinus function for specific angle. All sin and cos functions are pre-calculated so they are minor thing for total performance. At the moment game uses second method.
It’s easy to figure out one thing - if we want to simplify calculations the way I shown above then it’s gonna be needed to split edges into two types - vertical and horizontal. And this is done in the engine. For each type of edge there’s different procedure provided. Same as for special cases which are whenever the eye shoots ray which is parallel or perpendicular to the edge.
How to draw textures?
This is the most requiring part of code and I had to totally focus on optimizing it. All used texture are like originals: 64×64 with 8-bit indexed palette. I wrote Texture class that can load textures as PNG and raw data. Also, it creates mipmaps for improving overall graphics quality. Textures are being drawn by vertical lines. This is where all scaling is done too. The scaling function considers 3 cases:
- Vertical line is bigger than texture height,
- Vertical line is smaller than texture height
- Vertical line is equal with texture height
Third case is rather obvious - we do not have to calculate any scaling but copy all pixels to the buffer. First two cases reduces number of calculations by using smaller dimension as a base. If the texture is smaller then function goes through all texture pixels and finds their position at the column. Of course there are going to be blank holes between pixels after scaling but knowing previous and last pixel position we can just simply fill missing pixel with same color. This gives us always 64 iterations ( or less, depending on texture size ) even if the column takes entire screen. Same thing is done if scaled size is smaller than texture height.
There’s one more optimization. All calculations are mirrored. You cannot look up and down in the game so this makes things simpler. Scaling function calculates only half of the texture ( top part ) and copies pixels from the other half. Less dividing and shifting. This divides number of iterations by two.
Project is still in development and is more like tech-demo than game. This is how it currently looks:
No comments:
Post a Comment