Python numpy replacing values that are in certain pattern

user_2826801 0
Viewed 92

I am trying to 'avoid walls' using an A* star (A-Star) algorithm. My array look like this:

[1, 1, 1, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 0, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 1, 1]

I can only walk on 0 (zeroes) and 1 (ones) are the walls. I want my AI to walk on the center of the the path, assuming that there is enough room to walk. AI can walk diagonally.

for example instead of [1, 1, 1, 0, 0, 0, 1, 1, 1],(First array) since there is enough room not to block the path how can I replace it with [1, 1, 1, 1, 0, 1, 1, 1, 1],

Afterthought:

The optimal path here if we will walk on center is [4 3 2 2 3 4].

Also, what if we are given the shortest path possible for this case it would be [3 3 3 3 4 4] if we are going from (3, 0) to (4, 5). If we just don't want walls in our path like having a single element before the wall, how can we arrive to [3 3 2 2 3 4] if we allow start and finish to touch walls?

Edit: Ali_Sh answer is what I am initially looking for and is the accepted answer.

path-finding numpy python
3 Answers

Here's an example where it just finds all the values that are zero in each row and sets the path as the middle argument. If there was a row with two patches of zeros, this could run into trouble. In that case, you would need to make sure that the arguments above and below a zero patch are also zero patches.

I have used matplotlib here to visualize the path:

import matplotlib.pyplot as plt

p = []
A = [[1, 1, 1, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 0, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 1, 1]]

for i in range(len(A)):
    ptemp = []
    for j in range(len(A[0])):
        if A[i][j] == 0:
            ptemp.append(j) # find all the zero values
    p.append(ptemp[int(len(ptemp)/2)]) # set the path as the center zero value
    
print(p)
plt.imshow(A[::-1])
plt.plot(p[::-1],range(len(A)))
plt.show()
user_186417270

If a be the main array, indices of the middle 0 in each row can be achieved by:

cond = np.where(a == 0)
unique = np.unique(cond[0], return_index=True, return_counts=True)
ind = unique[1] + unique[2] // 2
cols = cond[1][ind]  # --> [4 3 2 2 3 4]

and it can be used to substitute 1 values in a ones array with the main array shape:

one = np.ones(shape=a.shape)
one[np.arange(len(one)), cols] = 0

which will:

[[1. 1. 1. 1. 0. 1. 1. 1. 1.]
 [1. 1. 1. 0. 1. 1. 1. 1. 1.]
 [1. 1. 0. 1. 1. 1. 1. 1. 1.]
 [1. 1. 0. 1. 1. 1. 1. 1. 1.]
 [1. 1. 1. 0. 1. 1. 1. 1. 1.]
 [1. 1. 1. 1. 0. 1. 1. 1. 1.]]
user_133948170

For the update section of the question, if we have another path for columns instead the optimal path that specified in my previous answer (e.g. [3 1 1 1 2 3] instead [4 3 2 2 3 4]), it can be applied just using:

cols = np.array([3, 1, 1, 1, 2, 3])
one = np.ones(shape=a.shape)
one[np.arange(len(one)), cols] = 0

# [[1. 1. 1. 0. 1. 1. 1. 1. 1.]
#  [1. 0. 1. 1. 1. 1. 1. 1. 1.]
#  [1. 0. 1. 1. 1. 1. 1. 1. 1.]
#  [1. 0. 1. 1. 1. 1. 1. 1. 1.]
#  [1. 1. 0. 1. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]]

If we want the all paths other than boundaries, we could add the following codes to the previous answer codes:

if we don't fully walk on the center but just avoid 'near walls' path just even 1 offset from the walls:

cols_min = cols - (unique[2] - 2) // 2
cols_max = cols + (unique[2] - 2) // 2
one[np.arange(len(one)), cols_min] = 0
one[np.arange(len(one)), cols_max] = 0

# [[1. 1. 1. 1. 0. 1. 1. 1. 1.]
#  [1. 1. 0. 0. 0. 1. 1. 1. 1.]
#  [1. 1. 0. 1. 1. 1. 1. 1. 1.]
#  [1. 1. 0. 1. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 1. 0. 1. 1. 1. 1.]]

For when we can touch the walls (here one of them) on the first and the last rows, we could add the following codes to the previous answer codes:

col_min_first = cols[0] - unique[2][0] // 2
col_min_last = cols[-1] - unique[2][-1] // 2
one[0, col_min_first:cols[0]] = 0
one[-1, col_min_last:cols[-1]] = 0

# [[1. 1. 1. 0. 0. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]
#  [1. 1. 0. 1. 1. 1. 1. 1. 1.]
#  [1. 1. 0. 1. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 0. 1. 1. 1. 1.]]

And, finally, if we want to find the shortest path, we can achieve the goal by finding the column with maximum number of 0 in it, firstly, and then, find the nearest column index 0 to that column for where the column not contains 0:

ind_max = np.argmax(np.sum(a == 0, axis=0))
mask_rows = a[:, ind_max] != 0
mask_col_min = a[:, ind_max - 1] == 0
mask_col_max = a[:, ind_max + 1] == 0
ind_max = np.where(mask_rows & mask_col_min, ind_max - 1, ind_max)
ind_max = np.where(mask_rows & mask_col_max, ind_max + 1, ind_max)
one = np.ones(shape=a.shape)
one[np.arange(len(one)), ind_max] = 0

# [[1. 1. 1. 0. 1. 1. 1. 1. 1.]   | a = np.array([[1, 1, 1, 0, 0, 0, 1, 1, 1],        [[1. 1. 1. 0. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]   |               [1, 0, 0, 0, 0, 0, 1, 1, 1],         [1. 1. 1. 0. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]   |               [0, 0, 0, 1, 1, 1, 1, 1, 1],   -->   [1. 1. 0. 1. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]   |               [1, 0, 0, 0, 1, 1, 1, 1, 1],         [1. 1. 1. 0. 1. 1. 1. 1. 1.] 
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]   |               [1, 1, 0, 0, 0, 1, 1, 1, 1],         [1. 1. 1. 0. 1. 1. 1. 1. 1.]
#  [1. 1. 1. 0. 1. 1. 1. 1. 1.]]  |               [1, 1, 1, 0, 0, 0, 1, 1, 1]])        [1. 1. 1. 0. 1. 1. 1. 1. 1.]]
user_133948170
Related