NPC서버의 몬스터 A* 길찾기 질문입니다.

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

Moderator: 류광

Locked
비회원

NPC서버의 몬스터 A* 길찾기 질문입니다.

Post by 비회원 »

안녕하세요. GPG여러분들.

질문을 하나 여쭙고 싶어 글 남깁니다.

다름이 아니라, NPC서버내에서 몬스터의 A*를 이용하여 이동에 관한 부하때문에 질문드립니다.

맵은 2차원배열의 타일맵(동적맵이며 흐름에따라 타일의 이동가능/장애물이 바뀜) 이며 몬스터(시작좌표)가 유

저의 좌표(목표지점)까지의 거리를 A*로 연산하여 최단거리를 탐색후에 이동카운트(타일의 이동가능한 개수)

의 개수만큼 이동하는 형식으로 만들었습니다. 문제는 몬스터(시작좌표) 유저의 좌표(목표좌표)간의 타일간의

거리가 길 경우 엄청난 연산부하때문에 문제가 야기되더군요.

그래서 몬스터의 시야값을 주어 해당 시야내에 유저케릭이 포함 되었을 경우 A*로 길찾기를 하려구 하니

시야가 포함이 안되어 있을때의 몬스터의 이동이 AI가 아닌 순수 랜덤이동으로 되어 어처구니없는 이동으로

포기를 하였습니다.

혹시 이와같은 문제를 해결하신 분이나 좋은 방향을 알려주시면 정말 감사드리겠습니다.
비회원

Post by 비회원 »

NPC를 클라이언트에 배정해주고 길찾기는 클라에서 해주는 방식은 어떨까요?
비회원

Post by 비회원 »

무조건 A*알고리즘을 사용하지 말고

특정 조건의 경우에 A*를 사용하도록 하면 많이 줄어들것 같습니다.

간단하게 하자면

타겟을 향해 일직선으로 움직였을때 타겟에 도달하는 경우도 상당히 많이 있으므로

일직선으로 이동중 앞에 장애물이 있는 경우에만 사용하거나 하는식으로

A*를 사용하는 빈도수를 줄이는게 제일 좋을것 같습니다
dell
Posts: 65
Joined: 2008-12-16 23:32

Post by dell »

NPC 의 전체 숫자가 어느정도인지는 모르겠지만
스타크래프트의 예를 들어서 생각해보면

최대길찾기(저글링으로 가득채음) 400*8 = 3,200 마리의 유닛이 A* 로 길찾기를 해도
크게 버벅이지 않는 모습을 보여줍니다. 여기에는 유닛과 유닛간의 충돌까지 포함된 숫자입니다.
그다지 높지않은 사양의 컴퓨터에서 3,200 마리의 유닛이 게임로직과 화면그리기를 포함하고도
끊기지 않는 길찾기를 수행해줍니다.
(스타크래프트는 모든 유닛이 개별적인 길찾기를 수행합니다.)

몇가지 노하우는.

1. 명령이 들어왔을때 몽땅 길찾기를 하는것이 아닌 UpdateManager 가 적당선에서 길찾기
프로세스를 나눠서 한다.

2. 서로 다른 해상도의 A* Grid 를 가지고 있어서 큰 Grid 에서 길을 못찾을때만
더 낮은 해상도의 Grid 로 진입한다.
큰 Grid 해상도에서 길찾기가 성공함은 그냥 직선으로 가도 된다는 뜻이다.

AI 최적화는 많은 방법이 있지만, 정말로 매우 어려운 분야임에 틀림 없습니다.

사실 지금 생각해도 스타크래프트는 분명 명품게임에 틀림 없습니다.

다른 방법은 그냥 상용 AI 미들웨어를 구입하는 방법이고.
상용 AI 미들웨어 구입을 추천하고 싶기는 합니다.
비회원

질문자 입니다!

Post by 비회원 »

질문자 입니다.

답변해주신 분들께 감사합니다.

dell님께서 말해주신 내용중에 질문이 있는데

직선거리의 서로다른 해상도의 큰grid라면 블럭의 단위를 1/1에서 3/3등으로 크게 잡구 A*를 실행한다는 말인가요?

만약 그렇다면

맵의 특성상 이동불가의 블럭이 많을 경우에는 큰grid의 역할이 상대적으로 많이 부족할거 같은데 이것의 해결

방법은 없을까요?
dell
Posts: 65
Joined: 2008-12-16 23:32

Post by dell »

Image

위의 이미지처럼 일단 Astar 알고리즘을 시작할때는 커다란 덩어리로 만들어진
뭉텅뭉텅한 그리드에서 알고리즘을 굴립니다.

그렇게 해서 "러프" 한 선분을 얻어냅니다.
위의 그림에서는 가운뎃 부분에서 "어딘지는 모르지만 장애물이 있습니다."
그래서 가운데 장애물부분에 대해서는 좀더 세부적으로
길찾기를 수행합니다.

즉 일단 뭉텅뭉텅한 그리드 단계에서 길찾기를 수행하고,
뭉텅뭉텅한 그리드단계에서 충돌한 부분에 대해서는 또다시 세부적으로 길찾기를 수행합니다.

이런 최적화가 효과를 보기 위해서는 무슨일을 해야할까요?

당연한 일이지만 "레벨디자인" 단계에서 맵이 최적화 되어야 합니다.

RTS 의 맵을 보시면 아시겠지만 미로같은 맵은 대부분 없으며,
잘못해서 유닛이 갇혀서 헤맬수 있는 U,C, 형 장애물이 없습니다.

물론 길찾기 Grid 는 아티스트와 연관이 있어서 뭐라고 딱 맞추기는 힘들지만
가급적이면 레벨디자인 초기단계부터 길찾기가 쉬운 형태로 만드는것이 Best 이기는 합니다.
비회원

답변 정말 감사합니다.

Post by 비회원 »

답변해주신 분들께 진심으로 감사드립니다.

바쁜시간 쪼개시며 그림까지 보여주신 dell님께도 진심으로 감사드립니다.

명쾌한 답변 이었습니다. 꾸벅~
Locked