'interesting moai code'

[dnhkng]

I hope this thread can start to accumulate some interesting code, not directly related to the SDK, but useful to game and app programming in Lua.

To kick things off, here is some maths code I wrote that does real-time Voronoi Decomposition of a 2D particle field. It could be used to generate non-repetitive tiling for strategy games, background art etc etc.

Please note Clause 2 when you use it in commercial games though

Code: Select all

1.  


2. --[[


3.  


4. Copyright (c) 2012 David Ng


5. dnhkng (at) gmail (dot) com


6.  


7. Permission is hereby granted, free of charge, to any person obtaining a copy


8. of this software and associated documentation files (the "Software"), to deal


9. in the Software without restriction, including without limitation the rights


10. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell


11. copies of the Software, and to permit persons to whom the Software is


12. furnished to do so, subject to the following conditions:


13.  


14. 1) That the above copyright notice and this permission notice shall be included in


15. all copies or substantial portions of the Software.


16.  


17. 2) That the user of this code spends approximately 25 seconds considering


18. whether or not to donate beer-money, an end-user license of any program


19. they have written that utilizes this Software, or both, to the author of


20. the Software.


21.  


22. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR


23. IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,


24. FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE


25. AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER


26. LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,


27. OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN


28. THE SOFTWARE.


29.  


30. Based of the work of Steve J. Fortune (1987) A Sweepline Algorithm for Voronoi Diagrams,


31. Algorithmica 2, 153-174, and its translation to C++ by Matt Brubeck,


32. <!-- m --><a class="postlink" href="http://www.cs.hmc.edu/~mbrubeck/voronoi.html">http://www.cs.hmc.edu/~mbrubeck/voronoi.html</a><!-- m -->


33.  


34. --]]


35.  


36.  


37. -- Heap Functions:


38. Heap = {}


39. function Heap:new()


40.     o = {heap = {}, nodes = {}}


41.     setmetatable(o, self)


42.     self.__index = self


43.     return o


44. end


45.  


46. function Heap:push(k, v)


47.     assert(v ~= nil, "cannot push nil")


48.     local t = self.nodes


49.     local h = self.heap


50.     local n = #h + 1 -- node position in heap array (leaf)


51.     local p = (n - n % 2) / 2 -- parent position in heap array


52.     h[n] = k -- insert at a leaf


53.     t[k] = v


54.     while n > 1 and t[h[p]] > v do -- climb heap?


55.         h[p], h[n] = h[n], h[p]


56.         n = p


57.         p = (n - n % 2) / 2


58.     end


59. end


60.  


61. function Heap:pop()


62.     local t = self.nodes


63.     local h = self.heap


64.     local s = #h


65.     assert(s > 0, "cannot pop from empty heap")


66.     local e = h[1] -- min (heap root)


67.     local r = t[e]


68.     local v = t[h[s]]


69.     h[1] = h[s] -- move leaf to root


70.     h[s] = nil -- remove leaf


71.     t[e] = nil


72.     s = s - 1


73.     local n = 1 -- node position in heap array


74.     local p = 2 * n -- left sibling position


75.     if s > p and t[h[p]] > t[h[p + 1]] then


76.         p = 2 * n + 1 -- right sibling position


77.     end


78.     while s >= p and t[h[p]] < v do -- descend heap?


79.         h[p], h[n] = h[n], h[p]


80.         n = p


81.         p = 2 * n


82.     if s > p and t[h[p]] > t[h[p + 1]] then


83.         p = 2 * n + 1


84.     end


85. end


86.     return e, r


87. end


88.  


89. function Heap:isEmpty()


90.     return self.heap[1] == nil


91. end


92.  


93.  


94. -- Double-linked list Functions


95. DoubleLinkedList = {}


96. function DoubleLinkedList:new()


97.     o = {first = nil, last = nil} -- empty list head


98.     setmetatable(o, self)


99.     self.__index = self


100.     return o


101. end


102.  


103. function DoubleLinkedList:insertAfter(node, data)


104.     local new = {prev = node, next = node.next, x = data.x, y = data.y } -- creates a new node


105.     node.next = new -- the node after node is the new node


106.     if node == self.last then -- check if the old node is the last node...


107.         self.last = new -- ...and set the new node as last node


108.     else


109.         --otherwise set the next nodes previous node to the new one


110.         new.next.prev = new


111.     end


112.     return new -- return the new node


