다익스트라 알고리즘#

win_width, win_height = 400, 400  # 가로 세로 400 400
rows, cols = 8, 17  # 세로 가로 / 행과 열
# 8*2 = 64 개의 grid
win = pygame.display.set_mode((win_width, win_height))  # (width, height)
pygame.display.set_caption("(그리드 & 다익스트라) 알고리즘")
grid_width, grid_height = win_width // cols, win_height // rows
#                         400 // 4,           400 // 4

target_flag = False  # 목표물이 설정되지 않은 상태
WHITE = (255, 255, 255)  # r, g, b


class Box:
    # constructor.. 박스가 박스이기 위한.. 필요한 것들이 뭐가 있나
    # __init__
    # 필요한것
    # x, y 좌표(위치)
    # start, goal, wall인지
    def __init__(self, x, y, block_width, block_height):
        self.x, self.y = x, y
        self.color = (217, 217, 217)

        self.cost = float('inf')

        self.width, self.height = block_width, block_height
        self.start, self.goal, self.wall = False, False, False
        self.path = False
        self.visited = False

    def setcolor(self, color): self.color = color

    def draw(self, mywin):
        # color = (0, 255, 0)
        pos = (self.x, self.y, self.width - 2.5, self.height - 2.5)
        pygame.draw.rect(mywin, self.color, pos)
import heapq
def dij(g, finish_x, finish_y, window):
    result_path = []
    result_cost = float('inf')
    q = [(0, 6, 7, [], g[6][7])]
    dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]
    xlen, ylen = len(g), len(g[0])

    cnt = 0

    while q:
        cost, x, y, path, bx = heapq.heappop(q)
        if bx.wall == True or \
                result_cost <= cost or bx.cost <= cost: continue
        g[x][y].cost = cost
        bx.cost = cost
        if (x, y) == (finish_x, finish_y):
            if result_cost > cost:
                result_cost = cost
                result_path = path
        colored = []
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < xlen and 0 <= ny < ylen:
                heapq.heappush(q, (cost + 1, nx, ny, path + [(x, y)], g[nx][ny]))
                colored.append((g[nx][ny], g[nx][ny].color))

        bx.setcolor((0, 224, 255))
        for b, c in colored:
            if c == (255,0,0): continue
            b.setcolor((51, 255, 0))

        for i in g:
            for j in i:
                j.draw(win)

        for b, c in colored: b.setcolor(c)

        pygame.image.save(window, "./screen_to_blog/blog_"+str(cnt)+".png")
        cnt+=1

        bx.setcolor((21, 106, 0))

        # win.fill(WHITE) #(r,g,b)
        # pygame.display.update(win)
        pygame.display.flip()
        pygame.time.delay(200)
    return result_path if result_cost != float('inf') else None


def solution():
    global target_flag
    # 그래픽 처리는 무조건 refresh 화면을 계속 찍는것
    g = []  # grids
    for i in range(cols):
        temp = []
        for j in range(rows):
            temp.append(Box(i * grid_width, j * grid_height, grid_width, grid_height))  # object 넣기
        g.append(temp)
    start_box = g[0][0]
    start_box.visited = True
    start_box.start = True
    start = False
    q = [start_box]
    target_pos = (0, 0)
    isRun = True
    while isRun:
        # 이벤트.. 이벤트 프로그래밍..  in cs
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                sys.exit()  # system
            elif event.type == pygame.MOUSEMOTION:
                position = pygame.mouse.get_pos()  # (x, y) 현재 마우스의 위치를 return함 tuple의 형태로
                x, y = position
                x, y = x // grid_width, y // grid_height
                if event.buttons[0]:  # 왼쪾 마우스가 클릭되면
                    print(f"방해물 설정 중 : 좌표 x = {x}, y = {y}")
                    if (x, y) == target_pos or (x, y) == (0, 0): continue
                    g[x][y].setcolor((255, 0, 0))
                    g[x][y].wall = True
                # 1번은 마우스 휠
                elif event.buttons[2] and target_flag == False:  # 오른쪽 마우스 클릭되면
                    print(f"목표물 설정 : 블럭 좌표 x = {x}, y = {y}")
                    g[x][y].setcolor((0, 0, 255))
                    g[x][y].goal = True
                    target_pos = (x, y)
                    target_flag = True
            elif event.type == pygame.KEYDOWN and target_flag == True:  # 키가 눌렸다면 실행
                print('알고리즘 시작')
                start = True
                g[6][7].start = True
                isRun = False
                nf = dij(g, target_pos[0], target_pos[1], win)
                if nf == None: return "경로 없음"
                else:
                    for (x,y) in nf:
                        g[x][y].setcolor((100,100,100))

        for i in g:
            for j in i:
                j.draw(win)

        # win.fill(WHITE) #(r,g,b)
        # pygame.display.update(win)
        pygame.display.flip()
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                sys.exit()  # system
        for i in g:
            for j in i:
                j.draw(win)
    return

