4
\$\begingroup\$

Traverse through any binary array using the Manhattan distance by giving a start node location and an end node location. The neighbor() method gives the neighbors next to the x,y coordinates that are == to 0, the f_value() method assigns a value to the neighboring nodes based on a heuristic, and the path() method tells the algorithm which neighbor it should move to, based on the f_values.

Any ways I can make this algorithm more efficient, specifically with loops/modules?

Also, any tips on the pythonic nature of my code would be appreciated as well.

    '''
    @author: BenNicholl
    '''   
      #  please cite algorithm if used
      #  Algorithm changes the integer values of the grid array being used

    import numpy as np

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

    class AStar():

        def __init__(self, grid, x, y, goal_x, goal_y)    :
            self.grid = grid
            self.initial_x = x  #  never changes
            self.initial_y = y  #  never changes
            self.x = self.initial_x  #  does change
            self.y = self.initial_y  #  does change
            self.goal_x = goal_x  # never changes
            self.goal_y = goal_y  #  never changes
            self.neighbors = []
            self.neighbor()

        def neighbor(self):
            #  if x and y == goal_x and goal_y, algo is complete
            if self.x == self.goal_x and self.y == self.goal_y:
                print('your done')
                return 'your done'

            #  sets the x and y coordinates to 1 so they are not revisited
            self.grid[self.x][self.y] = 1 

            #  the below if statements give you the coordinates of 
            #  the neighbors that have a value of 0            
            if self.x > 0:  #  if X will be on the grid if it moves UP 1 node
                if self.grid[self.x-1] [self.y] == 0:
                    self.neighbors.append([self.x - 1, self.y])  

            if self.x < self.grid.shape[0] - 1:  #  if X will be on the grid if it moves DOWN 1 node
                if self.grid[self.x+1][self.y] == 0: 
                    self.neighbors.append([self.x+1,self.y]) 

            if self.y > 0: #  If Y will be on grid if it moves LEFT 1 node
                if self.grid[self.x][self.y - 1] == 0:
                    self.neighbors.append([self.x, self.y - 1]) #  

            if self.y < self.grid.shape[1] - 1: #  If Y will be on grid if it moves RIGHT 1 node
                if self.grid[self.x][self.y + 1] == 0:
                    self.neighbors.append([self.x, self.y + 1]) 

            self.f_value()

        #  this method gives you the f_value off all the neighbors    
        def f_value(self):
            h_values = []
            g_values = []  

            #  calculate distance from the neighboring X, Y to end X, Y value using Manhattan distance 
            for i in self.neighbors:     
                x_distance = abs(i[0] - self.goal_x)  
                y_distance = abs(i[1] - self.goal_y)  
                h_value = (x_distance + y_distance)
                h_values.append(h_value)

            #  calculate distance from the neighboring X, Y to the initial X, Y values   
            for i in self.neighbors:
                x_distance = abs(i[0] - self.initial_x)  
                y_distance = abs(i[1] - self.initial_y)
                g_value = (x_distance + y_distance)
                g_values.append(g_value)

            #  add g_value and h_value to calculate f_value
            self.f_values = [h + g for h, g in zip(h_values, g_values)]
            self.path()

        #  gets the lowest f_value, then pops that f_value and corresponding neighbor
        #  the neighbor always has the same index as the f_values
        def path(self):

            for coordinate, i in enumerate(self.f_values):
                if i <= min(self.f_values):
                    value = i
                    index = coordinate 

            self.x = self.neighbors[index][0]        
            self.y = self.neighbors[index][1]

            print('f_values:', self.f_values)
            print('neighbors:', self.neighbors)  
            print('x:', self.x)
            print('y:', self.y)

            self.neighbors.pop(index)
            self.f_values.pop(index)

            self.neighbor()   
\$\endgroup\$
2
\$\begingroup\$

For the pythonic ways, I'd recommend using """ for documenting functions and methods.

Instead of:

#  this method gives you the f_value off all the neighbors    
def f_value(self):
    ...

I'd go with

def f_value(self):
    '''
    This method gives you the f_value off all the neighbors. 
    '''
    ...

And I recommend you read this link on why docstring is different from block comments and how you can get the best of them.

This allow you to write things like:

def return_6(self):
    '''
    This method return 6. 
    >>>return_6()
    6
    '''
    return 6

Then run automatised test using your docstring or writing this:

def random_number_generator(arg1, arg2):
    """
    Summary line.

    Extended description of function.

    Parameters
    ----------
    arg1 : int
        Description of arg1
    arg2 : str
        Description of arg2

    Returns
    -------
    int
        Description of return value

    """
    return 42

And then use tools like Sphinx to build your documentation with ReadTheDoc for example.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.