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

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

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

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

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

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

暴力但可行的办法
每当玩家想要在一个位置建造炮塔时,都重新跑一次寻路算法,看看能否从起点通向终点。如果不能的话,就不允许在当前位置建造炮塔。听起来是个挺耗费计算量的方法,但实际也是可行的。原因是一次只要对一个位置(玩家鼠标悬停的位置)进行寻路运算就行了,而且可以把运算的结果缓存下来,所以不会造成顿卡。

然而有更好的办法
如何知道建造了哪些炮塔后路会被堵死?其实是个著名的图论问题:求无向连通图的割点。解决这个问题有个线性时间复杂度的算法,Tarjan算法。算法的原理和实现都非常简单,具体可以参考wiki:https://en.wikipedia.org/wiki/Biconnected_component

运行这个算法后,我们可以获得一系列的割点。显然,我们想要的结果就在这些割点里面。然而,并不是所有割点都不可以放置炮塔。

未命名-1

如上图所示,B1、C2、D3和F5都是割点,但显然D3位置是可以放置炮塔的。实际上当我们运行算法时,只有处于start-end路径上的割点才是我们想要的。要实现这点也简单,只要在递归返回时加上状态就行了。

下面贴出测试代码:

g = [
#A B C D E F G H I
[1,1,0,1,0,0,0,0,0], # A
[1,1,1,0,0,0,0,0,0], # B
[0,1,1,0,0,1,0,0,0], # C
[1,0,0,1,0,0,1,0,0], # D
[0,0,0,0,0,0,0,0,0], # E
[0,0,1,0,0,1,0,0,1], # F
[0,0,0,1,0,0,1,0,0], # G
[0,0,0,0,0,0,0,0,0], # H
[0,0,0,0,0,1,0,0,1], # I
]

def neighbours(v):
	ret = []
	l = g[v]
	for i in range(len(l)):
		if i != v and l[i] == 1:
			ret.append(i)
	return ret

def dfs(start, end, d = 0, visited = {}, depth = {}, low = {}, parent = {}):
	visited[start] = True
	depth[start] = d
	low[start] = d
	childCount = 0
	isCutPoint = False
	reachedEnd = False

	for v in neighbours(start):
		if not visited.get(v, False):
			parent[v] = start
			reachedEnd = dfs(v, end, d + 1, visited, depth, low, parent)
			childCount += 1
			if low[v] >= depth[start]:
				isCutPoint = True
			low[start] = min(low[start], low[v])
		elif v != parent.get(start, -1):
			low[start] = min(low[start], depth[v])

	reachedEnd = reachedEnd or (start == end)

	p = parent.get(start, -1)
	if (p >= 0 and isCutPoint) or (p < 0 and childCount > 1):
		if reachedEnd:
			print("isCutPoint:", start)

	return reachedEnd

dfs(0, 8)

快速判断塔防迷宫中的割点(Tarjan算法)》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注