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?