113. end


114.  


115. function DoubleLinkedList:insertAtStart(data)


116.     local new = {prev = nil, next = self.first, x = data.x, y = data.y} -- create the new node


117.     if not self.first then -- check if the list is empty


118.         self.first = new -- the new node is the first and the last in this case


119.         self.last = new


120.    else


121.         -- the node before the old first node is the new first node


122.         self.first.prev = new


123.         self.first = new -- update the list's first field


124.    end


125.    return new


126. end


127.  


128. function DoubleLinkedList:delete(node)


129.     if node == self.first then -- check if the node is the first one...


130.         -- ...and set the new first node if we remove the first


131.         self.first = node.next


132.     else


133.         -- set the previous node's next node to the next node


134.         node.prev.next = node.next


135.     end


136.    


137.     if node == self.last then -- check if the node is the last one...


138.         -- ...the new last node is the node before the deleted node


139.         self.last = node.prev


140.     else


141.         node.next.prev = node.prev -- update the next node's prev field


142.     end


143. end


144.  


145. function DoubleLinkedList:nextNode(node)


146.     return (not node and self.first) or node.next


147. end


148.  


149.  


150. --Voronoi Functions


151. function processEvent(event)


152.     if event.valid then


153.         segment = {startPoint = {x = event.x, y = event.y}, endPoint = {x = 0, y = 0}, done = false, type = 1}


154.         table.insert(segments, segment)


155.         --Remove the associated arc from the front, and update segment info


156.        


157.         beachline:delete(event.arc)


158.        


159.         if event.arc.prev then


160.             event.arc.prev.seg1 = segment


161.         end


162.        


163.         if event.arc.next then


164.             event.arc.next.seg0 = segment


165.         end


166.        


167.         --Finish the edges before and after arc.


168.         if event.arc.seg0 then


169.             event.arc.seg0.endPoint = {x = event.x, y = event.y}


170.             event.arc.seg0.done = true


171.         end    


172.            


173.         if event.arc.seg1 then


174.             event.arc.seg1.endPoint = {x = event.x, y = event.y}


175.             event.arc.seg1.done = true


176.         end    


177.        


178.         -- debugging vertix list!!!


179.         table.insert(vertex, {x = event.x, y = event.y})


180.        


181.         --Recheck circle events on either side of p:


182.         if (event.arc.prev) then


183.             check_circle_event(event.arc.prev, event.x)


184.         end


185.         if (event.arc.next) then


186.             check_circle_event(event.arc.next, event.x)


187.         end    


188.         event.arc = nil


189.    end


190.    event = nil


191. end


192.  


193. function processPoint(point)


194.     --Adds a point to the beachline


195.     local intersect = intersect


196.     if (not beachline.first) then


197.         beachline:insertAtStart(point)


198.         return


199.     end


200.    


201.     --Find the current arc(s) at height p.y (if there are any).


202.     for arc in beachline.nextNode, beachline do


203.         z = (intersect(point,arc))


204.         if z then


205.             --New parabola intersects arc i.  If necessary, duplicate i.


206.             -- ie if there is a next node, but there is not interation, then creat a duplicate


207.             if not (arc.next and (intersect(point,arc.next))) then


208.                 beachline:insertAfter(arc, arc)


209.             else    


210.                 --print("test", arc.next,intersect(point,arc.next).x,intersect(point,arc.next).y, z.x,z.y  )


211.                 return


212.             end    


213.             arc.next.seg1 = arc.seg1


214.            


215.             --Add p between i and i->next.


216.             beachline:insertAfter(arc, point)


217.  


218.            


219.             segment = {startPoint = {x = z.x, y = z.y}, endPoint = {x = 0, y = 0}, done = false, type = 2}


220.             segment2 = {startPoint = {x = z.x, y = z.y}, endPoint = {x = 0, y = 0}, done = false, type = 2}


221.  


222.             -- debugging segment list!!!


223.             table.insert(segments, segment)


224.             table.insert(segments, segment2)


225.  


226.            


227.             --Add new half-edges connected to i's endpoints.


228.             arc.next.seg0 = segment


229.             arc.seg1 = segment


230.             arc.next.seg1 = segment2


231.             arc.next.next.seg0 = segment2


232.            


233.             --Check for new circle events around the new arc:


234.             check_circle_event(arc, point.x)


235.             check_circle_event(arc.next, point.x)


