Drawing a line between moving objects

[Richard_H]

I have 100 nodes that are randomly spawned across the screen and I am trying to draw a line between each of the neighboring nodes. I am able to connect the neighbors using display.newLine but I am having trouble updating each line as the nodes move. This picture shows my output when the lines are drawn. Next I remove the lines and redraw them as the nodes move.

The code I have below works but it causes massive amounts of lag every time the For loops get called.
 
[lua]
local function connectNeighbors()
   local isNeighbor = false
 

   – compare each nodes position to all other nodes 
   for index = 1, 100 do
 
      for index2 = 1, 100 do
         isNeighbor = hasCollidedCircle( nodeTable[index], nodeTable[index2] ) – returns true if objects are in same radius
            
         if ( isNeighbor == true ) then
            – draw line between nodes 

            local nodeLink = display.newLine( mainGroup, (nodeTable[index]).x, (nodeTable[index]).y, (nodeTable[index2]).x,

                            (nodeTable[index2]).y )
 
            – set line color to blue
            nodeLink:setStrokeColor( 0, 0, .8 )
 
            function nodeLink:timer()
              nodeLink:removeSelf()
            end
 
            – remove line after so long
            linkTimer = timer.performWithDelay( 1000, nodeLink, 1)
 
            isNeighbor = false
         end
      end
   end
end[/lua]

Is there a better way to do this that won’t cause so much lag? I have also tried using physics to give each node a large radius and draw a line when a collision is detected, but I can’t get the collision to re-trigger while the nodes remain next to each other. 

Any feedback would be great. Thank you.

[roaminggamer]

I don’t know if this will help, but this is what I worked up…

Full Example

https://github.com/roaminggamer/RG_FreeStuff/raw/master/AskEd/2017/03/nodelinks.zip

Video

https://www.youtube.com/watch?v=mUVRIV1ljrI&feature=youtu.be

Code Paste

io.output():setvbuf("no") display.setStatusBar(display.HiddenStatusBar) local mRand = math.random local getTimer = system.getTimer local left = display.contentCenterX - display.actualContentWidth/2 local right = left + display.actualContentWidth local top = display.contentCenterY - display.actualContentHeight/2 local bottom = top + display.actualContentHeight local nodes = {} local lines = {} local testCount = 15 local function enterFrame( ) -- Destroy all lines from last frame for i = 1, #lines do display.remove( lines[i]) end lines = {} -- Clean the nodes for i = 1, #nodes do nodes[i].linkedTo = {} end -- Draw new lines, but be efficient for i = 1, #nodes do local nodeA = nodes[i] for j = 1, #nodes do local nodeB = nodes[j] if( not nodeA.linkedTo[nodeB] ) then local line = display.newLine( nodeA.x, nodeA.y, nodeB.x, nodeB.y ) nodeA.linkedTo[nodeB] = line nodeB.linkedTo[nodeA] = line line:toBack() line:setStrokeColor(mRand(),mRand(),mRand()) line.strokeWidth = 2 lines[#lines+1] = line end end end end -- Not a great touch function so drag slowly local function touch( self, event ) self:toFront() self.x = event.x self.y = event.y return true end -- Draw 'fake' nodes for i = 1, testCount do local tmp = display.newImageRect( "circle.png", 50, 50 ) tmp.x = mRand( left + 50, right - 50 ) tmp.y = mRand( top + 50, bottom - 50 ) tmp:setFillColor(mRand(),mRand(),mRand()) tmp.touch = touch tmp:addEventListener("touch") nodes[#nodes+1] = tmp end Runtime:addEventListener( "enterFrame", enterFrame )

[roaminggamer]

You can modify my code by only drawing lines between nodes that within a specific distance of the other node.

Compare squared lengths instead of normal lengths to save the square-root calculation.

[roaminggamer]

To be absolutely clear, this is what I mean (requires SSK2):

Full Example

https://github.com/roaminggamer/RG_FreeStuff/raw/master/AskEd/2017/03/nodelinks2.zip

Video

https://www.youtube.com/watch?v=PRCUI0Cf5fk&feature=youtu.be

Code Paste( almost exactly the same)

