On Tue, Jun 22, 2010 at 5:22 AM, Narasimhan <
narasimhan1990@yahoo.co.in>wrote:
>
> thanks it helped. but in that script we can set the starting point. but
> since
> its random maze each time a different end point is generated. is there a
> way
> to set end point.
>
The attached script will generate mazes that start in the top-left and end
in the bottom-right.
if i spawn a robot at the starting point using stage. how to command the
> robot to reach the end point of the maze?
>
http://en.wikipedia.org/wiki/Maze_solving_algorithm
Tim
#!/usr/bin/python
import Image
import ImageDraw
import random
import sys
size = (400, 400)
step = ( 20, 20)
hall_connect = 998
max_recursion = 20000
debug = False
up = ( 0, 1)
down = ( 0, -1)
left = (-1, 0)
right = ( 1, 0)
dirs = [up, down, left, right]
def pix(pos):
if (pos[0] < 0) or (pos[0] >= size[0]) or (pos[1] < 0) or (pos[1] >= size[1]):
return None
return img.getdata()[pos[1] * size[0] + pos[0]]
def draw_hall(start_pos, end_pos, col):
minx = min(start_pos[0], end_pos[0])
maxx = max(start_pos[0], end_pos[0])
miny = min(start_pos[1], end_pos[1])
maxy = max(start_pos[1], end_pos[1])
draw.rectangle(((minx, miny), (maxx+step[0]-2, maxy+step[1]-2)), col)
def hallway(pos, dist):
global endpoint
global maxdist
while True:
available = []
for d in dirs:
c = pix((pos[0] + d[0] * step[0], pos[1] + d[1] * step[1]))
if c != None:
if c == (0, 0, 0):
available.append(d)
else:
if random.randint(0, 1000) > hall_connect:
available.append(d)
if len(available) == 0:
if dist > maxdist:
maxdist = dist
endpoint = pos
return
d = random.choice(available)
drawto = (pos[0] + d[0] * step[0], pos[1] + d[1] * step[1])
if debug:
t = min(int(dist * 0.05), 255)
c = (t, t, 255)
else:
c = (255, 255, 255)
draw_hall(pos, drawto, c)
hallway(drawto, dist + 1)
if __name__ == "__main__":
sys.setrecursionlimit(max_recursion)
start = (0, 0)
while True:
endpoint = (0,0)
maxdist = 0
img = Image.new("RGB", size)
draw = ImageDraw.ImageDraw(img)
hallway(start, 0)
if endpoint[0] < size[0] - step[0] or endpoint[1] < size[1] - step[1]:
continue
draw.rectangle((start, (start[0] + step[0] - 2, start[1] + step[1] - 2)), ( 0, 255, 0))
draw.rectangle((endpoint, (endpoint[0] + step[0] - 2, endpoint[1] + step[1] - 2)), (255, 0, 0))
break
img.save("maze.pgm")