[GPG 1 글 3.5] A* 알고리즘 최적화에 대해서 ...

GPG 시리즈 관련 질답, 논의 공간.

Moderator: 류광

비회원

A* 알고리즘 최적화에 대해서 ...

Post by 비회원 »

3D로 포트폴리오를 만들고 있는데요.

워크 카오스같은 컨셉에 게임을 만들고 싶어서 제작하고 있습니다.

책을 보며 최적화가 되지 않은 A* 알고리즘을 적용 하니...

역시나 길은 잘찾아지나 멀리 있는 곳을 클릭하면

길을 찾을때 동안 먹통이 되있다가 움직이더군요...

GPG 검색하니 루프 제한을 둬서 조금씩 찾아찾아 가는걸 적용해도

그래도 프레임이 길을 찾는 동안 50fps 정도 다운되는 현상도 있고 끊기고 그러더군요...

A* 알고리즘 최적화 방법에 대한 제시좀 해주시면 안될까요...

GPG 책이나 위즈덤을 보면서 연구하고있지만... 어려운부분이 많네요...

고수님들의 조언 부탁드립니다.
비회원

스레드를 적용하면 어떨까요

Post by 비회원 »

그런경우엔 스레드를 적용해보세요.
적용하여 테스트 해보기에 딱 좋은 상황같습니다.

-길찾기 처리 스레드 생성

-길찾기 스레드는 큐가 비어있으면 pause

-큐가 채워지면(시작점,끝점) resume
1. 길찾기 경로 생성
2. 경로 최적화
-1단계 ( 임의의 경로에서 시야에 들어오는 경로 제거 )
-2가중치처리( 경로가 너무 멀리 돌아가는 경우 )

- 대략 1항목의 계산량만 하더라도 쉽게 예측하기 어렵습니다.
- 이미 처리해놓으셨겠지만 실행시간에 바뀌지 않는
값이 있으면(가중치,edge의중점등) 충분히 선계산 해놓으셔야 합니다.


대략 위와같은 느낌으로 길찾기 스레드를 만들어 놓으시면 될듯합니다.
biron250
Posts: 1
Joined: 2008-10-08 14:42

어디서 본거긴 한데

Post by biron250 »

예전에 포폴할때 어떤책(실용적인 AI예제?)에서 본건데

계층을 나누는 겁니다. 전체맵을 큰 타일과 작은 타일 2개의 데이터를 만들어 내고

처음에 검색할때는 큰 타일로 빠르게 검색합니다. 그 후 실제로 유닛이 이동할때 현재 위치와 다음 큰 타일의

위치까지 작은타일에서 검색합니다. 완전히 최적화된 방법은 아니지만 GPG라던지 실용적인 AI예제를 보면

괜찮을듯 싶습니다.

그리고 AIWisdom 1권에서 나왔던 방법으로 길찾기 자체를 전처리 해버리는 방법도 있습니다.
비회원

Post by 비회원 »

가장 좋은 방법은 길을 찾아갈때에 처리해야 할 데이터를 정리하는게 좋지 않을까요?
뭔가 하나를 실행시키는데 정확하게 데이터가 빨리 안나온다는것은 참조 데이터가 정리가 안되어 있는 경우가
많은 것 같습니다.

맵 데이터의 Point를 찍을 수 있는 구조로 만들고 그 Point는 맵을 생성했을때 MapTool등에서 자동으로 최적화된 자리에 찍어 줄수 있는 구조라면 적은 Reference자료로 빠른 결과값을 얻을 수 있지 않을까 생각되어집니다.
비회원

Post by 비회원 »

일단 Wisdom 1권에 최적화 관련 내용이 있으니 그거 많이 참고하세요.

제가 거기서 적용한것중에 가장 속도가 효과를 본 것은 인라인 함수의 사용이였습니다.

또한 코드 최적화로는 한계가 있으니 윗분들이 말씀하신것 처럼

큰 타일로 검색한후 작은 타일로 검색하는 방법을 사용하는 것도 좋을 듯 합니다.

실제 스타크래프트에서도 그렇게 탐색을 하고 있습니다.
쌀밥
Posts: 1058
Joined: 2003-02-02 20:23
Location: THQ Inc.
Contact:

heuristic 하게 되지 않을까요?

Post by 쌀밥 »

A* 로 길을 찾는거라면 heuristic 한 방법을 시도해 보는것도 좋을것 같습니다.
Wiki 에도 heuristic 한 방법에 대해서 여러번 언급되어있습니다.
http://en.wikipedia.org/wiki/A*_search_algorithm

저는 Computer Vision 에서 segmentation 할때 heuristic 하게 사용하는걸 봤는데 게임 프로그래밍에 적합한 heuristic algorithm 도 비슷한 방법으로 될거라고 생각합니다.
I want to live in korea, making programs, but...
http://wrice.egloos.com
Post Reply