Yam Code

New Paste Browse

from PIL import Image
import numpy as np
from numpy import asarray
import math

class Point:
    def __init__(self, x1: int, y1: int):
        self.x = x1
        self.y = y1

def __eq__(self, o):
        return self.x == o.x and self.y == o.y

def __ne__(self, o):
        return self.x != o.x or self.y != o.y

def is_neg(self):
        return self.x >= 0 and self.y >= 0

class Node:
    def __init__(self, pos: Point,
                 cost: float = 0,
                 path_length: float = 0):
        self.pos = pos
        self.cost = cost
        self.path_length = path_length

def __gt__(self, o):
        return self.cost > o.cost

def __lt__(self, o):
        return self.cost < o.cost

def __str__(self):
        return str(str(self.pos.x) + " " + str(self.pos.y))

def manhattan(n1: Point, n2: Point):
    dx = abs(n1.x - n2.x)
    dy = abs(n1.y - n2.y)
    return dx + dy

def diagonal(n1: Point, n2: Point):
    dx = abs(n1.x - n2.x)
    dy = abs(n1.y - n2.y)
    return (dx + dy) + (math.sqrt(2) - 2) * min(dx, dy)

def euclidean(n1: Point, n2: Point):
    dx = abs(n1.x - n2.x)
    dy = abs(n1.y - n2.y)
    return math.sqrt(dx * dx + dy * dy)

class PriorityQueue(object):
    def __init__(self):
        self.queue = []

# for checking if the queue is empty
    def is_empty(self):
        return len(self.queue) == 0

# for inserting an element in the queue
    def insert(self, data):
        for i in range (len(self.queue)):
            if data.pos == self.queue[i].pos and data.cost<self.queue[i].cost:
                self.queue.append(data)
                del self.queue[i]
                i-=1
        self.queue.append(data)

# for popping an element based on Priority
    def delete(self):
        try:
            min_index = 0
            for k in range(len(self.queue)):
                if self.queue[k] < self.queue[min_index]:
                    min_index = k
            item = self.queue[min_index]
            del self.queue[min_index]
            return item
        except IndexError:
            print()
            exit()

def delete_2(self, pos:Point):
        for i in range (len(self.queue)):
            if self.queue[i].pos == pos:
                del self.queue[i]
                break

def top_min(self):
        try:
            min_index = 0
            for k in range(len(self.queue)):
                if self.queue[k] < self.queue[min_index]:
                    min_index = k
            item = self.queue[min_index]
            return item
        except IndexError:
            print()
            exit()

def __getitem__(self, item):
        return self.queue[item]

def a_star_path(pix_array: np.array,
                start: Point,
                goal: Point,
                m: int):

h, w = len(pix_array), len(pix_array[0])
    start_node = Node(start)
    nodes_to_visit = PriorityQueue()
    nodes_to_visit.insert(start_node)
    # adj = np.full(8, -1, int)
    new_point = np.full(8,Point(0,0),Point)
    g_cost = np.full((h, w),float('inf'),float)
    path = np.full((h, w), Point(-1, -1), Point)
    explorer = np.full((h, w), False, bool)

while not nodes_to_visit.is_empty():

cur = nodes_to_visit.delete()

if cur.pos == goal:
            total_distance = cur.path_length
            break

x = cur.pos.x
        y = cur.pos.y

if not explorer[x][y]:
            explorer[x][y] = True
            nodes_to_visit.delete_2(cur.pos)
        else:
            continue

print(cur.cost)

new_point[0] = Point(x, y+1)
        new_point[1] = Point(x + 1, y + 1)
        new_point[2] = Point(x + 1, y)
        new_point[3] = Point(x + 1, y - 1)
        new_point[4] = Point(x, y - 1)
        new_point[5] = Point(x - 1, y - 1)
        new_point[6] = Point(x - 1, y)
        new_point[7] = Point(x - 1, y + 1)

for i in range(8):

x2 = new_point[i].x
            y2 = new_point[i].y
            delta_alpha = pix_array[x][y] - pix_array[x2][y2]
            if new_point[i].is_neg() and delta_alpha <= m and not explorer[x2][y2]:

sgn = delta_alpha > 0 and 1 or -1
                distance = math.sqrt((x2 - x)*(x2 - x) + (y2 - y)*(y2 - y)) + (1/2 * sgn + 1)*abs(delta_alpha)
                # print("distance ", distance)
                g_new = g_cost[x][y] + distance

# print("heuristic: ", heuristic)

if g_new < g_cost[x2][y2]:
                    heuristic = diagonal(new_point[i], goal)
                    g_cost[x2][y2] = g_new
                    path[x2][y2] = cur.pos
                    f_cost = g_new + heuristic
                    nodes_to_visit.insert(Node(new_point[i], f_cost , cur.path_length + distance))
                    print("new cost: ", g_cost[x2][y2])

path2D = []
    i = goal
    while i != start:
        path2D.append(i)
        i = path[i.x][i.y]

path2D.append(start)

total_distance = cur.path_length

return path2D, total_distance

im = Image.open("map.bmp")
pix = im.load()
row, column = im.size
pix_array = np.zeros((row, column))
a = asarray(im)  # convert pixel to array

for i in range(row):
    for j in range(column):
        pix_array[i][j] = a[i][j].item(0)  # only get 1 value because 3 value same as each other

start = Point(5, 5)
goal = Point(400, 310)
m = 2

# print(m)
path, total_distance = a_star_path(pix_array, start, goal, m)

print(path)
for i in range(len(path)):
    x = int(path[i].x)
    y = int(path[i].y)
    r, g, b, p = pix[x, y]
    pix[x, y] = 255, g, b, p

im.show()

Paste Settings

Paste Title : [Optional]

Paste Folder : [Optional]

Syntax Highlighting : [Optional]

Paste Expiration : [Optional]

Paste Status : [Optional]

Password : [Optional]

Description: [Optional]

Tags: [Optional]

Encrypt Paste (?)

You are currently not logged in, this means you can not edit or delete anything you paste. Sign Up or Login

Paste Settings

Site Languages