내 게임에서 우리는 측면에서 집의 바닥을보고 영웅은 리프트를 취할 수 있습니다. 리프트는 화살표에 따라 항상 정확히 두 개의 리프트 쌍이 연결되어 있습니다. 영웅은 가로로 자유롭게 움직일 수 있지만 영웅이 세로로 움직일 수있는 유일한 방법입니다. 하우스 맵은 서로 다른 아이템과 가장 왼쪽, 맨 오른쪽 및 때로는 두 중간 위치 중 하나에 통과 할 수없는 벽이있는 무작위 11×5 그리드입니다.
내 질문 :지도가 항상 무작위 화되지만 항상 해결 가능하고 맨 아래 층의 왼쪽에서 시작하는 영웅이 항상 맨 위 층에서 위쪽을 가리키는 리프트를 통해지도를 떠날 수 있도록하려면 어떻게해야합니까?
가치가있는 것은 Lua 언어를 개발에 사용하고 있습니다. 정말 고마워!
답변
당신이하고 싶은 것은 모든 노드가 엘리베이터 위치가되도록 그래프를 만드는 것입니다. 그들 사이의 가장자리는 당신이 거기에서 걸거나 들어 올릴 수 있음을 의미합니다. 그래프를 작성하면 dfs / bfs를 사용하여 시작 노드에서 끝 노드로 이동할 수 있는지 확인할 수 있습니다.
위의 예를 사용하여 그래프가 어떻게 보이는지 그림을 만들었습니다. 녹색 원은 엘리베이터가 있고 녹색 선은 노드 간 이동을 의미합니다.
답변
현재 미로와 일반 미로의 차이점은 수직으로 인접하지 않은 연결이 있다는 것입니다. 당신이보고 있어야하는 것은 그래프 기반 미로 생성 알고리즘 이라고 생각합니다 . 이미 중간에 리프트 가 설치 되어 있지 않은 수직으로 정렬 된 바닥 그리드 셀 쌍이 인접 해 있다는 점에서 일반 2D 미로보다 “인접한 방”또는 “가능한 벽”이 더 필요합니다 . 명확한 리프트 모서리를 추가하면 우연히 다른 가능한 리프트 모서리가 삭제되는 그래프로이를 모델링 할 수 있습니다. 일부 알고리즘은 이것에 의해 혼동 될 수 있지만 다른 알고리즘은 혼동 될 수 없습니다.