# Finding surrounding tiles for all tiles

What can I do to improve performance of this function? So far I've changed stuff as local as possible and made a break if all possible surrounding tiles have been found. Also I use a separate variable to track the length of a list instead of len().

The usage of this is to find surrounding tiles for all tiles.

def getsurroundings(tiles):
for t in tiles:
currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
check = currentrect.colliderect
surroundings = t.surroundings
append = t.surroundings.append
surroundingscount = t.surroundingscount
for t2 in tiles:
if check(t2.rect) and not t == t2 and not t2 in surroundings:
append(t2)
t2.surroundings.append(t)
surroundingscount+=1
t2.surroundingscount+=1
if surroundingscount == 8:
break
return tiles


Here's the code without localisations which might be easier to read:

def getsurroundings(tiles):
for t in tiles:
currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
for t2 in tiles:
if currentrect.colliderect(t2.rect) and not t == t2 and not t2 in t.surroundings:
t.surroundings.append(t2)
t2.surroundings.append(t)
t.surroundingscount+=1
t2.surroundingscount+=1
if t.surroundingscount == 8:
break
return tiles


I don't know exactly what you are doing, but it seems like something similar to Minesweeper counts for bombs surrounding a tile.

I would to do this by iterating through the tiles once, and increment their neighbour's count by one if they have some feature you're interested in (like a bomb) to get the result. That way you only need k * 8 iterations (minus the ones over the edges) with k being the number of tiles having the feature you're interested in. For a board of 8x8 having 28 bombs that would be 224 iterations, instead of the 4096 when using a n^2 algorithm.

With Numpy this is relatively easy to do. And about ten times faster.

The problem here isn't in the details of the code, but in the algorithm. For every tile, you check all tiles, so for n tiles, your code has to perform n^2 checks, which is a lot. The only way to significantly reduce the running time of your code, is to make the search smarter. If you can make your use case a bit more visual, we might be able to come up with something.

def getsurroundings(tiles):
# skip the last rect in the outer loop, as it can't possibly have any subsequent neighbors
for index, t in enumerate(tiles[:-2]):
# if you've already found the maximum neighbors for t, skip the whole process
if len(t.surroundings) < 8:
currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
# only iterate over the part of the tile list that hasn't already been run through in the outer loop
for t2 in tiles[index + 1:]:
if currentrect.colliderect(t2.rect):
t.surroundings.append(t2)
t2.surroundings.append(t)
if len(t.surroundings) == 8:
break


I could be wrong, but I seem to recall that slicing does a shallow copy, so you could conceivably get even better performance if you swap the loops to iterating over indeces instead of slices.

