Tree data structure

[reno57]

Hello,

I'm trying to design a basic skeleton animation system as explained in the following tutorial: http://web.archive.org/web/201603221333 ... nes_System

The main idea behind this, is tree data structure. However, i found very few documentation about creating tree data structure with Lua. Everybody agrees that it's possible using metatables, but, i'm stuck in the function to create a bone structure using data from a file. My main issue is to code the creation of the tree and to be able to navigate through to make modification.

Is there any ressources to help me to manage this king of things ?

[s-ol]

There is no documentation because a tree is so trivial to build. You are overthinking this probably:

Code: Select all

local tree = {
  a = 3,
  b = 4,
  children = {
    { a = 2, b = 7 },
    { a = 5, b= 2, children = { { a=2, b=3 } } }
  }
}

And traversal is also dead simple by recursing:

Code: Select all

function traverse(tree)
  -- do sth with each node here

  for _, node in ipars(node.children) do
    traverse(node)
  end
end

[airstruck]

Plain tables should work pretty well.

Code: Select all

local bones = {
        name = 'root',
        x1 = 0, x2 = 0, y1 = 0, y2 = 0,
        {
            name = 'head',
            x1 = 0, x2 = 0, y1 = 2, y2 = 30,
        },
        {
            name = 'back',
            x1 = 0, x2 = 0, y1 = -2, y2 = 50,
            {
                name = 'left upper leg',
                x1 = 0, x2 = 0,  y1 = -1, y2 = 50,
                {
                    name = 'left lower leg',
                    x1 = 0, x2 = 0, y1 = 1, y2 = 50,
                },
            },
            {
                name = 'right upper leg',
                x1 = 0, x2 = 0, y1 = 1, y2 = 50,
                {
                    name = 'right lower leg',
                    x1 = 0, x2 = 0, y1 = -1, y2 = 50,
                },
            },
        },
        -- ...
    }

s-ol beat me to it :p

[Sir_Silver]

And traversal is also dead simple by recursing:

Code: Select all

function traverse(tree)
  -- do sth with each node here

  for _, node in ipars(node.children) do
    traverse(tree)
  end
end

Do you mean to pass the tree again to the traverse function, or perhaps you meant to pass the node instead? I think this example would result in an infinite loop.

[s-ol]

And traversal is also dead simple by recursing:

Code: Select all

function traverse(tree)
  -- do sth with each node here

  for _, node in ipars(node.children) do
    traverse(tree)
  end
end

Do you mean to pass the tree again to the traverse function, or perhaps you meant to pass the node instead? I think this example would result in an infinite loop.

whoops, basically typod on the phone. it should say node ofc.

[reno57]

Thanks for your answers.
the tree data structure using sub table is now clear for me and the way to got through it also. However, my difficulty is to create the tree from a descriptive text file of each node, ex :
/rank / x pos / y pos / angle / length / name
1 0.0000 0.0000 0.0000 0.0000 Root
2 0.0000 0.0000 1.5708 30.0000 Head
2 0.0000 0.0000 -1.5708 50.0000 Back
3 0.0000 0.0000 -0.7854 50.0000 LLeg
2 0.0000 0.0000 -0.1000 40.0000 LArm

To do so you have to go upwards and downwards in your tree structure,according the child node you have to add. And this is the kind of function, the i can't find out.

[airstruck]

create the tree from a descriptive text file of each node

Are you using a tool that outputs text files like that? If you're writing it by hand or generating it yourself, you might as well store it as Lua code and skip that extra step.

[pgimeno]

Thanks for your answers.
the tree data structure using sub table is now clear for me and the way to got through it also. However, my difficulty is to create the tree from a descriptive text file of each node, ex :
/rank / x pos / y pos / angle / length / name
1 0.0000 0.0000 0.0000 0.0000 Root
2 0.0000 0.0000 1.5708 30.0000 Head
2 0.0000 0.0000 -1.5708 50.0000 Back
3 0.0000 0.0000 -0.7854 50.0000 LLeg
2 0.0000 0.0000 -0.1000 40.0000 LArm

