Destructible terrain issue

I’ve had an idea for a battleground game with destructible terrain, but I want to find out how I can fix this issue with overlapping vertices: http://www.youtube.com/watch?v=HxOsTPAQ_-Q

Here’s the code:


--# Main
-- destructable

-- Use this function to perform your initial setup
function setup()
    ter = Terrain(vec2(WIDTH/2,HEIGHT/4),vec2(WIDTH,HEIGHT/2))
    
end

function touched(t)
    ter:touched(t)
end

-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness
    strokeWidth(5)

    -- Do your drawing here
    ter:draw()
end


--# Terrain
Terrain = class()

function Terrain:init(pos,size)
    self.pos = pos
    self.size = size
    local verts = {}
    for x=1,20 do
        table.insert(verts,vec2(pos.x-size.x/2+(size.x/20)*x,pos.y+size.y/2))
    end
    for y=1,20 do
        table.insert(verts,vec2(pos.x+size.x/2,pos.y+size.y/2-(size.y/20)*y))
    end
    for x=1,20 do
        table.insert(verts,vec2(pos.x+size.x/2-(size.x/20)*x,pos.y-size.y/2))
    end
    for y=1,20 do
        table.insert(verts,vec2(pos.x-size.x/2,pos.y-size.y/2+(size.y/20)*y))
    end
    self.verts = verts
    self.m = mesh()
    self.m:setColors(255,255,255,255)
    self.m.vertices = triangulate(verts)
end

function Terrain:draw()
    self.m:draw() 
end

function Terrain:touched(t)
    local p,s = self.pos,self.size
    local tp = vec2(t.x,t.y)
    local sp = #self.verts
    for i=1,sp do
        local sv = self.verts[i]
        if sv:dist(tp) < 60 then 
            local dir = (sv-tp):normalize()*20
            self.verts[i] = self.verts[i] + dir
        end
    end  
    for i=2,sp do
        local sv = self.verts[i]
        local svi = self.verts[i-1]
        if not sv then return end
        if sv:dist(svi)>60 then
            local d = (sv+svi)/2
            if d.x > p.x-s.x/2 and d.x < p.x+s.x/2 and d.y < p.y+s.y/2 and d.y > p.y-s.y/2 then
                table.insert(self.verts,i,d)
            else
                table.remove(self.verts,i)
            end
        end
        if sv:dist(svi)<20 then
            table.remove(self.verts,i)
        end
    end   
    self.m.vertices = triangulate(self.verts)
end

Sorry I can’t help you but wow thats awesome stuff!

Here’s a little update for anyone who wants to play around with it, added a ball and a polygon of the vertices (vertices now shown by red dots) its still quite buggy so if anyone can help its well appreciated. Also note that when two vertices are close they will merge together, this can be used to delete unwanted terrain.

Code below:



--# Main
-- destructable

-- Use this function to perform your initial setup
function setup()
    
    txture = readImage("Documents:ExampleCircle",5,5)
    ter = Terrain(vec2(WIDTH/2,HEIGHT/4),vec2(WIDTH,HEIGHT/2))
    circ = physics.body(CIRCLE,15)
    circ.position = vec2(WIDTH/2,600)
    holding = nil
end

function touched(t)
    local tp = vec2(t.x,t.y)
    local cp = circ.position
    if t.state == BEGAN and tp:dist(cp) < 30 then
        holding = tp
    end
    if t.state == MOVING and holding ~= nil then
        holding = tp
    end
    if t.state == ENDED and holding ~= nil then
        holding = nil
    end
    if holding == nil then
        ter:touched(t)
    end  
end

-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness
    strokeWidth(5)
    if holding ~= nil then
        circ:applyForce(holding-circ.position-circ.linearVelocity/4)
    end
    -- Do your drawing here
    ter:draw()
    sprite("Documents:circle",circ.x,circ.y,30,30)
end


--# Terrain
Terrain = class()

