Creating LOS zones on a 2D grid for chase AI

Question

I have a 2D grid, around 20x20, stored as an array. Each grid cell can contain an opaque object or not. I also already have an algorithm to calculate LOS between any two squares via Bresenham.

I want to implement an AI that chases the player in a step-time game. The current rules I have are (re-evaluated with this priority each step):

• If we can see the player go get them (a step at a time with Dijkstra/A* pathfinding).
• If we can't see the player go to where we last saw them.
• If we can't see the player and are where we last saw them, give up and head home.

But I want to add a further rule:

• If we can't see the player and are where we last saw them, but there is only one way they could have gone to now be hidden without coming past us, go that way.

This turns out to be really hard to detect. What I have wondered about doing is to assign each grid square one or more zone numbers, such that every square that is in a given zone can see all other squares in that zone; then if there is only one neighbouring zone than the guard has not visited the guard will move into it. However, the zones overlap and a ridiculously large number of them are generated for even simple maps (due to, for example, different parts of a room gradually becoming visible as you walk down a corridor into it) which makes this awkward or difficult, and the generation algorithm seems to be at least O(n^2) or worse. Alternatively the zones could be calculated as a navigation mesh but this seems very difficult to compute from a grid map.

Is there any way to do this without manually putting hints on the map?

Answer 1

This task can be surprisingly difficult in general; it is a variant of the Art gallery problem, and just like that problem, it is made dramatically harder with even slight complexities in the geometry.

But if you're willing to accept a flawed, "good enough" solution, here's one: leave a "vision trail", and assess whether there is only one exit that is not next to the "vision trail".

• When you spot the target, start marking all cells that you can see as "visited"
• After you have reached the target's last known position, inspect the boundaries of your LOS
  • If there is one exit which does not lead to "visited" cells, continue on to the unvisited exit, and keep going until this splits into two (or more)
  • If there are more than two exits that do not lead to "visited" cells, stop

Example of continuing condition:

                 |   |
                 |   | <--- unvisited exit
                 |...|
                 |...|
                 |...| <--- LOS
-----------------+...|
vvvvvvvvvvvvv......A.| <--- AI
---------------------+
         ^
      visited cells

Example of stopping condition:

                 |   |
                 |   | <--- unvisited exits (not contiguous)
                 |...|      |
                 |...|      |
                 |...|      v
-----------------+...+------------
vvvvvvvvvvvvv......A......
----------------------------------
         ^
      visited cells

The reason why this solution is "good enough" is because it will run into problems with edge cases like this one:

---------------------------------
vvvvvvv.........
vvvvvv.........+-+
vvvvv..........+-+
vvvv.......A......
---------------------------------

What should the AI do, in the presence of a small obstruction that splits the exit? Stop? Or continue? Remember, technically the target could be hiding just behind that obstruction and avoid being seen, and double back on your AI.

Virtually all problems of this kind (LOS, navigation) will be greatly simplified by performing some preprocessing, so that the geometry is simpler. It is then possible to do as you suggest - creating LOS zones - since we can make lots of assumptions with the simplified geometry. It is up to you to decide what kind of processing you can accept.

Answer 2

Eric Lippert presented a tutorial (in C# of course) on calculating Line-of-Sight with Shadowcasting for a square grid.

The first five sessions define various objects used in the algorithm, with the final code

private static Func<int, int, T> TranslateOrigin<T>(Func<int, int, T> f, int x, int y)
{
    return (a, b) => f(a + x, b + y);being this:


}

private static Action<int, int> TranslateOrigin(Action<int, int> f, int x, int y)
{
    return (a, b) => f(a + x, b + y);
}


private static Func<int, int, T> TranslateOctant<T>(Func<int, int, T> f, int octant)
{
    switch (octant)
    {
        default: return f;
        case 1: return (x, y) => f(y, x);
        case 2: return (x, y) => f(-y, x);
        case 3: return (x, y) => f(-x, y);
        case 4: return (x, y) => f(-x, -y);
        case 5: return (x, y) => f(-y, -x);
        case 6: return (x, y) => f(y, -x);
        case 7: return (x, y) => f(x, -y);
    }
}

and

public static void ComputeFieldOfViewWithShadowCasting(
    int x, int y, int radius,
    Func<int, int, bool> isOpaque,
    Action<int, int> setFoV)
{
    Func<int, int, bool> opaque = TranslateOrigin(isOpaque, x, y);
    Action<int, int> fov = TranslateOrigin(setFoV, x, y);

    for (int octant = 0; octant < 8; ++octant)
    {
        ComputeFieldOfViewInOctantZero(
            TranslateOctant(opaque, octant),
            TranslateOctant(fov, octant),
            radius);
    }
}

I have adapted this code for a terrain map on a hex-grid in my Hexgrid utilities project: Open Source under MIT Licence.