2d arrays of arbitrary size

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
SirDust
Prole
Posts: 15
Joined: Sat Feb 11, 2017 12:53 am

2d arrays of arbitrary size

Post by SirDust » Thu Dec 28, 2017 2:02 am

I am curious what the best way is in lua to represent a 2d array, or for that matter, any multi-dimensional array with an arbitrary size in lua? I need it to allow arbitrary reads and writes at any integer coordinate index (something like this: array[coordinate.x][coordinate.y]).

I've considered either casting the coordinates to strings and using that as the index or using metatables to do this, but I'm not sure which method is better/more efficient, and I was wondering if there is perhaps a better way of doing this?

Since the size of the array will be arbitrary, subject to change during run-time, I can't just pre-initialize an array of arrays to solve this.

User avatar
zorg
Party member
Posts: 2700
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: 2d arrays of arbitrary size

Post by zorg » Thu Dec 28, 2017 2:37 am

I'm not sure what you mean by pre-initialize, since lua tables don't need to be initialized (well, with the exception of you needing to define even an empty table for a nested table), but you can also add new indices during runtime to the necessary spots; you needn't iterate over all subtables and insert placeholders...

Some subtle things may arise though depending on your code; if you'll have sparse tables, then # and ipairs may not work correctly.
This works perfectly as you have written it: array[coordinate.x][coordinate.y]

There are many ways to do such things, and i can't really say which is the best way.
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.

Ostego160
Prole
Posts: 14
Joined: Tue Oct 17, 2017 7:18 pm

Re: 2d arrays of arbitrary size

Post by Ostego160 » Thu Dec 28, 2017 6:02 am

Hi! This is how I do it, but I don't know if it's the best way or does what your asking.

This would be if your are wanting something of a grid:

Code: Select all

grid = {}

gridWidth = 32
gridHeight = 32
worldWidth = 64
worldHeight = 64

for col=1, worldWidth do
  grid[col] = {} 
  for row=1, worldHeight do 
    grid[col][row] = {x=(col-1)*gridWidth, y=(row-1)*gridHeight}
  end 
end
This does limit the array to the world size so without any additional code, if an object were to go off grid, there would be no corresponding grid[col][row] and you would get an index error. So in this way, I try to limit my objects to the grid using some method.

Depending on what you want to do, a spacial hash/partition might be useful. I hope this helps in some way (and makes sense... keyboard slapping all day...)! :awesome:

User avatar
ivan
Party member
Posts: 1511
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: 2d arrays of arbitrary size

Post by ivan » Thu Dec 28, 2017 7:14 am

Ostego's method is fine, but it may be impractical for very wide tables. Each column is a new table which is wasteful in terms of memory.

If you know the size of the arrays ahead of time, you could store your data in a 1d table. All you have to do is convert the 2d index to a 1d index which is fairly simple.

prixt
Prole
Posts: 26
Joined: Sat Sep 12, 2015 5:53 am

Re: 2d arrays of arbitrary size

Post by prixt » Thu Dec 28, 2017 8:26 am

Code: Select all

local row_mt = {
	__index = function(self,k)
		local cell = {}
		self[k] = cell
		cell[self] = true
		return cell
	end,
	__mode = "v"
}
local matrix_mt = {
	__index = function(self,k)
		local row = setmetatable({},row_mt)
		self[k] = row
		row[self] = true
		return row
	end,
	__mode = "v"
}
matrix = setmetatable({},matrix_mt)

function insertEntity(entity,x,y)
	local cell = matrix[y][x]
	cell[entity] = true
	entity[cell] = true
end
Pros:
*No need to define grid/matrix size.
*Memory efficient, as matrix only grows when more cells are needed.

Cons:
*Difficult to manage, probably need additional wrapper functions to use.
*Relies on garbage collection, so can cause memory leak if you forget to remove a reference.

User avatar
SirRanjid
Prole
Posts: 34
Joined: Sun Nov 19, 2017 1:44 pm
Contact:

Re: 2d arrays of arbitrary size

Post by SirRanjid » Thu Dec 28, 2017 11:44 am

A bit more optimized would be having a table like you mentioned that stores chunks of predefined sized 2d tables which use ivans method.

Code: Select all

bigtable = {
 [x64] = {
  [y64]= {["x64y64"] = {[x+y*64] = {<TILE>}}}
 }
}
Just load/generate chunks from that bigtable as you need them for rendering. This makes it memory efficient if you plan on making something infinite procedually generated.

Traversing is also not that difficult:

Code: Select all

fuction chunk_at_pos(x,y)
 local ret_x  = math.floor((x+32)/64) --32 is the tilesize of 64/2
 local ret_y  = math.floor((y+32)/64)
 return bigtable[ret_x][ret_y]
end --returns a table with the 64x64 grid

fuction tile_at_pos(x,y) --if you wanna get a single tile
 local chunk  = bigchunk_at_pos(x,y)
 return chunk[(x-1)%64+1][(y-1)%64+1] --notsure here
end

(not tested but *should* work)

User avatar
Ensayia
Party member
Posts: 397
Joined: Sat Jun 12, 2010 7:57 pm
Location: Middle of Nowhere, TN

Re: 2d arrays of arbitrary size

Post by Ensayia » Sat Dec 30, 2017 5:26 am

Practically everything is done via tables in Lua. A table is a list, a dictionary, an array, and even a namespace all wrapped into one.

That being said, you can easily create an integer indexed two-dimensional table as such:

Code: Select all

myArray = {}
myArray[1] = {}
myArray[1][1] = {}
For each dimension you will need to enure all but the very last dimension (in this case, just myArray[x]) is defined before adding elements:

Code: Select all

--valid
myArray = {}
myArray[1] = {}
myArray[1][1] = {}
myArray[1][2] = {} ... 	myArray[1][n] = {}

--invalid

myArray = {}
myArray[1] = {}
myArray[1][1] = {}
myArray[2][1] = {}  --this will error, as we have not defined myArray[2]
All tables in Lua are mutable (editable) at any time. There are no private or constant elements unless explicitly defined. The size of any table is arbitrary and can be expanded or reduced at any point. There is no need to initialize variables like in some C/C++ like languages, only define them.

When it comes to iterating over tables you can step through each dimension with a for loop, nested for loops, Lua's built in numeric index iterator (ipairs) or it's generic table iterattor (pairs). Take heed when interating over sparse numeric tables with ipairs, any missing numbers will cause ipairs to stop at the last number in a sequence, in addition to stopping at any non-numeric table index (key):

Code: Select all

myArray = {}
myArray[1], myArray[2], myArray[3], myArray[4] = {}

for k, v in ipairs(myArray) do
	print("Hello!")
end
-- Hello! will print four times.
myArray = {}
myArray[1], myArray[2], myArray[4] = {}

for k, v in ipairs(myArray) do
	print("Hello!")
end
-- Hello! will print twice, stopping after myArray[2].
I hope this information helps a little. You seem new to Lua and I thought an explanation of table properties might help you grasp your situation a bit better. Please feel free to reply with any questions.

Post Reply

Who is online

Users browsing this forum: No registered users and 8 guests