Assuming this is PyGame, and assuming (since your code says you can't have more then 8 neighbors) that rects are non-overlapping and can only have one other rect per side (such as on a chess board), here's a bit better solution, I think:

Tile(Rect):

neighbors_map = ((('upper_center', 'mid_left'),
('mid_left', 'upper_center')),
(('upper_left', 'mid_right'),
('upper_right', 'mid_left'),
('mid_left', 'upper_right'),
('mid_right', 'upper_left')),
(('upper_center', 'mid_left'),
('mid_right', 'upper_center')),
(('upper_left', 'lower_center'),
('upper_center', 'lower_left'),
('lower_left', 'upper_center'),
('lower_center', 'upper_left')),
(('upper_center', 'lower_right'),
('upper_right', 'lower_center'),
('lower_center', 'upper_right'),
('lower_right', 'upper_center')),
(('mid_left', 'lower_center'),
('lower_center', 'mid_left')),
(('mid_left', 'lower_right'),
('mid_right', 'lower_left'),
('lower_left', 'mid_right'),
('lower_right', 'mid_left')),
(('mid_right', 'lower_center'),
('lower_center', 'mid_right')))

def __init__(self, *args, **kwargs):
self.clear_neighbors()
Rect.__init__(self, *args, **kwargs)

def clear_neighbors(self):
self.neighbors = [None] * 8

def __getattr__(self, name):
try:
index = self.resolve_name(name)
except ValueError:
raise AttributeError
return self.neighbors(index)

def __setattr__(self, name, value):
try:
super(Tile, self).__setattr__(name, value)
except AttributeError:
try:
index = self.resolve_name(name)
except ValueError:
raise AttributeError
if not self.neighbors[index]:
self.neighbors[index] = value
for neighbor_name, neighbor_neighbor_name in Tile.neighbors_map[index]:
neighbor = getattr(self, neighbor_name)
if neighbor:
setattr(neighbor, neighbor_neighbor_name, value)

def resolve_name(self, name):
parts = name.split('_')
if parts[0] == 'upper':
index = 0
elif parts[0] == 'mid':
if parts[1] == 'left':
return 3
elif parts[1] == 'right':
return 4
else:
raise ValueError
elif parts[0] == 'lower':
index = 5
else:
raise ValueError
if parts[1] == 'left':
return index
elif parts[1] == 'center':
return index + 1
elif parts[1] == 'right':
return index + 2
else:
raise ValueError


Then:

def populate_neighbors(tile_list):
tile_list_copy = copy.copy(tile_list)
while tile_list_copy:
current_tile = tile_list_copy.pop(0)
if all current_tile.neighbors:
continue
full_tile_indeces = []
for index, search_tile in enumerate(tile_list_copy):
if all search_tile.neighbors:
full_tile_indeces.append(index)
else:
if current_tile.right == search_tile.left + 1:
if current_tile.bottom == search_tile.top + 1:
current_tile.lower_right = search_tile
elif current_tile.top == search_tile.bottom - 1:
current_tile.upper_right = search_tile
elif (current_tile.top == search_tile.top
and current_tile.bottom == search_tile.bottom):
current_tile.mid_right = search_tile
elif current_tile.left == search_tile.right - 1:
if current_tile.bottom == search_tile.top + 1:
current_tile.lower_left = search_tile
elif current_tile.top == search_tile.bottom - 1:
current_tile.upper_left = search_tile
elif (current_tile.top == search_tile.top
and current_tile.bottom == search_tile.bottom):
current_tile.mid_left = search_tile
elif (current_tile.left == search_tile.left
and current_tile.right == search_tile.right):
if current_tile.bottom == search_tile.top + 1:
current_tile.lower_center = search_tile
elif current_tile.top == search_tile.bottom - 1:
current_tile.upper_center = search_tile
for index in reversed(full_tile_indeces):
tile_list_copy.pop(index)


It would probably be a good idea to break the neighbor setting logic out of the Tile class, but that can be something to figure out. :)

• Why not use itertools.combinations(tiles,2)? [If you're sticking with brute force pairwise comparisons, I mean.] – DSM Oct 25 '12 at 18:27
• @DSM because I didn't think of it. :) – Silas Ray Oct 25 '12 at 18:28
• The downside is that you couldn't short-circuit the same way at 8, I guess. You could islice to avoid making the slice copy, though. – DSM Oct 25 '12 at 18:29

I added a second list, so you only iterate over combinations you didn't already check.

By the way, you should code with spaces, not with tabs.

def getsurroundings(tiles):
tiles2 = tiles[:]
for t in tiles:
currentrect = Rect(t.rect[0] - t.rect[2] / 2, t.rect[1] - t.rect[3] / 2, t.rect[2] * 2, t.rect[3] * 2)
check = currentrect.colliderect
surroundings = t.surroundings
append = t.surroundings.append
surroundingscount = t.surroundingscount
tiles2.pop(0)
for t2 in tiles2:
if check(t2.rect) and not t == t2 and not t2 in surroundings:
append(t2)
t2.surroundings.append(t)
surroundingscount+=1
t2.surroundingscount+=1
if surroundingscount == 8:
break
return tiles

• But I like tabs D: – Syklis Oct 26 '12 at 8:08