최적의 멀티플레이어 미로 생성 알고리즘

Question

저는 2~4명의 플레이어가 미로의 별도 진입점에 배치되어 목표 지점에 도달해야 하는 간단한 멀티플레이어 게임을 만들고 있습니다.일반적으로 미로를 생성하는 것은 매우 쉽지만 이 경우 게임의 목표는 다른 사람보다 먼저 목표에 도달하는 것이며 생성 알고리즘이 다른 플레이어보다 한 플레이어를 크게 선호하는 것을 원하지 않습니다.

그래서 저는 시작점에서 목표점까지 각 플레이어의 최적 경로가 평균 경로보다 10% 이상 더 많은 단계를 넘지 않는 미로 생성 알고리즘을 찾고 있습니다.이런 식으로 플레이어는 어느 정도 동등한 경쟁의 장에 있게 됩니다.누구든지 그러한 알고리즘을 생각해 낼 수 있습니까?

(나는 한 가지 아이디어를 가지고 있지만 잘 생각되지 않았고 최적이 아닌 것 같습니다. 답변으로 게시하겠습니다.)

Answer 1

freespace의 대답에 대한 대안은 무작위 미로를 생성한 다음 각 셀에 미로 끝에 도달하기 위한 이동 횟수를 나타내는 값을 할당하는 것입니다(끝에서 시작하기로 결정한 경우 두 가지를 동시에 수행할 수 있습니다). ').그런 다음 거리(아마도 해당 거리에 n개의 점이 있는 가장 높은 거리)를 선택하고 해당 값을 가진 사각형에 플레이어를 배치합니다.

Answer 2

먼저 플레이어의 위치와 목표, 동일한 길이의 경로를 선택한 다음 정의된 경로를 존중하는 미로를 만드는 것은 어떻습니까?경로가 교차하지 않으면 쉽게 작동할 것입니다.

Answer 3

나는 목표와 각 플레이어의 진입점을 설정한 다음 목표까지 각각의 비슷한 길이의 경로를 생성하는 방식으로 접근합니다.그런 다음 다른 플레이어의 경로에 연결되거나 분기가 경로에 다시 연결되지 않도록 주의하면서 이러한 경로를 따라 잘못된 분기를 추가하기 시작했습니다.따라서 본질적으로 모든 지점은 막 다른 골목입니다.

이렇게 하면 경로의 길이가 유사하다는 것을 보장할 수 있습니다.그러나 플레이어가 서로 상호 작용하는 것은 허용되지 않습니다.그러나 두 경로의 분기 진입점이 목표에서 비슷한 거리에 있도록 분기 사이에 링크를 만들어 이를 넣을 수 있습니다.그리고 이 지점에서는 재미와 이익을 위해 더 많은 막다른 골목을 분기할 수 있습니다. :-)

Answer 4

제가 생각해 낼 수 있는 가장 쉬운 해결책은 평소와 같이 전체 미로를 무작위로 생성한 다음 목표 지점과 플레이어 시작 지점을 무작위로 선택하는 것입니다.이 작업이 완료되면 각 시작점에서 목표까지의 최단 경로를 계산합니다.평균을 찾아 모든 경로가 적절한 여백 내에 있을 때까지 그보다 훨씬 위에 있는 경로를 '평활화'(장벽 제거/이동 - 어떻게 작동하는지 모르겠습니다) 시작합니다.또한 평균보다 현저히 낮은 항목을 선택하고 추가 장벽을 삽입하는 것도 가능할 수 있습니다.

Answer 5

중간 어딘가에서 출구 지점을 선택하세요

N 경로를 시작하여 원하는만큼 길어질 때까지 루프 당 각 경로에 1을 추가하십시오.

N개의 시작점이 있으며 모두 길이가 같습니다.

미로가 가득 찰 때까지 선에 추가 가지를 추가합니다.