How to easily detect walls within a sight map? (FPS - Eye of the Beholder style)

Started by
3 comments, last by tonemgub 9 years, 2 months ago

Hello

I've been working on an Eye of the Beholder kind of game. For a good idea, I attached a few screenshots. Some of the art is temporary.

I have the following algorithm that checks what is in the actor's current sight. It somewhat takes an extreme approach that gets everything around the player, and then you can make calls on the current direction he is facing.

I reduced the code for readability.


int Actor::view(Map &map)
{
    // Sight area with a depth of 3. The actor is always at the center.
    char sight[] = {
        0, 0,  0,  0,  0, 0, 0,    // 0-6
         0, 0,  0,  0,  0, 0, 0,    // 7-13
        0, 0,  0,  0,  0, 0, 0,    // 14-20
        0, 0,  0, 'A', 0, 0, 0,    // 21-27
        0, 0,  0,  0,  0, 0, 0,    // 28-34
        0, 0,  0,  0,  0, 0, 0,    // 35-41
        0, 0,  0,  0,  0, 0, 0    // 42-48
    };

    char c;  
    int x_center = 3;
    int y_center = 3;

    // Build the actor's sight table
    for (int y = 0; y < 7; y++) {
        for (int x = 0; x < 7; x++) {
            sight[y * 7 + x] = map.peek(m_x, m_y, x - x_center, y - y_center);
        }
    }

    // Check the actor's facing direction
    switch (m_dir)
        {
        case EDir_N:
            {  
                /*
                WWW
                W*W (North-facing)
                */
                if (sight[N] == WALL && sight[E] == WALL && sight[W] == WALL)
                    return WALL_UP_CLOSE;
            }
            break;

        case EDir_E:
            {   
                /*
                WW
                *W (East-facing)
                WW
                */
                if (sight[E] == WALL && sight[N] == WALL && sight[S] == WALL)
                    return WALL_UP_CLOSE;
            }
            break;

        case EDir_W:
            {  
                /*
                WW
                W* (West-facing)
                WW
                */
                if (sight[W] == WALL && sight[N] == WALL && sight[S] == WALL)
                    return WALL_UP_CLOSE;
            }    
            break;

        case EDir_S:
            {
                /*
                W*W
                WWW (South facing)
                */
                if (sight[S] == WALL && sight[E] == WALL && sight[W] == WALL)
                    return WALL_UP_CLOSE;
            }
            break;
        }

    return -1;
}

As you can see, each direction has about the same check and the same returning ID. The returning ID draws the correct batch of images to the screen.

Although I reduced the code a few times, I feel I can reduce it even more. My question is, well, how can I reduce it? The player is facing a dead end on all four directions, so I feel I could just check it once somehow. I'm always tracking the player's position, so it helps me know what to draw.

I guess right now it just bugs me that there's 4 conditions to return the same ID based on direction. Can it be possible to have only one condition and not loose focus of the current facing direction?

Advertisement

It's not quite what you're looking for, but these might help:

http://www.roguebasin.com/index.php?title=Field_of_Vision

http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html

http://www.redblobgames.com/articles/visibility/

In this particular case, easiest solution would be to add a function getReverseDirection() to return north on south, west on east etc.

Then your checks would just become a check to see if the reverse direction is not wall and another check to see if at least 3 of the 4 surrounding cells ARE wall.

So 1. check each direction if there is a wall, and increment a counter by 1 (count surrounding walls)

2. check that the direction behind you is not a wall

3. If in 1 you counted 3 walls (or 4 I guess), then because of check 2 it follows youre facing a dead end

I often try to use integer vectors (int x,y thrown in a class) to represent directions (0,1 / 1,0 / -1,0 / 0,-1) since its easier to do things like "get the reverse direction" or "get the adjacent position to player" using nothing but math (with enums you end up with a lot of conditional logic). Also I usually have an easy way to iterate over all directions (simple way to do that is to just have a vec2 allDirections[4]; around to use in a for loop)

o3o

I wouldn't necessarily recommend doing a game this way today - even a homage game - but there's a few things you can do to simplify your work.

I will point out the book Gardens of Imagination. It's not necessarily the best book in many respects, and it's super out of date (it was written in the DOS era), but it has various algorithms and approaches for developing early era maze games. I mention it mostly out of nostalgia (I think it was the first game development book I ever got my hands on as a kid, back in the days when you _needed_ books because there was no Internet in every home) and not a recommendation to buy (though it is only $0.01 on Amazon...), but if you can get your hands on a copy it might be of interest to you.

For your specific problem, you can simplify your thinking by working with our good ol' friends: matrices. Define all your vision checks in a single orientation, which we'll call your local perspective. Just a "forward" orientation. Your wall checks then become things like "is a wall directly in front of me" or "is a wall in front of and just to the right of me." These would be encoded as offsets form a local perspective. For instance, the first one might be `IsWall(1, 0)` (is there a wall one unit forward and zero units to the side) and the second one might be `IsWall(1, 1)` (one unit forward and one unit right) and then a check like "is a wall two spaces in front of me and two spaces to the left" would be `IsWall(2, -2)`.

You can now map a local perspective to a world location with a simple integral 2x2 rotation matrix (integral since you're only rotating by 90 degrees at a time, so the matrix will always be made up of 0's, 1's, and -1's). You can toss in the player's position in the world by extending it to a 3x3 affine transformation matrix. This matrix is calculated from the player's position and facing. The `IsWall` functions then additionally take this matrix as input; multiply the local perspective coordinates by this matrix and there you have the actual world position to check for in the world map file.

You can extend the map format to store wall edges in a grid instead of whole blocks and then you can have different textures on each wall easily.

Sean Middleditch – Game Systems Engineer – Join my team!

Caching. You could implement those checks as part of your level data - pre-compute all the possible return IDs for all four directions and all of the map cells (visibility data) and store them as part of your level, then just use the new visibility data loaded from the level during gameplay, and update it only when objects are removed/added. Maybe you could implement a tool which does this for all your levels, or you could build up the initial visibility data as part of the level-loading phase.

This topic is closed to new replies.

Advertisement