📑프로젝트-A star 알고리즘

#### A-Star 알고리즘
생각보다 고등학교때는 파이썬 위주로 프로그램을 많이 짰던 것 같다. VS code에 highlight랑 여러 텍스트에디터를 깔아두고 코딩을 하면 간지가 나서 그랬을까 ㅋㅋ
파이썬으로 코딩했던 코드가 몇개 보존되어 있길래 오늘은 고등학교 때 했던걸 정리하면서 A-Star 알고리즘으로 미로를 만들었던걸 적어보려고 한다.

참고로 전문적인 길찾기 알고리즘을 참고하기엔 이 글은 적절하지 않다. 어떤 느낌인지 감만 잡고싶은 초보 프로그래머들이 한번 쯤 거쳐가면 좋은 글인 것 같다.

---

A-Star 알고리즘?

처음에 A-Star 알고리즘이라고 들었을때는 전혀 감이 오질 않았다. 당시에는 향후에 나올 재귀용법은 커녕 DFS,BFS 및 Dijkstra 등 길찾기 알고리즘에 관한 기본 지식도 없었으며 (지금도 없지만 ㅜㅜ) 어떻게 코딩해야할지 전혀 감을 잡지 못했다. 그래서 무작정 구글링해보며 코드를 작성해보았던 기억이 난다.

만능 지식 선생님인 위키백과를 보면 A-Star에 대해 이렇게 기술해놓았다.

A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 (다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나이다. 이 알고리즘은 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값 " h(x) 을 매기는 방법을 이용한다는 것이다.

처음에 이 글을 보고 무슨 소린지 이해가 안갔으나 구글링을 해보며 차근차근 이해해가보려 했다.
일단 이 A-Star 알고리즘은 "휴리스틱"기법이다. 그래서 이 휴리스틱이 뭐냐?

찍기

그냥 눈대중으로 보고 때려맞추는거래요 저도 잘 몰라요 ㅋㅋ

대충 사전적 정의로는
대충 어림짐작하기, 경험이 부족하거나 합리적 판단이 필요하지 않으며 빠르게 판단하고 싶을 때 사용

이라는데 이게 찍기랑 무슨 차이가 있으려나

그러나 나중에 와보니까 유전자 알고리즘이나 다익스트라 알고리즘 등 굵직한 알고리즘도 이런 휴리스틱에 기반하여 사용하니 꼭 알아두면 좋은 개념이다.

다시 본론으로 돌아와서 A-Star알고리즘이 휴리스틱에 기반했으며, 주어진 꼭짓점(노드)마다 최단 경로임을 판단한 후 이동하는 그래프 탐색 알고리즘임을 알 수 있었다.
A-Star 알고리즘의 핵심은 F=G+H이다. F는 출발 지점에서 목적지까지의 총 값, G는 현재 지점에서 출발 지점까지의 총 값, H는 현재 지점에서 목적지까지의 값인데 아마 목적지는 당장에 알 수 없으니 추정값이 아닐까 싶다. 참고로 여기서 H는 일반적으로 휴리스틱의 약자라고 한다.

여기서 파란색은 출발지점, 주황색은 도착지점이라고 해보자.
그리고 중간에 그어져 있는 저 선은 믿기지 않겠지만 장애물이다.
검은색 네모들은 길이다. 움직일때마다 1값씩 소모된다.

여기서 현재 우리가 와 있는 노드의 값이 3이라고 생각해보자.

대충 그렸지만 이렇게 생겼을 것이다. 그럼 우리가 3에 와 있으니까 F=G+H중에서 G는 3이 되네?
그럼 이제 우린 휴리스틱만 구해주면 A-Star를 이해할 수 있다.

그림을 거지같이 그려서 이상해보일지 몰라도 대충 앞으로 3칸, 위로 한칸이다.
중학교 시절때 배워온 사람이라면 대부분 알거다. 피타고라스 공식
그렇게 처음 나온 G=3과 피타고라스를 이용하여 구한 H=√10을 더하면 대충 도착지점인 7 근사값이 나오는 걸 확인할 수 있다. 와!

여기서 주의할 점은 근접거리가 값이 클 경우에는 다익스트라 알고리즘처럼 작동할 수도 있다고 한다.
초보 프로그래머인 내가 신경 쓸 건 아닌것 같지만...

A-Star는 생각보다 많은 곳에서 쓰인다. 아는 분이 아이나비 회사에 다니시는데 한 때 쓰이셨다고 하고, 다익스트라와 더불어 활용도가 높은 길찾기 알고리즘 중 하나이니 개념이라도 꼭 짚고 넘어갈 필요성이 있다.

그럼 A-Star의 기본적인 걸 익혔으니 이걸 코드로 구현해 보자.

---

💻프로젝트 시작

코드의 가독성을 위해 A-Star 알고리즘과 미로 생성 부분을 나눴다. 이번에 만들어 볼 것은 미로를
생성한 뒤 A-Star 알고리즘을 이용해 최적의 길찾기를 했는지 판별해주는 시스템이다.

A-Star Logic

def astar(maze, start, end):
    start_node = Node(None, start)  # 시작 노드 생성
    start_node.g = start_node.h = start_node.f = 0
    end_node = Node(None, end)  # 도착 노드 생성
    end_node.g = end_node.h = end_node.f = 0

    open_list = []  # 오픈 리스트
    closed_list = []  # 닫힌 리스트

아까 했던 것과 마찬가지로 시작노드와 도착노드를 생성해주었다.

 while len(open_list) > 0:  # 오픈 리스트에 노드가 없을때 종료
        current_node = open_list[0]
        current_index = 0
        # 오픈 리스트 노드들중에 가장 최소 비용 F를 가진 노드를 찾는다
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index

        open_list.pop(current_index)  # 오픈 리스트에 해당하는 노드 pop
        closed_list.append(current_node)  # 닫힌 리스트에 해당 노드 input

        if current_node == end_node:  # 도착 노드까지 탐색이 완료될 경우
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1]  # 역순으로 출력되게 반전 상태로 리턴 시킨다

