안녕하세요. GPG여러분들.
질문을 하나 여쭙고 싶어 글 남깁니다.
다름이 아니라, NPC서버내에서 몬스터의 A*를 이용하여 이동에 관한 부하때문에 질문드립니다.
맵은 2차원배열의 타일맵(동적맵이며 흐름에따라 타일의 이동가능/장애물이 바뀜) 이며 몬스터(시작좌표)가 유
저의 좌표(목표지점)까지의 거리를 A*로 연산하여 최단거리를 탐색후에 이동카운트(타일의 이동가능한 개수)
의 개수만큼 이동하는 형식으로 만들었습니다. 문제는 몬스터(시작좌표) 유저의 좌표(목표좌표)간의 타일간의
거리가 길 경우 엄청난 연산부하때문에 문제가 야기되더군요.
그래서 몬스터의 시야값을 주어 해당 시야내에 유저케릭이 포함 되었을 경우 A*로 길찾기를 하려구 하니
시야가 포함이 안되어 있을때의 몬스터의 이동이 AI가 아닌 순수 랜덤이동으로 되어 어처구니없는 이동으로
포기를 하였습니다.
혹시 이와같은 문제를 해결하신 분이나 좋은 방향을 알려주시면 정말 감사드리겠습니다.
NPC서버의 몬스터 A* 길찾기 질문입니다.
Moderator: 류광
-
- Posts: 65
- Joined: 2008-12-16 23:32
NPC 의 전체 숫자가 어느정도인지는 모르겠지만
스타크래프트의 예를 들어서 생각해보면
최대길찾기(저글링으로 가득채음) 400*8 = 3,200 마리의 유닛이 A* 로 길찾기를 해도
크게 버벅이지 않는 모습을 보여줍니다. 여기에는 유닛과 유닛간의 충돌까지 포함된 숫자입니다.
그다지 높지않은 사양의 컴퓨터에서 3,200 마리의 유닛이 게임로직과 화면그리기를 포함하고도
끊기지 않는 길찾기를 수행해줍니다.
(스타크래프트는 모든 유닛이 개별적인 길찾기를 수행합니다.)
몇가지 노하우는.
1. 명령이 들어왔을때 몽땅 길찾기를 하는것이 아닌 UpdateManager 가 적당선에서 길찾기
프로세스를 나눠서 한다.
2. 서로 다른 해상도의 A* Grid 를 가지고 있어서 큰 Grid 에서 길을 못찾을때만
더 낮은 해상도의 Grid 로 진입한다.
큰 Grid 해상도에서 길찾기가 성공함은 그냥 직선으로 가도 된다는 뜻이다.
AI 최적화는 많은 방법이 있지만, 정말로 매우 어려운 분야임에 틀림 없습니다.
사실 지금 생각해도 스타크래프트는 분명 명품게임에 틀림 없습니다.
다른 방법은 그냥 상용 AI 미들웨어를 구입하는 방법이고.
상용 AI 미들웨어 구입을 추천하고 싶기는 합니다.
스타크래프트의 예를 들어서 생각해보면
최대길찾기(저글링으로 가득채음) 400*8 = 3,200 마리의 유닛이 A* 로 길찾기를 해도
크게 버벅이지 않는 모습을 보여줍니다. 여기에는 유닛과 유닛간의 충돌까지 포함된 숫자입니다.
그다지 높지않은 사양의 컴퓨터에서 3,200 마리의 유닛이 게임로직과 화면그리기를 포함하고도
끊기지 않는 길찾기를 수행해줍니다.
(스타크래프트는 모든 유닛이 개별적인 길찾기를 수행합니다.)
몇가지 노하우는.
1. 명령이 들어왔을때 몽땅 길찾기를 하는것이 아닌 UpdateManager 가 적당선에서 길찾기
프로세스를 나눠서 한다.
2. 서로 다른 해상도의 A* Grid 를 가지고 있어서 큰 Grid 에서 길을 못찾을때만
더 낮은 해상도의 Grid 로 진입한다.
큰 Grid 해상도에서 길찾기가 성공함은 그냥 직선으로 가도 된다는 뜻이다.
AI 최적화는 많은 방법이 있지만, 정말로 매우 어려운 분야임에 틀림 없습니다.
사실 지금 생각해도 스타크래프트는 분명 명품게임에 틀림 없습니다.
다른 방법은 그냥 상용 AI 미들웨어를 구입하는 방법이고.
상용 AI 미들웨어 구입을 추천하고 싶기는 합니다.
-
- Posts: 65
- Joined: 2008-12-16 23:32
위의 이미지처럼 일단 Astar 알고리즘을 시작할때는 커다란 덩어리로 만들어진
뭉텅뭉텅한 그리드에서 알고리즘을 굴립니다.
그렇게 해서 "러프" 한 선분을 얻어냅니다.
위의 그림에서는 가운뎃 부분에서 "어딘지는 모르지만 장애물이 있습니다."
그래서 가운데 장애물부분에 대해서는 좀더 세부적으로
길찾기를 수행합니다.
즉 일단 뭉텅뭉텅한 그리드 단계에서 길찾기를 수행하고,
뭉텅뭉텅한 그리드단계에서 충돌한 부분에 대해서는 또다시 세부적으로 길찾기를 수행합니다.
이런 최적화가 효과를 보기 위해서는 무슨일을 해야할까요?
당연한 일이지만 "레벨디자인" 단계에서 맵이 최적화 되어야 합니다.
RTS 의 맵을 보시면 아시겠지만 미로같은 맵은 대부분 없으며,
잘못해서 유닛이 갇혀서 헤맬수 있는 U,C, 형 장애물이 없습니다.
물론 길찾기 Grid 는 아티스트와 연관이 있어서 뭐라고 딱 맞추기는 힘들지만
가급적이면 레벨디자인 초기단계부터 길찾기가 쉬운 형태로 만드는것이 Best 이기는 합니다.
답변 정말 감사합니다.
답변해주신 분들께 진심으로 감사드립니다.
바쁜시간 쪼개시며 그림까지 보여주신 dell님께도 진심으로 감사드립니다.
명쾌한 답변 이었습니다. 꾸벅~
바쁜시간 쪼개시며 그림까지 보여주신 dell님께도 진심으로 감사드립니다.
명쾌한 답변 이었습니다. 꾸벅~