python小程序----解迷宫图片_编程语言综合--HTML5中文学习网

　　一共做了三种，前两种分别是bfs和Astar，第三种不是解迷宫，是连通区域标记，用的是并查集。

　　效果如下(csdn貌似不能显示gif动态图，所以只是截了几幅图片。

　　本人觉得gif图还是很好看的，github有：https://github.com/scauPYygzx/picture_maze ^-^)：

bfs

Astar

并查集

　　从图中可以看出Astar比bfs搜少了好多点，但是因为用到了priorityQueue的原因，在这图上的时间效率不如bfs。

　　PS：用convert命令制作gif图真的很方便，推荐。

　　code：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

#-*- coding:utf-8 -*-

from PIL import Image

import Queue

import time

#只是玩玩就硬编码了..

ext = png

imageName = p.%s % ext

saveName = {0:05d}.{1}

#用PIL库载入图片

im = Image.open(imageName)

im = im.convert(RGB)

print im.format, im.size, im.mode

pix = im.load()

size = im.size

half = 256 >> 1

white = (255, 255, 255)

black = (0, 0, 0)

red = (255, 0, 0)

green = (0, 255, 0)

blue = (0, 0, 255)

yellow = (255, 255, 0)

fillColor = red

lineColor = yellow

colors = [red, green, blue, yellow, (0, 223, 248), (223, 8, 248), (255, 2, 146)]

cLen = len(colors)

#起点,终点

startPoint = [400, 984]

endPoint = [398, 25]

fa = [0] * size[0] * size[1]

def changeImage():

'''

将图片转换为二值图

'''

x, y = size

for i in xrange(x):

for j in xrange(y):

r, g, b = pix[i, j]

if r > half and g > half and b > half:

pix[i, j] = white

else:

pix[i, j] = black

#================================================================#

#BFS

def getNeighbor(point):

x, y = point

return [[x, y + 1], [x + 1, y], [x, y - 1], [x - 1, y]]

def inBounds(point, size):

x, y = point

sx, sy = size

if x < 0 or y < 0 or x >= sx or y >= sy:

return False

return True

def isWhite(point):

x, y = point

if pix[x, y] == white:

return True

return False

def bfs(start, end):

count = no = 0

q = [[start]]

while len(q):

path = q.pop(0);

p = path[-1]

if p[0] == end[0] and p[1] == end[1]:

im.save(saveName.format(no, ext))

no += 1

for pa in path:

pix[pa[0], pa[1]] = pix[pa[0], pa[1] - 1] = pix[pa[0], pa[1] - 2] = lineColor

count += 1

if not count % 200:

im.save(saveName.format(no, ext))

no += 1

im.save(saveName.format(no, ext))

return path

for ne in getNeighbor(p):

if inBounds(ne, size) and isWhite(ne):

newPath = list(path)

newPath.append(ne)

q.append(newPath)

pix[ne[0], ne[1]] = fillColor

if not count % 10000:

im.save(saveName.format(no, ext))

no += 1

count += 1

return None

#================================================================#

#Astar

def getValue(point, end):

'''

启发函数

'''

return abs(point[0] - end[0]) + abs(point[1] - end[1])

def aStar(start, end):

fillColor = green

lineColor = black

count = no = 0

Q = Queue.PriorityQueue()

Q.put([0,[start]])

while(Q.qsize()):

q = Q.get()

path = q[-1]

p = path[-1]

if p[0] == end[0] and p[1] == end[1]:

im.save(saveName.format(no, ext))

no += 1

for pa in path:

pix[pa[0], pa[1]] = pix[pa[0], pa[1] - 1] = pix[pa[0], pa[1] - 2] = lineColor

count += 1

if not count % 200:

im.save(saveName.format(no, ext))

no += 1

im.save(saveName.format(no, ext))

return path

for ne in getNeighbor(p):

if inBounds(ne, size) and isWhite(ne):

newPath = list(path)

newPath.append(ne)

newList = [getValue(p, end) + len(newPath), newPath]

Q.put(newList)

pix[ne[0], ne[1]] = fillColor

if not count % 10000:

im.save(saveName.format(no, ext))

no += 1

count += 1

return None

#================================================================#

#并查集

def getID(x, y):

return x * size[0] + y

def ufInit(size):

for i in range(size[0]):

for j in range(size[1]):

fa[getID(i, j)] = getID(i, j)

def ufFind(v):

if v != fa[v]:

fa[v] = ufFind(fa[v])

return fa[v]

def ufUnion(x, y):

x = ufFind(x)

y = ufFind(y)

if x == y: return

fa[x] = y

def connectivity():

fillColor = yellow

no = count = now = 0

d = {}

x_range = (5, 792)

y_range = (22, 986)

ufInit(size)

for x in range(x_range[0], x_range[1]):

for y in range(y_range[0], y_range[1]):

if pix[x, y] != black:

if pix[x - 1, y] == black and pix[x, y - 1] == black:

pass

elif pix[x - 1, y] == white and pix[x, y - 1] == black:

ufUnion(getID(x - 1, y), getID(x, y))

elif pix[x - 1, y] == black and pix[x, y - 1] == white:

ufUnion(getID(x, y - 1), getID(x, y))

else:

ufUnion(getID(x - 1, y), getID(x, y - 1))

ufUnion(getID(x, y), getID(x - 1, y))

for x in range(x_range[0], x_range[1]):

for y in range(y_range[0], y_range[1]):

count += 1

if pix[x, y] != black:

father = ufFind(getID(x,y))

if father not in d:

d[father] = colors[now % cLen]

now += 1

pix[x, y] = d[father]

if not count % 15000:

im.save(saveName.format(no, ext))

no += 1

im.save(saveName.format(no, ext))

#================================================================#

t1 = time.time()

changeImage()

#bfs(startPoint, endPoint)

#aStar(startPoint, endPoint)

connectivity()

t2 = time.time()

print t2- t1