[💬] 2d A* 알고리즘의 길찾기 충돌문제에 대해 질문드립니다.

[길찾기충돌(121.171)]

rts 비슷한 게임을 만들고 있는데요

길찾기에서 충돌처리를 어떻게 해야하는지 제 생각이 맞는지를 질문드리려 합니다.

우선 길을 찾고 현재타일에서 다음 타일로 가기전에 다음타일을 선점합니다. 그리고 이동시키는데

단순히 오른쪽 왼쪽 위 아래로 한칸 움직이는거는 문제가 안됩니다.

문제는 대각선에서 충돌인데요. 

A가 오른쪽 위 즉 대각선 방향으로 길을 찾았고 

그 방향의 타일을 선점하고 나자마자

A의 오른쪽이나 위 타일에(오른쪽이라 생각해보겠습니다.) B라는 또 다른 agent가  A의 오른쪽 타일을 길로 찾고 선점하면

A는 A의 오른쪽 위 타일로 가다가 B는 A의 오른쪽으로 가다가 서로 충돌하게 됩니다.

충돌을 무시하면 겹쳐서 어떻게든 각각의 목적지 타일로 가긴 할텐데 

겹치지 않게 만드려면 어떤식으로 생각해야할까요?

지금 잠정적으로  대각선으로 가야할경우에는 현재 타일의

위나 오른쪽도 대각선 타일을 선점할때 같이 선점하고 대각선 타일 중앙 근처에 오면 위나 오른쪽은 선점을 해제하는 방식을

생각하고는 있는데

구글 뒤져보니깐 사각형으로 인접 agent랑의 충돌을 검사해서 

http://gpgstudy.com/forum/viewtopic.php?t=14400 (제일 길고 자세하게 의견 남겨주신 댓글)

충돌했을경우에는 기다린다? 뭐 이런식의 의견을 보았는데

이게 도대체 무슨말인지 이해가안되네요..

[TD(121.167)]

A* 알고리즘의 타이브레이킹 문제는 게임마다 다를 수 밖에 없어.. 모든 agent가 하나의 그리드 정보를 공유하고 agent들 사이에 우선순위가 있어야 해결되는 문제로 보이네. 각자가 자기 편한대로 움직이면 부딪히지만 관리자가 모두의 움직임을 제어하면 누구도 부딪히지 않을 수 있어. 교통시스템이랑 똑같다. - dc App

[새우맨(222.120)]

패스 따라가다가 충돌이 일어나면(또는 자신의 다음 노드를 이미 다른 에이전트가 선점해버렸다면) 그자리에서 멈추고 바로 A* 길찾기를 다시 수행하는 건 어떨까요? 스타크래프트보면 그런 식인거 같더라고요

[작성자(121.171)]

TD님께 답변감사드립니다. 우선 모든 AGENT는 하나의 그리드맵을 공유하고 있습니다. 그건 타일매니저 객체에서 관리하는데요 AGENT사이에 우선순위라는게 무슨말씀인지 설명좀 해주실수 있으실까요? 제 상황에서 대각선으로 타일을 선점한 AGENT는 1순위고 오른쪽으로 타일선점한 AGENT는 2순위 아닌가요?

[작성자(121.171)]

새우맨님께 답변 감사드립니다. 네 그런데 지금 저 상황에서는 다음타일의 선점자체에는 문제가 없는데 다음타일로 가다가 충돌이 일어나는 경우에요. 단순히 다음타일만 선점할경우.. ㅠㅠ

[새우맨(222.120)]

음 생각을 살짝 바꿔서, 일어난 충돌을 해소하는게 아니라 애초에 충돌이 일어나지 않도록 만들어보세용. 에이전트는 모두 자신이 현재있는타일과 다음이동할타일을 모두 점유 표시를 해놔야돼요(실시간 갱신) 그리고 길찾기 알고리즘은 그 점유 그리드를 참고해서 패스를 찾아내고요. 에이전트가 그 패스를 따라가면서 다음 타일로 이동하기전에 해당 타일의 점유상태를

[새우맨(222.120)]

매번 새로 점검하도록 합니다.. 누군가 점유했다면 처음 출발당시 길찾기 했을 때와는 다르게 지금은 그리로 갈 수 없게된거져. 그래서 그자리에 멈춰서 현재위치에서부터 다시 목표지점으로 가는 새로운 경로를 탐색하면 되고요.

[작성자(121.171)]

새우맨님 답변감사합니다. 아예 충돌이 일어나지않게 해야겠네요

[TD(121.167)]

새우맨 방법은 하나 문제가 있는데, 드물게 레이스 컨디션이 생길 수 있다. 마주오던 사람이랑 서로 비키려고 갈팡질팡해 본 경험을 떠올리면 된다. 내가 말한 우선순위는 절대적으로 어떤 에이전트가 다른 에이전트보다 먼저 움직이도록 한다는 뜻이야. 지하철이나 엘리베이터에서 내리는 사람이 먼저고 타는 사람이 나중인 것처럼 말이지 - dc App

[TD(121.167)]

동기화 기법을 사용하면 별다른 노력없이 새우맨 방법이 통하는데, 성능 상에 문제가 생기겠지? 공간적으로 근접한 에이전트를 그룹화해서 각각에 우선순위를 부여하는 방법을 사용하기도 한다. 아예 혼자 동떨어져 있는 에이전트는 편하게 자기 갈 길 가면 되니까 - dc App

[작성자(121.171)]

TD님 답변 감사합니다