How can I distribute obstacles to my grid without writing them manually?


User 11791503

I'm working on the A-star algorithm, and as my code below shows, the grid is written by hand, and I'm thinking of making a 100*100 size grid. So writing them manually would be pretty bad. I need to put the start point at (0,0) and the target point at (99,99).

I am trying to make a grid using this line below

grid1 = [[0 for i in range(100)]for j in range(100)]

But how can I assign obstacles to this grid randomly or not without touching the location of the start and target points?

This is below my code:

from __future__ import print_function
import random

grid = [[0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],#0 are free path whereas 1's are obstacles
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 1, 0],
        [0, 0, 0, 0, 1, 0]]

'''
heuristic = [[9, 8, 7, 6, 5, 4],
             [8, 7, 6, 5, 4, 3],
             [7, 6, 5, 4, 3, 2],
             [6, 5, 4, 3, 2, 1],
             [5, 4, 3, 2, 1, 0]]'''

init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1] #all coordinates are given in format [y,x] 
cost = 1

drone_h = 60

#the cost map which pushes the path closer to the goal
heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
for i in range(len(grid)):    
    for j in range(len(grid[0])):            
        heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])

        #if grid[i][j] == 1:
            #heuristic[i][j] = 99 #added extra penalty in the heuristic map
print(heuristic)
elevation = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
for i in range(len(grid)):    
    for j in range(len(grid[0])): 
        if grid[i][j] == 1:
            elevation[i][j] = random.randint(1,100)
        else:
            elevation[i][j] = 0



#the actions we can take
delta = [[-1, 0 ], # go up
         [ 0, -1], # go left
         [ 1, 0 ], # go down
         [ 0, 1 ]] # go right


#function to search the path
def search(grid,init,goal,cost,heuristic):

    closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]# the referrence grid
    closed[init[0]][init[1]] = 1
    action = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]#the action grid

    x = init[0]
    y = init[1]
    g = 0

    f = g + heuristic[init[0]][init[0]] + elevation[init[0]][init[0]]
    cell = [[f, g, x, y]]

    found = False  # flag that is set when search is complete
    resign = False # flag set if we can't find expand

    while not found and not resign:
        if len(cell) == 0:
            resign = True
            return "FAIL"
        else:
            cell.sort()#to choose the least costliest action so as to move closer to the goal
            cell.reverse()
            next = cell.pop()
            x = next[2]
            y = next[3]
            g = next[1]
            f = next[0]


            if x == goal[0] and y == goal[1]:
                found = True
            else:
                for i in range(len(delta)):#to try out different valid actions
                    x2 = x + delta[i][0]
                    y2 = y + delta[i][1]
                    if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]):
                        if closed[x2][y2] == 0 and grid[x2][y2] == 0 and elevation[x2][y2] < drone_h :
                            g2 = g + cost
                            f2 = g2 + heuristic[x2][y2] + elevation[x2][y2]
                            cell.append([f2, g2, x2, y2])
                            closed[x2][y2] = 1
                            action[x2][y2] = i
    invpath = []
    x = goal[0]
    y = goal[1]
    invpath.append([x, y])#we get the reverse path from here
    while x != init[0] or y != init[1]:
        x2 = x - delta[action[x][y]][0]
        y2 = y - delta[action[x][y]][1]
        x = x2
        y = y2
        invpath.append([x, y])

    path = []
    for i in range(len(invpath)):
        path.append(invpath[len(invpath) - 1 - i])
    print("ACTION MAP")
    for i in range(len(action)):
        print(action[i])

    return path

a = search(grid,init,goal,cost,heuristic)
for i in range(len(a)):
    print(a[i])
joffrey

You can randomize the grid and then make sure there are no obstacles at the start and end points. For adjacent fields, you can do the same for both fields.

import random
grid1 = [[random.randint(0,1) for i in range(100)]for j in range(100)]

# clear starting and end point of potential obstacles
grid1[0][0] = 0
grid1[99][99] = 0

Related


Can I distribute my app for any device without UDID?

Almas Adilbek I've been searching stackoverflow, reading various blogs for answers to the question: "Can I distribute my app to someone without getting their device UDID?" The answers I've found are all about" No! You must have a list of UDIDs", however, I was

Can I distribute my app for any device without UDID?

Almas Adilbek I've been searching stackoverflow, reading various blogs for answers to the question: "Can I distribute my app to someone without getting their device UDID?" The answers I've found are all about" No! You must have a list of UDIDs", however, I've

Can I distribute my app for any device without UDID?

Almas Adilbek I've been searching stackoverflow, reading various blogs for answers to the question: "Can I distribute my app to someone without getting their device UDID?" The answers I've found are all about" No! You must have a list of UDIDs", however, I've