A* 알고리즘 코드#

class Astar():
    def __init__(self, grid):
        self.grid = grid

    def heuristic_Diagonal_Distance(self, node, goal, D1=1, D2=2 ** 0.5):
        dx = abs(node.position[0] - goal.position[0])
        dy = abs(node.position[1] - goal.position[1])

        return D1 * (dx + dy) + (D2 - 2 * D1) * min(dx, dy)

    def heuristic_Euclidean_Distance(self, current, end):
        return ((current.position[0] - end.position[0]) ** 2)\
                + ((current.position[1] - end.position[1]) ** 2)

    def CalcNode(self, childNode, currentNode, endNode):
        childNode.g = currentNode.g + 1 + childNode.density ** 2
        childNode.h = self.heuristic_Euclidean_Distance(currentNode, endNode)
        childNode.f = childNode.g + childNode.h

    def NodeSet(self, node, g: int, f: int, h: int):
        node.g = g
        node.h = h
        node.f = f

    def getPath(self, node, board: list[list]):
        path = []
        while node.parent != None:
            y, x = node.position
            board[y][x] = node.f
            path.append(node.position)
            node = node.parent
        return path[::-1]

    def AStar(self, board: list[list], start: tuple, end: tuple, delay: int = 0):
        import heapq as hq
        from CompyLib.Algorithms import Node

        startNode = Node(None, start, board[start[0]][start[1]], 0)
        endNode = Node(None, end, board[end[0]][end[1]], 0)

        self.NodeSet(startNode, 0, 0, 0)

        openList: list[Node] = list()
        closedList: list[Node] = list()

        openList.append(startNode)
        dx, dy = [0, 0, -1, 1, -1, -1, 1, 1], [-1, 1, 0, 0, -1, 1, -1, 1]

        Visualization = self.grid != None
        self.CalcNode(startNode, startNode, endNode)
        while openList:
            currentNode: Node = hq.heappop(openList)
            closedList.append(currentNode)
            if Visualization:
                self.grid.changeBox(self.grid.getBoxbyIndex(currentNode.position[0],
                                                            currentNode.position[1]), "GREEN")

            if endNode == currentNode:
                return self.getPath(currentNode, board)

            children: list[Node] = []

            for i in range(8):
                ny = currentNode.position[0] + dy[i]
                nx = currentNode.position[1] + dx[i]

                if 0 > ny or ny >= len(board) or 0 > nx or \
                        nx >= len(board[0]) \
                        or board[ny][nx] == 1:
                    continue
                children.append(Node(None, (ny, nx), board[ny][nx], 0))
            for child in children:
                if child in closedList: continue
                self.CalcNode(child, currentNode, endNode)
                # print(child.f, currentNode.f, currentNode, child)
                # if child.f > currentNode.f: continue or child.g + child.density > currentNode.g + 1: continue  # or
                # child.g + child.density <= currentNode.g + 1:
                flag: bool = False
                for node in openList:
                    if child == node and child.g > node.g:
                        flag = True
                        break
                if flag: continue

                child.parent = currentNode

                hq.heappush(openList, child)
            if Visualization: self.grid.boardUpdate(delay)

        return -1

격자 생성#

