They say that for every problem there is a solution which is simple, elegant, and wrong. I found mine today while working on ETD, and I also find the correct solution (which is also elegant, although a bit less simple).

One of the rules of the “Tower Defense” games is that you cannot completely lock the path that the enemies take from the entrance to the exit of your maze. This path may be as long as it takes, but it must exist. In my implementation, I’m writing in each cell of the path the cost to go to the exit, so that each enemy does not need to calculate their exit paths all the time. Then I have to have a “locking detection” routine that detects if placing an aditional tower in a given location will lock down the maze or not, to prevent that tower from being put.

My first idea was to see what are the distance values of the cells the new tower is going to occupy. If those values were not repeated anywhere else in the maze, that means that that path is a bottleneck, and cannot be blocked. Thinking this solution for a bit while showed that it was wrong (exercise to the reader :-P). The new solution is thus: The entrance and the exit of the maze bissect the surrounding walls into two groups. I give each of this group a flag, and I check each tower when it is put down to see if it connects to one of the groups. If it does, I give it the same flag as the group. If a tower connects BOTH groups, then it means that it blocks the path from the entrance to the exit. I only have to deal with the special case of “island” towers, by giving them a third, “neutral”, group flag, which is painted 1 or 2 when one of the groups reaches the island.

I have not finished implementing the above, but I have implemented most everything else that I needed from the map. I did not have as much time to program today as I had yesterday because I used the bright sunny day to walk around a little bit, clean my home (including washing the dreaded bath), and meeting my friend Dionisio. All in all, I had about 4 hours to hack away at ETD today, and I think I managed quite a bit in this time. Tomorrow I’ll finish implementing the maps, then a bit of tower logic, then link the genome with the tower and the map :-) I hope!