3
\$\begingroup\$

For school, I made a pathfinder for a weighted grid, but anything beyond a 7x7 grid takes a significant portion of time. I was wondering if I can improve my code at all, or if there is a way to reduce the time complexity.

I would appreciate any pointers for improving my code whether it's readability or efficiency.

import math
import random

class Grid:
    def __init__(self,width,height):
        self.board = []
        self.width = width;
        self.height = height; 
        for x in range(width*height):
            self.board.append([])
        for x in range(width):
            for y in range(height):
                rand = random.randint(0,3)
                self.board[x].append(rand)
    def display(self):
        for x in range(self.width):
            for y in range(self.height):
                print(str(self.board[x][y]) + " ",end="")
            print()

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def add(self,x,y):
        return Point(self.x+x,self.y+y)
    def sub(self,x,y):
        return Point(self.x-x,self.y-y)

class Node:
    def __init__(self,start,end):
        self.start = start
        self.end = end
        self.elements = [start]
    def size(self):
        return len(self.elements)
    def get(self,index):
        return self.elements[index]
    def append(self,element):
        self.elements.append(element)
    def calc(self,grid):
        cur_point = self.elements[self.size()-1]
        total = distance(cur_point,end)
        for x in range(self.size()):
            point = self.elements[x]
            total += grid.board[point.x][point.y]
        return total
    def clone(self):
        node = Node(self.start,self.end)
        node.elements = self.elements[:]
        return node
    def display_path(self,grid):
        for x in range(self.size()):
            point = self.elements[x]
            grid.board[point.x][point.y] = "P"
        grid.display()

class PriorityList:
    def __init__(self,node):
        self.elements = [node]
    def size(self):
        return len(self.elements)
    def get(self,index):
        return self.elements[index]
    def append(self,element):
        self.elements.append(element)
    def sort(self,grid):
        index = 1
        while index < self.size():
            node = self.elements[index]
            n = self.elements[index-1]
            if node.calc(grid) < n.calc(grid):
                self.elements[index] = n
                self.elements[index-1] = node
                index = 1
            index += 1

def distance(p1,p2):
    return math.sqrt( math.pow(p2.x-p1.x,2) + math.pow(p2.y-p1.y,2) )

def getPoint(x,y):
    x = int(input("Enter " + x + ": "))
    y = int(input("Enter " + y + ": "))
    return Point(x,y)

print("Customize grid...")
dimensions = getPoint("Width","Height")
print("Enter the starting point...")
start = getPoint("X","Y").sub(1,1)
print("Enter the ending point...")
end = getPoint("X","Y").sub(1,1)

grid = Grid(dimensions.x,dimensions.y)
grid.display()

print()

n = Node(start,end)

queue = PriorityList(n)

class Pathfinder(Exception): pass
try:
    while True:
        queue.sort(grid)
        node = queue.get(0)
        discovered = False
        for x in range(-1,2):
            for y in range(-1,2):
                point = node.get(node.size()-1)
                if point.x + x >= 0 and point.y + y >= 0 and point.x + x < grid.width and point.y + y < grid.height:
                    if x != 0 or y != 0:
                        discovered = True
                        new = node.clone()
                        new.append(point.add(x,y))
                        queue.append(new)
                        if point.x+x == end.x and point.y+y == end.y:
                            score = new.calc(grid)
                            new.display_path(grid)
                            print("Score: " + str(score))
                            raise Pathfinder
                        discovered = True
        if discovered:
            queue.elements.remove(queue.get(0))
except Pathfinder:
    pass          
\$\endgroup\$
2
\$\begingroup\$

The thing that sticks out the most is that your PriorityList, a priority queue, is a list instead of a heap.

You sort() the list every iteration, which (if implemented correctly) would be O(n log n), but in a proper priority queue adding/removing elements should be O(log n)

Your actual comparison-sort implementation is O(n), which is impossible, meaning it doesn't even work correctly as-is.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

I suggest to use numpy instead of Python lists. For example your Grid class

class YourGrid:
    def __init__(self,width,height):
        self.board = []
        self.width = width;
        self.height = height; 
        for x in range(width*height):
            self.board.append([])
        for x in range(width):
            for y in range(height):
                rand = random.randint(0,3)
                self.board[x].append(rand)
    def display(self):
        for x in range(self.width):
            for y in range(self.height):
                print(str(self.board[x][y]) + " ",end="")
            print()

can be reduced to just:

class NumpyGrid:
    def __init__(self, width, height): 
        self.width = width
        self.height = height
        self.board = np.random.randint(0, 4, size=(width, height))

    def display(self):
        print(self.board)

To compare it with bigger boardsize:

>>> %timeit YourGrid(100, 100)
17.6 ms ± 215 µs per loop
>>> %timeit NumpyGrid(100, 100)
73.7 µs ± 3.38 µs per loop

and this will of course scale up: the straight Python list implementation will become slower as you increase sizes. Avoid for loops, append methods as much as you can, these will make your code inefficient. There is a nice talk about this by Jake VanderPlas at PyCon. This is particularly true to your while True section: too much list manipulation there, which slows it down.

I think your Point class should implement more functionality. Make a distance method for example, it's not hard:

    def distance(self, other):
        if not isinstance(other, Point):
            raise TypeError("Point object is expected.")
        return math.sqrt(math.pow(other.x-self.x,2) + math.pow(other.y-self.y,2)) 

If you don't use any class functionality, why make it object oriented?

Also, calculating the distance between points is much-much faster with numpy.linalg.norm or scipy.spatial.distance.cdist, but that's probably an overkill.

This

def size(self):
        return len(self.elements)

should be

def __len__(self):
        return len(self.elements)

and it can be accessed via len(object).

def get(self, index):

should be

def __getitem__(self, indeces):

In the Point class you return new instances of itself. I don't think you should do that. Maybe you just want to modify the x and y inplace, so it can be

def add(self, x, y):
    self.x += x
    self.y += y

Note that there is also a built-in method called __add__.

Your whole main script should be in a __main__ guard:

if __name__=='__main__':
    print("Customize grid...")
    dimensions = getPoint("Width","Height")
...

You don't validate any user input.

You break out the main while loop with a custom exception. I think it can be just break, there is no point of the try-except. Or move the condition to while loop. A little sketch what I mean:

condition = False
while not condition:
    for x in range(1000):
        if x == 100:
            condition=True

According the style, you should follow PEP8.

I won't try to rewrite this, but probably there is a lot more to improve besides I posted above. Also you should add comments, it's hard to figure out what are you doing with each step.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you! This is very informative, but I do have a question. You said I could break, but I don't think you can break from the outer loop without a custom exception. Correct me if I'm wrong. \$\endgroup\$ – ZL11378 Jan 6 at 19:21
  • \$\begingroup\$ You should be able to break out. Also instead of while True might be worth to change it to something likewhile not condition. \$\endgroup\$ – Péter Leéh Jan 6 at 19:32
  • \$\begingroup\$ @ZL11378 You can break out of any loop, no exceptions required, if that's what you were asking. \$\endgroup\$ – AMC Jan 9 at 0:47

Your Answer

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