#-*-coding:utf-8-*-
"""連連看連接算法

為連連看游戲提供連接算法
模塊中包含一個(gè)Point類(lèi)，該類(lèi)是游戲的基本單元“點(diǎn)”，該類(lèi)包含屬性：x,y,value。
其中x,y代表了該點(diǎn)的坐標(biāo)，value代表該點(diǎn)的特征：0代表沒(méi)有被填充，1-8代表被填充為游戲圖案，9代表被填充為墻壁
模塊中還包含一個(gè)名為points的Point列表，其中保存著整個(gè)游戲界面中的每個(gè)點(diǎn)
使用模塊的時(shí)候應(yīng)首先調(diào)用createPoints方法，初始化游戲界面中每個(gè)點(diǎn)，然后可通過(guò)points訪問(wèn)到每個(gè)點(diǎn)，繼而初始化界面
模塊中核心的方法是link，通過(guò)提供源點(diǎn)和終點(diǎn)，可嘗試連接兩點(diǎn)，如果可以連接則返回保存路徑的path列表，否則返回False
"""
import random

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

class Point:
"""Point類(lèi)

Point類(lèi)是游戲中基本單元：“點(diǎn)”
"""
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):
"""構(gòu)造點(diǎn)的方向集

每個(gè)點(diǎn)在連接的過(guò)程中都持有一個(gè)方向集，這個(gè)方向集中保存著該點(diǎn)的前進(jìn)方向選擇的優(yōu)先級(jí)
優(yōu)先級(jí)：指向目標(biāo)點(diǎn)的方向級(jí)別最高，在同等級(jí)別并且遵循x方向優(yōu)先于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):
"""點(diǎn)的前進(jìn)動(dòng)作

點(diǎn)的前進(jìn)即是依次從方向集中取出優(yōu)先級(jí)高的方向，并判斷該方向上的下一個(gè)點(diǎn)是否被填充
如果沒(méi)有被填充則說(shuō)明該方向可通，并返回該方向。否則試探下一個(gè)方向，如果方向集中沒(méi)有方向可用了，則返回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):
"""判斷方向變化

返回在該點(diǎn)前進(jìn)時(shí)，是否帶來(lái)了方向的變化，即方向不同于原方向
"""
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):
"""構(gòu)造游戲界面的點(diǎn)

初始化界面中的所有的點(diǎn)，并且規(guī)則如下：
最外一層是“墻壁”點(diǎn)，接下來(lái)的一層是沒(méi)有被填充的點(diǎn)，被包裹的是填充的點(diǎn)
"""
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):
"""點(diǎn)的連接

連接方法的思想：針對(duì)源點(diǎn)的每個(gè)方向嘗試前進(jìn)，如果可以前進(jìn)，則將針對(duì)該方向上的下個(gè)點(diǎn)的每個(gè)方向嘗試前進(jìn)
當(dāng)一個(gè)點(diǎn)的可選方向都不能前進(jìn)的時(shí)候，則返回到已有前進(jìn)路徑中的前一個(gè)點(diǎn)，嘗試該點(diǎn)其他可選方向。當(dāng)回源點(diǎn)
的每個(gè)方向都走不通或是路徑的方向變化等于4的時(shí)候，連接失敗返回False。否則當(dāng)路徑連接到目標(biāo)點(diǎn)而且路徑的方向變化小
于4的時(shí)候，連接成功返回路徑
"""
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