236.             check_circle_event(arc.next.next, point.x)


237.  


238.             return


239.            


240.         end    


241.     end


242.  


243.     --Special case: If p never intersects an arc, append it to the list.


244.     -- Find the last node.


245.    


246.     beachline:insertAtStart(point)


247.  


248.     segment = {startPoint = {x = X0, y = (beachline.last.y + beachline.last.prev.y) / 2}, endPoint = {x = 0, y = 0}, done = false, type = 3}


249.    


250.     table.insert(segments, segment)


251.    


252.     beachline.last.seg0 = segment


253.     beachline.last.prev.seg1 = segment


254. end


255.  


256. function check_circle_event(arc, x0)


257.     --Look for a new circle event for arc i.


258.     --Invalidate any old event.


259.  


260.     if (arc.event and arc.event.x ~= x0) then


261.         arc.event.valid = false


262.     end


263.     arc.event = nil


264.  


265.     if ( not arc.prev or not arc.next) then


266.         return


267.     end


268.    


269.     local a = arc.prev


270.     local b = arc


271.     local c = arc.next


272.  


273.     if ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) >= 0) then


274.         return false


275.     end    


276.  


277.     --Algorithm from O'Rourke 2ed p. 189.


278.     local A = b.x - a.x


279.     local B = b.y - a.y


280.     local C = c.x - a.x


281.     local D = c.y - a.y


282.     local E = A*(a.x+b.x) + B*(a.y+b.y)


283.     local F = C*(a.x+c.x) + D*(a.y+c.y)


284.     local G = 2*(A*(c.y-b.y) - B*(c.x-b.x))


285.  


286.     if (G == 0) then


287.         --return false --Points are co-linear


288.         print("g is 0")


289.     end


290.  


291.     --Point o is the center of the circle.


292.     local o = {}


293.     o.x = (D*E-B*F)/G


294.     o.y = (A*F-C*E)/G


295.  


296.     --o.x plus radius equals max x coordinate.


297.     local x = o.x + math.sqrt( math.pow(a.x - o.x, 2) + math.pow(a.y - o.y, 2) )


298.    


299.     if x and x > x0 then


300.         --Create new event.


301.         arc.event = {x = o.x, y = o.y, arc = arc, valid = true, event = true}


302.         events:push(arc.event, x)


303.     end


304. end


305.  


306. function intersect(point, arc)


307.     --Will a new parabola at point p intersect with arc i?


308.     local res = {}


309.     if (arc.x == point.x) then


310.         return false


311.     end


312.  


313.     if (arc.prev) then


314.         --Get the intersection of i->prev, i.


315.         a = intersection(arc.prev, arc, point.x).y


316.     end    


317.     if (arc.next) then


318.         --Get the intersection of i->next, i.


319.         b = intersection(arc, arc.next, point.x).y


320.     end    


321.     --print("intersect", a,b,p.y)


322.     if (( not arc.prev or a <= point.y) and (not arc.next or point.y <= b)) then


323.         res.y = point.y


324.         -- Plug it back into the parabola equation.


325.         res.x = (arc.x*arc.x + (arc.y-res.y)*(arc.y-res.y) - point.x*point.x) / (2*arc.x - 2*point.x)


326.         return res


327.     end


328.     return false


329. end


330.  


331. function intersection(p0, p1, l)


332.     -- Where do two parabolas intersect?


333.    


334.     local res = {}


335.     local p = {x = p0.x, y = p0.y}


336.  


337.     if (p0.x == p1.x) then


338.         res.y = (p0.y + p1.y) / 2


339.     elseif (p1.x == l) then


340.         res.y = p1.y


341.     elseif (p0.x == l) then


342.         res.y = p0.y


343.         p = p1


344.    else


345.       -- Use the quadratic formula.


346.       local z0 = 2*(p0.x - l);


347.       local z1 = 2*(p1.x - l);


348.  


349.       local a = 1/z0 - 1/z1;


350.       local b = -2*(p0.y/z0 - p1.y/z1);


351.       local c = (p0.y*p0.y + p0.x*p0.x - l*l)/z0 - (p1.y*p1.y + p1.x*p1.x - l*l)/z1


352.       res.y = ( -b - math.sqrt(b*b - 4*a*c) ) / (2*a)


353.    end


354.    


355.    -- Plug back into one of the parabola equations.


356.    res.x = (p.x*p.x + (p.y-res.y)*(p.y-res.y) - l*l)/(2*p.x-2*l)


