bird's eye view game's shadow

moongodjon · 03-25-2011, 01:05 PM

Hey y'all. This is my first post on the forum so please be kind.

Anyways, here's my question/problem thingy: I've been working on this console-based game (in c) in which the player walks around touches floating orbs which do things ect. and I want to make it so that an object on the map blocks the sight of the player, which is something I haven't tried until now. This is the part of the code which handles this sort of thing :

void uncover(int shadow)
{
int wp,
hp,
xp,
yp,
pp, // point placement
mp, // maximum pp value // (that's what she said)
lp; // light placement

struct point
{ int x;
int y;
} plist[100];

pp=0;
if(shadow==1)
{
for(hp=0; hp<19; hp++) /* first pass gets blocking points... */
{
for(wp=0; wp<19; wp++) /* || */
{
if(sqrt((wp-x)*(wp-x)+(hp-y)*(hp-y)) <= light ) /* if the spot is neer the player and its not already visible */
{
if(map[z][hp][wp]!='.')
{
plist[pp].x=wp;
plist[pp].y=hp;
pp++;
}
// mask[z][hp][wp]= 1; /* it does not yet become visable*/
}
}}
}
mp=pp;
int inspection; /* inspection =1 if passed 0 if failed */
for(hp=0; hp<19; hp++) /*...second pass tests if points are within their shadow. */
{
for(wp=0; wp<19; wp++) /* || */
{
inspection=1; /* next inspection is innocent until proven guilty */
for(pp=0; pp<mp; pp++)
{
if(
plist[pp].x>x
&&wp>plist[pp].x
||
plist[pp].y>y
&&hp>plist[pp].y
||
plist[pp].x<x
&&wp<plist[pp].x
||
plist[pp].y<y
&&hp<plist[pp].y
)
{
inspection=0;
}
}
if(sqrt((wp-x)*(wp-x)+(hp-y)*(hp-y)) > light ) /* if the spot is far from the player */
{
inspection=0;
}
if(inspection==1)
{ mask[z][hp][wp]=1;
}
}}

}

This <works> but isn't very nice. What I would like to do is to change the third to last if statement, which is really more of a geometry problem, which could be frased as :

given points (x,y) , (plist[pp].x,plist[pp].y) and (wp,hp) create a conditional which tests weather or not point (wp,hp) is within the shadow cast by light-source (x,y) being blocked by an object at (plist[pp].x,plist[pp].y), [with some width, ~1]

but there isn't a geometry forum, and it's somewhat more related to programming.

Thank-You

SigTerm · 03-25-2011, 01:59 PM

Quote:

Originally Posted by moongodjon

given points (x,y) , (plist[pp].x,plist[pp].y) and (wp,hp) create a conditional which tests weather or not point (wp,hp) is within the shadow cast by light-source (x,y) being blocked by an object at (plist[pp].x,plist[pp].y), [with some width, ~1]

A shadow in 2d is defined by two directions formed by light source and object edges.
A direction in 2D is defined by point and rotation angle (that would rotate x axis to make it point into right directioN).
In case of 2D shadow light source serves as a reference point for calculating shadow directions.
To find out whether a point is within a shadow, you need to ensure that it is

Behind the shadowcaster.
The angle to point you test is located between angles created by shadow.

All calculation are relative to light source (i.e. light source is the point of origin).

The rest should be trivial.

Nominal Animal · 03-25-2011, 02:56 PM

Note: please use [CODE][/CODE] tags for code snippets (and indent the code for readability).

Quote:

Originally Posted by moongodjon

I want to make it so that an object on the map blocks the sight of the player

I think you mean that you wish to check which objects are visible to the user, and lighted by at least one light source not too far away?

As it happens, mathematically the tests are actually the same, with the sum illumination masked by the observer tests. (Distance attenuation can differ, although usually people just use 1/r^2 since that is easiest to compute and looks pretty realistic.)

The implementation and the math depends on whether you use a map with fixed-size tiles, or an object list.

