Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

AABB function library

edited June 2014 in Code Sharing Posts: 425

I have been using AABBs to find collisions in my games recently and have put together functions for handling them.
If you have any thoughts or suggestions please post them below. The code here is for anyone to use:

--AABB.lua
--------------------------------------------------------------------------------------------------
--[[
    The AABB namespace contains functions for working with AABBs (axis aligned bounding boxes)
    an AABB is required (and output) in the table format like so:
        { x = Xpos, y = Ypos, w = Width, h = Height}
    the x and y are taken from the lower left corner of the AABB
--]]
--------------------------------------------------------------------------------------------------

AABB={}
AABB.pointIn=function(aabb,p)
    --determines weather a point is within an AABB
    return (p.x > aabb.x and p.x < aabb.x + aabb.w and p.y > aabb.y and p.y < aabb.y + aabb.h)
end
AABB.query=function(aabb1,aabb2)
    --do two AABBs overlap?
    if aabb1.x>aabb2.x+aabb2.w or aabb2.x>aabb1.x+aabb1.w or 
       aabb1.y>aabb2.y+aabb2.h or aabb2.y>aabb1.y+aabb1.h then
        return false
    end
    return true
end
AABB.getOverlap=function(aabb1,aabb2)
    --get the AABB which is the overlap between two other AABBs
    local x1=math.max(aabb1.x,aabb2.x)
    local y1=math.max(aabb1.y,aabb2.y)
    local x2=math.min(aabb1.x+aabb1.w,aabb2.x+aabb2.w)
    local y2=math.min(aabb1.y+aabb1.h,aabb2.y+aabb2.h)
    if x1<=x2 and y1<=y2 then
        return {x=x1,y=y1,w=x2-x1,h=y2-y1}
    end
    return false
end
AABB.get=function(verts,pad)
    --return an AABB from a list of vec2 points
    --pad os the padding around the edge default is 0
    local minX,minY,maxX,maxY
    for k,v in ipairs(verts) do
        minX=math.min(v.x,minX or v.x)
        minY=math.min(v.y,minY or v.y)
        maxX=math.max(v.x,maxX or v.x)
        maxY=math.max(v.y,maxY or v.y)
    end
    local x,y,w,h
    x,y=minX,minY
    w=maxX-minX
    h=maxY-minY
    if pad then
        x = x - pad
        y = y - pad
        w = w + pad*2
        h = h + pad*2
    end
    return {x=x,y=y,w=w,h=h}
end