357.    return res


358. end


359.  


360. function finishEdges()


361.     --Advance the sweep line so no parabolas can cross the bounding box.


362.     l = X1 + (X1-X0) + (Y1-Y0)


363.  


364.     --Extend each remaining segment to the new parabola intersections.


365.     for arc in beachline.nextNode, beachline do


366.         if arc.seg1 then


367.             p = intersection(arc, arc.next, l*2)


368.             arc.seg1.endPoint = {x = p.x, y = p.y}


369.             arc.seg1.done = true


370.         end    


371.     end


372. end


373.  


374.  


375. -- Example code for Moai SDK


376.  


377. screenX = 320


378. screenY =


379.  


380. MOAISim.openWindow ( "Voronoi Decomposition for Moai", 320, 480 )


381.  


382. viewport = MOAIViewport.new ()


383. viewport:setSize ( 320, 480 )


384. viewport:setScale ( 320, 480 )


385.  


386. layer = MOAILayer2D.new ()


387. layer:setViewport ( viewport )


388. MOAISim.pushRenderPass ( layer )


389.  


390. math.randomseed(os.time())


391. X0 = -160


392. X1 = 160


393. Y0 = -240


394. Y1 = 240


395. NUMPOINT = 30


396. points_list= {}


397.  


398.  


399. --Point that share the exact same coordinates can cause problems; adding a random decimal is a quick fix.


400. for i = 1,NUMPOINT do


401.     points_list[i] = {x = math.random(X0,X1) + math.random(),y = math.random(Y0,Y1) + math.random(),dx = math.random(-2,2), dy = math.random(-2,2)}


402. end


403.  


404.  


405. function onDraw ( index, xOff, yOff, xFlip, yFlip )


406.         --Clear and reset tables


407.     beachline = DoubleLinkedList:new()


408.     events = Heap:new()


409.     vertex = {}


410.     segments = {}


411.    


412.     --Update point positions


413.     for i = 1,#points_list do


414.         points_list[i].x =  points_list[i].x + points_list[i].dx


415.         if points_list[i].x < X0 then


416.             --points_list[i].x = X0


417.             points_list[i].dx = -1*points_list[i].dx


418.         end


419.         if points_list[i].x > X1 then


420.             --points_list[i].x = X1


421.             points_list[i].dx = -1*points_list[i].dx


422.         end


423.        


424.         points_list[i].y =  points_list[i].y + points_list[i].dy


425.         if points_list[i].y < Y0 then


426.             --points_list[i].y = Y0


427.             points_list[i].dy = -1*points_list[i].dy


428.         end


429.         if points_list[i].y > Y1 then


430.             --points_list[i].y = Y1


431.             points_list[i].dy = -1*points_list[i].dy


432.         end


433.        


434.                 MOAIGfxDevice.setPenColor(1,0,0,1)


435.                 MOAIDraw.drawCircle(points_list[i].x,points_list[i].y,3)


436.                


437.         events:push(points_list[i], points_list[i].x)


438.     end


439.  


440.    


441.     while not events:isEmpty() do


442.         e, x = events:pop()


443.         if e.event then


444.             processEvent(e)


445.         else


446.             processPoint(e)


447.         end    


448.     end


449.     finishEdges()


450.    


451.    


452.     --Draw the vertex and line segments


453.     for i = 1, #vertex do


454.                 MOAIGfxDevice.setPenColor(1,0,1,1)


455.         MOAIDraw.drawCircle(vertex[i].x,vertex[i].y,3)


456.     end


457.     for i = 1,#segments do


458.         if segments[i].done then


459.                         MOAIGfxDevice.setPenColor(0,1,0,1)


460.                         MOAIDraw.drawLine (segments[i].startPoint.x,segments[i].startPoint.y,segments[i].endPoint.x,segments[i].endPoint.y)


461.         end    


462.     end


463. end


464.  


465.  


466. scriptDeck = MOAIScriptDeck.new ()


467. scriptDeck:setRect ( -160, 160, 240, 240 )


468. scriptDeck:setDrawCallback ( onDraw )


469.  


470. prop = MOAIProp2D.new ()


471. prop:setDeck ( scriptDeck )


472. layer:insertProp ( prop )


473.  


474.  

[ibisum]

Hey, great! Still trying to work out how one would use this in a game, but in the meantime .. very nice!