# How to detect whether or not a tile is occupied?

I'm using Python 2.7 on Win7x64 with PyGame

What is the best way to iterate over all the tiles in the game or screen, efficienty? Ideally I have about 800 tiles, but that is a dynamic number I've been playing around with.

The way I've got it is the logic is looking through all the tiles per frame (at 60fps, and I haven't yet got GFX and Logic decoupled):

for tile in TILES: #tiles is a simple list
if player_pos is in tile.coords: #coords is a list filled with (x, y) tuples
tile.color = RED #a simple attribute change, performance hit whether this line is 'pass' or not


but the list of TILES is huge enough that looking through 800 tiles, 60x a second obviously isn't efficient.

What is the best way to proceed from here? How do I find the occupied tiles, without iterating over them every frame? I could split the map up into quadrants or something similar, but maybe there's a fancy concept I'm not familiar with that would work better.

edit: Solved, for now: I added an attribute to the Tile class that has the lowest and highest two coordinates and then every frame, the logic looks to see of the player's pos is between the two ranges like so:

for tile in TILEs: #pos is player pos
if tile.range_x <= pos <= tile.range_x: #range_x is the lowest and highest
# x coordinate within the tile in pixels
if tile.range_y <= pos <= tile.range_y: #low and high y here
pos_tiles.append(tile)


edit2; I should mention that a tile holds several coordinates, meaning a unit (or player) can move within a tile.

• Do you mean 800 tiles total or an 800x800 map? Because looping through 800 tiles doesn't sound like much to me. May 8 '12 at 18:18
• @jhocking 825 tiles total, on a 800x600 pixel screen, with each tile being 25x25. I'm using Python, which is said to be slow, but who knows. I've changed the lines of code to: for tile in TILES: pass and the game still takes a 10FPS or so hit. edit: Also note that the coords attribute has 625 coords in it. May 8 '12 at 18:24

It would be faster to store all the tiles in a array and then simply check the tile at the players position. That would eliminate the loop (pseudo code):

TileDataClass[500,500] arr = mapdata
arr[playerposx,playerposy].color = red

• Is an array like that the best solution for doing all things tile related though? Thanks for the quick answer. I'm not that deep into gamedev yet, but I did use arrays for a roguelike I worked on a while back. It doesn't seem like it could be as dynamic as what I want to use it for. I'm probably wrong though. May 8 '12 at 18:51

If your tiles are rectangular, and if you make your tiles a 2D structure rather than a 1D structure then you can deduce the boundaries in world coordinates from the tile's position in 'tile coordinates', without needing to store any such values for each tile or iterate at all to find which tile is at a certain place.

Assuming tiles start at 0,0 in world space, the tile index for the world position (x,y) will be (x/tile width, y/tile height), rounding down.

Similarly, the world coordinate bounds of a tile at (p,q) are from (p*tile_width) to (p*tile_width+tile_width), and (q*tile_height) to (p*tile_width+tile_height), non-inclusive of the end-points.

• Alright, so then the 2D array is definitely the consensus. Thank you for the the clarification as well as the detailed answer! May 9 '12 at 0:48
• You could also cut out storing coordinates in the tiles and calculate them instead. I made a level editor that worked that way for levels. Instead of each tile having an X and Y coordinate value, it is simply calculated. This allows you to have levels bigger by a factor of your tile size. For example, the coordinate of tile would be 6400, 6400 with a 32x32 tile size. You can also store the player's position as a tile location + remainder instead of raw x,y coordinate. If the player's position were 5,6 R 16,0, the player would be located in/on tile 5,6 + 16 in the x. May 9 '12 at 2:49
• For the level editor I mentioned, I had two variables in my tile class. The first was an int that stored what it was graphically. It would take the int value and multiply it by tile width and height to get the tile's graphic in the sprite sheet. The second was a bool for if the tile was suppose to be shown or not. On rendering, I would just grab the tiles that were suppose to be in the screen plus one around the edges and render those. I would get the camera position, calculate where it is in tile coordinats, then go half the screen in each direction + 1 tile. Something else to consider May 9 '12 at 2:55