class Type:
    def __init__(self, screen: p.Surface = None, row: int = 5, col: int = 5):

        self.Running = True

        # Pygame 객체

        self.screen = screen
        self.row = row
        self.col = col

        if screen == None: self.Running = False

        # 기본 색 설정

        self.RED: tuple = (255, 0, 0)
        self.BLUE: tuple = (0, 0, 255)
        self.GREEN: tuple = (0, 255, 0)
        self.BLACK: tuple = (0, 0, 0)
        self.WHITE: tuple = (255, 255, 255)

        # 색 접근
        self.custom_color: dict = {"RED": self.RED, "BLUE": self.BLUE,
                                   "GREEN": self.GREEN, "BLACK": self.BLACK,
                                   "WHITE": self.WHITE, "ORANGE": (255, 95, 0),
                                   "DARKORANGE": (255, 135, 0), "GOLD": (255, 215, 0),
                                   "YELLOW": (255, 255, 0), "AQUA": (0, 255, 255),
                                   "NAVYBLUE": (0, 0, 95)}
        self.color_idx: list = ["BLUE", "RED", "GREEN", "BLACK", "WHITE", "ORANGE",
                                "DARKORANGE", "GOLD", "YELLOW", "AQUA", "NAVYBLUE"]

    def update(self):
        return

    def changeColor(self, *inp):
        length: int = len(inp[0])

        # print(inp[0])

        inp = inp[0]

        if length < 2 or type(inp[1]) != str:
            return False

        if inp[1] not in self.custom_color.keys():

            if length < 3 or type(inp[2]) != tuple:
                return False

            self.custom_color[inp[1]] = inp[2]

        ret: str

        if type(inp[0]) == int:
            ret = self.color_idx[inp[0]]
            self.color_idx[inp[0]] = inp[1]
        elif type(inp[0]) == str:

            if inp[0] not in self.color_idx:
                return False

            ret = inp[0]
            self.color_idx[self.color_idx.index(inp[0])] = inp[1]
        else:
            return False

        return ret

    def addColor(self, name: str, color: tuple):

        if name == None or name == "":
            return False

        self.custom_color[name] = color
        return True
        
        
class Grid(Type):

    def __init__(self, screen: p.Surface = None,
                 row: int = 5, col: int = 5,
                 space: float = -1.5):

        super().__init__(screen, row, col)

        self.space = space
        self.board: list = list()  # [[0 for i in range(row)] for i in range(col)]

        (sc_width, sc_height) = screen.get_size()

        self.bx_width = sc_width // row
        self.bx_height = sc_height // col

        for i in range(row):
            self.board.append(list())

            for j in range(col):
                self.board[i].append(Box(i * self.bx_width, j * self.bx_height,
                                         self.bx_width + space, self.bx_height + space))  # x, y, width, height, color

    def boardUpdate(self, delay: int):
        self.screen.fill(self.WHITE)

        for i in self.board:
            for j in i:
                j.draw(self.screen, p)
        p.display.flip()

        p.time.delay(delay)

    def Colors(self):
        cnt: int = 0

        for name, rgb in self.custom_color.items():
            cnt += 1
            print(f"{name}의 rgb값은 {rgb}  ", end='')
            if cnt // 3 == 1:
                cnt = 0
                print()

    def changeColor(self, *inp):
        res: str = super().changeColor(inp)
        if not res: return False
        for i in self.board:
            for box in i:
                if box.colorName != res: continue
                box.colorName = inp[1]
                box.color = self.custom_color[inp[1]]
        return True

    def changeBox(self, *inp):
        # x: int, y: int, color=0):
        box: Box

        if len(inp) > 2:
            x, y = inp[0], inp[1]
            box = self.board[y][x]

            if type(inp[2]) == int:
                color: int = inp[2]
            else:
                color: str = inp[2]
        else:
            box = inp[0]

            if type(inp[1]) == int:
                color: int = inp[1]
            else:
                color: str = inp[1]
        # print(inp, box, color)
        if type(color) == int:
            box.colorName = self.color_idx[color]
            box.color = self.custom_color[box.colorName]

        elif type(color) == str:
            box.colorName = color
            box.color = self.custom_color[color]

        else:
            return False
        return True

    def getBoxbyCoordinate(self, x: int, y: int):
        return self.board[x // self.bx_width][y // self.bx_height]

    def getBoxbyIndex(self, x: int, y: int):
        return self.board[y][x]

    def getBox(self, x: int, y: int):
        return self.getBoxbyCoordinate(x, y)