리스트를 활용하여 만들어보려고 했다.

아까 설명하면서 지정한 것과는 달리, 미로에서 플레이어가 움직일 때는 항상 유동적으로 값이 바뀌기에 현재 노드중 가장 최소 비용을 가진 노드를 바로바로 찾아줘야한다.

그게 F고 도착 노드까지 탐색이 완료될 경우에는 역으로 출력되도록 코딩해두었다.

 if node_position[0] > (len(maze) - 1) or node_position[0] < 0 \
                   or node_position[1] > (len(maze[len(maze) - 1]) - 1) or node_position[1] < 0: 
                continue

if maze[node_position[0]][node_position[1]] == 1:  # 이동될 지점이 벽일때
                continue
            elif node_position[1] == start[1]-1 and current_node.position == start_node.position:
                continue

이런씩으로 미로 벽 밖으로 나갔을때 루프를 다시 돌게끔 만들어 정상적으로 출력되게 해주었으며

            if check == False:
                child.g = current_node.g + 1
                child.h = ((child.position[0] - end_node.position[1]) ** 2) + (
                    (child.position[1] - end_node.position[0]) ** 2)
                child.f = child.g + child.h

아까 피타고라스의 정리로 수평과 수직 경로의 가중치를 설정했으니 그것 또한 똑같이 설정해주었다.

A-Star 미로구현

미로는 pygame으로 제작했다.
파이썬의 제작 라이브러리중에서 가볍게 만들어보기엔 pygame만한게 없는 것 같다

import pygame
import sys
from time import sleep
import A_star_logic

white = (255, 255, 255)
gold = (255, 204, 0)
green = (0, 255, 0)
dark_green = (0, 153, 0)
black = (0, 0, 0)

size = [800, 600]  # setup game size
box_size = 45  # setup box size
player_size = 20  # setup player size

start_point = (0, 1)  # start y,x
end_point = (9, 15)  # end y,x

maze_x = 17  # max maze x
maze_y = 11  # max maze y

