快速判断塔防迷宫中的割点(Tarjan算法)

凡是允许玩家自行建造迷宫的塔防游戏都有一个规则,那就是不允许玩家封死迷宫。目前我观察到的塔防游戏大概有三种处理方法:

  1. 基于魔兽RPG地图的塔防大多有这种设定,当玩家封死迷宫后,怪物会变成主动攻击玩家的炮塔。
  2. 另外有一些作品,比如《防御阵型:觉醒》,当玩家封死迷宫后,怪物可以从炮塔建筑的间隙中穿过。
  3. 还有一些作品,比如《兽人必须死》,游戏根本就不允许你在可以封死迷宫的位置建造炮塔。

第一处理方法是比较简单讨巧的。当玩家建造或拆除炮塔后,游戏必然会重新触发一次怪物的寻路。如果此时发现无法到达终点,那么久开启怪物的攻击性。

第二种方法更加简单,建造炮塔的位置并不是完全封死的,而是给一个极大的障碍权重值。这样,寻路算法自然会在路被堵死的时候穿越炮塔了。

难就难在第三种处理方法:我要怎么知道建造了哪些炮塔后路会被堵死?

继续阅读