Based on your code, I assume you have an object/tile map in map[][][] and an illumination/visibility map in mask[][][], right? Do you really use three dimensions? (That'd be a feat with console graphics.)

If you use a 2D tile map, I'd recommend creating an illumination map, the same size as the tile map. Whenever a light changes, or a tile is modified, you recompute the region near the changes. (This way you can use a lot of light sources without slowing down your game.)
Whenever the user/observer moves, you copy the maximum visible area to a temporary map, and mask it with the observer visibility map, to get the actual map to draw.

For the observer, you can use a data structure, a lookup table of sorts, which allows you to do the visibility test in O(width×height) time. If your light sources are all the same type, you can use another lookup table for illumination rules. (And that allows you to create flickering lights and so on, since every light change is just an O(maxdistance^2) operation, without consuming a lot of CPU time.)

The idea of this data structure is to build a list of tiles that may block a given cell, relative to origin. Each tile in the visibility map refers to one or more tiles (up to 3 for square tiles in 2D, up to 7 in 3D) with corresponding relative weights. If the referred to tile is not blocked, the weight multiplied by the visibility at that tile is added to the visibility of the current tile. The map must be processed in increasing distance from origin, so the list must specify tiles in increasing distance from origin too.

Code:

struct vref {
     signed char     dx; /* -1, 0, +1 */
     signed char     dy; /* -1, 0, +1 */
     unsigned short  m;  /* 0.0 .. 1.0 (*65535.0) */
};

/* If 3D, use 7 instead of 3! */
struct vtile {
     signed char     x;     /* -128..127, relative to source */
     signed char     y;     /* -128..127, relative to source */
     unsigned char   n;     /*  1..3, number of referred to tiles */
     signed char     dx[3]; /* -128..127, relative to source */
     signed char     dy[3]; /* -128..128, relative to source */
     unsigned char   m[3];  /*  0..255 = 0.0 .. 1.0, visibility factor */
};

The size of the needed struct vtile array depends on the distance attenuation -- basically you need an array that can hold the number of tiles that would be visible in a perfectly flat unobstructed plain in 2D, or empty space in 3D. I'm omitting the struct vtile construction for now. (Let's talk about that later in this thread, if you're interested.)

To apply the visibility map rules is very simple and very, very efficient:

Code:

/* Return 0 if tile at (x,y) is opaque, 255 if it is fully transparent.
 * Return 0 for tiles outside the map.
*/
int transparency(int const x, int const y);

/* Compute a visibility map. 255 = fully visible, 0 = not visible.
 * v is a pointer to the center of the visibility map (not upper left corner).
*/
void visibility(unsigned char *const v, int const stride,
                int const x, int const y,
                struct vtile const cell[], int const cells)
{
    int i, k, s;

    /* Center of the map is always fully visible. */
    v[0*stride + 0] = 255;

    for (i = 0; i < cells; i++) {
        s = 0;
        for (k = 0; k < cell[i].n; k++)
            if (cell[i].dx[k] == 0 && cell[i].dy[k] == 0)
                s += 255*255; /* Center is never blocked */
            else
                s += (int)cell[i].m[k] * (int)transparency(x + cell[i].dx[k], y + cell[i].dy[k]);

        if (cell[i].n > 0)
            v[cell[i].y*stride + cell[i].x] = s / (255 * (int)cell[i].n);
        else
            v[cell[i].y*stride + cell[i].x] = 0;
    }
}

Note that v points to the center of map, so you'd use it like this:

Code:

unsigned char mask[21][21];
struct vtile  cell[21*21];

visibility(&(mask[10][10]), 21, x, y, cell, 21*21);

Note that the above implementation assumes that blocking objects themselves are visible, unless blocked by something else; it also uses 256 distinctive visibility or lighting levels (0 to 255, inclusive).

This algorithm works fine for all regular plane- and space-filling tilings. (I would only implement it if there is only one tile shape; the data structures become quite hairy if there are more than one tile shape in the plane or space.)

Does this look like something you'd like to implement?

moongodjon · 03-25-2011, 09:03 PM

(@nominal animal)
a) I don't need anything that complicated.(although that would be kind-of cool), I just need an expression which evaluates true if the point (wp,hp) is behind something seen by the player, in which (x,y) is the player, and (plist[pp].x,plist[pp].y) is any object the player sees.
b) map[][][] isn't used as a 3d array but a 1d array of 2d arrays if that makes sense, and mask[][][] is an int array with the same dimensions as map[][][] in which each point is 1 if the coresponding point on map[][][] is visable by the player and 0 if not.
c) my game doesn't use light sources(sorry if my explanation was confusing)...see a).

