This is a read-only snapshot of the ComputerCraft forums, taken in April 2020.
michthom's profile picture

Managing tasks in a recursive, parallel program

Started by michthom, 24 February 2016 - 07:44 PM
michthom #1
Posted 24 February 2016 - 08:44 PM
Hi folks

I was challenged by my Minecraft and math-loving son to create a Menger sponge using command computers.
I have a program that "sort of" works, but while I'm happy to have my effort described as "sick!" I'm aware the code may make you all queasy.

Spoiler

-- Create a Menger Sponge (https://en.wikipedia.org/wiki/Menger_sponge) using command computer
local maxScale=5 -- Control the number of iterations of the Menger Sponge
local x0, y0, z0 = commands.getBlockPosition() -- where is my CC in the world?

y0 = y0 - 1 -- Offset the building area
x0 = x0 + 5
z0 = z0 + 5

function cube(x, y, z, scale)
  -- recursive function to build the sponge from the outside in.
  local i, j, k
  -- Stop when we get to the single-block scale
  if scale>0 then
	-- fill a cube with sides 3-to-the-power-of-"scale" long
	commands.execAsync("fill "..x.." "..y.." "..z.." "..(x+3^scale-1).." "..(y+3^scale-1).." "..(z+3^scale-1).." minecraft:wool 0")
	-- knock holes in that cube along the x, y, z axes
	commands.execAsync("fill "..(x + 3^(scale-1)).." "..(y + 3^(scale-1)).." "..z.." "..(x + 3^scale-1-3^(scale-1)).." "..(y+3^scale-1-3^(scale-1)).." "..(z+3^scale-1).." minecraft:air")
	commands.execAsync("fill "..(x + 3^(scale-1)).." "..y.." "..(z + 3^(scale-1)).." "..(x + 3^scale-1-3^(scale-1)).." "..(y+3^scale-1).." "..(z+3^scale-1-3^(scale-1)).." minecraft:air")
	commands.execAsync("fill "..x.." "..(y + 3^(scale-1)).." "..(z + 3^(scale-1)).." "..(x + 3^scale-1).." "..(y+3^scale-1-3^(scale-1)).." "..(z+3^scale-1-3^(scale-1)).." minecraft:air")
	-- for each of the 'sub-cubes' of the current sized cube
	for i = 0, 2 do
	  for j = 0, 2 do
		for k = 0, 2 do
		  if ( i ~= 1 and j ~= 1 ) or ( j ~= 1 and k ~= 1 ) or ( i ~= 1 and k ~= 1 ) then
			--skipping the sub-cube volumes along the axes, recurse down at the next lower scale
			cube(x + 3^(scale-1) * i, y + 3^(scale-1) * j, z + 3^(scale-1) * k, scale-1)
		  end
		end
	  end
	end
  end
end

cube(x0, y0, z0, maxScale)

I wanted to take the advice from Bomb Bloke here (http://www.computerc...413#entry215413) and ensure that I don't run out of tasks, but I'm now at a stage that the program starts, schedules a bunch of tasks and then gets stuck.

Of course I tried to be too clever by half, and actually track the tasks I'm queueing, and only decrement my task counter when one of my own tasks completes.

Currently this code starts out, queues a bunch of tasks then resolutely sits and does nothing, I can't see if any task_complete events are being caught never mind recognised.

Gently please, put me back on the right track?

Spoiler

local maxScale = 5
local maxTasks = 200
local runningTasks = 0
local taskList = {}
local commandString = ""

local x0, y0, z0 = commands.getBlockPosition()

y0 = y0 - 1
x0 = x0 + 5
z0 = z0 + 5

local function snooze()
-- A faster way to yield than os.sleep(0)
--
-- From http://www.computercraft.info/forums2/index.php?/topic/25670-bbs-guide-to-coroutines/
-- Modified to include a pseudo-random suffix on a human-readable prefix
--
  local myEvent = "MT_snooze_" .. string.sub(tostring({}),-6)
  os.queueEvent(myEvent)
  os.pullEvent(myEvent)
end

local function queueTask(thisCommand)
  local newTaskID = 0

  while runningTasks >= maxTasks do snooze() end

  newTaskID = commands.execAsync(thisCommand)

  if newTaskID then
	print("Queued taskID: "..newTaskID)
	taskList[newTaskID] = {}
	runningTasks = runningTasks + 1
  end
end

local function pullTaskComplete()
  local event=""
  local taskID=0
  local success=false
  local errorString=""

  while true do
	event, taskID, success, errorString = os.pullEvent("task_complete")
	print("task_complete: "..taskID)

	if taskList[taskID] then
	  print("Completed taskID: "..taskID)

	  taskList[taskID] = nil
	  curCommands = curCommands - 1
	end
  end
end

function mengerSponge(x, y, z, scale)
  local i, j, k
  if scale>0 then

	queueTask("fill "..x.." "..y.." "..z.." "..(x+3^scale-1).." "..(y+3^scale-1).." "..(z+3^scale-1).." minecraft:wool 0")
	queueTask("fill "..(x + 3^(scale-1)).." "..(y + 3^(scale-1)).." "..z.." "..(x + 3^scale-1-3^(scale-1)).." "..(y+3^scale-1-3^(scale-1)).." "..(z+3^scale-1).." minecraft:air")
	queueTask("fill "..(x + 3^(scale-1)).." "..y.." "..(z + 3^(scale-1)).." "..(x + 3^scale-1-3^(scale-1)).." "..(y+3^scale-1).." "..(z+3^scale-1-3^(scale-1)).." minecraft:air")
	queueTask("fill "..x.." "..(y + 3^(scale-1)).." "..(z + 3^(scale-1)).." "..(x + 3^scale-1).." "..(y+3^scale-1-3^(scale-1)).." "..(z+3^scale-1-3^(scale-1)).." minecraft:air")

	for i = 0, 2 do
	  for j = 0, 2 do
		for k = 0, 2 do
		  if ( i ~= 1 and j ~= 1 ) or ( j ~= 1 and k ~= 1 ) or ( i ~= 1 and k ~= 1 ) then
			mengerSponge(x + 3^(scale-1) * i, y + 3^(scale-1) * j, z + 3^(scale-1) * k, scale-1)
		  end
		end
	  end
	end
  end
end

parallel.waitForAny(pullTaskComplete, mengerSponge(x0, y0, z0, maxScale))

Cheers
Mike Thomson
KingofGamesYami #2
Posted 24 February 2016 - 10:26 PM
The problem here is the parrallel.waitForAny. Take a close look at the arguments you are passing it.


parallel.waitForAny( pullTaskComplete, mengerSponge( x0, y0, z0, maxScale ) )

pullTaskComplete is a function, that's fine

mengerSponge( x0, y0, z0, maxScale ) is not fine, because it's nil. Why? Because you called your function. So you're passing the return value (nil) - actually, you never get that far. Since your mengerSponge function never ends, parallel.waitForAny never actually executes. Because it never executes, it never calls pullTaskComplete.
Lyqyd #3
Posted 24 February 2016 - 11:19 PM
The easiest/quickest fix for the problem described above is to put your desired function call in an anonymous function:


parallel.waitForAny( pullTaskComplete, function() mengerSponge( x0, y0, z0, maxScale ) end )

I haven't looked at the rest of the code in-depth, so I can't state with certainty that this will fix your program as a whole, but it will fix this line.
Bomb Bloke #4
Posted 25 February 2016 - 12:59 AM
I've been waiting for someone to try fractal building… This thing's pretty cool to watch in action, it just keeps going and going… :o/>
michthom #5
Posted 25 February 2016 - 07:55 PM
That loud percussive sound was my hand to my forehead! Thanks KingofGamesYami, Lyqyd, Bomb Bloke. Easy to see why this is the "Pro" forum…

I didn't *quite* realise how big this thing gets at maxScale = 5!
And to be honest, the cleanup script is if anything *more* fun to watch in action.

Here's the code fixed up with another bug squished, and the corresponding clearup script.

Spoiler

local maxScale = 5
local maxTasks = 200
local runningTasks = 0
local taskList = {}
local commandString = ""

local x0, y0, z0 = commands.getBlockPosition()

y0 = y0 - 1
x0 = x0 + 5
z0 = z0 + 5

local function snooze()
-- A faster way to yield than os.sleep(0)
--
-- From http://www.computercraft.info/forums2/index.php?/topic/25670-bbs-guide-to-coroutines/
-- Modified to include a pseudo-random suffix on a human-readable prefix
--
  local myEvent = "MT_snooze_" .. string.sub(tostring({}),-6)
  os.queueEvent(myEvent)
  os.pullEvent(myEvent)
end

local function queueTask(thisCommand)
  local newTaskID = 0

  while runningTasks >= maxTasks do snooze() end

  newTaskID = commands.execAsync(thisCommand)

  if newTaskID then
    print("Queued taskID: "..newTaskID)
    taskList[newTaskID] = {}
    runningTasks = runningTasks + 1
  end
end

local function pullTaskComplete()
  local event=""
  local taskID=0
  local success=false
  local errorString=""

  while true do
    event, taskID, success, errorString = os.pullEvent("task_complete")
    print("task_complete: "..taskID)

    if taskList[taskID] then
      print("Completed taskID: "..taskID)

      taskList[taskID] = nil
      runningTasks = runningTasks - 1
    end
  end
end

function mengerSponge(x, y, z, scale)
  local i, j, k
  if scale>0 then

    queueTask("fill "..x.." "..y.." "..z.." "..(x+3^scale-1).." "..(y+3^scale-1).." "..(z+3^scale-1).." minecraft:wool 0")
    queueTask("fill "..(x + 3^(scale-1)).." "..(y + 3^(scale-1)).." "..z.." "..(x + 3^scale-1-3^(scale-1)).." "..(y+3^scale-1-3^(scale-1)).." "..(z+3^scale-1).." minecraft:air")
    queueTask("fill "..(x + 3^(scale-1)).." "..y.." "..(z + 3^(scale-1)).." "..(x + 3^scale-1-3^(scale-1)).." "..(y+3^scale-1).." "..(z+3^scale-1-3^(scale-1)).." minecraft:air")
    queueTask("fill "..x.." "..(y + 3^(scale-1)).." "..(z + 3^(scale-1)).." "..(x + 3^scale-1).." "..(y+3^scale-1-3^(scale-1)).." "..(z+3^scale-1-3^(scale-1)).." minecraft:air")

    for i = 0, 2 do
      for j = 0, 2 do
        for k = 0, 2 do
          if ( i ~= 1 and j ~= 1 ) or ( j ~= 1 and k ~= 1 ) or ( i ~= 1 and k ~= 1 ) then
            mengerSponge(x + 3^(scale-1) * i, y + 3^(scale-1) * j, z + 3^(scale-1) * k, scale-1)
          end
        end
      end
    end
  end
end

parallel.waitForAny(pullTaskComplete, function() mengerSponge(x0, y0, z0, maxScale) end)

Spoiler

local maxScale=5
local maxTasks = 200
local runningTasks = 0
local taskList = {}
local commandString = ""

local x0, y0, z0 = commands.getBlockPosition()

y0 = y0 - 1
x0 = x0 + 5
z0 = z0 + 5

local function snooze()
-- A faster way to yield than os.sleep(0)
--
-- From http://www.computercraft.info/forums2/index.php?/topic/25670-bbs-guide-to-coroutines/
-- Modified to include a pseudo-random suffix on a human-readable prefix
--
  local myEvent = "MT_snooze_" .. string.sub(tostring({}),-6)
  os.queueEvent(myEvent)
  os.pullEvent(myEvent)
end

local function queueTask(thisCommand)
  local newTaskID = 0

  while runningTasks >= maxTasks do snooze() end

  newTaskID = commands.execAsync(thisCommand)

  if newTaskID then
    print("Queued taskID: "..newTaskID)
    taskList[newTaskID] = {}
    runningTasks = runningTasks + 1
  end
end

local function pullTaskComplete()
  local event=""
  local taskID=0
  local success=false
  local errorString=""

  while true do
    event, taskID, success, errorString = os.pullEvent("task_complete")
    print("task_complete: "..taskID)

    if taskList[taskID] then
      print("Completed taskID: "..taskID)

      taskList[taskID] = nil
      runningTasks = runningTasks - 1
    end
  end
end

function clear(x, y, z, scale)
  local i, j, k
  if scale>0 then

    queueTask("fill "..x.." "..y.." "..z.." "..(x+3^scale-1).." "..(y+3^scale-1).." "..(z+3^scale-1).." minecraft:air")

    for i = 0, 2 do
      for j = 0, 2 do
        for k = 0, 2 do
            clear(x + 3^(scale-1) * i, y + 3^(scale-1) * j, z + 3^(scale-1) * k, scale-1)
        end
      end
    end
  end
end

parallel.waitForAny(pullTaskComplete, function() clear(x0, y0, z0, maxScale) end)

Nothy #6
Posted 03 March 2016 - 08:08 AM
Mike, may I use this code to sit and be absolutely mesmerized in class all day? :D/>