2 Pacmans의 길 찾기 알고리즘

Question

저는 Pacman을 구현하려고합니다. 그것은 잘 작동하지만, 지금까지 유령은 길 찾기를 사용하지 않고, 대신에 각 경로 교차점에서 무작위로 결정합니다. Pathfinding Algorithm For Pacman

:

그래서 내가 팩맨의 알고리즘을 찾는 경로에 대해 조금 읽고 여기에 SO에 내가 정말 좋은 답을 찾을 수 없음), 그래서 당신은 팩맨 게임을 승리하기가 정말 어려운 일이 아니다는 것을 상상할 수

대답은 http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter%204

모두 괜찮습니다. 제 구현의 Pacman에는 두 명의 다른 플레이어가 사용하는 두 개의 Pacmans가 있습니다. 따라서 경로 찾기 알고리즘을 적용하는 방법이 궁금해 지므로 유령이 항상 한 명의 플레이어를 쫓아 다니는 것은 아닙니다.

유령이 두 선수에게 어느 정도 공평하게 적용되도록 알고리즘을 수정하는 방법에 대한 의견이 있으십니까?

Answer 1

가장 쉬운 전략은 각 유령이 플레이어를 가장 가까이에서 쫓아 버리는 것입니다. 근접 거리는 맨해튼 거리 (길 찾기 질문에 링크가 있음) 또는 유클리드 거리 또는 플레이어의 경로 길이를 사용하여 계산할 수 있습니다. 마지막 옵션은 두 플레이어의 경로를 계산해야 함을 의미합니다. 이러한 모든 옵션을 시도하고 취향에 맞게 선택하십시오.

또한 쪽지에. pathfinding question에 답변하는 모든 사람들은 Dijkstra's algorithm을 언급하지 않았지만 BFS보다 느립니다. :) 그러나 모든 최단 경로를 한 번만 검색 할 수 있습니다. 즉, A * 또는 BFS를 구현하고 n 개의 개의 유령이 있다면 적어도 n 길 찾기 쿼리를 작성합니다. Dijkstra를 사용하면 플레이어에서 한 번만 시작할 수 있습니다. 그러나 모든 것이 달려 있습니다. 게임 필드가 너무 큰 경우 Dijkstra가 최선의 선택이 아닙니다. 시도해보십시오. 어쩌면 그것은 당신에게 어울릴 것입니다.

Answer 2

(나는 보지 못했다.) 모든 고스트 알고리즘이 유령과 '플레이어'의 상대적인 위치에 기초를두고 있다고 생각합니다. 음, 단순히 각각의 유령이 두 가지 중 어느 것을 염두에 두어야하는지 생각해보십시오. 플레이어는 알고리즘에서 '플레이어'로 사용합니다. ?이 유령에 따라 다를 두 선수의 상대 근접에 따라 달라 정해진 일정에 있어야 무작위 -

플레이 테스트에 대한 질문이 될 것입니다 정확히 무엇 "모든 너무 자주 * 여기에서 의미 결정 - 균일 한/푸 아송/다른 분포에?

당신은 '너무 좋음'과 '너무 어리 석다'라는 두 가지 행동을 피하고자 마음에 두십시오 ...

Answer 3

어느 하나의 팩맨에서 거리와 방향을 쿼리 할 수 ​​있다면 현재 하나의 팩을 쫓고있는 유령 (유령) 수와 유령 cman, 당신은 창의성이있는 아주 좋고 간단한 인공 지능을 만들 수 있어야합니다.

Answer 4

당신이 언급 한 길 찾기 알고리즘을 on this web page으로 계속 기록한 것 같습니다. 그러면 게임이 원본보다 더 사실이 될 것입니다. 유일한 문제는 얼마나 많은 유령이 특정 팩맨을 추적하는지 결정하는 것입니다. 이 동작에는 모든 유령이 한 명의 플레이어를 쫓는 시나리오가 포함되어야한다고 생각합니다. 따라서 1, 2, 3 또는 4 개의 유령이 플레이어를 쫓고 있는지를 결정하는 알고리즘이 필요합니다. 알고리즘은 플레이어 간의 포인트 차이를 기반으로 할 수 있습니다. 따라서 선두에있는 플레이어는 더 많은 유령에 쫓기게됩니다. 알고리즘은 플레이어가 남긴 생명의 수를 고려해야합니다. 따라서 리드에있는 플레이어의 생명력이 적다면 알고리즘은 리드에서 플레이어를 쫓는 유령의 수를 늘리는 것을 지연해야합니다.플레이어를 추적하는 유령 수의 변화 빈도는 너무 자주 발생해서는 안됩니다. 유령이 선수를 너무 많이 쫓아 내면 유령이 쫓기지 않는 것 같습니다. 언급 된 웹 페이지처럼, 좋은 행동을 취하는 것은 약간의 실험을 할 것입니다. 나는 처음에는 간단하게 유지하는 것이 중요하다고 생각합니다. 때로는 복잡하게 보이는 행동이 몇 가지 간단한 규칙을 사용하여 달성 될 수 있기 때문입니다. 행운을 빈다. 나는 네가 무엇을 생각하는지보고 싶다. 완료되면 링크를 게시하십시오!

Answer 5

"fairness"의 개념과 일치하는지는 모르겠지만 한 플레이어가 모든 4 개의 유령에게 더 가까운 목표물이되는 경우를 막기를 원하고 상상을 초월한다고 생각합니다. 그를 따라 다니고 다른 플레이어를 따라 다니며 다시는 다른 플레이어를 쫓아 가지 않습니다. 이것은 유령이 항상 가장 가까운 선수를 따라 가게하는 규칙의 가능한 결과 일 것입니다.

먼저 플레이어 1에게 2 개의 유령을 할당하고 플레이어 2에게는 2 개의 다른 유령을 할당 한 다음 대상을 추적하여 (그리고 자주마다 재 할당하는 것) 고려할 수 있습니다. 비록 내가 현실 세계에서 유령이라면, 모든 친구들과 내가 팩맨 1 대에 갇혀 있는지 상관하지 않겠다.

BFS 또는 Dijkstra 대신 깊이 검색을 사용하여 깊이 3 또는 4로 검색 트리의 나뭇잎에서 유령과 팩맨 사이의 직교 거리를 사용하고 가장 좋은 잎의 값을 루트까지 선택합니다. . 작은 선견 자의 경우, BFS와 Dijkstra에 비해 코드 작성이 더 빠르고 쉽습니다. 심도 제한 검색은 게임 보드에 나선형을 벗어나기 위해 필요한 이동 수가 3 또는 4보다 큰 나선형 통로가 없다고 가정하면 유령에 대한 지능적인 동작을 제공해야합니다. 알고리즘의 실행 시간은 BFS와 Dijkstra와 같이 커다란 보드와 커다란 보드에서 증가합니다. 다시 말하면 당신은 나선형 통로가 없다고 가정합니다.