Pathfinding - Infrastructure

After supplying our AI with an easy way to find its path from everywhere to everywhere, we want it to do something useful. And in order to win a game in Squar, our AI has to build some infrastructure.

Again we will do some kind of pathfinding, this time for what we call the "buildpaths". Boring? Not at all! What we are doing now will be quite different to what we did before, because of the different circumstances.

The major differences to our navigation pathfinding are the following:
a) While the walls on our map are static, the squares on which we can build towers are not! Whenever our enemy builds a tower on a hitherto neutral square we have to build around this tower. So the pathfinding we apply for our buildpaths has to be dynamic (i.e., it has to be performed at runtime) - which means that can not use something as expensive as Floyd/Warshall anymore.
b) While our graph for navigation contained edges between diagonal neighbors (and I pointed out that this was indeed necessary) we don't have diagonal edges here, because our infrastructure is restricted to orthogonal connections.

While a) means that we have to do things efficiently, b) tells us that we are lucky enough to have an algorithm for this situation that runs in O(n):
As we have a single source shortest paths problem one could think that something more expensive would be needed, but in a graph where all edges have the same costs we can simply use a modified breadth-first search (BFS) as follows:

Initially, let our BFS-queue contain all squares that are somehow connected to our base. For all these squares we can store that it costs us 0 towers to connect them to our base. As long as our queue is not empty we take a square ("square") from the queue.

Starting in square, we we walk up to 4 steps in all 4 (orthogonal) directions.
As long as we don't encounter something that blocks our way (e.g., an enemy tower) we know that we could build a tower here ("nextsquare"), which would raise our costs to reach this position by 1 (compared to "square"). If we already found a cheaper way to reach nextsquare before, we do nothing. But if our new way to reach nextsquare is cheaper than what we have found out until now, we will update the costs to reach nextsquare by costs[square]+1 and define buildpathpredecessor[nextsquare] = square.

There are some little exceptions:
E.g., we have to make sure that we do not step over the border of our gameboard. Or, e.g., we can build a connection under a wall (i.e., we will not break if we detect a wall while going into a direction), but we can not build a tower under a wall (i.e., we will never set a wallsquare as a predecessor).



Once we have calculated the cheapest buildpathcosts and predecessors for all squares, we simply check which source (resp. its neighbors) are the cheapest to connect to our base.

Then we walk the corresponding buildpath backwards (by help of the array buildpathpredecessor) and compare for every square on the path the distance of our tank to this square.

The square that is returned will be the next square we build a tower on.