We used this algorithm in the RTS Outpost 2 in 1997. I think the original Command and Conquer did something similar. Given the hardware of the time and the (re

We used this algorithm in the RTS Outpost 2 in 1997. I think the original Command and Conquer did something similar. Given the hardware of the time and the (relatively) large maps, we couldn't just use A. Fun fact: There was a building called the "Robot Command Center." If you had one, path finding was upgraded by first running this method, and then running A constrained to some distance from the initial path. The result was a more efficient path that removed silly bits of backtracking and so forth. I've not seen another RTS where there was an upgrade that affected path finding.