Re: [ros-users] random maze

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")