Comments

  • Posts: 1,595

    This is quite useful thanks, how do you think it would work for a particle engine? I don't have my iPad with me atm so I can't test for myself, but have you done any speed/stress tests?

  • edited July 2014 Posts: 425

    It can run about 2000 queries every frame and retain about 60 FPS:

    -- Main
    supportedOrientations(CurrentOrientation)
    function setup()
        player={x=WIDTH/2,y=HEIGHT/2,w=5,h=5}
        rects={}
        for i=1,2000 do
            table.insert(rects,
          {x=math.random(0,WIDTH),y=math.random(0,HEIGHT),w=math.random(1,10),h=math.random(1,10)}
            )
        end
        parameter.watch("math.floor(1/DeltaTime+0.5)")
        print("tilt to move")
    end
    function draw()
        background(0)
        noSmooth()
        player.x = player.x + Gravity.x*10
        player.y = player.y + Gravity.y*10
        local colliding=false
        for i=1,#rects do
            if AABB.query(player,rects[i])then colliding=true break end
        end
        if colliding then fill(255,0,0)else fill(255)end
        rectMode(CORNER)
        rect(player.x,player.y,player.w,player.h)
        fill(0,255,0)
        for k,v in pairs(rects) do
            rect(v.x,v.y,v.w,v.h)
        end
    end
    
  • edited July 2014 Posts: 1,595

    Little particle field, touch to pull the box towards you. Getting around 20 fps so for 1000 particles thats very good. Updated code:

    --# AABB
    --AABB.lua
    --------------------------------------------------------------------------------------------------
    --[[
        The AABB namespace contains functions for working with AABBs (axis aligned bounding boxes)
        an AABB is required (and output) in the table format like so:
            { x = Xpos, y = Ypos, w = Width, h = Height}
        the x and y are taken from the lower left corner of the AABB
    --]]
    --------------------------------------------------------------------------------------------------
    
    AABB={}
    AABB.pointIn=function(aabb,p)
        --determines weather a point is within an AABB
        return (p.x > aabb.x and p.x < aabb.x + aabb.w and p.y > aabb.y and p.y < aabb.y + aabb.h)
    end
    AABB.query=function(aabb1,aabb2)
        --do two AABBs overlap?
        if aabb1.x>aabb2.x+aabb2.w or aabb2.x>aabb1.x+aabb1.w or 
           aabb1.y>aabb2.y+aabb2.h or aabb2.y>aabb1.y+aabb1.h then
            return false
        end
        return true
    end
    AABB.getOverlap=function(aabb1,aabb2)
        --get the AABB which is the overlap between two other AABBs
        local x1=math.max(aabb1.x,aabb2.x)
        local y1=math.max(aabb1.y,aabb2.y)
        local x2=math.min(aabb1.x+aabb1.w,aabb2.x+aabb2.w)
        local y2=math.min(aabb1.y+aabb1.h,aabb2.y+aabb2.h)
        if x1<=x2 and y1<=y2 then
            return {x=x1,y=y1,w=x2-x1,h=y2-y1}
        end
        return {x=0,y=0,w=0,h=0}
    end
    AABB.get=function(verts,pad)
        --return an AABB from a list of vec2 points
        --pad os the padding around the edge default is 0
        local minX,minY,maxX,maxY
        for k,v in ipairs(verts) do
            minX=math.min(v.x,minX or v.x)
            minY=math.min(v.y,minY or v.y)
            maxX=math.max(v.x,maxX or v.x)
            maxY=math.max(v.y,maxY or v.y)
        end
        local x,y,w,h
        x,y=minX,minY
        w=maxX-minX
        h=maxY-minY
        if pad then
            x = x - pad
            y = y - pad
            w = w + pad*2
            h = h + pad*2
        end
        return {x=x,y=y,w=w,h=h}
    end
    --# Main
    -- Main
    supportedOrientations(CurrentOrientation)
    function setup()
        player={x=WIDTH/2,y=HEIGHT/2,w=30,h=90}
        vel = vec2()
        rects={}
        for i=1,1000 do
            table.insert(rects,
          {x=math.random(400,WIDTH),y=math.random(400,HEIGHT),w=math.random(15,20),h=math.random(15,20),cd = false,
            vel = vec2(0,0)}
            )
        end
        parameter.watch("math.floor(1/DeltaTime+0.5)")
        print("tilt to move")
        tch = nil
    end
    function touched(t)
        tch = t
        if t.state == ENDED then tch = nil end
    end
    function draw()
        background(0)
        noSmooth()
        player.x = player.x + vel.x
        player.y = player.y + vel.y
        local pt = vec2(player.x+player.w/2,player.y+player.h/2)
        if tch then
            if vec2(player.x,player.y):dist(vec2(tch.x,tch.y))>10 then
                vel = vel + (vec2(tch.x,tch.y)-pt):normalize()*2-vel/10
            else
                vel = vec2()
            end
            vel = vel*0.9
        end
        if pt.x<player.w/2 then
            vel = vec2(math.abs(vel.x),vel.y)
        end
        if pt.x>WIDTH-player.w/2 then
            vel = vec2(-math.abs(vel.x),vel.y)
        end
        if pt.y<player.h/2 then
            vel = vec2(vel.x,math.abs(vel.y))
        end
        if pt.y>HEIGHT-player.h/2 then
            vel = vec2(vel.x,-math.abs(vel.y))
        end
        local colliding=false
        for i=1,#rects do
            if AABB.query(player,rects[i]) then 
                local overlap = AABB.getOverlap(rects[i],player)
                local overlap2 = overlap
                --vec2(player.w,player.h):len()-pt:dist(vec2(rects[i].x,rects[i].y))
                local ol = (vec2(rects[i].x,rects[i].y)-pt)
                local oln = ol:normalize()
                oln.x = player.w/2 - math.abs(ol.x)
                oln.y = player.h/2 - math.abs(ol.y)
                if overlap.w > overlap.h then overlap2.h = 0 else overlap2.w = 0 end
                rects[i].vel = rects[i].vel*0.93
                ol.x=ol.x*overlap2.h
                ol.y=ol.y*overlap2.w
                rects[i].vel = rects[i].vel + (ol):normalize()*ol:len()*0.006-rects[i].vel/3+vec2(vel.x*overlap2.h,vel.y*overlap2.w)*0.01
                rects[i].x = rects[i].x + ol.x*0.02
                rects[i].y = rects[i].y + ol.y*0.02
                vel = vel-ol*0.0003
                rects[i].cd = true 
            else 
                if rects[i].x<0 then
                    rects[i].vel = vec2(math.abs(rects[i].vel.x)+1,rects[i].vel.y)
                end
                if rects[i].x>WIDTH then
                    rects[i].vel = vec2(-math.abs(rects[i].vel.x)-1,rects[i].vel.y)
                end
                if rects[i].y<0 then
                    rects[i].vel = vec2(rects[i].vel.x,math.abs(rects[i].vel.y)+1)
                end
                if rects[i].y>HEIGHT then
                    rects[i].vel = vec2(rects[i].vel.x,-math.abs(rects[i].vel.y)-1)
                end
                rects[i].cd = false 
            end
            rects[i].x=rects[i].x+rects[i].vel.x
            rects[i].y=rects[i].y+rects[i].vel.y
            rects[i].vel = rects[i].vel*0.97
        end
        rectMode(CORNER)
        fill(255, 255, 255, 255)
        rect(player.x,player.y,player.w,player.h)
        for k,v in pairs(rects) do
            if v.cd then fill(255,0,0)else fill(255)end
            rect(v.x,v.y,v.w,v.h)
        end
    end
    
  • edited July 2014 Posts: 425

    Yep that is very good, thanks for this example. I like the way the square is buffeted around by the particles

  • edited July 2014 Posts: 1,595

    No problem this is a great library, I've updated the code to user the overlap function. It might be a bit slower, I don't know as I was running it on my macbook for a bit extra speed. It's like a snow plough now, follows basic (I mean very basic and inaccurate but workable) laws of particle resistance.

  • Posts: 425

    Another example,building on my last one, this one resolves collisions too:

    -- Main
    --requires AABB function library
    supportedOrientations(CurrentOrientation)
    function setup()
        player={x=WIDTH/2,y=HEIGHT/2,w=50,h=50,vel=vec2(0,0)}
        rects={}
        for i=1,20 do
            table.insert(rects,
            {x=math.random(0,WIDTH),y=math.random(0,HEIGHT),w=math.random(20,80),h=math.random(20,80)}
            )
        end
        parameter.watch("math.floor(1/DeltaTime+0.5)")
        print("tilt to move")
    end
    function draw()
        background(0)
        noSmooth()
        player.vel=Gravity*10
        new={x=player.x+player.vel.x,y=player.y+player.vel.y,w=player.w,h=player.h}
        for i=1,#rects do
            overlap=AABB.getOverlap(new,rects[i])
            if overlap then
                if overlap.w>overlap.h then
                    --collision is vertical
                    player.vel.y=0
                    if player.y>rects[i].y then
                        --block is below me
                        player.y=rects[i].y+rects[i].h+1
                    else
                        --block is above me
                        player.y=rects[i].y-player.h-1
                    end
                else
                    --collision is horizontal
                    player.vel.x=0
                    if player.x>rects[i].x then
                        --block is right of me
                        player.x=rects[i].x+rects[i].w+1
                    else
                        --block is left of me
                        player.x=rects[i].x-player.w-1
                    end
                end
            end
        end
        fill(255)
        player.x = player.x + player.vel.x
        player.y = player.y + player.vel.y
        rectMode(CORNER)
        rect(player.x,player.y,player.w,player.h)
        fill(0,255,0)
        for k,v in pairs(rects) do
            rect(v.x,v.y,v.w,v.h)
        end
    end
    
  • The user and all related content has been deleted.
  • Posts: 1,595

    @NatTheCoder It's @Coder 's AABB code (library) and my example using it.

  • Jmv38Jmv38 Mod
    Posts: 3,297

    this is nice. How does it compare to build in physics engine perf?

  • Posts: 1,595

    @Jmv38 there isn't a way to rotate the AABB in this code so you can't have a full fledged physics engine, but velocities and direction are good.

  • Posts: 425

    Rotate, hmm... Maybe that's next. Just rotate all the coordinates by the angle of the AABB, but what if there are two? (I guess axis-aligned means it doesn't rotate)

  • Posts: 1,595

    @Coder have fun with the algebra :))

  • Posts: 425

    woo! my favourite :)

Sign In or Register to comment.