[게임 AI] 양보하는 에이전트 만들기

개요

양보하는 에이전트를 통해 길찾기 도중 에이전트끼리 겹치지 않게 한다.

길찾기를 하는 에이전트끼리 겹치지 않게 하기위해 양보하는 방법을 선택하였다.
결론만 말하자면 이는 실패한 방법이다. 어떤 아이디어로 개발을 했고, 어째서 실패한 알고리즘이라고 생각하는지 알아보자.

설명

어떤 알고리즘으로 에이전트의 겹침을 해결했는지 알아보자.

길찾기 알고리즘을 통해 나온 결과만으로 에이전트를를 제어하면, 동일한 경로를 가진 에이전트끼리는 겹치게 된다.
에이전트들의 경로가 겹치게 되면, 목적지인 하나의 타일위에 여러개의 에이전트끼리 뭉쳐지게 된다.

이러한 현상을 회피하고자 필자가 선택한 방법은 ‘하나의 타일엔 하나의 에이전트만 올라갈 수 있다.’라는 전제를 설정하는 것이었다.

하나의 타일엔 하나의 에이전트만 올라갈 수 있다

타일에 ‘점유’라는 플래그를 만들고, 평소엔 false로 설정한다. 만약 에이전트가 타일위에 올라서 있으면 ‘점유’플래그를 true로 설정한다.
그리고 에이전트는 이동하기 전에 항상 이동하려는 타일이 점유되어있는 타일인지 아닌지를 검사한다.

만약 점유되어있는 타일이라면, 그 타일위엔 다른 에이전트가 올라가있다는 의미이므로 그 타일로 움직이지 않는다. 점유되어 있지 않다면 아무런 에이전트도 올라와있지 않다는 의미이므로 움직일 타일의 점유 플래그를 true로 변경한 후에 움직인다.

에이전트가 서있는 타일과, 에이전트가 이동하려는 타일의 점유 플래그는 항상 true로 설정되어있어야 한다. 다음으로 이동할 타일을 점유하지 않으면, 그 타일로 이동하려는 에이전트가 둘 이상일경우 겹치게 된다.

에이전트가 이동을 마치게 되면 이동하기 전에 서 있던 타일의 점유 플래그를 false로 설정하여서 다른 에이전트들이 그 타일 위로 이동할 수 있도록 한다.

이동하려는 타일이 점유되어 있는 경우

이동하려는 타일이 점유되어 있다면, 그 타일로 움직이지 않아야 한다고 위에서 설명했다. 하지만 그렇다고 그 타일위로 지나가지 않는 경로를 새로 탐색하게 된다면 문제가 발생한다.

만약 여러 에이전트들이 이동하려는 목적지가 한 개의 입구를 가지고 있어서 에이전트들이 줄지어서 입구로 들어가고 있다고 가정하자. 이때 앞에서 두 번째로 이동중인 에이전트가 이동하려는 타일이 첫 번째 에이전트가 점유중이라면 어떻게 될까?

점유할때마다 새로운 길찾기를 하게 된다면, 앞에 있는 에이전트와 뒤에 있는 에이전트 사이에서 우왕좌왕 움직이게 될것이다.

때문에 이동하려는 타일이 점유되어 있다면 대기해야 한다. 점유되어있다는 의미는 에이전트가 이동중이라는 의미이고, 그 에이전트가 이동하고 나면 점유가 풀릴것이라는 의미이다. 따라서 앞에있는 에이전트가 곧 지나갈것을 기대하며 기다리면 된다.

이처럼 에이전트가 지나갈때까지 움직이지 않고 대기하는것에서 양보라고 이름지었다.

여기에서 점유되어있다는 의미는 에이전트가 이동중이라는 의미이기 때문에, 에이전트가 완전히 정지한 상태라면 그 타일은 점유가 아닌 장애물로 취급되어야 한다. 또, 이동하려는 타일이 장애물이라면 대기하는것이 아닌 즉시 새로운 경로를 찾아야 한다.

무조건 기다리기만 하면 되는가?

만약 앞에있는 에이전트의 이동속도가 매우 느리고, 앞에있는 에이전트가 지나가길 기다리는 에이전트의 이동속도가 매우 빠르다면 어떻게 될까?

뒤에있는 에이전트는 매우 느린 에이전트와 이동속도가 동일해져서 느릿느릿 움직이게 될것이다.
이를 해결하는 방법은, 에이전트의 이동속도가 일정속도보다 작다면, 타일을 점유하는것이 아닌 장애물로 취급하는것이 있다.
혹은 일정시간만큼 대기하였음에도 여전히 점유중이라면, 새로운 경로를 찾는 것이다.

필자는 후자를 선택했다. 하지만 이 방법에도 문제는 있었다.

에이전트끼리 마주보고 있다면 어떻게 되는가?

에이전트끼리 마주보고 있다면 똑같은 시간동안 대기하다가 새로운 경로를 찾는다. 만약 새로운 경로도 서로 마주보는 경로라면 두 에이전트가 서로 옆으로 비켜주면서 전진하지 못하는 문제가 생긴다.

서로 양보만 하다가 나아가지 못하는 모습이 종종 연출된다

이를 해결하기 위해서 일정시간 이상 기다렸음에도 여전히 점유중이라면, 한번 더 기다리거나 새로운 경로로 빠르게 이동하도록 했다.

https://youtu.be/odIw4yxAmIE?si=r4DFvTtGXSPuFfw5

나아가지 못하는 모습이 연출되긴 하지만, 빈도가 확연히 줄었다.

겹치지 않았는데 왜 실패한 알고리즘인가?

영상을 보면 알겠지만, 매우 부자연스럽다.
현실세계에선 맞은편에 다가오고 있는 사람이 있을때, 그 사람이 코앞까지 오고 나서야 몇초동안 노려본 뒤에 자리를 비켜주는 우스꽝스러운 모습은 볼 수 없다. (볼 수 없어야 한다.)

멈칫멈칫하며 움직이는것보단, 길을 막고있는 에이전트들이 비키게끔해서 그 사이를 비집고 지나가는것이 더 나은 움직임이라고 판단되었다.

따라서 이부분은 조종행동을 추가하여서 해결할것이다.

마치며

이번 포스팅은 아쉬움이 많아서 만든 포스팅이다.

나름 이 방법을 생각했을땐 훌륭한 아이디어라고 생각했는데, 그 모습이 예상한것보다 훨씬 볼품없었다.
하지만 그동안 사용한 시간이 아까워서 그 결과를 영상과 함께 남기고 싶어서 작성해보았다.

참고로 실패한 알고리즘이라고 판단한 이유는 위에 기술한 것 외에 더 있다.
만약 맵 중간에 장애물이 생성된다거나, 에이전트가 밀쳐져야 한다면 지금 알고리즘으로는 구현하기 매우 까다롭다.

그 외에도 에이전트가 이동하다가 속박되거나 기절해서 이동이 중지된다면, 점유한 타일을 어떻게 관리할것인지 고민이 많았다.

이러한 실패 하나하나가 성공의 밑거름이 될거라 굳게 믿으며 다른 방법을 고민해봐야겠다.