(@sigterm)
yes. I understand that, but what I am asking for is the "trivial" expression as defined in a).

z) All I really need to know is : how do I test the angle of a point relative to another point???

zz) ps. the code is hosted at https://github.com/moongodjon/cursesrooms

moongodjon · 03-25-2011, 09:43 PM

why does

Code:

 if((plist[pp].y-y)/(plist[pp].x-x)+1>(hp-y)/(wp-x)>((plist[pp].y-y)/(plist[pp].x-x)-1))

produce a "Floating point exception" run time error???

Nominal Animal · 03-26-2011, 02:33 PM

Quote:

Originally Posted by moongodjon

a) I don't need anything that complicated.(although that would be kind-of cool), I just need an expression which evaluates true if the point (wp,hp) is behind something seen by the player, in which (x,y) is the player, and (plist[pp].x,plist[pp].y) is any object the player sees.

You also need the object size in order to calculate that properly; for example, plist[pp].r if the objects are cylindrical or spherical. Or are all objects the same size, 1 (tile)?

This is actually very easy to solve using vector math. Can you use floating point numbers (doubles), or are you programming for an integer-only platform?

Quote:

Originally Posted by moongodjon

b) map[][][] isn't used as a 3d array but a 1d array of 2d arrays if that makes sense, and mask[][][] is an int array with the same dimensions as map[][][] in which each point is 1 if the coresponding point on map[][][] is visable by the player and 0 if not.

Ah. Levels?

Nominal Animal · 03-26-2011, 02:40 PM

Quote:

Originally Posted by moongodjon

why does

Code:

 if((plist[pp].y-y)/(plist[pp].x-x)+1>(hp-y)/(wp-x)>((plist[pp].y-y)/(plist[pp].x-x)-1))

produce a "Floating point exception" run time error???

Because you divide by zero whenever the object in plist is at the same column or row as the user, and also when wp == x.

Note that you're not testing what you think you are.

Code:

    if (a < b < c) ...

is actually

Code:

    if ((a < b) < c) ...

where (a < b) is either TRUE or FALSE, depeding on whether a is smaller than b or not.
So you are comparing whether c is larger than TRUE or FALSE, which does not make much sense to me.

Nominal Animal · 03-26-2011, 03:48 PM

Here's a test program you might wish to try.

Code:

#include <unistd.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

typedef struct {
    int     x;
    int     y;
} coord_t;

/** occluded() - Occlusion test for tiled maps
 *  @point       Point tested for occlusion
 *  @source      Observer or light source
 *  @object      Coordinates for occluding tiles
 *  @objects     Number of objects to test
 * This function will return zero if @point is not occluded,
 * one if @point is occluded by an @object.
*/
int occluded(coord_t const point,
             coord_t const source,
             coord_t const object[], int const objects)
{
    double const    x = (double)(source.x - point.x);
    double const    y = (double)(source.y - point.y);
    double const    d = sqrt(x*x + y*y);
    int             o;

    /* Point at source is never occluded. */
    if (source.x == point.x && source.y == point.y)
        return 0;

    for (o = 0; o < objects; o++) {
        double const    ox = (double)(object[o].x - point.x);
        double const    oy = (double)(object[o].y - point.y);
        double const    od = sqrt(ox*ox + oy*oy);

        /* If the object is further than the point,
         * it cannot occlude the point. */
        if (od > d + 0.5 || od < 0.8)
            continue;

        /* Project object to the same distance as point.
        */
        {   double const    px = ox * d / od;
            double const    py = oy * d / od;
            double const    pr = 0.5 * (d / od);

            /* Not within the same tile? */
            if (px < x - pr || px > x + pr ||
                py < y - pr || py > y + pr )
                    continue;

            /* Same tile; point is occluded. */
            return 1;
        }
    }

    /* No occlusions found. */
    return 0;
}

