Java 2D 게임에서 경로 찾기?

Question

본질적으로 제가 작업하고 있는 팩맨 클론 게임입니다.Enemy 클래스가 있고 이 클래스의 인스턴스 4개가 생성되었으며 모두 게임의 유령 4개를 나타냅니다.

모든 유령은 화면의 무작위 영역에서 시작한 다음 팩맨 캐릭터를 향해 나아가야 합니다.플레이어가 팩맨을 제어하고 이리저리 움직이면 팩맨을 따라가며 팩맨을 향해 가능한 가장 가까운 길을 가야 합니다.

(아직) 미로/장애물이 없으므로 전체 지도(400x400픽셀)가 열려 있습니다.

플레이어와 각 Ghost에 대해 X, Y, 이미지 너비 및 높이 속성을 검색할 수 있습니다.또한 충돌 감지 알고리즘이 이미 있으므로 걱정하지 않고 유령이 팩맨으로 가는 길을 찾는 것에 대해서만 걱정합니다.

Answer 1

좋은 경로 찾기 알고리즘의 경우 사용하십시오 ㅏ* 그러나 정교하고 효율적이며 효과적인 경로 검색이 필요하지 않은 간단한 게임의 경우 대상의 방향을 찾아서 캐릭터가 대상을 향해 이동하도록하는 것이 충분할 것입니다.

예를 들어, 슈도 코드에서 캐릭터를 움직이게하기로 한 결정 :

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

그렇습니다. 캐릭터는 가장 효율적인 움직임을 만들지는 않지만 게임 루프의 각 반복마다 대상에 가까워 질 것입니다.

80 년대 초반의 아케이드 게임은 아마도 정교한 경로 변형 알고리즘을 사용하지 않을 것이라고 생각합니다.

Answer 2

Pacman과 Ghost가 자유롭게 움직일 수있는 "큰 필드"라는 픽셀 그리드가 있다면 가장 짧은 경로는 쉬운 길입니다.

그러나 "가장 짧은 경로"는 항상 그래프 이론 문제를 해결하려고한다는 것을 의미합니다. (그래프, 일부 그래프 이론, 조정 행렬 등에 대한 지식을 가정하고 있습니다!)

위의 경우 각 픽셀을 그래프의 노드로 간주하십시오. 각 노드는 가장자리에 따라 이웃에 연결되며 각 모서리는 동일한 "무게"를 갖습니다 (위의 노드로 이동 "은"아래의 "아래"로 이동하는 것보다 느리지 않습니다).

그래서 당신은 이것을 가지고 있습니다 : ( "*"= node, "-, /, , |"= Edge)

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-* 

Pacman이 중앙에 있으면 다른 노드로 매우 쉽게 이동할 수 있습니다.

현실에 더 가까운 것은 다음과 같습니다.

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-* 

이제 Pacman은 대각선으로 움직일 수 없습니다. 중앙에서 오른쪽 하단으로 이동하려면 하나가 아닌 2 개의 "홉"이 필요합니다.

진행을 계속하려면 :

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

이제 중간의 노드에서 상단의 노드로 이동하려면 3 개의 홉이 필요합니다. 그러나 바닥으로 이동하려면 1 홉 만 필요합니다.

게임 보드 설정을 그래프로 번역하는 것은 쉽습니다. 각 "교차로"는 노드입니다. 두 교차로 사이의 경로는 가장자리이며, 그 경로의 길이는 그 가장자리의 무게입니다.

a*를 입력하십시오. 그래프를 구성하면 (Adjency Matrix 또는 노드 목록 사용) A* 알고리즘을 사용하여 가장 짧은 경로를 찾을 수 있습니다. 다른 알고리즘에는 dijkstra가 있습니다. 그리고 많은 다른 사람들! 그러나 먼저 그래프 측면에서 문제를 구성한 다음 노드 A (Pacman)에서 Node B (Ghost)로가는 방법을 사용하여 장난감을 가져야합니다.

도움이되기를 바랍니다!

Answer 3

매우 오랜 시간이 지났지 만 기억에서 Pac-Man의 유령은 길 찾기에 많은 도움이되지 않았습니다. 그들은 당신을 "발견"할 때까지 상당히 표준적인 무작위 미로 트래버스를 할 것입니다. 여기에는 당신을 향한 복도의 축을 따라 방해받지 않는 경로를 찾는 것이 포함되었고, 당신이 그들의 시야에서 사라질 때까지 직접 당신을 향해 움직일 것입니다. 임의의 패턴을 재개합니다. 더 높은 수준에서 Pac-Man은 유령이 "냄새"를 "냄새"하고 때로는 따라갈 수있는 보이지 않는 흔적을 잠시 동안 남겨 둘 것입니다.

