Compute what the player can see in turn-based grid strategy game

Unity Engine
1

Hello. I’m currently developing a game, in which every character are bound to cells. Each cell can have walls at their top/bottom/right/left and are linked to their neighbor cells (top/bottom/right/left again). I’d like to put in a list every cell currently visible to the player (it means they are not hidden by a wall). Until now, I’ve only used mathematics, and algorithms such as A* to navigate in the grid with my character, and I’d like to find a solution that doesn’t use Raycasting. Do you guys know an algorithm that can help me achieve that? The only thing you can do with cells are :
-Check where are the walls
-Get the neighboring cells you can navigate to.

Here is my current code, as you can see in the image, the visible cells, in blue, might be in corners that shouldn’t be visible from the character point of view.

//The classic pattern : everything in the field of view of the player
    protected List<GridCell> classicPattern(GridCell start, int range){
        int currentRange = range-1;
        int authorizedRange = 2;
        /* Initializing with adjacent cells */
        if (start.hasDown())
            reachable.Add(start.getDown());
        if (start.hasUp())
            reachable.Add(start.getUp());
        if (start.hasLeft())
            reachable.Add(start.getLeft());
        if (start.hasRight())
            reachable.Add(start.getRight());
       
   
       
        while (currentRange != 0){
            List<GridCell> tmp = new List<GridCell>();
            currentRange--;
            foreach(GridCell cell in reachable){
                if (cell.hasDown() && Math.CellDistance(start, cell.getDown()) == authorizedRange && !tmp.Contains(cell.getDown()) && !reachable.Contains(cell.getDown()))
                    tmp.Add(cell.getDown());
                if (cell.hasUp() && Math.CellDistance(start, cell.getUp()) == authorizedRange && !tmp.Contains(cell.getUp()) && !reachable.Contains(cell.getUp()))
                    tmp.Add(cell.getUp());
                if (cell.hasLeft() && Math.CellDistance(start, cell.getLeft()) == authorizedRange && !tmp.Contains(cell.getLeft()) && !reachable.Contains(cell.getLeft()))
                    tmp.Add(cell.getLeft());
                if (cell.hasRight() && Math.CellDistance(start, cell.getRight()) == authorizedRange && !tmp.Contains(cell.getRight()) && !reachable.Contains(cell.getRight()))
                    tmp.Add(cell.getRight());
            }
            authorizedRange ++;
            foreach(GridCell cell in tmp){
                reachable.Add(cell);
            }
        }
        return reachable;
    }

1476×732 201 KB

Thank you for your help guys and have fun coding games!

2

*Hi @TontonPixel *

Not sure if it’s 100 percent suitable, but I’d check roguelike lighting/shadowing algorithms, search for
roguelike octant lighting. Roguebasin also has tons of examples.

1 Like
3

How I would approach this is to floodfill tiles from the player outward, and only add tiles to the visible list when there is direct line of sight with the player. This way you incrementally build the visible tile list outwards and cull parts that weren’t visible anyway (eg. skip neighbors of non-visible tiles). How costly this is, depends on how accurate you want this to be. Do you want the ‘visible tiles’ to only include tiles that are completely visible or where any part is visible? You will probably have to check all 4 corners of each tile. You could also consider the tile visible if there is a direct line of sight from the player to the center of the tile, which would only require a single line of sight check.

Remember that these line of sight checks don’t have to be full-blown physics raycasts. Since your environment is essentially 2D, you can reduce to problem to whether two lines intersect eachother:

  • The line from the player to the location you are currently evaluating (center of the tile, corner of the tile?)
  • Each wall that you can represent as a line from (x1, y1) to (x2, y2)

As a naive approach, you could check intersection of the player line of sight with every wall line, but a simple and effective culling method is to only check walls that are within the same distance from the player as the point you are currently checking. Walls that are further away from the player can never intersect the line of sight anyway. There are probably other tricks you can apply to avoid having to check many walls. Maybe this is a great resource as well.

1 Like
4

Thank you for your advice! I solved my problem using the Bresenham’s line algorithm, as recommended in a Roguebasin article about Roguelike Octant lighting. For those it might interest, I proceed as follows:

  • I gather all the cells that would be seen by the player if there was no wall at all in a candidate list. They’re simply the cells close enough to the player’s character, depending on his vision range.
  • For each of these candidates, I try to draw a line with the Bresenham’s line algorithm. If I reach a point in the algorithm when I cannot reach the goal because of a wall, then the candidate cell is considered hidden
  • I enjoy the result!

Here is what the result looks like :

The hidden cells have not yet been visited by the player,
The gray cells have been visited but aren’t currently in player vision’s range,
The clear cells are currently in player vision’s range.

Since it’s a turn-based game, and the number of cells to check is quite low, there are no performance issues at all.

Bye guys, and thanks again.

2 Likes