[인공지능]인공지능 A*를 이용한 길찾기와 min max 알고리즘으로 구현한 게임

소개

인공지능의 대표적인 알고리즘인 A*를 이용한 길찾기 기본의 게임입니다.
c++로 구현하였으며 모든 프로그램은 객체지향 설계에 맞추어 제작하였으므로 A*알고리즘은 독립적 으로 재사용이 가능하며 A*를 이용한 min max도 구현되어 있습니다.게임 제목은 digging man으로 순수 창작게임이며 과목 프로젝트 1등 수상작입니다. 주석또한 상세히 설명되어있으며 파워포인트와 프로그램 분석문서 그리고
프로그램 소스 맵 에디터까지 구현하였습니다.

컴파일 실행환경

윈도우 xp 비주얼스트디오 6.0 c++

본문내용

• A* 알고리즘
1. 시작 지점을 노드 P로 둔다
2. 노드 P에 f, g, h 값을 배정한다.
3. P를 open queue에 추가한다. 이 시점에서 open queue에는 P 밖에 없다.
4. open queue의 노드들 중 최선의 노드 (최선의 노드란 f 값이 가장 작은 노드이다. )를 B로 둔다.
a. B가 목표 노드이면 경로를 찾은 것이므로 알고리즘을 끝낸다.
b. open queue 가 비었다면 경로를 찾을 수 없는 것이므로 알고리즘을 끝낸다.
5. B에 연결된 유효한 노드를 C로 둔다.
a. C 에 f, g, h 값들을 배정한다.
b. C가 open queue 나 close queue에 들어있는지 점검한다.
i. 만일 들어있다면, 새 경로가 효율적( f 값이 더 작은지 )인지 점검한다.
1.만일 그렇다면 경로를 갱신한다
ii. 들어있지 않다면 C를 열린 목록에 추가한다.
c. 단계 5를 B에 연결된 모든 유효한 자식 노드들에 대해 반복한다.
6. 4부터 다시 반복한다.


이 알고리즘을 기본으로 구현 하였으며 시작점을 (sx,sy) 목표점을 (dx,dy) 라고 하였을 때,
H= |dx-sx|+|dy-sy|
G= 각 단계마다 1씩 증가하는 스텝 값 (시작 시 초기값 0)
F= H+G
로 설정하였다. 그러나 우리가 사용하는 평면 좌표(2차원 좌표)에서는 대각선 이동을 허용하지 않고 상하좌우 이동만을 허용하기 때문에 약간의 문제가 발생한다. 그것은 항상 같은 f값을 가지는 노드가 매 스탭 당 2개씩 나타난 다는 것이다. 그리고 이전 스텝의 최소값과 같은 노드가 계속하여 생겨난 다는 점이다. 예를 들어 목표의 좌표가 (4,4) 이고 현 위치가 (1,1) 에서의 인접한 노드는 (1,0), (0,1), (2,1), (1,2) 이다. 각 노드의 f, h, g 값을 위의 식을 적용하여 살펴보면,
(1, 0) h = 7, g = 1, f = 8
(0, 1) h = 7, g = 1, f = 8
........

참고자료

· 없음