function Terrain:init(pos,size)
    self.pos = pos
    self.size = size
    local verts = {}
    for x=1,20 do
        table.insert(verts,vec2(pos.x-size.x/2+(size.x/20)*x,pos.y+size.y/2))
    end
    for y=1,20 do
        table.insert(verts,vec2(pos.x+size.x/2,pos.y+size.y/2-(size.y/20)*y))
    end
    for x=1,20 do
        table.insert(verts,vec2(pos.x+size.x/2-(size.x/20)*x,pos.y-size.y/2))
    end
    for y=1,20 do
        table.insert(verts,vec2(pos.x-size.x/2,pos.y-size.y/2+(size.y/20)*y))
    end
    self.verts = verts
    self.m = mesh()
    self.m:setColors(255,255,255,255)
    self.m.vertices = triangulate(verts)
    self.floor = physics.body(POLYGON,unpack(verts))
    self.floor.type = STATIC
    
    self.bound = 30
    self.oe = ElapsedTime
end

function Terrain:draw()
    if ElapsedTime > self.oe+0.2 then
        self.oe = ElapsedTime
        if self.t then
        self.m.vertices = triangulate(self.verts)
        self.floor:destroy()
        self.floor = physics.body(POLYGON,unpack(self.verts))
        self.floor.type = STATIC
        end
    end
    self.m:draw() 
    local sv = self.verts
    for i=1,#sv do
        sprite(txture,sv[i].x,sv[i].y,5,5)
    end
    pushStyle()
        fill(0,255)
        text(math.floor(1/DeltaTime),100,600)
    popStyle()
end

function Terrain:touched(t)
    self.t = true
    if t.state == ENDED then
        self.t = false
    end
    local p,s = self.pos,self.size
    local tp = vec2(t.x,t.y)
    local sp = #self.verts
    for i=1,sp do
        local sv = self.verts[i]
        if i > 1 then
        local svi = self.verts[i-1]
        if not sv then return end
            if sv:dist(svi)>self.bound*2 then
                local d = (sv+svi)/2
                if d.x > p.x-s.x/2 and d.x < p.x+s.x/2 and d.y > p.y-s.y/2 then
                    table.insert(self.verts,i,d)
                else
                    table.remove(self.verts,i)
                    return
                end
            end
       
        if sv:dist(svi)<15 then
            table.remove(self.verts,i)
            return
        end
        end
        if sv:dist(tp) < self.bound then 
            local dir = (sv-tp):normalize()*5+vec2(t.deltaX,t.deltaY)
            self.verts[i] = self.verts[i] + dir
        end
    end  
end

@Luatee can i use this to make my own game out of it?

Sure but there are a few bugs such as overlapping meshes

@Luatee, what should be happening if you move a vertex over another set of vertices? Should it remove the ones being overlapped or just stop it from allowing the overlap? I think either option would require you to compare the vertex being moved to all vertices that currently exist. Having to use a nested for loop to do this may decrease performance though.

Edit: you may be able to take your table of vertices and put them into a temporary table that is sorted by x and y position and use this temporary table for the comparison.

Well there are a few ways i can check for overlapping, but I’m not sure which way to do it, I was thinking that I could check on the timer i use to update the vertices and if it does overlap then seperate the vertices from the mesh by copying the ones after the overlap and then deleting them and reproducing them to another mesh

@Luatee, I almost have it to where it won’t allow the overlap. Here is the modified Terrain:touched function:

function Terrain:touched(t)
    self.t = true
    if t.state == ENDED then
        self.t = false
    end
    local p,s = self.pos,self.size
    local tp = vec2(t.x,t.y)
    local sp = #self.verts
    for i=1,sp do
        local sv = self.verts[i]
        local svi
        if i > 1 then
            svi = self.verts[i-1]
        else
            svi = self.verts[sp]
        end
        if not sv then return end
        local pass = true
        if sv:dist(tp) < self.bound then
            local dir = (sv-tp):normalize()*5+vec2(t.deltaX,t.deltaY)
            for ii=1,sp do
                if i ~= ii then
                    local tsv = self.verts[ii]
                    if tsv:dist(sv+dir) < self.bound/2 then
                        pass = false
                    end
                end
            end
            --pass = true
            if pass then
                self.verts[i] = self.verts[i] + dir
            end
        end
        if sv:dist(svi) > self.bound*2 and pass then
            local d = (sv+svi)/2
            if d.x > p.x-s.x/2 and d.x < p.x+s.x/2 and d.y > p.y-s.y/2 then
                table.insert(self.verts,i,d)
            else
                table.remove(self.verts,i)
                return
            end
        elseif sv:dist(svi) < self.bound/2 then
            table.remove(self.verts,i)
            return
        end
    end  
