How to detect whether or not a tile is occupied?

Question

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[0] <= pos[0] <= tile.range_x[1]: #range_x is the lowest and highest
                                       # x coordinate within the tile in pixels
        if tile.range_y[0] <= pos[1] <= tile.range_y[1]: #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.

Answer 1

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

Answer 2

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.