3D로 포트폴리오를 만들고 있는데요.
워크 카오스같은 컨셉에 게임을 만들고 싶어서 제작하고 있습니다.
책을 보며 최적화가 되지 않은 A* 알고리즘을 적용 하니...
역시나 길은 잘찾아지나 멀리 있는 곳을 클릭하면
길을 찾을때 동안 먹통이 되있다가 움직이더군요...
GPG 검색하니 루프 제한을 둬서 조금씩 찾아찾아 가는걸 적용해도
그래도 프레임이 길을 찾는 동안 50fps 정도 다운되는 현상도 있고 끊기고 그러더군요...
A* 알고리즘 최적화 방법에 대한 제시좀 해주시면 안될까요...
GPG 책이나 위즈덤을 보면서 연구하고있지만... 어려운부분이 많네요...
고수님들의 조언 부탁드립니다.
[GPG 1 글 3.5] A* 알고리즘 최적화에 대해서 ...
Moderator: 류광
스레드를 적용하면 어떨까요
그런경우엔 스레드를 적용해보세요.
적용하여 테스트 해보기에 딱 좋은 상황같습니다.
-길찾기 처리 스레드 생성
-길찾기 스레드는 큐가 비어있으면 pause
-큐가 채워지면(시작점,끝점) resume
1. 길찾기 경로 생성
2. 경로 최적화
-1단계 ( 임의의 경로에서 시야에 들어오는 경로 제거 )
-2가중치처리( 경로가 너무 멀리 돌아가는 경우 )
- 대략 1항목의 계산량만 하더라도 쉽게 예측하기 어렵습니다.
- 이미 처리해놓으셨겠지만 실행시간에 바뀌지 않는
값이 있으면(가중치,edge의중점등) 충분히 선계산 해놓으셔야 합니다.
대략 위와같은 느낌으로 길찾기 스레드를 만들어 놓으시면 될듯합니다.
적용하여 테스트 해보기에 딱 좋은 상황같습니다.
-길찾기 처리 스레드 생성
-길찾기 스레드는 큐가 비어있으면 pause
-큐가 채워지면(시작점,끝점) resume
1. 길찾기 경로 생성
2. 경로 최적화
-1단계 ( 임의의 경로에서 시야에 들어오는 경로 제거 )
-2가중치처리( 경로가 너무 멀리 돌아가는 경우 )
- 대략 1항목의 계산량만 하더라도 쉽게 예측하기 어렵습니다.
- 이미 처리해놓으셨겠지만 실행시간에 바뀌지 않는
값이 있으면(가중치,edge의중점등) 충분히 선계산 해놓으셔야 합니다.
대략 위와같은 느낌으로 길찾기 스레드를 만들어 놓으시면 될듯합니다.
-
- Posts: 1
- Joined: 2008-10-08 14:42
어디서 본거긴 한데
예전에 포폴할때 어떤책(실용적인 AI예제?)에서 본건데
계층을 나누는 겁니다. 전체맵을 큰 타일과 작은 타일 2개의 데이터를 만들어 내고
처음에 검색할때는 큰 타일로 빠르게 검색합니다. 그 후 실제로 유닛이 이동할때 현재 위치와 다음 큰 타일의
위치까지 작은타일에서 검색합니다. 완전히 최적화된 방법은 아니지만 GPG라던지 실용적인 AI예제를 보면
괜찮을듯 싶습니다.
그리고 AIWisdom 1권에서 나왔던 방법으로 길찾기 자체를 전처리 해버리는 방법도 있습니다.
계층을 나누는 겁니다. 전체맵을 큰 타일과 작은 타일 2개의 데이터를 만들어 내고
처음에 검색할때는 큰 타일로 빠르게 검색합니다. 그 후 실제로 유닛이 이동할때 현재 위치와 다음 큰 타일의
위치까지 작은타일에서 검색합니다. 완전히 최적화된 방법은 아니지만 GPG라던지 실용적인 AI예제를 보면
괜찮을듯 싶습니다.
그리고 AIWisdom 1권에서 나왔던 방법으로 길찾기 자체를 전처리 해버리는 방법도 있습니다.
-
- Posts: 1058
- Joined: 2003-02-02 20:23
- Location: THQ Inc.
- Contact:
heuristic 하게 되지 않을까요?
A* 로 길을 찾는거라면 heuristic 한 방법을 시도해 보는것도 좋을것 같습니다.
Wiki 에도 heuristic 한 방법에 대해서 여러번 언급되어있습니다.
http://en.wikipedia.org/wiki/A*_search_algorithm
저는 Computer Vision 에서 segmentation 할때 heuristic 하게 사용하는걸 봤는데 게임 프로그래밍에 적합한 heuristic algorithm 도 비슷한 방법으로 될거라고 생각합니다.
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
http://wrice.egloos.com