tile engine view area

i wrote a tile engine and it is completely working.
i am making a turn based game so the players move 1 tile each move (not 1 pixel) and the current tiles are 32x32 pixels
what i am trying to do is make a slightly more realistic tile engine and add some strategy to it.
i want to make it so if there is an opaque tile in front of the player, such as a tree, they will not be able to see the tiles behind it.

such as:
G G G _ G G G
G G G _ G G G
G G G O G G G
G G G P G G G
G G G G G G G
G G G G G O G
G G G G G G _
G = basic grass tiles
P = player
O = opaque object that the player cannot see through
_ = area that isnt displayed

i have spent alot of time thinking about this and i cannot find a way to correctly calculate the tiles that should not be shown

Use different layers of tiles?

Are you talking about blacking out any tiles that the user should not be able to see? Like the old versions of Ultima? If this is so (God I hated that feature of ultima), you should be able to do some sort of line checking, such as move up on the Y axis, if you hit an opaque object, keep moving up the y axis and draw black tiles in place of the remaining tiles.

Dante Shamest: there is only one layer of tiles, each tile stores a moveable variable to detect player collision

rockytriton: i have never played ultima, but it is probobly what i am trying to do. the problem with moving up the y axis and blacking out the tiles after opaque objects is if there is an opaque object diagonal to the player or to the left of the player it would not work. i am thinking that i will need to use triginometry for this, though its been years since i learned about triginometry

it shouldn't be too hard an algorithm to figure out if things are diagonal as well, it's simple x,y coordinates.

ah i got it, im just going to find the player coordinates and the coordinates of the opaque object then do a simple y=mx+b thing and loop through it to find all the tiles that need to be not shown

y=mx+b AHHH ALGEBRA HATE IT ARHGGG

lol :d

Cast enough rays to fit the resolution of your tile map. Based on ray intersection information you can determine whether or not a tile is visible or not.

You will need these:

tan(theta)=opposite/adjacent
cos(theta)=adjacent/hypotenuse
sin(theta)=opposite/hypotenuse

tan(a)=x/y
cos(a)=y/h
sin(a)=x/h

so:

You can step through your map using tan() instead of cos/sin. On a 100x100 tile grid, cos and sin method will force you to search 100x100 intersections. Not good.

Here is the basis for tangent ray casting.

tan(angle)=x/y

Well you know that x is your horizontal cell or tile size.
You also know that y is your vertical cell or tile size.

So you split the ray cast into two parts: Cast on X or horizontal, and cast on Y or vertical.

Y cast
tan(angle)=x/y
tan(angle)*y=x

Code:

float stepsizex=tanf(angle)*(float)cellheight;

X cast
tan(angle)=x/y
tan(angle)/x=y

Code:

float stepsizey=tanf(angle)/(float)cellwidth;

or

Code:

float oneOverCellWidth=1.0f/cellwidth;
float stepsizey=tanf(angle)*oneOverCellWidth;

To figure out what angle is in the equation
HFOV=Horizontal Field Of View

Code:

float LeftRayAngle=PlayerHeading-(HFOV*0.5f);
if (LeftRayAngle<=0.0f) LeftRayAngle+=360.0f;

float RightRayAngle=LeftRayAngle+HFOV;
if (RightRayAngle>=360.0f) RightRayAngle-=360.0f;

Now you need to decide on the resolution of your raycast. If you wish to cast out a lot of rays, your cast will be more precise, but will take longer. For a tile map you shouldn't need a huge resolution. I'd say 90 rays would suffice.

So:

Code:

....
float AngleStep=NumberOfRays/360.0f;

or

Code:

float oneOver360=1.0f/360.0f;
float AngleStep=NumberOfRays*oneOver360;

Now just create two loops, one to raycast on x and one on y. If TileMap(x,y) is an opaque object, exit the loop, increment the ray angle, and continue. If not, continue stepping in ray direction until opaque tile is hit. You could render an entire scene this way. Start out with a black screen and render. Darken the correct vertices of the quad that is the last one visible and you will have a 'fog of war' Command and Conquer type effect.

Instead of doing this using anglestep you could use linear interpolation.

Code:

float Lerp(float v1,float v2,float interpamount)
{
  return (v1+interpamount*(v2-v1));
}

float LerpASM(float v1,float v2,float interpamount)
{
  float result=0.0f;
  asm {

    ;load v2 into st(0)
    fld [v2]

    ;subtract v1 from st(0)
    fsub [v1]

    ;multiply st(0) by interpamount
    fmul [interpamount]

    ;add v1 to st(0)
    fadd [v1]

    ;pop st(0) off stack into result
    ;only necessary to get along with function prototypes
    fstp [result]
  }
  return result; 
}

Now instead of using stepangle you can use an interpolation amount to interpolate from one ray angle to the next or from LeftRayAngle to RightRayAngle. Since the HFOV is usually 60 degrees, and interpamount of 0.5f would be roughly halfway or 30 degrees.

Note that in the last function I had to specifcally return a value even though the result is left in st(0). I had to do this because the compiler sees the float return type and even though my code does in fact leave the correct value in st(0), the compiler has no way of knowing that. If this function was coded in pure asm, the prototype would still be float LerpASM(), but I would not have to return anything since the correct value is left in st(0) and the compiler would pick that up automatically. For more information consult an assembly language book.

Quite a post there Bubba :d

WOW thanks Bubba

Well I didn't invent the idea. You can thank John Carmack and DOOM 1 for the idea. That is essentially how Carmack and ID software got a 3D 'looking' first-person shooter to run on an old 386 w/o a math co-processor. They used raycasting.

Pretty simple process.

Cast a ray.
When it hits a wall or a non-zero element in the array, compute the distance to the point. This can be done w/o using square root by using the law of similar triangles. Then decide on a wall height. Divide wall height by distance. Divide the final result by 2.

StartLineY=CenterOfScreenY-height2;
EndLineY=CenterOfScreenY+height2;

Doing textures is easy because you just find out how far into each cell you are - this is a simple calculation and you use the float value you get to index into the texture. You only need u since v never changes. This is also perspective correct texture mapping because the raycast takes care of the divide by z. To do characters you simply raycast and when you reach a cell where a character is, you stick the current X location of the cast and the ID of the character into memory. Then on a second pass you start at that location and draw the sprite centered vertically on the screen. Doors are done much the same way.
You should try it some time. It's easy to code and it's very very fast on modern computers.

But raycasting can also be used for doing voxel engines like Novalogic's Delta Force 1 and 2. It is used in 3D games to do bullet trajectories and computations and many many other things.

A ray cast is as simple as this:

RayEndX=RayOriginX+cos(RayAngle)*RayCastDistance;
RayEndY=RayOriginY+sin(RayAngle)*RayCastDistance;

But you can also use the tangent form to speed your engine up.

Do some research on raycasting and if you are interested, non-orthogonal raycasting methods.

A friend of mine made a 3d looking game on Basic.. with sins and cos and etc etc....


it really looks 3d, using trig calculations for perspective n stuff, in BASIC :d, its pretty wild, TOO much math for me :d

thanks Bubba, looks like i need to stop sleeping through geometry :P

>>You can thank John Carmack and DOOM 1 for the idea.

You mean Wolfentstein3D ... and then DooM

That's the reason why the horizontal field of view in those games was 45 degrees: tan(45) = 1, allowed them to take out some math.