AI algorithm idea

I was playing Battle for Wesnoth earlier and became interested in the problem of partitioning all the enemy units according to which defensive position they're headed for. That interest was actually motivated by watching my enemy react to the movement of my units.

I don't know what approach Wesnoth uses ... it's probably much more advanced, but I proposed a simple solution that should be pretty accurate.

After the enemy units take a turn, compare the current position of each enemy unit to its previous position. If the new position reduces the distance from the enemy unit to one or more defensive position, take whichever one is closest and assume that the enemy is moving towards that defensive position.

The first solution you might think of is picking arbitrary units and doing a kind of breadth-first search around them until it finds clusters of enemies, then tracking these clusters. The simple yes/no question of whether a unit occupies a given hex grid asked repeatedly by such an algorithm would make it a lot cheaper than having to number crunch the distance for each enemy unit and defensive position ... when enemies move together in tight groups. But in a game like Wesnoth, units can spread out when using attrition tactics and even when using conventional tactics, if certain units have much greater movement rates than others. So the BFS approach doesn't work generally.

Still, this approach isn't computationally terrible. Since the total number of distances calculated is — defensive positions times enemies, doubled because the current position has to be compared with the previous position in each pairing of defensive positions with enemy units. So the algorithm consistently runs at .

That's the basic approach, but there are a few ways it could be improved. A few suggestions from myself and others:

One of the considerations I had immediately after coming up with the algorithm is that feints and even honest temporary retreats sometimes break up an approach. A simple way to handle this fact is to assign each defensive position a number and keep a running average of how many times an enemy unit attempts to approach which defensive positions. The expected value, then, is the most likely target of the enemy unit. For instance, say a castle is labeled zero and an outlying keep is labeled one. If an enemy unit is seen to approach the castle four times but has to head away from powerful guards towards the keep one time, the expected value is .20. Round that down to zero and the enemy is considered to be approaching the castle.

Neural networks would be ideal for detecting feints and other maneuvers, but I don't want to get bogged down in that shit right now. Maybe when I'm doing grad research.

If parts of the terrain are impassible, it's reasonable to assume that enemy units moving in a certain corridor are headed in a certain direction. The way to track enemies according to those data would be to flag passages in between large tracts of difficult terrain—passages that are shorter than the paths around the masses that surround them—and take note whenever an enemy crosses them. That might not even be worth the effort though.

Another idea is to look at the algorithm sailors use to anticipate collisions, Closest Point of Approach. A variant of this algorithm can be very useful when the defenders are moving and when movement of units is continuous. (On a game board, time and space are discrete.)

Someone else suggested that, if there's any ambiguity in whether an enemy unit is approaching a given position (i.e., might be approaching two or more positions), there should be a probability of attack attached to each position to clear up the ambiguity. Calculating that probability might be difficult though. A castle is worth more for the enemy than a small keep, but, for example, a few lesser units stand no chance against a hardened facility. There are so many factors to take into account and it would probably be necessary to analyze games for each possible approach. Overall, I feel that this algorithm should be limited to gathering data on movement; threat assessment should be a separate task altogether.