So the only info about the tree is "rank" and the ordering, right? Well, something like this should work.

Code: Select all

function parse_file(f)
  local backpath = {[0] = {}}
  for line in f:lines() do
    if not line:find("^%s*/") then
      local rank, xpos, ypos, angle, length, name = line:match("(%S+)%s+(%S+)%s+(%S+)%s+(%S+)%s+(%S+)%s+(%S+)")
      rank, xpos, ypos, angle, length = tonumber(rank), tonumber(xpos), tonumber(ypos), tonumber(angle), tonumber(length)
      backpath[rank] = {xpos=xpos, ypos=ypos, angle=angle, length=length, name=name}
      local lastNode = backpath[rank - 1]
      if not lastNode.children then lastNode.children = {} end
      lastNode.children[#lastNode.children + 1] = backpath[rank]
    end
  end
  return backpath[0].children
end

It returns a sequence of root nodes. If you're sure there's exactly one, then you can return backpath[0].children[1] instead.

Edit: Or based on airstruck's suggestion, to avoid having an extra table just for the children, you can use the sequence part of the table for the children, which also saves some code:

Code: Select all

function parse_file(f)
  local backpath = {[0] = {}}
  for line in f:lines() do
    if not line:find("^%s*/") then
      local rank, xpos, ypos, angle, length, name = line:match("(%S+)%s+(%S+)%s+(%S+)%s+(%S+)%s+(%S+)%s+(%S+)")
      rank, xpos, ypos, angle, length = tonumber(rank), tonumber(xpos), tonumber(ypos), tonumber(angle), tonumber(length)
      backpath[rank] = {xpos=xpos, ypos=ypos, angle=angle, length=length, name=name}
      local lastNode = backpath[rank - 1]
      lastNode[#lastNode + 1] = backpath[rank]
    end
  end
  return backpath[0]
end

Again, return backpath[0][1] instead if you are sure you only have one root per node.

[reno57]

Thank you very much, i will try you suggestion.

[reno57]

Hi, thank you, you inspired me to find a new way to solve the problem. I put the way to do it below to close the subject (may it's not the perfect way, but it's a way i master).
So first, i complete de description txt file with a new info which is the id of the node and the id of its parent :
Example
node id/ parent id / node name / xpos / ypos / angle / length
1 1 Head 100 100 1.6 20
2 1 Back 0 0 0 50
3 2 Lleg 0 0 0.5 30
4 3 Lleg2 0 0 0 40
5 2 Rleg 0 0 -0.5 30 5
6 5 Rleg2 0 0 0 40
7 1 Larm 0 0 1.6 50
8 1 Rarm 0 0 -1.6 50

Then i have a peace of code that creates each node (i call it also bone) and then a peace of code to connect each child to its parent node.

Code: Select all

function loadSkeleton(file)	-- file is a string of character corresponding to the file in the projet directory
  		local bones = {}
  		local i = 1
  		-- Create each bone of the skeleton
  		for line in love.filesystem.lines(file) do
    		if not line:find("^%s*/") then
      			local id, parent, name, x, y, a, l = line:match("(%S+)%s+(%S+)%s+(%S+)%s+(%S+)%s+(%S+)%s+(%S+)%s+(%S+)")
      			id, parent, x, y, a, l = tonumber(id), tonumber(parent), tonumber(x), tonumber(y), tonumber(a), tonumber(l)
      	
      			bones[i] = Bone(id, parent, name, x, y, a, l)
      			i = i + 1
    		end
    	end
    	-- Link each child with its parent
    	for _,b in ipairs(bones) do
    		if b.id ~= 1 then
    			bones[b.parent]:addChild(b)
    		end
    	end
    	print("Skeleton from file "..file.." has been loaded")
  		return bones[1]
	end

See you for new adventures ...