I've reached a point in my current project at which I want to start working on the enemy AI, and find myself uncertain of an appropriate approach. I therefore come here in the hope of advice. The game is a 2D top-down shooter (which takes much inspiration from the Rogue-like genre as well). The play-field is a (theoretically, and hopefully seemingly) infinite plane, dotted about with "islands" - obstacles of fairly arbitrary shape, essentially. The problem arises from this: since the play-field is rather large, I'm not attempting to keep the entire thing in memory, but am rather generating it on the fly, constructing new islands as the player moves to new regions, and destroying them as the player moves away. The use of a calculated seed allows me to reproduce a given configuration of islands should the player return. Given this, pre-processing of the scene to produce enemy AI nodes doesn't seem to me to be a useful idea. I could attempt to pre-process each new section of islands once it has been generated, but I'm not confident of achieving this quickly enough for it to be not noticeable. Thankfully, there is fairly little for a given enemy to "consider": it should attempt to close on the player, avoid getting too close, avoid the player's line of fire, and not plan to fly through an island. My current primary idea is this: The basic idea: Strike out at random, generating a handful of paths, and find the best of them, preferring paths in line with the elements given above.

// Variables:
//  num_paths - the number of candidate paths generated when looking for a path
//              to take.
//  depth - the number of nodes to generate in a given candidate path.
//
// Each node has a score variable; positive scores are good, negative scores are
// bad.  For the enemy, that is - the player might see things the other way
// around. ;)

For i < num_paths:
 - For j < depth:
   - Strike out in a random direction, generating a target node.  (The direction
     may not be entirely random, instead being some perturbation of the current
     direction, especially for nodes after the first in a path.)
   - If the line between the previous node and the new node passes too close to
     an island (a comparison between the island's size and the distance between
     the island's origin point and the line being tested), assign the new node a
     very negative number, and terminate the current path.
   - Else, assign the new node a score - this score is increased by being close
     to a good firing distance from the player, and decreased by being close to
     the player's line of fire.

Find the path with the highest total score, taken simply as the sum of the
scores of its component nodes, and adopt this as the new path to follow.

Repeat at appropriate intervals.

The interval between AI recalculations, number of candidate paths spawned and depth of path search would all probably be member variables of the "Enemy" class, allowing for tweaking and, potentially, variation between creatures. I do see a problem with this: it's quite possible for this system to "jump" past a good position. This might be mitigated by point-to-line distance checks between the generated line and the player's position, but I'm not sure that this is a sufficiently efficient solution. I'm also not convinced that this algorithm would be sufficiently fast - while at first glance it doesn't appear too bad, I fear that good results might call for frequent recalculations and possibly deep planning as well. (I may well have missed other problems.) Another idea might be to find a desired location and construct a ray between that point and the enemy's current position. If this ray passes through an undesirable location, split it and offset the split in a direction orthogonal to that of the ray. Repeat as desired. Again, however, I question its efficiency, especially if a large number of splits are required, and I wonder how often it would fail to find a usable path... So, am I on the right track? If not, what do you suggest? If so, what improvements, if any, do you recommend? My thanks for any suggestions given. ^_^

This sounds like Steering Behaviors

Aah, thank you very much - that link proved rather useful. ^_^