Octree - Efficient way of storing, and que...
mentlerd 22 Jan 2013
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:
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
Jharii 23 Jan 2013
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.
Thank you.
Mikeemoo 23 Jan 2013
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!
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!
NeverCast 23 Jan 2013
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.
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.
GopherAtl 23 Jan 2013
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!
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.
NeverCast 23 Jan 2013
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!
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!
BigSHinyToys 23 Jan 2013
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!
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!
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
Eric 23 Jan 2013
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!
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!
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}]
NeverCast 23 Jan 2013
I take it that it's not possible to have multiple values as an index?
grid[ x,y,z] ??
grid[ x,y,z] ??
grabie2 23 Jan 2013
it's impossible, but you can have table of tables of tables
For example:
BUT that's less memory efficient and less impressive that one posted by mentlerd
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
mentlerd 24 Jan 2013
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.
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.
KaoS 24 Jan 2013
grabie2, on 23 January 2013 - 12:27 PM, said:
it's impossible, but you can have table of tables of tables
For example:
BUT that's less memory efficient and less impressive that one posted by mentlerd
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
GopherAtl 26 Jan 2013
if you're using sparse arrays, you shouldn't be creating tables in get calls. Get should be something like this:
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.
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.
KaoS 26 Jan 2013
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