[Typescript] A* 길찾기 알고리즘 구현

https://mika0203.github.io/Pathfinding-Algorithm/

 

일단 구현 페이지..

 

 

대충 이런 느낌으로 구현했다.

 

알고리즘 구현은 이 단계를 걸쳤다.

A*의 자세한 알고리즘은 아래에 내가 참조한 사이트를 첨부할 예정. 

즉 알고리즘 설명은 거의 없다

 

1. startPosition, targetPosition, obstacles 지정

2. currentNode 를 startPosition 으로 지정

3. currenNode 를 closeNodeList 에 추가, openNodeList 에서 제거

4. currentNode 에서 8방향으로 Node 를 생성하여 ( 여기서 closeNodeList 에 있는 노드는 제외한다)  생성된 Node 들을 openNodeList 에 저장

5. openNodeList 중 적합한 Node 를 찾아 currentNode 로 지정 후 3번으로 이동

 

6. 위의 반복을 벗어나는 조건이 맞으면 이후 단계 진행

* 조건

- currentNode 가 targetPosition 과 위치가 같음 [찾음]

- openNodeList 의 길이가 0임. 즉 더 이상 찾을 Node 가 없음 [못찾음]

- 계산이 너무 많음 (원래 화면을 벗어난 좌표는 제한시켜야하는데 아직 미완성이라... 100,000회 반복하면 종료하게 만들어둠)

 

대충 이렇게 단계를 걸친다.

 

현재 개발이 더 필요하다고 느끼는 점이

1. 장애물 판별하는 코드

장애물 판별을 x, y 값 비교를 하나하나 다 하고 있는데 8방향 Node 를 구할 때 계산이 좀 낭비되는 듯 하다. 

 

2. 시간

잘 만들어진 알고리즘과 비교하였을 때 시간차이가 얼마나 나는지 체크하고 어디서 계산시간이 많이 소모되는지 체크 후 업데이트

 

3. open, closeNodeList 를 시각적으로 표시

 

일단 대충 이정도?

 

git 주소와 astar 알고리즘 소스도 첨부...

github.com/Mika0203/Pathfinding-Algorithm

github.com/Mika0203/Pathfinding-Algorithm/blob/master/src/ts/Astar.ts

 

참조

lhh3520.tistory.com/343

[알고리즘] A* (A Star) 길찾기 알고리즘

http://egloos.zum.com/cozycoz/v/9748811

A* Algorithm 구현