Multidimensional table with negative keys

Yet another question from me to pros. But at least the questions are getting more and more complicated so I guess I'm getting somewhere :D/>/>.

I want to have a list over a four dimensional space (in this case X, Y, Z and Direction), including negative indexes/keys. That list is going to contain a normal table ({0,getHeuristic(position),nil,nil}). I can't use a normal table since it won't accept negative indexes. I can't use a table as a key because the keys are references, when I make a new table it won't be found as a key in the table. And for some reason I can't use "openNodes = {0={0={0={0={0,getHeuristic(position),nil,nil}}}}}".

Thank you for your time.

This should get you started:

map = {}

for x = -10, 10 do
map[x] = {}
for y = -10, 10 do
map[x][y] = "X - "..x.." Y - "..y
end
end

print (map[-5][5])

Aha… I think I understand…

Thanks man!

No… Wait a second.
I just tried:

openNodes = {}
openNodes[0] = {}
openNodes[0][0] = {}
(and so on)

But "# openNodes" is still 0. Can someone explain why it isn't 1?
'#' gives the size of a table, right?

You've only declared tables, but you haven't filled them with anything yet.
Fill them with some data and check again. :D/>/>

I've filled the table openNodes with another table right?

Maybe I should write out the "and so on" ^^

…
openNodes[0][0][0] = {}
openNodes[0][0][0][0] = {0,getHeuristic(position),nil,nil}

So isn't the table filled?

Are you by chance implementing A*? I just did that. I used string representations of positions to point to data about that position. But the nested table construction you have seems like it should be better.

Code-wise, I would advise something like:

openNodes = {}
openNodes[0] = {}
openNodes[0][0] = {}
openNodes[0][0][0] = {}
openNodes[0][0][0][0] =  {0,getHeuristic(position),nil,nil}

This isn't the prettiest way to write it, but I'm fairly sure it will work. You explicitly put in each new table on the way down. And there shouldn't be a problem with negative keys, any Lua object can be a key in a table.

Also, you might want to have a look at my mapPut function for inserting/updating data in a sparse structure like this:

-- Store a state in the map (EMPTY or BLOCKED)
function putMap(x, y, z, state)
-- Were we passed a vector?
if not z then
  state = y
  z = x[3]
  y = x[2]
  x = x[1]
end

-- Map is stored z-major since we will probably path-find in the plane
if  map[z] == nil then
  map[z] = {}
end
local plane = map[z]

if plane[y] == nil then
  plane[y] = {}
end
local col = plane[y]

col[x] = state
end

Yours would need another level for direction.

Yes Interfect, I'm trying out A* on a turtle.
Right now I guess I have to understand how to loop through this map, to find the next node.
How do I make a for-loop through all the nodes?

Binarin, on 28 February 2012 - 10:47 PM said:

Yes Interfect, I'm trying out A* on a turtle. Right now I guess I have to understand how to loop through this map, to find the next node. How do I make a for-loop through all the nodes?

The general way to loop through a multi-dimensional array would go like this:

local openNodes = { { { "Hello", "World" }, { "How", "are" } }, { { "you", "feeling" }, { "today", "?" } } }

for i = 1, #openNodes do    -- i elements in the first dimension
  for j = 1, #openNodes[i] do     -- j elements in every [i]
    for k = 1, #openNodes[i][j] do      -- k elements in every [i][j]
      print( "openNodes["..i.."] ["..j.."] ["..k.."] = "..openNodes[i][j][k] )
    end
  end
end

This would iterate through all three dimensions (i, j, k) of openNodes.
First through k, then through j, then through i. From the inside out, so to speak.

Let's say you have 2 elements in each dimension (like in the example), then it will iterate through them like this:

openNodes[1][1][1]
openNodes[1][1][2]

openNodes[1][2][1]
openNodes[1][2][2]

openNodes[2][1][1]
openNodes[2][1][2]

openNodes[2][2][1]
openNodes[2][2][1]

Espen, on 28 February 2012 - 11:18 PM said:

Binarin, on 28 February 2012 - 10:47 PM said:

Yes Interfect, I'm trying out A* on a turtle. Right now I guess I have to understand how to loop through this map, to find the next node. How do I make a for-loop through all the nodes?

The general way to loop through a multi-dimensional array would go like this:

local openNodes = { { { "Hello", "World" }, { "How", "are" } }, { { "you", "feeling" }, { "today", "?" } } }

for i = 1, #openNodes do	-- i elements in the first dimension
  for j = 1, #openNodes[i] do	 -- j elements in every [i]
	for k = 1, #openNodes[i][j] do	  -- k elements in every [i][j]
	  print( "openNodes["..i.."] ["..j.."] ["..k.."] = "..openNodes[i][j][k] )
	end
  end
end

This would iterate through all three dimensions (i, j, k) of openNodes.
First through k, then through j, then through i. From the inside out, so to speak.

Let's say you have 2 elements in each dimension (like in the example), then it will iterate through them like this:

openNodes[1][1][1]
openNodes[1][1][2]

