top down game - checking, drawing enemy's line of sight area with obstacles

Question

Examples of what i'm going to need:

I'm using cocos2d to draw a CCTMXTiledMap, on those tiles i'll have to draw the LOS cone.

How would i test if the player is within that cone, taking obstacles into account? How would i draw the line of sight area on the map tiles, again taking obstacles into account, like in the examples above?

This is a re-post of a question i've put on stackoverflow.

Answer 1

There's an article on GDNet about walls and shadows in 2D; the technique can be applied to visibility determination as well. Additionally there this old-school post on 2D visibility, this post on StackOverflow and a variety of other resources online you can find via Google.

Once you have a logical understanding of the visibility region for an agent in your game, you can convert that to a visual one for display (you can and should keep these distinct, so you could render a smooth cone even if your algorithm is working with tiles, for example).

One way to do that is with a stencil buffer -- you render your normal scene, and write to the stencil buffer every time you draw an obstacle, then render your visibility cone with an appropriate stencil test enable. Unfortunate cocos2d may not support the requisite functionality for you to do this (but that linked thread has some notes on using texture combiners to simulate the effect).

An alternative, very crude, solution if your game is more like the second screenshot you posted (top-down) is to render the floors, then render the visibility regions, then render obstacles. However this will not give you the effect like in the Commandos screenshot where you can see that the tree (for example) are blocking the visibility.

The GDNet article discusses a rendering technique as well, but it's triangle-based and will need some adjustment to remove the jagged edges it produces.

Answer 2

First, most of these sensors system don't use "triangles", but an opening angle and a distance at which the NPC can detect the player. Doing this kind of detection is pretty easy, determine the distance and angle between the heading of the NPC and the player's position. Using these two values you can test if the player is within the range of the sensor, if it is you can then apply the more costly check, a ray cast that tests if an obstacle is between both characters. If the raycast doesn't hit anything, you see your target, otherwise you don't see it.

As for rendering... you either follow the same strategy that is used for projected shadows or you could render a "triangle fan" representing your sensor after rendering the floor and before rendering the obstacles and actors, allowing you to see the sensor on top of the floor but below everything else. This will not be as good looking as the projected sensors and will not take obstacles into account (removing parts of the sensors when hitting an obstacle) but should be faster to implement and have a lower processing cost.

Answer 3

The project I asked this question for (2 years ago) didn't progress, but I got to tackle this issue again. I actually implemented the line of sight thing treating it as a red light. This is the tutorial that helped finally understand how to get it done: http://archive.gamedev.net/archive/reference/programming/features/2dsoftshadow/

I made a CCNode subclass that overrides the 'draw' method and put the rendering code in there, the class also received an array of shadow caster classes that had convex hull data...

Answer 4

I used an A* search algorithm. If your game is rendering tiles, then use this to determine if the tiles are solid or not. It creates a path of "passable" tiles for the enemy to follow the player around walls, in the shortest distance. It could easily be adapted for detecting if the surrounding tiles are solid or not (see through or not). Basically, you need something like the following:

public List<Tile> visibleTiles(Entity e){
    List<Tile> visibleTiles = new ArrayList<Tile>();
    Tile at = null;
    for (int i = 0; i > 9; i++){
        int x = current.tile.getX();
        int y = current.tile.getY();
        int xi = (i % 3) - 1;
        int yi = (i / 3) - 1;
        Tile at = getTile(x + xi, y + yi);
        if (at.isSolid()){
            continue;
        } else {
            visibleTiles.add(at);
        }
    }
    return visibleTiles;
}

This will search the tiles surrounding the entity passed through, and return a list of tiles that are "visible". All you need to do is update them so they appear to be lit up. Hope this is helpful. Apologies it is in Java, it is taken from my game which is Java. Hope you get the idea though