新鲜出炉的连连看连接算法Python版
这段时间老是“不务正业”的搞一些东西玩。之前的贪吃蛇，俄罗斯方块激发了我研究游戏算法的兴趣。经过1个星期的构思，连连看的连接算法终于出炉了。再过一段时间就基于这个算法使用JavaScript推出网页版的连连看。下面是说明及代码。功能：为连连看游戏提供连接算法
说明：模块中包含一个Point类，该类是游戏的基本单元“点”，该类包含属性：x,y,value。
其中x,y代表了该点的坐标，value代表该点的特征：0代表没有被填充，1-8代表被填充为游戏图案，9代表被填充为墙壁
模块中还包含一个名为points的Point列表，其中保存着整个游戏界面中的每个点
使用模块的时候应首先调用createPoints方法，初始化游戏界面中每个点，然后可通过points访问到每个点，继而初始化界面
模块中核心的方法是link，通过提供源点和终点，可尝试连接两点，如果可以连接则返回保存路径的path列表，否则返回False
鸣谢：感谢我的同学asy668(http://hi.baidu.com/myasy)完善这个算法中createPoints，帮助我测试这个算法，并为这个算法写了一个用户交互界面。
[*]#-*-coding:utf-8-*-
[*]"""连连看连接算法
[*]
[*]为连连看游戏提供连接算法
[*]模块中包含一个Point类，该类是游戏的基本单元“点”，该类包含属性：x,y,value。
[*]其中x,y代表了该点的坐标，value代表该点的特征：0代表没有被填充，1-8代表被填充为游戏图案，9代表被填充为墙壁
[*]模块中还包含一个名为points的Point列表，其中保存着整个游戏界面中的每个点
[*]使用模块的时候应首先调用createPoints方法，初始化游戏界面中每个点，然后可通过points访问到每个点，继而初始化界面
[*]模块中核心的方法是link，通过提供源点和终点，可尝试连接两点，如果可以连接则返回保存路径的path列表，否则返回False
[*]"""
[*]importrandom
[*]importtime
[*]
[*]__author__="http://blog.csdn.net/anhulife"
[*]__license__="python"
[*]
[*]classPoint:
[*]"""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
[*]ifstx>=0:
[*]self.directs.append("right")
[*]self.directs.append("left")
[*]else:
[*]self.directs.append("left")
[*]self.directs.append("right")
[*]ifsty>=0:
[*]self.directs.insert(1,"up")
[*]self.directs.append("down")
[*]else:
[*]self.directs.insert(1,"down")
[*]self.directs.append("up")
[*]ifpre==None:
[*]return
[*]spx=pre.x-self.x
[*]spy=pre.y-self.y
[*]ifspx==0:
[*]ifspy==1:
[*]self.directs.remove("up")
[*]else:
[*]self.directs.remove("down")
[*]else:
[*]ifspx==1:
[*]self.directs.remove("right")
[*]else:
[*]self.directs.remove("left")
[*]
[*]
[*]defforward(self,pre,target):
[*]"""点的前进动作
[*]
[*]点的前进即是依次从方向集中取出优先级高的方向，并判
[*]断该方向上的下一个点是否被填充如果没有被填充则说明该方
[*]向可通，并返回该方向。否则试探下一个方向，如果方向集中没
[*]有方向可用了，则返回None
[*]"""
[*]ifself.directs==None:
[*]self.__createDirect(pre,target)
[*]iflen(self.directs)==0:
[*]returnNone
[*]direct=None
[*]while(True):
[*]iflen(self.directs)==0:
[*]break
[*]tmpDirect=self.directs.pop(0)
[*]iftmpDirect=="up":
[*]x=self.x
[*]y=self.y+1
[*]eliftmpDirect=="down":
[*]x=self.x
[*]y=self.y-1
[*]eliftmpDirect=="left":
[*]x=self.x-1
[*]y=self.y
[*]eliftmpDirect=="right":
[*]x=self.x+1
[*]y=self.y
[*]p=points
[*]ifp.value>0andp!=target:
[*]continue
[*]else:
[*]direct=tmpDirect
[*]ifpre==None:
[*]self.changed=1
[*]else:
[*]if(pre.x-self.x)==0and(p.x-self.x)==0:
[*]self.changed=0
[*]else:
[*]if(pre.y-self.y)==0and(p.y-self.y)==0:
[*]self.changed=0
[*]else:
[*]self.changed=1
[*]break
[*]returndirect
[*]
[*]def__eq__(self,p):
[*]ifp==None:
[*]returnFalse
[*]ifself.x==p.xandself.y==p.y:
[*]returnTrue
[*]else:
[*]returnFalse
[*]
[*]points=list()
[*]valuestack=list()
[*]
[*]defcreatePoints(w,h):
[*]"""构造游戏界面的点
[*]
[*]初始化界面中的所有的点，并且规则如下：
[*]最外一层是“墙壁”点，接下来的一层是没有被填充的点，被包裹的是填充的点
[*]"""
[*]r=random.randint
[*]random.seed(time.time())
[*]Pointstack(w,h)
[*]forxinrange(w):
[*]temp=list()
[*]foryinrange(h):
[*]ifx==0orx==(w-1)ory==0ory==(h-1):
[*]temp.append(Point(x,y,9))
[*]else:
[*]ifx==1orx==(w-2)ory==1ory==(h-2):
[*]temp.append(Point(x,y,0))
[*]else:
[*]temp.append(Point(x,y,valuestack.pop()))
[*]points.append(temp)
[*]
[*]defPointstack(w,h):
[*]size=w*h-(w*4+h*4-16)
[*]size=size/2
[*]random.seed(time.time())
[*]foriinrange(size):
[*]value=random.randint(1,8)
[*]iflen(valuestack)==0:
[*]valuestack.append(value)
[*]valuestack.append(value)
[*]else:
[*]valuestack.insert(random.randint(1,len(valuestack)),value)
[*]valuestack.insert(random.randint(1,len(valuestack)),value)
[*]
[*]deflink(source,target):
[*]"""点的连接
[*]
[*]连接方法的思想：针对源点的每个方向尝试前进，如果可以前进，
[*]则将针对该方向上的下个点的每个方向尝试前进，
[*]当一个点的可选方向都不能前进的时候，则使用规定的信息标记该点，
[*]并返回到已有前进路径中的前一个点，尝试该点其他可选方向。当回源点
[*]的每个方向都走不通，连接失败返回False。否则当路径连接到目标点而且
[*]路径的方向变化小于4的时候，连接成功返回路径
[*]"""
[*]ifsource==target:
[*]returnFalse
[*]ifsource.value==9orsource.value==0:
[*]returnFalse
[*]path=list()
[*]fail=dict()
[*]change=0
[*]current=source
[*]tempPoint=None
[*]whileTrue:
[*]ifcurrent==targetandchange<4:
[*]forpinpath:
[*]p.directs=None
[*]returnpath
[*]ifchange==4:
[*]current.directs=None
[*]fail=change
[*]current=path.pop()
[*]change=change-current.changed
[*]continue
[*]ifcurrent==source:
[*]direct=current.forward(None,target)
[*]else:
[*]direct=current.forward(path,target)
[*]ifdirect!=None:
[*]ifdirect=="up":
[*]x=current.x
[*]y=current.y+1
[*]elifdirect=="down":
[*]x=current.x
[*]y=current.y-1
[*]elifdirect=="left":
[*]x=current.x-1
[*]y=current.y
[*]elifdirect=="right":
[*]x=current.x+1
[*]y=current.y
[*]iffail.has_key(str(x)+"_"+str(y)):
[*]ifchange>=fail.get(str(x)+"_"+str(y)):
[*]continue
[*]else:
[*]fail.pop(str(x)+"_"+str(y))
[*]change=change+current.changed
[*]path.append(current)
[*]current=points
[*]else:
[*]ifcurrent==source:
[*]source.directs=None
[*]returnFalse
[*]else:
[*]current.directs=None
[*]fail=change
[*]current=path.pop()
[*]change=change-current.changed
[*]#createPoints(8,8)
[*]#p=link(points,points)
[*]#printp
[*]
页:
[1]