a*용 맵을 미리 생성해서 실시간 계산 부하를 줄이는 방법이 이상없을까요?

게임의 인공지능에 관한 포럼입니다.

Moderator: 류광

Locked
비회원

a*용 맵을 미리 생성해서 실시간 계산 부하를 줄이는 방법이 이상없을까요?

Post by 비회원 »

http://cafe.naver.com/bitmapgames.cafe? ... ticleid=60
여기에 보면 a* 길찾기을 위한 맵데이터를 미리 생성해서 실시간 계산하는 부하를 줄이는
방법이 나와있습니다.
그런데 제가 보기엔 이런 방식의 알고리즘 자체도 a* 알고리즘과는 틀린거 같구
이걸 mmorpg에 적용할수 있을까하는 생각도 들어서 여러가지로 고민중입니다.
링크에 나와있는 방식이나 아님 다른 부하를 줄일수 있는 방식에 대한 의견좀
부탁드리겠습니다.
Rica
Posts: 86
Joined: 2004-08-09 08:27

Post by Rica »

미리 길찾기용 맵을 만들어 두는 방식은, 길찾기의 대상이 되는 환경이 정적이거나, 환경이 동적으로 변화하되 변화하는 내용이 길찾기 전략에 영향을 주지 않을 때만 사용할 수 있습니다.

예를 들어, 다리가 멀쩡하면 다리를 건너가고 다리가 부서졌으면 다른 곳으로 돌아간다 같은 AI가 필요하면 미리 맵을 만들어 두기 어렵습니다. 맵 전체에 다리가 하나면 모를까 여러개면 경우의 수가 너무 늘어나지요.

Floyd가 그런 길찾기 방식인데, 위 조건을 만족하면 그럭저럭 쓸만한 것 같습니다. 저희 프로젝트에서도 사용하고 있습니다. 아직 CBT수준의 검증만 거친 상태지만요. 메모리 요구량이 길찾기 노드수의 제곱에 비례하고 계산량은 최소 세제곱에 비례합니다만 노드수를 많이 줄여서 해결했습니다.


@ 원문은 카페 가입해야만 볼 수 있네요.

@ 지각의 압박에 원문을 찬찬히 읽진 못했는데, 원문의 알고리즘에는 복잡한 맵에서 길찾기가 실패하는 케이스가 있는 것 같습니다.
Locked