LÖVE

davisdude wrote:Say for instance, you have non-tile-based-movement. How then would it be implemented? I guess you would check if the screen is covering the tile at all, then draw it, right? But then that would require you to loop through the tables, wouldn't it?

Correct. The trick of ignoring off-screen-tiles only works if the data-structure matches the spatial distribution of the tiles. In a 2d-array you can know the coordinates of a tile, without even accessing it. If you have the tiles in an arbitrary order in a list, then you have to loop through the whole list.

For non-tile-based objects there is a structure called quad-tree. This is a data structure that stores entities depending on their position in a 2d space.

You can still easily use the same technique with non-tile based movement, just make left and right one less than and one more than the actual screen size (top and bottom too of course). So you do have a bit more draw calls than absolutely necessary, but you don't have to loop the entire table.

davisdude wrote:Say for instance, you have non-tile-based-movement. How then would it be implemented? I guess you would check if the screen is covering the tile at all, then draw it, right? But then that would require you to loop through the tables, wouldn't it?

Not necessarily. This kind of problem has been studied already. The solution to the problem of "detecting quickly which shapes overlap with a given shape" is resolved with a family of data structures called Spatial Databases. Quadtrees are one kind of spatial databases, but they are not the only one. Grids serve this purpose too - they are also simpler to understand and implement than quadtrees, and offer similar speeds (I have implemented both).

When you use a grid for spatial hashing, you do the following:

• The grid is formed by rows (for example grid.rows). Each row has cells(i.e. grid.row[1].cells[2]). Each cell has a list of "items touching it"(grid.row[1].cells[2].touching[item]=true).
• When you insert a new "shape" in the system, you iterate over all the cells that "touch" it, and put add the item to the "list of items touching that cell" (row[y].cell[x].touching[item] = true). I quote "touch" because you don't really need to insert exactly those cells and those cells only. In most cases it's ok to use the bunding rectangle around the shape to mark the cells. You will mark more cells than the item really touches, but that's ok. Using a rectangle, you can use the trick I showed before with the loops and the left,right,top,bottom.
• When you remove a shape from the system (for example, a killed enemy) then you just remove it from all the cells that were touching it (again, you don't have to iterate over all the cells, just the ones the were touching it when it disappeared).
• When you move a shape around, you first remove it, and then you add it again.
• When you need to draw the screen, you do the same thing you did before with the tile-based approach: you parse all the cells, and "draw" the items in them (you will probably want to have some sort of dictionary so that you don't draw the same objects more than once).

This approach also works great for doing collision testing - instead of testing "every object with every object", the spatial hash allows you to test every item with "just the objects on the same cells as the item". If you think about it, in the particular case of a camera, what you are really doing is testing that the "rectangle of the screen" collides with some of your items, and then doing an action according to that (in this case, draw the items colliding). This is the approach I use in bump. I believe that HardonCollider uses a similar approach.

I'm going to throw in a shameless plug here and say that my library, STI, already does everything discussed in this thread. If you create your map with the super useful Tiled Map Editor, than you can simply plug your map into STI and everything will be taken care of for you.

I have a tangentially related problem, but not exactly the same.
I've tried this and I can draw the grid/table just fine, my next challenge is to have a mouse-click pick that tile within the grid.
A friend and I have tried several things trying to determine if a mouse's X/Y is within the area of the tile.

So like, we have tiles, X/Y are 48px each, with X/Y padding of 4px each.
We're able to draw the grid so it looks like this (where each letter is a specific graphic):

E A C D D C D A
A E D C C A E E
D C H H A E D C
E A C D D C D A
A E D C C A E E
D C H H A E D C
A E D C C A E E
D E A C C E A A

But the snag is being able to set a variable to which tile is being picked.
Any ideas?

One simple method would be on mouse click, calculate which square you're in by using modulo or math.floor and division