[SOLVED] Trying to figure out collision detection for a randomly generated maze

ChrisKarpinski

I am making a game that involves tilting a ball through a randomly generated maze. I retrieved some code that randomly generates a maze from Wildbill from http://codea.io/talk/discussion/1275/open-the-maze/p1. I added a ball that can be tilted through the maze and I have enabled touch detection on the outer edges of the maze so that the ball cannot pass through. My problem is that I cannot seem to figure out how to detect when the ball is touching the lines inside the maze, so that the ball will not simply pass through each line. Does anyone know how to get the ball to not pass through the lines of the maze with the code I am currently using or with any other code that can randomly generate a maze and can allow a ball to be tilted through? Any help would be much appreciated.

Thanks,

Chris

ChrisKarpinski

local ballX
local ballY
local mazeDraw
function setup()

    displayMode(FULLSCREEN)
    EAST = 0
    NORTH = 1
    WEST = 2
    SOUTH = 3
    EWALL = 1
    NWALL = 2
    WWALL = 4
    SWALL = 8
    XOFF = 30
    YOFF = 70
    d=0
    ALLWALLS = EWALL + NWALL + WWALL + SWALL
    VISITED = 16
    NMAX = 15
    mazeDraw = true
    N = 15
    pN = 15
    M = WIDTH
    XYOFF = XOFF

    if HEIGHT < WIDTH then
        M = HEIGHT                
        XYOFF = YOFF
    end

    stack = {}
    startx = 1; starty = 1
    endx  = N; endy = N
    createmaze(N, startx, starty, endx, endy)
    --solvemaze()
    ballX = 210
    ballY = 60
end


function draw() 

    -- This sets a dark background color 
    background(255, 0, 0, 255)
    if mazeDraw == true then
  ballX = ballX + Gravity.x*12
  ballY = ballY + Gravity.y*12
    -- This sets the line thickness
    -- See if maze size has changed
    strokeWidth(5)

    if pN ~= N then
        createmaze(N, startx, starty, endx, endy)
        pN = N
    end


    for i=1, N do
        x = XOFF + (i-1)*S
        for j=1, N do
            y = YOFF + (j-1)*S
            c = maze[i][j]
            w = c%VISITED
            we = w%2
            wn = math.floor(w/NWALL)%2
            ww = math.floor(w/WWALL)%2
            ws = math.floor(w/SWALL)
            fill(255, 255, 255, 255)
            if we == 1 then
                line(x+S+150, y+20, x+S+150, y-S+20)
            end
            if wn == 1 then
                line(x+150, y+20, x+S+150, y+20)
            end
            if ww == 1 then
                line(x+150, y+20, x+150, y-S+20)
            end
            if ws == 1 then
                line(x+150, y-S+20, x+S+150, y-S+20)
            end
        end
    end

    fontSize(30)
    font("AmericanTypewriter-Bold")
    text("Tilt the ball through the maze!", 512, 700)
    strokeWidth(5)
    stroke(0, 73, 255, 255)
    fill(0, 78, 255, 255)
    ellipse(ballX, ballY, 30)
    fill(255, 255, 255, 255)
        stroke(255, 255, 255, 255)
    if ballX > x+S+150 and ballY < y+20 and ballX > y-S+20 then 
        ballX = ballX - 20
        ballY = ballY - 20
    end
    if ballY > y+20 then
        ballX = ballX - 20
        ballY = ballY - 20
    end
    if ballX < 180 then
        ballX = ballX + 20
    end
    if ballY < 60 then
        ballY = ballY + 20
    end
    end
    if ballX < 780 and ballX > 760 and ballY > 650 and ballY < 670 then
        fontSize(30)
        font("Futura-Medium")
        text("You made it to the end of the maze!", 512, 384)
        mazeDraw = false
    end
end   
function createmaze(n, sx, sy, ex, ey)
    if mazeDraw == true then 
    if ex > N then
        ex = N; ey = N
    end
    S = (M - 2*XYOFF)/N
    maze = {}
    for i=0, NMAX+1 do
        maze[i] = {}
        for j = 0, NMAX+1 do
            maze[i][j] = ALLWALLS
            if i == 0 or i == N+1 then
                maze[i][j] = maze[i][j] + VISITED
            elseif j == 0 or j == N+1 then
                maze[i][j] = maze[i][j] + VISITED
            end

        end
    end

    x = ex; y = ey
    sp = 1
    setvisited(ex, ey)
    erasewalls(sx-1, sy, sx, sy)
    erasewalls(ex, ey, ex+1, ey)      
    while true do
        nx, ny = getunvisitedneighbor(x, y)
        if nx < 0 then
            x, y = pop()
            if sp == 1 then          
                break
            end
        else 
            setvisited(nx, ny)
            push(x, y)
            erasewalls(x, y, nx, ny)
            x = nx; y = ny

        end
    end
        end