end

I swapped some things around in it. It now checks to see if the vertex coordinates should be updated before adding or removing any current vertices. Also I made it so you can move the add to the first position by making it compare index 1 with the last index in the table of vertices.

It still needs some tweaking, but it is getting close.

I’ve managed to do most of this already, I done the first and last comparison and the updating the vertices only when changed but this looks good I’m going to see where I can get with this overlapping situation

Hehe, I figured you would probably be as far as I am by now. One problem I notice is that for the overlapping to work you need to compare the distance of the moved vertex to all other vertices and then stop the move if it gets too close, but some of the auto-generated vertices are generated within the bounds of the test so they can’t be moved after being created. I see you have bounds set to 30 but the vertices are being placed on a 5x5 grid. If I change it to a 30x30 grid it works much better but also cuts down on the smoothness of the terrain.

Haha I’m still at it now Ive been doing a bit of research and here’s a good read: http://www-ai.cs.uni-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/LITERATUR/OverlappingCommunities.pdf
A network (set of points) has many different algorithms for all different situations, so finding this overlapping of vertices isn’t such a big problem! I have tried other varieties if points and bounds but I find this to be the best rocky/cave looking ratio so I stuck with this.

Interesting, add some water to this:

Only changing the Main:

-- destructable

-- Use this function to perform your initial setup
function setup()
    parameter.boolean("addWater",false)
    defaultGravity = physics.gravity()
    parameter.boolean("useGravity",false, function(v)
       if v then 
        physics.gravity(Gravity)
       else
        physics.gravity(defaultGravity)
       end
    end)
    
    parameter.watch("#balls")
    
    txture = readImage("Documents:ExampleCircle",5,5)
    ter = Terrain(vec2(WIDTH/2,HEIGHT/4),vec2(WIDTH,HEIGHT/2))
    circ = physics.body(CIRCLE,15)
    circ.position = vec2(WIDTH/2,600)
    holding = nil
    setupWater()
    bgImg = readImage("SpaceCute:Background")
end

function touched(touch)
    if addWater then
        WaterTouched(touch)
    else
        TerrainTouched(touch)
    end
end

function TerrainTouched(t)
    local tp = vec2(t.x,t.y)
    local cp = circ.position
    if t.state == BEGAN and tp:dist(cp) < 30 then
        holding = tp
    end
    if t.state == MOVING and holding ~= nil then
        holding = tp
    end
    if t.state == ENDED and holding ~= nil then
        holding = nil
    end
    if holding == nil then
        ter:touched(t)
    end  
end

-- This function gets called once every frame
function draw()
    if useGravity then 
        physics.gravity(Gravity)
    end
    --background(127, 127, 127, 255)
    background(255)
    sprite(bgImg, WIDTH/2, HEIGHT/2, WIDTH, HEIGHT)
    -- This sets the line thickness
    strokeWidth(5)
    if holding ~= nil then
        circ:applyForce(holding-circ.position-circ.linearVelocity/4)
    end
    -- Do your drawing here
    ter:draw()
    waterDraw()
    sprite("Documents:ExampleCircle",circ.x,circ.y,circ.radius*2.5)
end


function setupWater()
    m = {}
    m.shader = shader(vS, fS)
    Number_of_Balls = 500
    Metaball_Resolution = 211
    Metaball_Size = 50
    
    function GENERATE_METABALL()
        local mr = Metaball_Resolution
        local ms = Metaball_Size
        blendMode(NORMAL)
        ballTex = image(166, 166)
        local a,d2,ref2
        ref2 = ms*ms/15
        for i = 1,166 do 
            for j =1,166 do
             d2 = (i-100)*(i-100) + (j-100)*(j-100)
             a = math.exp(-d2/ref2)*255
             ballTex:set(i,j,color(a,a,a,255))
             
            end
        end 
    end

    GENERATE_METABALL()
    balls = {}
    

    img = image(WIDTH, HEIGHT)
    m = mesh()
    r = m:addRect(WIDTH / 2, HEIGHT / 2, WIDTH, HEIGHT)
    m:setRectTex(r, 0, 0, 1, 1)
    m.texture = img
    m.shader = shader(vS, fS) 
    --soft = SoftBody()
