Octree - Efficient way of storing, and querying 3D data

Hello everyone!

This is my first time posting there, so I will make this post short.

I made an automatically mining turtle yesterday, and found that I need a way to store visited blocks, without knowing the size of the area I excavate. A well known solution popped into my mind: an octree

I would not like to expain its inner workings, but in sort, it is a three dimensional (in this case infinite) "array", where you can store values, in any shape, efficently.
In my implementation, I added a few tweaks, such as the octree can grow as big as you want it, without any side effects.

Basically, this data structure allows you to store data in an "infinite" three dimensional "array", without having to worry about resizing, or reallocating lua tables.

For further information about the data structure, take a look at the wiki page of octrees.

You can access the code here: https://gist.github.com/4587030

Almost forgot, the api:

tree = octree.new()
tree:get( x, y, z ) - Returns the previously set value, or nil
tree:set( x, y, z, value ) - Self explanatory

Looks good! An impressive first post, certainly.

very nice!!! … I can cross that off my list of TODO's

Very very nice indeed! Well done.

As a complete amateur programmer, and even newer in the realm of LUA and CC, this is extremely helpful. Not only for the access to a vector, but it is an excellent example of how to set up a LUA "class"/"object".

Thank you.

Great that you've made a lua octree!

However, struggling to work out what advantages this would give. I've really only ever used/written quadtrees and octrees in collision detection and/or rendering. With turtles you're mostly going to be querying for specific locations, which is a simple 3d array and wouldn't need something like this..

However, I'm sure I'm maybe just misunderstanding something!

noob question but where does the "self" variable come from ?

BigShinyToys,

Enjoy http://www.lua.org/pil/16.html


Short Answer: Self is added by using a colon : instead of a period .and refers to the table the function was executed on.

Mikeemoo, on 23 January 2013 - 05:41 AM said:

Great that you've made a lua octree!

However, struggling to work out what advantages this would give. I've really only ever used/written quadtrees and octrees in collision detection and/or rendering. With turtles you're mostly going to be querying for specific locations, which is a simple 3d array and wouldn't need something like this..

However, I'm sure I'm maybe just misunderstanding something!

I was thinking the same thing. I suppose there's still memory space advantages, but unless you're talking about a very huge area, they're minimal, and lua tables can be used as sparse arrays (can have index 1 and 5 without 2-4) which would cancel out much of the size advantage as well.

Impressive technically, but the advantageous use cases escape me.

If this were me I would've just created a function that returns a unique key for x,y,z, and then dropped values in to the table with those keys.
It would automatically return nil if it didn't exist.

That said, the code is impressive.. and maybe one day it'll have a cause!

NeverCast, on 23 January 2013 - 08:46 AM said:

If this were me I would've just created a function that returns a unique key for x,y,z, and then dropped values in to the table with those keys.
It would automatically return nil if it didn't exist.

That said, the code is impressive.. and maybe one day it'll have a cause!

something like this ??

local tTable = {}
local function get(x,y,z)
    return tTable[table.concat({x,y,z},"-")]
end
local function set(x,y,z,val)
	 tTable[table.concat({x,y,z},"-")] = val
end

BigSHinyToys, on 23 January 2013 - 09:08 AM said:

NeverCast, on 23 January 2013 - 08:46 AM said:

If this were me I would've just created a function that returns a unique key for x,y,z, and then dropped values in to the table with those keys.
It would automatically return nil if it didn't exist.

That said, the code is impressive.. and maybe one day it'll have a cause!

something like this ??

local tTable = {}
local function get(x,y,z)
	return tTable[table.concat({x,y,z},"-")]
end
local function set(x,y,z,val)
	 tTable[table.concat({x,y,z},"-")] = val
end

Or in a cooler way:

local grid_mt = {
  __index = function(self, t)
    return rawget(self, table.concat(t, "-"))
  end,
  __index = function(self, t, v)
    return rawset(self, table.concat(t, "-"), v)
  end
}

local grid1 = setmetatable({}, grid_mt)
local grid2 = setmetatable({}, grid_mt)

grid1[{1, 2, 3}] = 3
grid2[{4, 5, 6}] = grid1[{1, 2, 3}]

I take it that it's not possible to have multiple values as an index?

grid[ x,y,z] ??

it's impossible, but you can have table of tables of tables ;)/>
For example:

local data = {}
local function set(x, y, z, value)
  if not data[x] then data[x] = {} end
  if not data[x][y] then data[x][y] = {} end
  data[x][y][z] = value
end
local function get(x, y, z)
  if not data[x] then data[x] = {} end
  if not data[x][y] then data[x][y] = {} end
  return data[x][y][z]
end

BUT that's less memory efficient and less impressive that one posted by mentlerd ;)/>

Thank you for the compliments. You questioned my reasons for making this, so let me explain. (Initially I made this to learn, and get my lua knowledge back in shape.)

Well, it really turned out to be an overkill at the end, but I wanted to store a lot of data. I am currently using this ocrtee implementation in a turte, that digs for valuable ores in the ground, and in the modpack I am playing, there are huge areas filled with marble.

It is easy to dig, but very tiring, so I decided to make a turtle do all the job. As it digs blocks, the nodes of the octree collapse automatically (since I am storing the same values in them), so it saves me some trouble later on. (Detecting missed blobs is quite easy)

I also wanted to investigate, if isung an octree will speed up my turtles A* searches (programmer curiosity :)/>), altought I havent made an implementation based on my octrees yet; it now just relies on basic tables.

grabie2, on 23 January 2013 - 12:27 PM said:

it's impossible, but you can have table of tables of tables ;)/>
For example:

local data = {}
local function set(x, y, z, value)
  if not data[x] then data[x] = {} end
  if not data[x][y] then data[x][y] = {} end
  data[x][y][z] = value
end
local function get(x, y, z)
  if not data[x] then data[x] = {} end
  if not data[x][y] then data[x][y] = {} end
  return data[x][y][z]
end

BUT that's less memory efficient and less impressive that one posted by mentlerd ;)/>

I quite like that method if it is done using metatables it works well

local mt={}
mt.__index=function(self,index)
  rawset(self,index,setmetatable({},mt))
  return self[index]
end
local vector=setmetatable({},mt)

then you can just say vector[1][2][5]="x" and it will create the necessary tables

of course it is not wise to allow it to do this for limitless dimensions or when you try to get a value that is empty you will get an empty table so limit it to the dimensions you need

I still must say I am highly impressed at the skill shown by mentlerd. wish I was that good when I started

if you're using sparse arrays, you shouldn't be creating tables in get calls. Get should be something like this:

function get(x,y,z)
  if data[z] and data[z][y] then
    return data[z][y][x]
  else
    return nil
  end
end

So you create tables only as required to SET values. Otherwise you'd fairly quickly wind up with most of the full 3x3 table created even if they stored no data.

indeed but that wouldn't bother me much as I would only be requesting data within the co-ordinates of my operating range, having an empty table there is fine by me