GD:迷宮產生器及解

require "gd"
grid={x=10,y=10};
size={x=50,y=50};
start_pos={x=1,y=1};
target_pos={x=50,y=50};
maze={};
for u=1,size.x,1 do
    maze[ u]={};
    for v=1,size.y,1 do
        maze[ u][v]={v=false,s=true,e=true};
    end
end
math.randomseed(os.time());
total_count = size.x*size.y;
magic= math.random(1,total_count);
cur_pos={};
function magic_to_pos()
    local x,y;
    magic = (magic + 997)% total_count;
    x = magic % size.x + 1;
    y = math.floor(magic / size.x) + 1;
    return x,y;
end
cur_pos.x , cur_pos.y = magic_to_pos();
cur_pos.dir = math.random(1,4);
maze[cur_pos.x][cur_pos.y].v = true;
cur_count = 1;
function move_north()
    if( cur_pos.y == 1 ) then return false end;
    if( maze[cur_pos.x][cur_pos.y-1].v == true ) then
        return false;
    else
        cur_pos.y = cur_pos.y - 1;
        maze[cur_pos.x][cur_pos.y].s=false;
        maze[cur_pos.x][cur_pos.y].v=true;
        return true;
    end
end
function move_south()
    if( cur_pos.y == size.y ) then return false end;
    if( maze[cur_pos.x][cur_pos.y+1].v == true ) then
        return false;
    else
        maze[cur_pos.x][cur_pos.y].s=false;
        cur_pos.y = cur_pos.y + 1;
        maze[cur_pos.x][cur_pos.y].v=true;
        return true;
    end
end
function move_east()
    if( cur_pos.x == size.x ) then return false end;
    if( maze[cur_pos.x+1][cur_pos.y].v == true ) then
        return false;
    else
        maze[cur_pos.x][cur_pos.y].e=false;
        cur_pos.x = cur_pos.x + 1;
        maze[cur_pos.x][cur_pos.y].v=true;
        return true;
    end
end
function move_west()
    if( cur_pos.x == 1 ) then return false end;
    if( maze[cur_pos.x-1][cur_pos.y].v == true ) then
        return false;
    else
        cur_pos.x = cur_pos.x - 1;
        maze[cur_pos.x][cur_pos.y].e=false;
        maze[cur_pos.x][cur_pos.y].v=true;
        return true;
    end
end
move={move_north,move_east,move_south,move_west};
function gen_path()
    while (move[cur_pos.dir]()) do
        local dir = math.random(-1,1);
--        print("Dir=",dir);
        cur_count = cur_count + 1;
        cur_pos.dir = (dir+cur_pos.dir-1)%4+1;
--        print(cur_pos.x,cur_pos.y,cur_pos.dir);
    end
end
function new_path()
    cur_pos.x, cur_pos.y = magic_to_pos();
    while (maze[cur_pos.x][cur_pos.y].v == false) do
        cur_pos.x, cur_pos.y = magic_to_pos();
    end
    cur_pos.dir = math.random(1,4);
end
while ( cur_count < total_count ) do
    gen_path();
    new_path();
end
-- print(cur_count);
-- plot maze
im = gd.createTrueColor(grid.x*size.x+1,grid.y*size.y+1);
white = im:colorResolve(255,255,255);
red   = im:colorResolve(255,  0,  0);
green = im:colorResolve(  0,255,  0);
blue  = im:colorResolve(  0,  0,255);
im:line(  0, 0, grid.x*size.x, 0, green);
im:line(  0, 0, 0, grid.y*size.y, green);
for v=1,size.y,1 do
    for u=1,size.x,1 do
        if(maze[ u][v].e) then
            im:line(  grid.x*u, grid.y*(v-1),  grid.x*u,  grid.y*v, green);
        end
        if(maze[ u][v].s) then
            im:line(  grid.x*(u-1), grid.y*v,  grid.x*u,  grid.y*v, green);
        end
    end
end
-- im:png("maze.png");
-- reslove maze
--]]
path={};
search_count = 1;
search_pos={x=start_pos.x, y=start_pos.y, dir=0};
table.insert(path,search_pos);
function read_north()
    if( search_pos.y == 1 ) then
        return;
    else
        if ( not maze[search_pos.x][search_pos.y-1].s ) then
            local node = {x=search_pos.x, y=search_pos.y-1, dir=3, r=search_count};
            table.insert(path,node);
        end
    end
end
function read_south()
    if( search_pos.y == size.y ) then
        return;
    else
        if ( not maze[search_pos.x][search_pos.y].s ) then
            local node = {x=search_pos.x, y=search_pos.y+1, dir=1, r=search_count};
            table.insert(path,node);
        end
    end
end
function read_east()
    if( search_pos.x == size.x ) then
        return;
    else
        if ( not maze[search_pos.x][search_pos.y].e ) then
            local node = {x=search_pos.x+1, y=search_pos.y, dir=4, r=search_count};
            table.insert(path,node);
        end
    end
end
function read_west()
    if( search_pos.x == 1 ) then
        return;
    else
        if ( not maze[search_pos.x-1][search_pos.y].e ) then
            local node = {x=search_pos.x-1, y=search_pos.y, dir=2, r=search_count};
            table.insert(path,node);
        end
    end
end
while ( not (search_pos.x == target_pos.x and search_pos.y == target_pos.y) ) do
    if( search_pos.dir ~= 1 ) then read_north() end;
    if( search_pos.dir ~= 3 ) then read_south() end;
    if( search_pos.dir ~= 2 ) then read_east() end;
    if( search_pos.dir ~= 4 ) then read_west() end;
    search_count = search_count + 1;
    search_pos.x = path[search_count].x;
    search_pos.y = path[search_count].y;
    search_pos.dir = path[search_count].dir;
--    print(search_count, search_pos.x, search_pos.y, path[search_count].r );
end
-- print(search_count, search_pos.x, search_pos.y, path[search_count].r );
r_count  = path[search_count].r;
rr_count = search_count;
while ( r_count > 1 ) do
--    print( path[r_count].x, path[r_count].y );
    im:line(path[rr_count].x*grid.x-grid.x/2, path[rr_count].y*grid.y-grid.y/2, path[r_count].x*grid.x-grid.x/2, path[r_count].y*grid.y-grid.y/2, red);
    rr_count= r_count;
    r_count = path[r_count].r;
end
im:line(path[rr_count].x*grid.x-grid.x/2, path[rr_count].y*grid.y-grid.y/2, start_pos.x*grid.x-grid.x/2, start_pos.y*grid.y-grid.y/2, red);
im:jpeg("r-maze.jpg",100);