require "ssk2.loadSSK" \_G.ssk.init( { launchArgs = ..., enableAutoListeners = true, exportCore = true, exportColors = true, exportSystem = true, measure = false, useExternal = true, gameFont = native.systemFont, debugLevel = 0 } ) io.output():setvbuf("no") display.setStatusBar(display.HiddenStatusBar) local mRand = math.random local getTimer = system.getTimer -- https://roaminggamer.github.io/RGDocs/pages/SSK2/libraries/math2D/#vector-representations local vecSub = ssk.math2d.sub local len2Vec = ssk.math2d.length2 local left = display.contentCenterX - display.actualContentWidth/2 local right = left + display.actualContentWidth local top = display.contentCenterY - display.actualContentHeight/2 local bottom = top + display.actualContentHeight local nodes = {} local lines = {} local testCount = 25 local minDist = 200 local minDist2 = minDist ^ 2 local function enterFrame( ) -- Destroy all lines from last frame for i = 1, #lines do display.remove( lines[i]) end lines = {} -- Clean the nodes for i = 1, #nodes do nodes[i].linkedTo = {} end -- Draw new lines, but be efficient for i = 1, #nodes do local nodeA = nodes[i] for j = 1, #nodes do local nodeB = nodes[j] if( not nodeA.linkedTo[nodeB] ) then local dist2 = vecSub( nodeA, nodeB ) dist2 = len2Vec( dist2 ) if( dist2 \<= minDist2 ) then local line = display.newLine( nodeA.x, nodeA.y, nodeB.x, nodeB.y ) nodeA.linkedTo[nodeB] = line nodeB.linkedTo[nodeA] = line line:toBack() line:setStrokeColor(mRand(),mRand(),mRand()) line.strokeWidth = 2 lines[#lines+1] = line end end end end end -- Not a great touch function so drag slowly local function touch( self, event ) self:toFront() self.x = event.x self.y = event.y return true end -- Draw 'fake' nodes for i = 1, testCount do local tmp = display.newImageRect( "circle.png", 50, 50 ) tmp.x = mRand( left + 50, right - 50 ) tmp.y = mRand( top + 50, bottom - 50 ) tmp:setFillColor(mRand(),mRand(),mRand()) tmp.touch = touch tmp:addEventListener("touch") nodes[#nodes+1] = tmp end Runtime:addEventListener( "enterFrame", enterFrame )

[roaminggamer]

The second example can be made even more efficient by adding a dirty flag and only updating when the flag is set to true.

• Set the flag to true whenever a dot is moved
• Set the flag to false after you do a redraw pass

This controls / gates  an entire redraw pass.

With additional work you can refine the algorithm for individual objects, but I’d skip that unless you find the current solution too slow.

[Richard_H]

@roaminggamer

You can modify my code by only drawing lines between nodes that within a specific distance of the other node.

Compare squared lengths instead of normal lengths to save the square-root calculation.

Thanks for the help! Your first solution works much more efficient than mine.

Will your second example work with SSK2 lite or does it require the Pro version?

[roaminggamer]

No, the lite version is just fine.  This example is using the math2d library to do the calculations.  Both lite and PRO include math2d. 

[davebollinger]

quick drive-by hint re nested loops, triangular, n(n+1)/2 vs n^2, for j=i+1,n – google it

[roaminggamer]

@davebollinger,

Roger that.  I started off with that as the loop, but took it out in case he modified the algorithm or alternate uses.

@Richard_H,

If you want to add Dave’s optimization this is the change:

 -- Draw new lines, but be efficient for i = 1, #nodes do local nodeA = nodes[i] for j = i, #nodes do -- THIS LINE -- ALL THIS CODE IS THE SAME end end

Dave is right.  For large sets, this is a huge improvement to the loop structure:

Ex: For a set of 1000 points, this trims the loop from 1,000,000 iterations down to 500,500.  

[Richard_H]

Thanks. That simple change greatly improves the loop. I didn’t even think about how I was making so many unnecessary comparisons. 

[roaminggamer]

I don’t know if this will help, but this is what I worked up…

Full Example

https://github.com/roaminggamer/RG_FreeStuff/raw/master/AskEd/2017/03/nodelinks.zip

Video

https://www.youtube.com/watch?v=mUVRIV1ljrI&feature=youtu.be

Code Paste

io.output():setvbuf("no") display.setStatusBar(display.HiddenStatusBar) local mRand = math.random local getTimer = system.getTimer local left = display.contentCenterX - display.actualContentWidth/2 local right = left + display.actualContentWidth local top = display.contentCenterY - display.actualContentHeight/2 local bottom = top + display.actualContentHeight local nodes = {} local lines = {} local testCount = 15 local function enterFrame( ) -- Destroy all lines from last frame for i = 1, #lines do display.remove( lines[i]) end lines = {} -- Clean the nodes for i = 1, #nodes do nodes[i].linkedTo = {} end -- Draw new lines, but be efficient for i = 1, #nodes do local nodeA = nodes[i] for j = 1, #nodes do local nodeB = nodes[j] if( not nodeA.linkedTo[nodeB] ) then local line = display.newLine( nodeA.x, nodeA.y, nodeB.x, nodeB.y ) nodeA.linkedTo[nodeB] = line nodeB.linkedTo[nodeA] = line line:toBack() line:setStrokeColor(mRand(),mRand(),mRand()) line.strokeWidth = 2 lines[#lines+1] = line end end end end -- Not a great touch function so drag slowly local function touch( self, event ) self:toFront() self.x = event.x self.y = event.y return true end -- Draw 'fake' nodes for i = 1, testCount do local tmp = display.newImageRect( "circle.png", 50, 50 ) tmp.x = mRand( left + 50, right - 50 ) tmp.y = mRand( top + 50, bottom - 50 ) tmp:setFillColor(mRand(),mRand(),mRand()) tmp.touch = touch tmp:addEventListener("touch") nodes[#nodes+1] = tmp end Runtime:addEventListener( "enterFrame", enterFrame )

