【下载文档:  Python 连连看连接算法.txt 】

---

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