Need help implementing robust tile table

[Taehl]

I need a little help. In brief, I need a table that will contain up to about 2100 immobile tiles. This table needs to be in some format to facilitate the following:

- Object lookup by x and y coordinates (with little to no overhead)
- Ability to randomly select an object

Or, to be more specific, this table must firstly give me an efficient way to know if a tile is on the screen or not (so love.draw() can know whether or not to bother drawing it), secondly to tell me if a tile is at a given coordinate, and finally, offer a way to choose a tile at random.

So far I've been using tiles[x][y] = tile. This lets me easily know if a tile exists at a coordinate by saying "if tiles[x][y] then". I can also tell if a tile is on the screen or not in the draw function by doing "for x, row in pairs(tiles) do if x > camera.x and x < camera.x+screen.x then". However, what I CAN'T do this way is choose a tile at random.

So, does anyone have any ideas?

[bartbes]

Why can't you, just use math.random for both x and y.

[Taehl]

What if there's no tile there? My current method of picking a tile at random does just that - chooses random coordinates until it hits a tile. But if a level is 10000x10000, this method gets far too expensive.

[kikito]

Use two tables then. A 2-dimensional table for 2d access and a 1-dimensional one that stores the tiles sequentially.

Code: Select all

-- the tables are called tiles(2d) and existingTiles(1d)

-- a new tile is inserted
tiles[x][y] = tile
table.insert(existingTiles, tile)

-- get the x,y tile
return tiles[x][y]

-- get a random tile
return existingTiles[math.random(#existingTiles)]

[Taehl]

That's a good idea. I tried hacking something like that into my project and it worked quite well. I'll see if I can also use that for the more unusual features of my game.

However, wouldn't this use up a lot of memory?

[bartbes]

It would, yes. It'd have to store 1000000 references in the table.

[Robin]

Tiles are not duplicated though.

[bartbes]

Still, it needs to store references, at best these are pointers, which makes them at least 32-bits, 4 bytes per entry, equals 4000000 bytes, including some extra table data that is 4 MB. Not shocking, but not best coding practice either.

[Taehl]

Not quite. The area may be 10000x10000, but I'm not going to use more than about 2100 tiles or so (Love starts having issues at that point. Yes, the tile table consists of a lot of empty space). So that'd be more like 8kb?

[bartbes]

It still isn't ideal, but manageable.