新鲜出炉的连连看连接算法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[x][y]
  
• 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[str(current.x)+"_"+str(current.y)]=change
  
• current=path.pop()
  
• change=change-current.changed
  
• continue
  
• ifcurrent==source:
  
• direct=current.forward(None,target)
  
• else:
  
• direct=current.forward(path[len(path)-1],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[x][y]
  
• else:
  
• ifcurrent==source:
  
• source.directs=None
  
• returnFalse
  
• else:
  
• current.directs=None
  
• fail[str(current.x)+"_"+str(current.y)]=change
  
• current=path.pop()
  
• change=change-current.changed
  
• #createPoints(8,8)
  
• #p=link(points[2][2],points[5][2])
  
• #printp
  
•