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.
CodePudding user response:
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.]]
CodePudding user response:
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()