int main(void)
{
    char        map[41][43];
    coord_t     user;
    coord_t     wall[100];
    coord_t     p;
    int         i, n = 0;

    for (p.y = 0; p.y <= 40; p.y++)
        for (p.x = 0; p.x <= 40; p.x++)
            map[p.y][p.x] = '.';

    for (p.y = 0; p.y <= 40; p.y++) {
        map[p.y][41] = '\n';
        map[p.y][42] = 0;
    }

    srand((unsigned int)time(NULL));

    /* Observer */
    user.x = 10 + rand() % 21;
    user.y = 10 + rand() % 21;

    /* Random walls */
    while (n < 20) {
        wall[n].x = rand() % 40;
        wall[n].y = rand() % 40;
        if (wall[n].x == user.x && wall[n].y == user.y)
            continue;
        n++;
    }

    /* Draw the user and the walls to the map */
    map[user.y][user.x] = 'o';
    for (i = 0; i < n; i++)
        map[wall[i].y][wall[i].x] = 'x';

    /* Check for occlusions */
    for (p.y = 0; p.y <= 40; p.y++)
        for (p.x = 0; p.x <= 40; p.x++)
            if (map[p.y][p.x] != 'o')
                if (occluded(p, user, wall, n))
                    map[p.y][p.x] = '#';

    /* Output the map. */
    for (p.y = 0; p.y <= 40; p.y++)
        fputs(map[p.y], stdout);

    return 0;
}

Note that this is much slower than the method I described in my first post. The other method has the additional benefit of not needing a separate array for occluding objects, as you can use the map directly, with a separate lookup table of transparencies/opacities/occlusion factors for each map tile type.

SigTerm · 03-27-2011, 12:48 AM

Quote:

Originally Posted by moongodjon

z) All I really need to know is : how do I test the angle of a point relative to another point???

Using arctangent function (atan). Subtract origin("another point") from point, calculate tangent (y/x) of a difference vector, calculate arctangent, correct the results according to y and x signs of difference vector (atan returns values in +-pi/2 range so you should adjust returned value by +-pi/2 depending on signs), avoid divide by zero.
Tangents and arctangents should be mentioned in school's trigonometry program.

moongodjon · 03-27-2011, 07:10 AM

@sigterm,

I haven't taken trig yet(I'll probably take it next year), and your language is a tad hard to read, could you rephrase that, perhaps as an expression?

moongodjon · 03-27-2011, 08:20 AM

@Nominal animal

could you elaborate on this part of the code :