end  
function push(a, b)
    stack[sp]  = a
    stack[sp+1] = b
    sp = sp + 2
end
function pop()
    sp = sp - 1
    b = stack[sp]
    a = stack[sp-1]
    sp = sp - 1
    return a, b
end
function getneighbor(x, y, d)
    --print("x ", x, "y ", y, "d ", d)
    if d == EAST then
        x = x + 1
    elseif d == NORTH then
        y = y + 1
    elseif d == WEST then
        x = x -1
    else 
        y = y - 1
    end
    return x, y
end
function notvisited(x, y)
    if x < 1 or x > N then
        return false
    end
    if y < 1 or y > N then
        return false
    end
    v = math.floor(maze[x][y] / VISITED)
    if v >= 1 then
        return false
    else 
        return true
    end
end
function setvisited(x, y)
    maze[x][y] = maze[x][y] + VISITED
end
function getunvisitedneighbor(x, y)
    nu = 0
    uds = {}
    for i=EAST, SOUTH do
        nx, ny = getneighbor(x, y, i)
        if notvisited(nx, ny)then
            nu = nu + 1
            uds[nu] = i
        end
    end
    if nu == 0 then
        return -1, -1
    end
    td = math.random(1, nu)
    nx, ny = getneighbor(x, y, uds[td])
    return nx, ny
end
function getdirection(x, y, nx, ny)
    if nx > x then
        d = EAST
    elseif ny > y then
        d = NORTH
    elseif nx < x then
        d = WEST
    else
        d = SOUTH
    end
    return d
end
function erasewalls(x, y, nx, ny)
    d = getdirection(x, y, nx, ny)
    if d == EAST then
        maze[x][y] = maze[x][y] - EWALL
        maze[nx][ny] = maze[nx][ny] - WWALL
    elseif d == NORTH then
        maze[x][y] = maze[x][y] - NWALL
        maze[nx][ny] = maze[nx][ny] - SWALL
    elseif d == WEST then
        maze[x][y] = maze[x][y] - WWALL
        maze[nx][ny] = maze[nx][ny] - EWALL
    else
        maze[x][y] = maze[x][y] - SWALL
        maze[nx][ny] = maze[nx][ny] - NWALL
    end
end

dave1707

@ChrisKarpinski The easiest way is to use physics.body with EDGE. EDGE would be used to draw all the lines. Then let the physics engine do all the collision testing. I already did what you're trying to do using physics.body and it's posted somewhere in this forum. I'll try to find it and post the link.

Monkeyman32123

Depending on the size of the maze, you could use physics. I can't run the code right now, or I would give a better answer. But I think physics is probably your most viable option.

dave1707

@ChrisKarpinski Here's the code that I added physics.body to. I did it in August 2013. It looks like we started out with the same code.

supportedOrientations(PORTRAIT)
displayMode(FULLSCREEN)

function setup()
    c1=physics.body(CIRCLE,10)
    c1.x=700
    c1.y=800
    c1.gravityScale=0
    c1.sleepingAllowed=false

    tab1={}
    tab2={}

    EAST = 0
    NORTH = 1
    WEST = 2
    SOUTH = 3
    EWALL = 1
    NWALL = 2
    WWALL = 4
    SWALL = 8
    XOFF = 30
    YOFF = 70
    ALLWALLS = EWALL + NWALL + WWALL + SWALL
    VISITED = 16
    NMAX = 40
    N=10  -- maze size
    pN = N
    M = WIDTH
    XYOFF = XOFF
    stack = {}
    startx = 1; starty = 1
    endx  = N; endy = N
    createmaze(N, startx, starty, endx, endy)
    done=false
end

function draw() 
    background(0,0,0)
    translate(0,100)
    fill(255, 0, 0, 255)
    strokeWidth(2)
    ellipse(c1.x,c1.y,20)
    c1.x=c1.x+Gravity.x*10
    c1.y=c1.y+Gravity.y*10
    strokeWidth(5)
    for i=1, N do
        x = XOFF + (i-1)*S
        for j=1, N do
            y = YOFF + (j-1)*S
            c = maze[i][j]
            w = c%VISITED
            we = w%2
            wn = math.floor(w/NWALL)%2
            ww = math.floor(w/WWALL)%2
            ws = math.floor(w/SWALL)
            if we == 1 then
                line(x+S, y, x+S, y-S)
                pb(x+S,y,x+S,y-S)
            end
            if wn == 1 then
                line(x, y, x+S, y)
                pb(x, y, x+S, y)
            end
            if ww == 1 then
                line(x, y, x, y-S)
                pb(x, y, x, y-S)
            end
            if ws == 1 then
                line(x, y-S, x+S, y-S)
                pb(x, y-S, x+S, y-S)
            end
        end
    end
    done=true
