Most efficient way to check cells and change neighbors matching a condition in a dataframe

Question

I'm using a pandas dataframe to store a dynamic 2D game map for a rougelike style game map editor. The player can draw and erase rooms. I need to draw walls around these changing rooms.

I have this:

0  1  2  3  4  5  6
0  .  .  .  x  .  .
1  .  .  x  x  .  .
2  .  x  x  x  .  .
3  .  .  .  .  .  .
4  .  .  .  .  .  . 

And need this:

0  1  2  3  4  5  6
0  .  #  #  x  #  .  
1  #  #  x  x  #  . 
2  #  x  x  x  #  . 
3  #  #  #  #  #  . 
4  .  .  .  .  .  . 

What is the most efficient way to do this?

So far I followed the approach outlined here, but this leaves me with some nested if and for before and after the lambda. As I have to check first if a cell is currently dug out. Then check all eight neighbors if they are dug out or not before changing the matching cells. This really takes a tool on the frame rate. I can't be the first to struggle with something like this, but got stuck at finding a solution.

I was hoping to find a way by applying mask or a similar binary comparison. Still, I have no idea how to efficiently do the neighbor checks without falling back into nested loops.

Answer 1

What you want to do is called a binary dilation. You can do this on the underlying numpy array with scipy.ndimage.morphology.binary_dilation:

from scipy.ndimage.morphology import binary_dilation
import numpy as np

a = df.eq('x').to_numpy()
# [[False False  True  True  True False]
#  [False  True  True  True  True False]
#  [ True  True  True  True  True False]
#  [False  True  True  True False False]
#  [False False False False False False]]

df = pd.DataFrame(np.where(binary_dilation(a), 'x', df))

output:

   0  1  2  3  4  5
0  .  .  x  x  x  .
1  .  x  x  x  x  .
2  x  x  x  x  x  .
3  .  x  x  x  .  .
4  .  .  .  .  .  .

Now to get a different symbol, you can use a more complex mask (binary_dilation(a)^a) with a XOR operation (^):

a = df.eq('x').to_numpy()
df = pd.DataFrame(np.where(binary_dilation(a)^a, '#', df))

output:

   0  1  2  3  4  5
0  .  .  #  x  #  .
1  .  #  x  x  #  .
2  #  x  x  x  #  .
3  .  #  #  #  .  .
4  .  .  .  .  .  .

all neighbors

Use a different structuring element (here a 3x3 matrix of 1s):

from scipy.ndimage.morphology import binary_dilation

a = df.eq('x').to_numpy()
kernel = np.ones((3,3))

df = pd.DataFrame(np.where(binary_dilation(a, kernel)^a, '#', df))

output:

   0  1  2  3  4  5
0  .  #  #  x  #  .
1  #  #  x  x  #  .
2  #  x  x  x  #  .
3  #  #  #  #  #  .
4  .  .  .  .  .  .

other kernels

You can easily adapt the code to have any combination of neighbors

example: top left

kernel = np.array([[1, 1, 0],
                   [1, 1, 0],
                   [0, 0, 0]])

   0  1  2  3  4  5
0  .  #  #  x  .  .
1  #  #  x  x  .  .
2  #  x  x  x  .  .
3  .  .  .  .  .  .
4  .  .  .  .  .  .