Python 连连看连接算法

功能：为连连看游戏提供连接算法
说明：模块中包含一个Point类，该类是游戏的基本单元“点”，该类包含属性：x,y,value。
其中x,y代表了该点的坐标，value代表该点的特征：0代表没有被填充，1-8代表被填充为游戏图案，9代表被填充为墙壁
模块中还包含一个名为points的Point列表，其中保存着整个游戏界面中的每个点
使用模块的时候应首先调用createPoints方法，初始化游戏界面中每个点，然后可通过points访问到每个点，继而初始化界面
模块中核心的方法是link，通过提供源点和终点，可尝试连接两点，如果可以连接则返回保存路径的path列表，否则返回False

复制代码 代码如下:
#-*-coding:utf-8-*-
\”\”\”连连看连接算法

为连连看游戏提供连接算法
模块中包含一个Point类，该类是游戏的基本单元“点”，该类包含属性：x,y,value。
其中x,y代表了该点的坐标，value代表该点的特征：0代表没有被填充，1-8代表被填充为游戏图案，9代表被填充为墙壁
模块中还包含一个名为points的Point列表，其中保存着整个游戏界面中的每个点
使用模块的时候应首先调用createPoints方法，初始化游戏界面中每个点，然后可通过points访问到每个点，继而初始化界面
模块中核心的方法是link，通过提供源点和终点，可尝试连接两点，如果可以连接则返回保存路径的path列表，否则返回False
\”\”\”
import random

__author__ =\”http://blog.csdn.net/anhulife\”
__license__ =\”python\”

class Point:
\”\”\”Point类

Point类是游戏中基本单元：“点”
\”\”\”
def __init__(self,x,y,value):
self.x = x
self.y = y
self.value = value
self.directs = None
self.changed = 0
def __createDirect(self,pre,target):
\”\”\”构造点的方向集

每个点在连接的过程中都持有一个方向集，这个方向集中保存着该点的前进方向选择的优先级
优先级：指向目标点的方向级别最高，在同等级别并且遵循x方向优先于y方向
\”\”\”
self.directs = list()
stx = target.x – self.x
sty = target.y – self.y
if stx >= 0 :
self.directs.append(\”right\”)
self.directs.append(\”left\”)
else:
self.directs.append(\”left\”)
self.directs.append(\”right\”)
if sty >= 0 :
self.directs.insert(1,\”up\”)
self.directs.append(\”down\”)
else:
self.directs.insert(1,\”down\”)
self.directs.append(\”up\”)
if pre == None :
return
spx = pre.x – self.x
spy = pre.y – self.y
if spx == 0 :
if spy == 1:
self.directs.remove(\”up\”)
else:
self.directs.remove(\”down\”)
else :
if spx == 1:
self.directs.remove(\”right\”)
else:
self.directs.remove(\”left\”)
def forward(self,pre,target):
\”\”\”点的前进动作

点的前进即是依次从方向集中取出优先级高的方向，并判断该方向上的下一个点是否被填充
如果没有被填充则说明该方向可通，并返回该方向。否则试探下一个方向，如果方向集中没有方向可用了，则返回None
\”\”\”
if self.directs == None :
self.__createDirect(pre,target)
if len(self.directs) == 0 :
return None
direct = None
while(True):
if len(self.directs) == 0 :
break
tmpDirect = self.directs.pop(0)
if tmpDirect == \”up\” :
x = self.x
y = self.y + 1
elif tmpDirect == \”down\”:
x = self.x
y = self.y – 1
elif tmpDirect == \”left\”:
x = self.x – 1
y = self.y
elif tmpDirect == \”right\”:
x = self.x + 1
y = self.y
p = points[x][y]
if p.value > 0 and p != target:
continue
else :
direct = tmpDirect
if pre == None:
self.changed = 1
else:
if (pre.x – self.x) == 0 and (p.x – self.x) == 0:
self.changed = 0
else:
if (pre.y – self.y) == 0 and (p.y – self.y) == 0:
self.changed = 0
else :
self.changed = 1
break
return direct
def isChanged(self):
\”\”\”判断方向变化

返回在该点前进时，是否带来了方向的变化，即方向不同于原方向
\”\”\”
return self.changed
def __eq__(self,p):
if p == None :
return False
if self.x == p.x and self.y == p.y :
return True
else:
return False
points = list()
def createPoints(w,h):
\”\”\”构造游戏界面的点

初始化界面中的所有的点，并且规则如下：
最外一层是“墙壁”点，接下来的一层是没有被填充的点，被包裹的是填充的点
\”\”\”
r = random.randint
for x in range(w):
temp = list()
for y in range(h):
if x == 0 or x == (w-1) or y == 0 or y == (h-1):
temp.append(Point(x,y,9))
else:
if x == 1 or x == (w-2) or y == 1 or y == (h-2):
temp.append(Point(x,y,0))
else:
temp.append(Point(x,y,r(1,8)))
points.append(temp)
def link(source,target):
\”\”\”点的连接

连接方法的思想：针对源点的每个方向尝试前进，如果可以前进，则将针对该方向上的下个点的每个方向尝试前进
当一个点的可选方向都不能前进的时候，则返回到已有前进路径中的前一个点，尝试该点其他可选方向。当回源点
的每个方向都走不通或是路径的方向变化等于4的时候，连接失败返回False。否则当路径连接到目标点而且路径的方向变化小
于4的时候，连接成功返回路径
\”\”\”
if source == target:
return False
path = list()
change = 0
current = source
while True:
if current==target and change < 4:
for p in path:
p.directs = None
return path
if change == 4:
current.directs = None
current = path.pop(len(path)-1)
change = change – current.isChanged()
continue
if change == 0:
direct = current.forward(None,target)
else:
direct = current.forward(path[len(path)-1],target)
if direct != None:
change = change + current.isChanged()
if direct == \”up\” :
x = current.x
y = current.y + 1
elif direct == \”down\”:
x = current.x
y = current.y – 1
elif direct == \”left\”:
x = current.x – 1
y = current.y
elif direct == \”right\”:
x = current.x + 1
y = current.y
print x,y
path.append(current)
current = points[x][y]
else:
if change == 0:
return False
else:
current.directs = None
current = path.pop(len(path)-1)
change = change – current.isChanged()
createPoints(8,8)
p = link(points[2][2],points[5][2])
print p