openNodes[1][2][1]
openNodes[1][2][2]

openNodes[2][1][1]
openNodes[2][1][2]

openNodes[2][2][1]
openNodes[2][2][1]

Hmm, ok.
But that goes from 1 and upwards, it won't work on my map since it has negative keys and there will be holes in the map.
And also # openNodes still does not seem to be working like I want to, it seems to only count the positive keys.

Binarin, on 28 February 2012 - 11:33 PM said:

Espen, on 28 February 2012 - 11:18 PM said:

Binarin, on 28 February 2012 - 10:47 PM said:

Yes Interfect, I'm trying out A* on a turtle. Right now I guess I have to understand how to loop through this map, to find the next node. How do I make a for-loop through all the nodes?

The general way to loop through a multi-dimensional array would go like this:

local openNodes = { { { "Hello", "World" }, { "How", "are" } }, { { "you", "feeling" }, { "today", "?" } } }

for i = 1, #openNodes do	-- i elements in the first dimension
  for j = 1, #openNodes[i] do	 -- j elements in every [i]
	for k = 1, #openNodes[i][j] do	  -- k elements in every [i][j]
	  print( "openNodes["..i.."] ["..j.."] ["..k.."] = "..openNodes[i][j][k] )
	end
  end
end

This would iterate through all three dimensions (i, j, k) of openNodes.
First through k, then through j, then through i. From the inside out, so to speak.

Let's say you have 2 elements in each dimension (like in the example), then it will iterate through them like this:

openNodes[1][1][1]
openNodes[1][1][2]

openNodes[1][2][1]
openNodes[1][2][2]

openNodes[2][1][1]
openNodes[2][1][2]

openNodes[2][2][1]
openNodes[2][2][1]

Hmm, ok.
But that goes from 1 and upwards, it won't work on my map since it has negative keys and there will be holes in the map.
And also # openNodes still does not seem to be working like I want to, it seems to only count the positive keys.

#tbl will only count the positive keys; that's just how it works.
You could keep track of the number of positive/negative keys are in the table yourself, if you wanted to; but as far as I know, there isn't an easy way of doing this.

Hmm, I see what you mean. If you don't always know how many elements there will be or even at which index it will start and what the next index will be, etc. then you can use this:

local openNodes = { { { "Hello", "World" }, { "How", "are" } }, { { "you", "feeling" }, { "today", "?" } } }

for key, value in pairs( openNodes ) do
  for k2, v2 in pairs( openNodes[key] ) do
	for k3, v3 in pairs( openNodes[key][k2] ) do
	  print( "["..key.."] ["..k2.."] ["..k3.."] -> "..tostring(v3) )
	end
  end
end

This should print out all keys and their respective values, regardless of what key. It will just take the next and the next, etc.
But that method is very icky in combination with how you want to use the keys.

Edit: Fixed code.

Edit 2: Another example to illustrate the use of random indices (even negative ones) where this kind of iteration still works:

local openNodes = {}
openNodes[-5] = {}
openNodes[-8] = {}
openNodes[2] = {}
openNodes[-5][-3] = {}
openNodes[-8][2] = {}
openNodes[2][21] = {}
openNodes[-5][-3][4] = "Hello"
openNodes[-8][2][-24]= "World"
openNodes[2][21][-107] = "!"

for key, value in pairs( openNodes ) do
  for k2, v2 in pairs( openNodes[key] ) do
    for k3, v3 in pairs( openNodes[key][k2] ) do
      print( "["..key.."] ["..k2.."] ["..k3.."] -> "..tostring(v3) )
    end
  end
end

Espen, on 28 February 2012 - 11:43 PM said:

Hmm, I see what you mean. If you don't always know how many elements there will be or even at which index it will start and what the next index will be, etc. then you can use this:

local openNodes = { { { "Hello", "World" }, { "How", "are" } }, { { "you", "feeling" }, { "today", "?" } } }

for key, value in pairs( openNodes ) do
  for k2, v2 in pairs( openNodes[key] ) do
	for k3, v3 in pairs( openNodes[key][k2] ) do
	  print( "["..key.."] ["..k2.."] ["..k3.."] -> "..tostring(v3) )
	end
  end
end

This should print out all keys and their respective values, regardless of what key. It will just take the next and the next, etc.
But that method is very icky in combination with how you want to use the keys.

Edit: Fixed code.

Ah, that explained something, I was using ipairs instead of pairs.
I think I know everything I need for now, I'll adjust the code tomorrow. Thanks everyone ^_^/>/>

Binarin, on 28 February 2012 - 11:57 PM said:

Ah, that explained something, I was using ipairs instead of pairs. I think I know everything I need for now, I'll adjust the code tomorrow. Thanks everyone ^_^/>/>

Yeah, ipairs only iterates through number-indices and will stop at the first nil-entry, even if there are more elements after that.
This won't happen with pairs, which will go through all elements there are.
But be aware that the order of iteration might not be as predictable with the method above!
For example: The last code I illustrated above will output "World" "!" "Hello". Not what you'd expect given their coordinates.