A star pathfinder

 

 

 

 

 

https://github.com/nexmin0805/A_star_Pathfinder

GitHub - nexmin0805/A_star_Pathfinder

 

 

 

 

이 코드는 A* 경로 찾기 알고리즘을 시각화하는 프로그램입니다. Pygame 라이브러리를 사용하여 그래픽 사용자 인터페이스를 구현하였습니다. 이 프로그램은 사용자가 장애물을 생성하거나 랜덤하게 생성할 수 있고, 마우스를 드래그하여 시작점 및 도착점을 설정할 수 있게 해주며, 두 가지 휴리스틱 방식(맨하탄 거리, 유클리드 거리) 중 하나를 선택하여 A* 알고리즘을 실행할 수 있습니다.

 

 

 

1. screen.py: GUI의 그리기 함수와 버튼 처리를 구현합니다.

2. block.py: 그리드의 각 셀에 대한 클래스 및 기능을 구현합니다.

3. search.py: A* 알고리즘을 구현하고, 시작 노드와 종료 노드 간의 최단 경로를 찾습니다.

4. main.py: 애플리케이션을 실행하고 사용자 인터페이스와 상호작용을 관리합니다.

 

 

1. screen.py

`screen.py` 파일은 GUI의 그리기 함수와 버튼 처리를 구현합니다. 주요 기능은 다음과 같습니다.

 

- `draw(win, grid, rows, width, manhattan_checked, euclidean_checked)`: 윈도우 객체에 그리드, 버튼 및 체크박스를 그립니다.

- `draw_grid(win, rows, width)`: 그리드 라인을 그립니다.

- `draw_buttons(win, width, manhattan_checked, euclidean_checked)`: 사용자 인터페이스의 버튼과 체크박스를 그립니다.

- `get_clicked_pos(pos, rows, width)`: 클릭한 위치를 기반으로 그리드 내의 행과 열을 반환합니다.

- `handle_buttons(pos, width)`: 클릭한 위치를 기반으로 버튼 및 체크박스 이벤트를 처리합니다.

 

 

 

2. block.py

`block.py` 파일은 그리드의 각 셀에 대한 클래스 및 기능을 구현합니다. 주요 기능은 다음과 같습니다.

 

- `Cell` 클래스: 각 셀의 속성과 메서드를 정의합니다. 셀은 다양한 상태(열림, 닫힘, 벽, 시작, 종료, 경로)를 가질 수 있습니다.

- `make_grid(rows, width)`: 주어진 행 수에 대한 그리드를 생성하고 각 셀 객체를 초기화합니다.

 

 

 

3. search.py

`search.py` 파일은 A* 알고리즘을 구현하며, 주요 기능은 다음과 같습니다.

 

- `h(p1, p2, heuristic)`: 두 점 간의 휴리스틱 값(Manhattan 또는 Euclidean)을 계산합니다.

- `reconstruct_path(came_from, current, draw)`: 마지막 노드에서 시작 노드까지 역추적하여 경로를 구성합니다.

- `a_star(draw, grid, start, end, heuristic_func)`: A* 알고리즘을 구현하고, 시작 노드와 종료 노드 간의 최단 경로를 찾습니다.

- `no_solution_path(came_from, lowest_f_node, draw)`: 경로가 발견되지 않은 경우, 가장 낮은 F 값을 가진 노드로 역추적하여 경로를 구성합니다.

 

 

4. main.py

`main.py` 파일은 애플리케이션을 실행하고 사용자 인터페이스와 상호작용을 관리합니다. 주요 기능은 다음과 같습니다.

 

- `make_buttons()`: 버튼 및 체크박스의 위치와 크기를 설정합니다.

- `main(win, width)`: 애플리케이션의 메인 루프를 실행합니다. 이 함수는 그리드를 초기화하고 이벤트 처리를 수행합니다. 사용자가 버튼을 클릭하면 해당 작업이 수행됩니다(예: 경로 찾기 시작, 무작위 벽 생성, 그리드 리셋 등). 또한 사용자가 선택한 휴리스틱(Manhattan 또는 Euclidean)에 따라 A* 알고리즘이 실행됩니다.

- `if __name__ == "__main__":` 명령줄 인수를 처리, 프로그램을 실행. 그리드의 행 수, 창 너비 및 장애물 비율을 설정 가능합니다.

 

 

 

 

 

 

 

 

1. 그리드 크기, 창 너비, 장애물 비율을 설정하고 프로그램을 실행.( Grid cells의 행은 ‘r’, 원도우의 크기는 ‘w’, inc obstacle ratio의 값은 ‘o’로 argparse를 이용하여 command line에서 입력받을 수 있도록 했습니다.). (ex. python main.py -r=60)

 

 

 

2. • 장애물 - 사용자 배치: 다음으로 사용자 배치에서는, grid world상의 마우스 클릭된 grid cell을 focus cell이라 할때 해당 cell이 비어있다면 장애물로 바뀝니다. 만약 해당 focus cell이 장애물이었다면 toggle되어 다시 비어있는 cell로 바뀝니다.

 

 

3. 시작지점과 목표지점: 시작지점과 목표지점은 초기에 고정위치에 표시되도록 하고, 사용자 마우스 drag를 통해 이동될 수 있도록 했습니다.

 

 

 

 

4. A* Search 수행: Start A* Search 버튼 클릭시 A* search를 수행하여, 최단경로를 찾을 경우 해당 경로를 yellow line으로 표시합니다. 또한, 콘솔화면에 해를 탐색할때까지의 총 explored nodes갯수를 출력합니다.

 

 

5. A* Search Heuristic 함수: 휴리스틱 함수로 현재 node의 위치와 gold node위치간의 1) Manhattan 거리, 2) Euclidean 거리 두 가지중 하나를 화면 우측의 ratio button을 통해 선택할 수 있도록 했습니다.

-Manhattan거리

-2. Euclidean 거리

6. A* Search 결과 - 해가 없을 때 : 만약 A* search 결과 해가 없다면, 콘 솔화면에 path가 발견되지 않았다는 메시지를 출력합니다.

 

 

 

 

 

 

프로젝트의 장점과 단점

 

장점:

• 사용자가 직접 그리드를 그려 경로를 탐색할 수 있습니다.
• 두 가지 휴리스틱 (Manhattan 및 Euclidean)을 비교할 수 있는 기능을 제공합니다.
•  

단점:

• 대규모 그리드 또는 복잡한 환경에서는 성능이 저하될 수 있습니다.
• 현재 코드는 다양한 휴리스틱이나 알고리즘을 추가하는 데 제한적일 수 있습니다.

 

 

 

 

프로젝트를 향후 개선할 수 있는 방법

1. 알고리즘의 성능을 향상시키기 위해 다양한 최적화 기법을 적용할 수 있습니다..
2. 다양한 휴리스틱 및 알고리즘을 지원하도록 코드를 리팩토링 할 수 있습니다.
3. 다양한 환경 및 장애물 구성을 불러올 수 있는 기능을 추가할 수 있습니다.
4. 다양한 알고리즘, 예를 들어 Dijkstra, Greedy Best-First Search, BFS, DFS 등을 비교할 수 있도록 프로젝트를 확장할 수 있습니다.