Pac-Man이 전원을 켜면 알고리즘의 유일한 차이점은 그들이 당신을 발견했을 때 귀신이 당신을 향해 나아가는 대신 당신을 도망 칠 것입니다.

따라서, 진정한 경험을 위해서는 아마도 매우 정교한 길 찾기 알고리즘이 필요하지 않을 것입니다. 당신이 화려하고 싶다면 물론*를 구현할 수 있습니다.

Answer 4

적을 향해 직접 걷는 것이 시작이지만 미로를 추가할 때 유령이 굽은 길이나 막다른 골목에 갇히지 않도록 좀 더 똑똑한 길 찾기를 추가하고 싶을 것입니다.

다음 튜토리얼은 다운로드 가능한 예제와 함께 A*를 시작하기 위한 훌륭한 경량 가이드입니다.

타일 ​​기반 지도에서 경로 찾기

Answer 5

Pacman에서 모든 유령은 다른 체이스 알고리즘을 가졌습니다.

• Blinky-> 추격. 일반적으로 가장 짧은 길을 가고 따라하는 경향이 있습니다.
• 핑키 -> 매복. Pac-Man에게보다 원형 교차로를 취하는 경향이 있습니다. 치명적인. (Pinky와 Blinky는 방향을 선택할 때 다른 선택을하는 경향이 있습니다.
• Inky-> 괴물. 이 친구는 이상하게 행동합니다. 그는 보드를 상당히 무작위로 움직이지만 때로는 가까이에있을 때 쫓아갑니다.
• Clyde-> 바보. 무작위로 움직입니다. 별로 위협이 아닙니다.

유령들은 자신의 움직임에 흥미로운 패턴을 가지고 있습니다. 때로는 팩맨을 추구하고 "산란 모드"에 들어가는 미로의 각 모서리로 돌아가는 것을 동시에 멈추고 위험에 빠뜨릴 것입니다.

Algo에 대한 전체 설명이 있습니다 Pacman Dossier

문안 인사

기 illa

Answer 6

당신은 시작할 수 있습니다 * (별)를보고

그리고 여기에 페이지가 있습니다 다른 경로 찾기 알고리즘에 대한 링크가 있습니다.

편집] gah ... 뇌가 너무 느립니다 ...이 책에 대해 잊어 버렸습니다. 그것은 C 또는 C ++입니다 (나는 어느 것을 잊어 버리지만) 여전히 Java의 개념을 얻을 수 있습니다. 읽기가 가장 쉽지는 않지만 전반적으로 나쁘지는 않습니다. David M. Bourg, Glenn Seemann의 게임 개발자를위한 AI.

Answer 7

Pacman이 만든 모든 움직임에서 가장 짧은 경로 알고리즘을 생각합니다. 아주 좋은 구현입니다 Dijkstra의 알고리즘.

요약하려면 : 미로를 정점과 가장자리가있는 그래프로 시각화하십시오. 각 모서리에는 대기가 있습니다 (귀하의 경우 모든 가장자리는 무게가 동일합니다). 이 알고리즘은 즉각적인 도달 가능한 가장자리를 한 단계 아래로 내려서 소스 평점에서 베르티스를 대상으로 가장 짧은 경로를 찾습니다. 그런 다음 다음 위도에서 당신은 똑같이하고 목표에 도달 할 때까지 계속해야합니다. 도달 한 첫 번째 경로는 가장 짧은 경로입니다. Pacman이 이전 위치에있는 위치와 알고리즘에서 일부 상속자를 얻을 수 있도록 어떤 방향으로 이동하는지 고려 하여이 알고리즘에 많은 최적화가 수행 될 수 있습니다. 나는 모든 운동에서 각 유령에서 팩맨으로 가장 짧은 길을 찾아서 유령을 그 방향으로 움직일 것을 제안합니다. 결국 거리가 줄어들고 Pacman을 잡을 수 있습니다.

Pacman의 즉각적인 가장자리를 찾기 위해 사용할 수있는 또 다른 휴리스틱은 Ghosts에 의해 가능한 한 많은 정점을 덮으려고 노력합니다. 따라서 Pacman을 대상 평점으로 설정하는 대신 Pacman이 Pacman에 의해 즉시 도달 할 수있는 정점을 설정하여, 이용 가능한 유령이 Pacman의 Themajor Escape 경로를 덮고 그를 붙잡 으려고 노력할 것입니다.