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)

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

``````

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

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
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()
defaultGravity = physics.gravity()
parameter.boolean("useGravity",false, function(v)
if v then
physics.gravity(Gravity)
else
physics.gravity(defaultGravity)
end
end)

parameter.watch("#balls")

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()
end

function touched(touch)
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
ter:draw()
waterDraw()
end

function setupWater()
m = {}
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
--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)
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 = [[
//
//

//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 = [[
//
//

//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:

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

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)

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
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/