[roaminggamer]

You can modify my code by only drawing lines between nodes that within a specific distance of the other node.

Compare squared lengths instead of normal lengths to save the square-root calculation.

[roaminggamer]

To be absolutely clear, this is what I mean (requires SSK2):

Full Example

https://github.com/roaminggamer/RG_FreeStuff/raw/master/AskEd/2017/03/nodelinks2.zip

Video

https://www.youtube.com/watch?v=PRCUI0Cf5fk&feature=youtu.be

Code Paste( almost exactly the same)

require "ssk2.loadSSK" \_G.ssk.init( { launchArgs = ..., enableAutoListeners = true, exportCore = true, exportColors = true, exportSystem = true, measure = false, useExternal = true, gameFont = native.systemFont, debugLevel = 0 } ) io.output():setvbuf("no") display.setStatusBar(display.HiddenStatusBar) local mRand = math.random local getTimer = system.getTimer -- https://roaminggamer.github.io/RGDocs/pages/SSK2/libraries/math2D/#vector-representations local vecSub = ssk.math2d.sub local len2Vec = ssk.math2d.length2 local left = display.contentCenterX - display.actualContentWidth/2 local right = left + display.actualContentWidth local top = display.contentCenterY - display.actualContentHeight/2 local bottom = top + display.actualContentHeight local nodes = {} local lines = {} local testCount = 25 local minDist = 200 local minDist2 = minDist ^ 2 local function enterFrame( ) -- Destroy all lines from last frame for i = 1, #lines do display.remove( lines[i]) end lines = {} -- Clean the nodes for i = 1, #nodes do nodes[i].linkedTo = {} end -- Draw new lines, but be efficient for i = 1, #nodes do local nodeA = nodes[i] for j = 1, #nodes do local nodeB = nodes[j] if( not nodeA.linkedTo[nodeB] ) then local dist2 = vecSub( nodeA, nodeB ) dist2 = len2Vec( dist2 ) if( dist2 \<= minDist2 ) then local line = display.newLine( nodeA.x, nodeA.y, nodeB.x, nodeB.y ) nodeA.linkedTo[nodeB] = line nodeB.linkedTo[nodeA] = line line:toBack() line:setStrokeColor(mRand(),mRand(),mRand()) line.strokeWidth = 2 lines[#lines+1] = line end end end end end -- Not a great touch function so drag slowly local function touch( self, event ) self:toFront() self.x = event.x self.y = event.y return true end -- Draw 'fake' nodes for i = 1, testCount do local tmp = display.newImageRect( "circle.png", 50, 50 ) tmp.x = mRand( left + 50, right - 50 ) tmp.y = mRand( top + 50, bottom - 50 ) tmp:setFillColor(mRand(),mRand(),mRand()) tmp.touch = touch tmp:addEventListener("touch") nodes[#nodes+1] = tmp end Runtime:addEventListener( "enterFrame", enterFrame )

[roaminggamer]

The second example can be made even more efficient by adding a dirty flag and only updating when the flag is set to true.

• Set the flag to true whenever a dot is moved
• Set the flag to false after you do a redraw pass

This controls / gates  an entire redraw pass.

With additional work you can refine the algorithm for individual objects, but I’d skip that unless you find the current solution too slow.

[Richard_H]

@roaminggamer

You can modify my code by only drawing lines between nodes that within a specific distance of the other node.

Compare squared lengths instead of normal lengths to save the square-root calculation.

Thanks for the help! Your first solution works much more efficient than mine.

Will your second example work with SSK2 lite or does it require the Pro version?

[roaminggamer]

No, the lite version is just fine.  This example is using the math2d library to do the calculations.  Both lite and PRO include math2d. 

[davebollinger]

quick drive-by hint re nested loops, triangular, n(n+1)/2 vs n^2, for j=i+1,n – google it

[roaminggamer]

@davebollinger,

Roger that.  I started off with that as the loop, but took it out in case he modified the algorithm or alternate uses.

@Richard_H,

If you want to add Dave’s optimization this is the change:

 -- Draw new lines, but be efficient for i = 1, #nodes do local nodeA = nodes[i] for j = i, #nodes do -- THIS LINE -- ALL THIS CODE IS THE SAME end end

Dave is right.  For large sets, this is a huge improvement to the loop structure:

Ex: For a set of 1000 points, this trims the loop from 1,000,000 iterations down to 500,500.  

[Richard_H]

Thanks. That simple change greatly improves the loop. I didn’t even think about how I was making so many unnecessary comparisons.