end

function createDrop(x,y)
    local ball = physics.body(CIRCLE, 6)
    --ball.type = DYNAMIC
    ball.x = x
    ball.y = y
    ball.restitution = .1
    ball.linearVelocity = vec2(0,0)
    ball.friction = 0.05
    ball.mass = 0.1
    ball.angularVelocity = 0.0
    ball.bullet = false
    ball.linearDamping = 0
    return ball
end


function waterDraw()
    -- remove invisible balls... here to avoid flickering
    for k,b in ipairs(balls) do
        if b.x+Metaball_Size> WIDTH +Metaball_Size *2 or b.x<-Metaball_Size then
            table.remove(balls, k)
            b:destroy()
        end
    end
    blendMode(NORMAL)
    setContext(img)
        background(0) -- clear buffer
        --tint(139, 145, 157, 255)
        blendMode(ADDITIVE)
        for k,b in ipairs(balls) do
            sprite(ballTex, b.x, b.y)
        end
        --noTint()
   setContext()
   
   m.texture = img
   blendMode(MULTIPLY)
   m:draw()
   
end

function WaterTouched(touch)
    if touch.state == BEGAN or touch.state == MOVING then
        if balls[Number_of_Balls + 1] == nil then
            local ball = createDrop(touch.x,touch.y)
            table.insert(balls, ball)
        else
            balls[Number_of_Balls + 1].x = touch.x
            balls[Number_of_Balls + 1].y = touch.y
        end
    end
end

vS = [[
//
// A basic vertex shader
//

//This is the current model * view * projection matrix
// Codea sets it automatically
uniform mat4 modelViewProjection;

//This is the current mesh vertex position, color and tex coord
// Set automatically
attribute vec4 position;
attribute vec4 color;
attribute vec2 texCoord;

//This is an output variable that will be passed to the fragment shader
varying lowp vec4 vColor;
varying highp vec2 vTexCoord;

void main()
{
    //Pass the mesh color to the fragment shader
    vColor = color;
    vTexCoord = texCoord;

    //Multiply the vertex position by our combined transform
    gl_Position = modelViewProjection * position;
}
]]

fS = [[
//
// A basic fragment shader
//

//Default precision qualifier
precision highp float;


//This represents the current texture on the mesh
uniform lowp sampler2D texture;

//The interpolated vertex color for this fragment
varying lowp vec4 vColor;

//The interpolated texture coordinate for this fragment
varying highp vec2 vTexCoord;

void main()
{
    //Sample the texture at the interpolated coordinate
    lowp vec4 col = texture2D( texture, vTexCoord ) * vColor;

    //Set the output color to the texture color
    if (max(col.r, max(col.g, col.b)) > 0.75)
    {
        gl_FragColor = vec4(0.0, 0.0, 1.0, 1.0);
    }
    else
    {
        gl_FragColor = vec4(1.0, 1.0, 1.0, 1.0);
    }
}
]]


Video and gist:

http://www.youtube.com/watch?v=5jm0xtwNyo0

Only changing the Main:
https://gist.github.com/juaxix/6240100

@juaxix your water looks brilliant now! Reminds me of where’s my water, I don’t understand why it’s going to the right though, I haven’t checked the code out yet…

It is the same as before :smiley:

I thought the other one wasn’t see through

@Luatee I’ve been messing about with your excellent code. This version improves the overlapping problem if you are removing bits of terrain (does something funny when adding bits) and divides the original polygon into two if you go right through. Would be awesome if the polygons could be made into dynamic objects but haven’t had the time to work on that


--# Main
-- destructable

-- Use this function to perform your initial setup
function setup()
    tertab={}
    v1={vec2(100,100),vec2(100,400),vec2(400,400),vec2(400,100)}
    table.insert(tertab,Terrain(v1))    
    v2={vec2(500,100),vec2(500,400),vec2(700,400),vec2(700,100)}
    table.insert(tertab,Terrain(v2))
    selv=vec2(0,0)
    selv2=vec2(0,0)
    np=1
    np2=1
    bitesize=40