end  

function pb(x,y,x1,y1) 
    local z
    if not done then
        for z=1,#tab1 do
            if tab1[z].x==x and tab1[z].y==y and
                tab1[z].z==x1 and tab1[z].w==y1 then
                    return
            end
        end
        table.insert(tab1,vec4(x,y,x1,y1))
        table.insert(tab2,physics.body(EDGE,vec2(x,y),vec2(x1,y1)))
        tab2[#tab2].sleepingAllowed=false
    end
end

function createmaze(n, sx, sy, ex, ey)
    if ex > N then
        ex = N; ey = N
    end
    S = math.floor((M - 2*XYOFF)/N)
    maze = {}
    for i=0, NMAX+1 do
        maze[i] = {}
        for j = 0, NMAX+1 do
            maze[i][j] = ALLWALLS
            if i == 0 or i == N+1 then
                maze[i][j] = maze[i][j] + VISITED
            elseif j == 0 or j == N+1 then
                maze[i][j] = maze[i][j] + VISITED
            end
        end
    end
    x = ex; y = ey
    sp = 1
    setvisited(ex, ey)
    erasewalls(sx-1, sy, sx, sy)
    erasewalls(ex, ey, ex+1, ey)      
    while true do
        nx, ny = getunvisitedneighbor(x, y)
        if nx < 0 then
            x, y = pop()
            if sp == 1 then          
                break
            end
        else 
            setvisited(nx, ny)
            push(x, y)
            erasewalls(x, y, nx, ny)
            x = nx; y = ny
        end
    end
end  

function push(a, b)
    stack[sp]  = a
    stack[sp+1] = b
    sp = sp + 2
end

function pop()
    sp = sp - 1
    b = stack[sp]
    a = stack[sp-1]
    sp = sp - 1
    return a, b
end

function getneighbor(x, y, d)
    if d == EAST then
        x = x + 1
    elseif d == NORTH then
        y = y + 1
    elseif d == WEST then
        x = x -1
    else 
        y = y - 1
    end
    return x, y
end

function notvisited(x, y)
    if x < 1 or x > N then
        return false
    end
    if y < 1 or y > N then
        return false
    end
    v = math.floor(maze[x][y] / VISITED)
    if v >= 1 then
        return false
    else 
        return true
    end
end

function setvisited(x, y)
    maze[x][y] = maze[x][y] + VISITED
end

function getunvisitedneighbor(x, y)
    nu = 0
    uds = {}
    for i=EAST, SOUTH do
        nx, ny = getneighbor(x, y, i)
        if notvisited(nx, ny)then
            nu = nu + 1
            uds[nu] = i
        end
    end
    if nu == 0 then
        return -1, -1
    end
    td = math.random(1, nu)
    nx, ny = getneighbor(x, y, uds[td])
    return nx, ny
end

function getdirection(x, y, nx, ny)
    if nx > x then
        d = EAST
    elseif ny > y then
        d = NORTH
    elseif nx < x then
        d = WEST
    else
        d = SOUTH
    end
    return d
end

function erasewalls(x, y, nx, ny)
    d = getdirection(x, y, nx, ny)
    if d == EAST then
        maze[x][y] = maze[x][y] - EWALL
        maze[nx][ny] = maze[nx][ny] - WWALL
    elseif d == NORTH then
        maze[x][y] = maze[x][y] - NWALL
        maze[nx][ny] = maze[nx][ny] - SWALL
    elseif d == WEST then
        maze[x][y] = maze[x][y] - WWALL
        maze[nx][ny] = maze[nx][ny] - EWALL
    else
        maze[x][y] = maze[x][y] - SWALL
        maze[nx][ny] = maze[nx][ny] - NWALL
    end
end

JhaSeh

Funny ... I was experimenting with the exact same thing. What I did was make all walls inside physicsbodies as well and that works for me!

ChrisKarpinski

Thanks so much for the code Dave, my maze works perfectly now and now I've learned a thing or two about using physics in Codea. Big thanks to everyone else for the ideas and the help!