make_maze = [[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
             [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1],
             [1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1],
             [1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
             [1, 1, 1, 1, 0, 1, 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, 1, 0, 1],
             [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1],
             [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
             [1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1],
             [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 1],
             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

미로를 만들어주고 초기값을 싹 설정해주었다.

def __init__(self):
        pygame.init()

        self.display = pygame.display.set_mode(size)  # display setup
        pygame.display.set_caption('maze')  # caption setup
        self.fps = pygame.time.Clock()  # fps setup

        self.player_x = 70  # pixcel x
        self.player_y = 20  # pixecl y

        self.x = start_point[1]  # real x
        self.y = start_point[0]  # real y

        self.font = pygame.font.SysFont("Arial", 40)  # font setup

        self.cnt = 0  # move count check
        self.path = [start_point, ]  # add move path

        self.maze()

그 뒤 파이게임의 기본 캡션과 fps, 픽셀 x,y값을 설정해주었으며

  if key[pygame.K_RIGHT]:  # move right
            if make_maze[self.y][self.x + 1] == 1:
                pass
            elif make_maze[self.y][self.x + 1] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_x += box_size
                self.x += 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_x += box_size
                self.x += 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

        elif key[pygame.K_LEFT]:  # move left
            if make_maze[self.y][self.x - 1] == 1:
                pass
            elif make_maze[self.y][self.x - 1] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_x -= box_size
                self.x -= 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_x -= box_size
                self.x -= 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

        elif key[pygame.K_UP]:  # move up
            if make_maze[self.y - 1][self.x] == 1:
                pass
            elif make_maze[self.y - 1][self.x] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_y -= box_size
                self.y -= 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_y -= box_size
                self.y -= 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

        elif key[pygame.K_DOWN]:  # move down
            if make_maze[self.y + 1][self.x] == 1:
                pass
            elif make_maze[self.y + 1][self.x] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_y += box_size
                self.y += 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_y += box_size
                self.y += 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

키보드를 누르면 이동하게끔 설정
얼추 다 된것 같으니 실행해보면 될 것 같았다.

실행도 잘 되고

최적 루트일때의 값도, 아닐때의 값도 잘 출력되는 모습을 볼 수 있다.

---

고등학교때 내가 이걸 어떻게 만들었는지 모르겠다 ㅋㅋㅋ
당시에 아는 선배나 인터넷 도움 받아가면서 꾸역 꾸역 만들었는데 이제 와서 코드를 보니 다시 공부해야겠다는 생각이 새삼 들었다.

아래에 코드 전문을 첨부했으니 언젠가는 살펴보겠지..?

미로

import pygame
import sys
from time import sleep
import A_star_logic

white = (255, 255, 255)
gold = (255, 204, 0)
green = (0, 255, 0)
dark_green = (0, 153, 0)
black = (0, 0, 0)

size = [800, 600]  # setup game size
box_size = 45  # setup box size
player_size = 20  # setup player size

start_point = (0, 1)  # start y,x
end_point = (9, 15)  # end y,x

maze_x = 17  # max maze x
maze_y = 11  # max maze y

make_maze = [[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
             [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1],
             [1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1],
             [1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
             [1, 1, 1, 1, 0, 1, 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, 1, 0, 1],
             [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1],
             [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
             [1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1],
             [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 1],
             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]


class MAZE:
    def __init__(self):
        pygame.init()

        self.display = pygame.display.set_mode(size)  # display setup
        pygame.display.set_caption('maze')  # caption setup
        self.fps = pygame.time.Clock()  # fps setup

        self.player_x = 70  # pixcel x
        self.player_y = 20  # pixecl y

        self.x = start_point[1]  # real x
        self.y = start_point[0]  # real y

        self.font = pygame.font.SysFont("Arial", 40)  # font setup

        self.cnt = 0  # move count check
        self.path = [start_point, ]  # add move path

        self.maze()

    def maze(self):  # draw maze
        mx = 0
        my = 0

        for i in range(0, maze_x * maze_y):
            if make_maze[my][mx] == 3:
                pygame.draw.rect(
                    self.display, gold, (mx * box_size, my * box_size, box_size, box_size))
            if make_maze[my][mx] == 2:
                pygame.draw.rect(self.display, green, (mx *
                                                       box_size, my * box_size, box_size, box_size))
            if make_maze[my][mx] == 1:
                pygame.draw.rect(
                    self.display, white, (mx * box_size, my * box_size, box_size, box_size), 2)
            mx += 1
            if mx == maze_x:
                mx = 0
                my += 1

    def Character(self):  # setup character
        self.player = pygame.Rect(
            self.player_x, self.player_y, player_size, player_size)

    def move(self):  # check the key press and move
        key = pygame.key.get_pressed()
        speed = 0.3

        if key[pygame.K_RIGHT]:  # move right
            if make_maze[self.y][self.x + 1] == 1:
                pass
            elif make_maze[self.y][self.x + 1] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_x += box_size
                self.x += 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_x += box_size
                self.x += 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

        elif key[pygame.K_LEFT]:  # move left
            if make_maze[self.y][self.x - 1] == 1:
                pass
            elif make_maze[self.y][self.x - 1] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_x -= box_size
                self.x -= 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_x -= box_size
                self.x -= 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

        elif key[pygame.K_UP]:  # move up
            if make_maze[self.y - 1][self.x] == 1:
                pass
            elif make_maze[self.y - 1][self.x] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_y -= box_size
                self.y -= 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_y -= box_size
                self.y -= 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

        elif key[pygame.K_DOWN]:  # move down
            if make_maze[self.y + 1][self.x] == 1:
                pass
            elif make_maze[self.y + 1][self.x] == 2:
                make_maze[self.y][self.x] = 0
                self.cnt -= 1
                pygame.draw.circle(self.display, green,
                                   (self.player_x, self.player_y), player_size)
                self.player_y += box_size
                self.y += 1
                sleep(speed)
            else:
                make_maze[self.y][self.x] = 2
                pygame.draw.circle(self.display, white,
                                   (self.player_x, self.player_y), player_size)
                self.player_y += box_size
                self.y += 1
                self.cnt += 1
                self.path.append((self.y, self.x))
                sleep(speed)

    def show(self):  # display Move count string
        showcount = self.font.render("Move:" + str(self.cnt), False, white)
        self.display.blit(showcount, (650, 500))

    def run(self):
        while True:
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    pygame.quit()
                    sys.exit()

            self.fps.tick(60)
            self.display.fill(black)

            self.move()
            self.maze()
            self.Character()
            self.show()

            pygame.draw.circle(self.display, green, (self.player.left,
                                                     self.player.top), player_size)  # draw character
            pygame.draw.circle(self.display, dark_green, (self.player.left - 1,
                                                          self.player.top - 1), player_size)  # draw gradation

            if self.x == end_point[1] and self.y == end_point[0]:
                print("도착!")
                print("도착지까지의 들은 비용은 : " +str(self.cnt))

                if self.cnt == answer:
                    print("\n최적의 경로 값입니다!")
                    print("A * 알고리즘이 찾은 경로는 : " +str(answer_path))
                    print("플레이어가 찾은 경로는 : " +str(self.path))
                else:
                    print("\n최적의 경로 값은 아닙니다...")

                sys.exit()

            # draw last move point
            if (self.x == start_point[1] and self.y == start_point[0]) and self.cnt > 0:
                self.cnt = 0
                mx = 0
                my = 0
                for i in range(0, maze_x * maze_y):
                    if make_maze[my][mx] == 2:
                        make_maze[my][mx] = 0
                        pygame.draw.rect(
                            self.display, white, (mx * box_size, my * box_size, box_size, box_size), 2)
                    mx += 1
                    if mx == maze_x:
                        mx = 0
                        my += 1

            pygame.display.update()


if __name__ == "__main__":  # start main
    global answer_path, answer

    answer_path = A_star_logic.main(
        make_maze, start_point, end_point)  # a star 알고리즘 경로
    answer = len(answer_path)-1  # a star 알고리즘 경로 길이 값

    MAZE().run()

로직

class Node():
    def __init__(self, parent=None, position=None):
        self.parent = parent  # 부모 노드
        self.position = position  # 노드 위치

        # 노드의 g,h,f
        self.g = 0
        self.h = 0
        self.f = 0

    def __eq__(self, other):
        return self.position == other.position


def astar(maze, start, end):
    start_node = Node(None, start)  # 시작 노드 생성
    start_node.g = start_node.h = start_node.f = 0
    end_node = Node(None, end)  # 도착 노드 생성
    end_node.g = end_node.h = end_node.f = 0

    open_list = []  # 오픈 리스트
    closed_list = []  # 닫힌 리스트

    open_list.append(start_node)  # 오픈 리스트 처음은 시작 노드 값으로

    while len(open_list) > 0:  # 오픈 리스트에 노드가 없을때 종료
        current_node = open_list[0]
        current_index = 0
        # 오픈 리스트 노드들중에 가장 최소 비용 F를 가진 노드를 찾는다
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index

        open_list.pop(current_index)  # 오픈 리스트에 해당하는 노드 pop
        closed_list.append(current_node)  # 닫힌 리스트에 해당 노드 input

        if current_node == end_node:  # 도착 노드까지 탐색이 완료될 경우
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1]  # 역순으로 출력되게 반전 상태로 리턴 시킨다

        children = []
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]:  # 동서남북 그리고 대각선 방향으로 한칸씩 이동

            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])

            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 \
                    or node_position[1] > (len(maze[len(maze) - 1]) - 1) or node_position[1] < 0:  # 이동될 지점이 maze 바깥일때
                continue

            if maze[node_position[0]][node_position[1]] == 1:  # 이동될 지점이 벽일때
                continue
            elif node_position[1] == start[1]-1 and current_node.position == start_node.position:
                continue

            new_node = Node(current_node, node_position)
            children.append(new_node)  # 자식 노드에 이동할 지점 즉 이동 노드 값 대입

        for child in children:
            check = False
            for closed_child in closed_list:
                if child == closed_child:  # 탐색중인 자식 노드가 닫힌 리스트와 같은 값일 경우
                    check = True

            if check == False:
                child.g = current_node.g + 1
                child.h = ((child.position[0] - end_node.position[1]) ** 2) + (
                    (child.position[1] - end_node.position[0]) ** 2)  # 피타고라스 정리에 의해 수평과 수직 경로의 가중치 설정
                child.f = child.g + child.h

                # for open_node in open_list:
                #     if child == open_node and child.g > open_node.g:
                #         continue

                open_list.append(child)


def main(maze, start, end):
    path = astar(maze, start, end)  # a star 탐색 결과
    return path
    #print("도착지까지의 최소 경로는 : ", path)  # 경로 출력
    #print("경로에 드는 비용은 : ", len(path))  # 최소 비용 출력