end

function touched(t)
    for c,tt in pairs(tertab) do
    tt:touched(t)
    end
end

-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness
    strokeWidth(5)

    -- Do your drawing here
        for c,tt in pairs(tertab) do
    tt:draw()
    end
end


--# Terrain
Terrain = class()

function Terrain:init(v)
    self.pos = vec2(WIDTH/2,HEIGHT/2)
    self.size = vec2(WIDTH,HEIGHT)
    local verts = v        
    self.verts = verts
    self.m = mesh()
    self.m:setColors(255,255,255,255)
    self.m.vertices = triangulate(verts)
end

function Terrain:draw()
    self.m:draw()     
    for i=1,#self.verts do
        local sv = self.verts[i]
        fontSize(8)
        fill(255)
        text(i,sv.x,sv.y)
    end  
    fill(122)
end

function Terrain:touched(t)
    local p,s = self.pos,self.size
    local tp = vec2(t.x,t.y)
    local sp = #self.verts
    del=0
    for i=1,sp do
        local sv = self.verts[i]
        if sv:dist(tp) < bitesize then 
            local dir = (sv-tp):normalize()*bitesize/3
            local d = self.verts[i] + (sv-tp):normalize()*bitesize/3
                --winding number wn is zero if outside the polygon
                --algorithm adapted from http://geomalgorithms.com/a03-_inclusion.html
                local wn=0
                for w=1,sp-1 do
                    selv=self.verts[w]
                    selv2=self.verts[w+1]
                    if selv.y<=d.y then
                        if selv2.y>d.y then
                            if isLeft(selv,selv2,d)>0 then
                                wn = wn + 1
                            end
                        end
                    else
                        if selv2.y<=d.y then
                            if isLeft(selv,selv2,d)<0 then
                                wn = wn -1
                            end
                        end
                    end                
                end
            if wn==0 then            
                del=1
                --find the two nearest points and join them to the previous and next points in the polygon
                local nearp=100000--not ideal
                np=1
                for j=1,sp do
                    local pt = self.verts[j]
                    if pt:dist(sv) < nearp and i~=j then 
                        nearp=pt:dist(sv)
                        np=j
                    end
                end
                np2=i
            end                       
            self.verts[i] = self.verts[i] + dir
        end
    end

    for i=1,sp do
        local svi =vec2(0,0)
        local sv = self.verts[i]
        if i==1 then
            svi=self.verts[sp]
        else
            svi = self.verts[i-1]
        end
        if not sv then return end
        if sv:dist(svi)>bitesize then
            local d = (sv+svi)/2
            if d.x > p.x-s.x/2 and d.x < p.x+s.x/2 and d.y < p.y+s.y/2 and d.y > p.y-s.y/2 then
                table.insert(self.verts,i,d)
            else
               table.remove(self.verts,i)
            end
        end
        if sv:dist(svi)<bitesize/3 then
            table.remove(self.verts,i) --merge poits which are close
        end
    end   
    
        if del==1 then
            self.tempverts={}
            self.tempverts2={}
            for p=1,sp do
                if p>np2+1 and p<np-1 then
                    table.insert(self.tempverts,self.verts[p])
                elseif p<np2-1 or p>np+1 then
                    table.insert(self.tempverts2,self.verts[p])
                end
            end
            self.verts=self.tempverts
            del=0
            if #self.tempverts2>3 then
                table.insert(tertab,Terrain(self.tempverts2))
            end
     end
    self.m.vertices = triangulate(self.verts)
end

function isLeft(P0,P1,P2)
    return ( (P1.x - P0.x) * (P2.y - P0.y)- (P2.x -  P0.x) * (P1.y - P0.y) )
end

Talk about excellence! That’s much better, could make a game with it now

Just an update: If you follow Emanuele Feronato (which you probably don’t), she posts some really cool physics examples. Anyways, she recently posted a new post about destructive terrains. Just thought I might share it: http://www.emanueleferonato.com/2013/10/17/how-to-create-destructible-terrain-using-box2d-step-2/