Code:

        /* Project object to the same distance as point.
        */
        {   double const    px = ox * d / od;
            double const    py = oy * d / od;
            double const    pr = 0.5 * (d / od);

            /* Not within the same tile? */
            if (px < x - pr || px > x + pr ||
                py < y - pr || py > y + pr )
                    continue;

and also what is the continue statement?

ps. in your test program look at the case wall[n].x=user.x ;wall[n].y=user.y+1;

Nominal Animal · 03-27-2011, 09:05 AM

Quote:

Originally Posted by moongodjon

@Nominal animal

could you elaborate on this part of the code :

Code:

        /* Project object to the same distance as point.
        */
        {   double const    px = ox * d / od;
            double const    py = oy * d / od;
            double const    pr = 0.5 * (d / od);

            /* Not within the same tile? */
            if (px < x - pr || px > x + pr ||
                py < y - pr || py > y + pr )
                    continue;

First, the continue statement skips the rest of the code for this loop, and continues with the next round.

The above snippet works by "pushing" the possibly occluding object to the same distance as the point we're testing for, using the observer position as origin. To have the object cover the same visual angle from the observer, we need to "grow" it as we push it further. pr is the adjusted visual size ("radius") of the object.

In other words, the above code can be explained in plain English as:

If we push this object to the same distance as the tested point is, relative to the observer, and grow it at the same time so that it'll still be the same angular size from the observer's point of view, does it overlap the tested point? If not, go to the next round of the innermost loop.

Quote:

Originally Posted by moongodjon

ps. in your test program look at the case wall[n].x=user.x ;wall[n].y=user.y+1;

Oops

It was a thinko. I edited the code, changing od > d + 1.0 to od > d + 0.5, which fixes it, I think.

SigTerm · 03-27-2011, 01:34 PM

Quote:

Originally Posted by moongodjon

@sigterm,

I haven't taken trig yet(I'll probably take it next year),

Then I'd suggest to get trigonometry book and read about tangents/arctangents ahead of school's course. You could also borrow someone's lectures, or ask your math teacher to explain arctangent to you. Knowledge about sine, cosine, tangent, vector algebra and Pythagorean theorem is absolutely necessary for making games. There should be also articles on the internet - along with explanations.

Quote:

Originally Posted by moongodjon

and your language is a tad hard to read, could you rephrase that, perhaps as an expression?

You really should have found solution yourself, so get a trigonometry book:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

const float pi = 3.14159265f;

float getVectorAngle(float x, float y){
	bool negX = x < 0, negY = y < 0;
	float tanValue = 0;
	if (x == 0){
		if (negY)
			tanValue = -pi*0.5f;
		else
			tanValue = pi*0.5f;
	}
	else
		tanValue = y/x;
	float result = atan(tanValue);
	if (negX)
		result += pi;
	if (result < 0)
		result += pi*2.0f;
	return result;
}

float getVectorAngle(float x, float y, float originX, float originY){
	return getVectorAngle(x - originX, y - originY);
}

int main(int argc, char** argv){
	const int numAngles = 256;
	for (int i = 0; i < numAngles; i++){ //test
		float angle = pi*2.0f*(float)i/(float)numAngles;
		float length = (float)((rand()&0xff)+1);
		float x = cosf(angle)*length;
		float y = sinf(angle)*length;
		float vecAngle = getVectorAngle(x, y);
		float diff = vecAngle - angle;
		printf("angle: %f, getVectorAngle result: %f, difference: %f, vector: (x:%04.2f, y:%04.2f)\n", angle, getVectorAngle(x, y), diff, x, y);
	}
	return 0;
}

Note that this is a C++ code, which may not be a valid C code.
getVectorAngle(float, float) returns angle between any vector and x axis.
getVectorAngle(float, float, float, float) returns angle of a vector (originX, originY)->(x, y) and xAxis.
For your example originX, originY is a position of a light source, and x, y is a position of a point.

Nominal Animal · 03-27-2011, 03:40 PM

Quote:

Originally Posted by SigTerm

Then I'd suggest to get trigonometry book and read about tangents/arctangents ahead of school's course.

Seconded. Trigonometry, basic vector algebra, and some descriptive geometry will give you the tools you need to solve these kinds of problems without breaking a sweat.

@SigTerm: You do realize there is a atan2(y,x) (man 3 atan2) in math.h, which returns the angle in radians ([-π,π]) between (x,y), origin, and the positive x axis?

SigTerm · 03-27-2011, 04:29 PM

Quote:

Originally Posted by Nominal Animal

S
@SigTerm: You do realize there is a atan2(y,x)

Forgot about this one/wasn't sure if this is standard.
Understanding how it works won't hurt anyway.