Page 1 of 1

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

Posted: 2017-03-28 02:01
by lht94
rts 비슷한 게임을 만들고 있는데요


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

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

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

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

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

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

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

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

지금 잠정적으로 대각선으로 가야할경우에는 현재 타일의
위나 오른쪽도 대각선 타일을 선점할때 같이 선점하고 대각선 타일 중앙 근처에 오면 위나 오른쪽은 선점을 해제하는 방식을
생각하고는 있는데

구글 뒤져보니깐 사각형으로 인접 agent랑의 충돌을 검사해서
http://gpgstudy.com/forum/viewtopic.php?t=14400 (제일 길고 자세하게 의견 남겨주신 댓글)
충돌했을경우에는 기다린다? 뭐 이런식의 의견을 보았는데
이게 도대체 무슨말인지 이해가안되네요..

10년이나 지났지만 저 댓글을 남기신분께 이야기를 들을수 있다면 얼마나 좋을까요 ㅎㅎㅎ

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

Posted: 2017-03-28 12:21
by 류광
언급하신 글이 http://gpgstudy.com/forum/viewtopic.php?p=78933#p78933 인거죠?

'선점'의 사전적 정의를 따른다면, A가 한 타일을 선점한 상태에서는 B가 그 타일을 선점할 수 없어야 합니다. A가 그 타일을 지나가서 선점을 푼 후에야 비로소 B가 그 타일을 선점할 수 있게(그리고 경로의 다음 칸을 선점하지 못하면 제자리에 머무르게) 한다면 자연스럽게 A가 먼저 지나가길 기다렸다가 B가 이동하는 결과가 나겠지요. 아마 그런 이야기가 아닐까 짐작합니다.

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

Posted: 2017-03-28 19:47
by lht94
류광 wrote: 2017-03-28 12:21 언급하신 글이 http://gpgstudy.com/forum/viewtopic.php?p=78933#p78933 인거죠?

'선점'의 사전적 정의를 따른다면, A가 한 타일을 선점한 상태에서는 B가 그 타일을 선점할 수 없어야 합니다. A가 그 타일을 지나가서 선점을 푼 후에야 비로소 B가 그 타일을 선점할 수 있게(그리고 경로의 다음 칸을 선점하지 못하면 제자리에 머무르게) 한다면 자연스럽게 A가 먼저 지나가길 기다렸다가 B가 이동하는 결과가 나겠지요. 아마 그런 이야기가 아닐까 짐작합니다.
류광님 댓글 정말 감사합니다.
네 저도 그렇게 이해했는데
충돌은 어떻게 해결할지에 대한 의문이 안풀려서요

# *
A @ B

A가 *쪽을 선점한 바로 후에 B가 @를 선점해서 같이 이동하게되면

A는 현재 A의 타일과 *의 타일로 가는 도중에 B는 현재 B의 타일과 @의 타일로로 가는 도중에
박스 충돌이 일어납니다, (A, B 각각의 AGENT 박스크기가 타일의 크기라 가정하면요)
그런데 의견 올리신분의 내용에서는 박스충돌시 무조건 기다리게 하라하셨는데 그부분이 이해가 안되서요..



우선 저는 잠정적으로
A가 *를 선점해서 이동하려면 @와 #도 같이 선점해서 *쪽에 도착하면 #와 @ 타일의 선점은 해제하는 식으로 해야 할거라
결론을 내렸는데 제가 놓치는게 무엇인지 알고싶어서 ㅠㅠ

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

Posted: 2017-03-30 12:47
by 류광
정답이 있는 문제는 아닌 것 같고요. 제 생각에 타일 선점은 그냥 두 유닛이 동시에 같은 타일에 도달하려는 사고를 방지하는 목적으로만 사용하면 충분할 것 같고, 그와는 별도로 두 유닛이 충돌했을 때 누구에게 우선권을 줄 것인지에 대한 방침을 정해야 하지 않을까요? 이를테면 더 중요한(건설 비용이 큰?) 유닛이 먼저 지나가게 하는 등으로요.

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

Posted: 2017-07-14 16:59
by mouse
류광 wrote: 2017-03-28 12:21 언급하신 글이 http://gpgstudy.com/forum/viewtopic.php?p=78933#p78933 인거죠?

'선점'의 사전적 정의를 따른다면, A가 한 타일을 선점한 상태에서는 B가 그 타일을 선점할 수 없어야 합니다. A가 그 타일을 지나가서 선점을 푼 후에야 비로소 B가 그 타일을 선점할 수 있게(그리고 경로의 다음 칸을 선점하지 못하면 제자리에 머무르게) 한다면 자연스럽게 A가 먼저 지나가길 기다렸다가 B가 이동하는 결과가 나겠지요. 아마 그런 이야기가 아닐까 짐작합니다.
류광님께서 말씀하신 선점의 방식이 맞습니다.
한가지 더 덧붙이자면 선점을 하게 되면 유닛 위치의 타일에 선점 하게 되는 속성 값을 넣게 되는데 한개의 타일에 2개 이상의 유닛이 선점을 하는 경우도
나오게 됩니다.

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

Posted: 2017-07-14 17:03
by mouse
lht94 wrote: 2017-03-28 02:01
구글 뒤져보니깐 사각형으로 인접 agent랑의 충돌을 검사해서
http://gpgstudy.com/forum/viewtopic.php?t=14400 (제일 길고 자세하게 의견 남겨주신 댓글)
충돌했을경우에는 기다린다? 뭐 이런식의 의견을 보았는데
이게 도대체 무슨말인지 이해가안되네요..

10년이나 지났지만 저 댓글을 남기신분께 이야기를 들을수 있다면 얼마나 좋을까요 ㅎㅎㅎ
선점에 대한 내용은 위에 류광님의 답변의 글에 덧붙여서 올려 놓았고요..
저도 스타1 과 거의 동일한 엔진을 만들었는데 저 위의 글을 한 10번은 읽어 봤던것 같습니다.
매우 자세하게 써주신 글이라 이 자리를 빌어 저글을 올려주신 분께 감사의 말씀 전합니다.

감사합니다.

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

Posted: 2017-08-14 03:11
by lht94
mouse wrote: 2017-07-14 17:03
lht94 wrote: 2017-03-28 02:01
구글 뒤져보니깐 사각형으로 인접 agent랑의 충돌을 검사해서
http://gpgstudy.com/forum/viewtopic.php?t=14400 (제일 길고 자세하게 의견 남겨주신 댓글)
충돌했을경우에는 기다린다? 뭐 이런식의 의견을 보았는데
이게 도대체 무슨말인지 이해가안되네요..

10년이나 지났지만 저 댓글을 남기신분께 이야기를 들을수 있다면 얼마나 좋을까요 ㅎㅎㅎ
선점에 대한 내용은 위에 류광님의 답변의 글에 덧붙여서 올려 놓았고요..
저도 스타1 과 거의 동일한 엔진을 만들었는데 저 위의 글을 한 10번은 읽어 봤던것 같습니다.
매우 자세하게 써주신 글이라 이 자리를 빌어 저글을 올려주신 분께 감사의 말씀 전합니다.

감사합니다.
아 답변을 이제 확인했네요.. 감사합니다.

사실 길찾기는 대강 구현을 하였는데 아직 부족한 부분이 조금 있는듯하여

실례가 안된다면 스타 길찾기 관련해서 질문좀 해도될까요??

01050208308로 문자주신다면 감사하겠습니다

사례는 꼭하겠습니다