Cześć, piszę grę pacman w Javie Swing. Gra opiera się na mapie, która ma 30x30 znaków(załączona poniżej) oraz jeden element na ekranie zajmuje 16px. Chciałem zastosować szukanie pacmana przez potworki algorytmem BFS. Udało mi się zaimplementować ten algorytm (algorytm opiera się na wcześniej wspomnianej mapie), lecz problem pojawił się z implementacją wykonania znalezionej drogi.
Mapa:
##############################
#.............##.............#
#.#####.#####.##.#####.#####.#
#.#####.#####.##.#####.#####.#
#.#####.#####.##.#####.#####.#
#............................#
#.#####.##.########.##.#####.#
#.#####.##.########.##.#####.#
#.......##....##....##.......#
#######.#####.##.#####.#######
#.#####.##.#####.#
#.##..........##.#
#.##.###..###.##.#
#######.##.#......#.##.#######
#..........#......#..........#
#######.##.#......#.##.#######
#.##.########.##.#
#.##..........##.#
#.##.########.##.#
#######.##.########.##.#######
#.............##.............#
#.#####.#####.##.#####.#####.#
#.#####.#####.##.#####.#####.#
#....##................##....#
####.##.##.########.##.##.####
####.##.##.########.##.##.####
#.......##....##....##.......#
#.###########.##.###########.#
#............................#
##############################
Kod szukania i tworzenia ścieżki do pacmana:
public void playGame(Graphics2D g2d) {
int oldX, oldY;
if(dying) {
death();
} else {
oldX = pacmanX;
oldY = pacmanY;
movePacman();
if(oldX != pacmanX || oldY != pacmanY) {
findPath();
createPath();
}
if(!path.isEmpty()) {
moveGhost();
}
drawPacman(g2d);
drawGhost(g2d);
checkMaze();
}
}
public void findPath() {
int x, y;
q.clear();
q.addLast((ghostY/BLOCK_SIZE));
q.addLast((ghostX/BLOCK_SIZE));
while(!q.isEmpty()) {
y = q.removeFirst();
x = q.removeFirst();
if((y == pY) && (x == pX)){break;}
for(int i=-1; i<=1; i++) {
for(int j=-1; j<=1; j++) {
if((i != j) && (i-j!=2) && (j-i!=2)) {
if(pathData[y+i][x+j] == '.' || pathData[y+i][x+j] == ' ') {
if(i == -1) pathData[y+i][x+j] = 'd';
else if(i == 1) pathData[y+i][x+j] = 'u';
else if(j == -1) pathData[y+i][x+j] = 'r';
else if(j == 1) pathData[y+i][x+j] = 'l';
q.addLast(y+i);
q.addLast(x+j);
}
}
}
}
}
}
public void createPath() {
path.clear();
int i,j;
char c;
if(pathData[pY][pX] != '.') {
i = pY; j = pX;
while((i != (ghostY/BLOCK_SIZE)) || (j != (ghostX/BLOCK_SIZE))) {
c = pathData[i][j];
path.addLast(i*BLOCK_SIZE); // Y
path.addLast(j*BLOCK_SIZE); // X
if(c == 'd') {
i++;
} else if(c == 'u') {
i--;
} else if(c == 'r') {
j++;
} else if(c == 'l') {
j--;
}
}
}
for(i=0; i<N_BLOCKS; i++) {
for(j=0; j<N_BLOCKS; j++) {
pathData[i][j] = levelData[i][j];
}
}
}
public void moveGhosts() {
System.out.println(path.toString());
ghostX = path.removeLast();
ghostY = path.removeLast();
}
Po odpaleniu otrzymuję ścieżkę:
[368, 224, 368, 208, 352, 208, 336, 208, 320, 208, 320, 192, 320, 176, 320, 160, 304, 160, 288, 160, 272, 160, 256, 160, 240, 160, 224, 160, 208, 160, 192, 160, 176, 160, 176, 176, 176, 192, 176, 208, 176, 224, 192, 224, 208, 224],
która jest prawidłowa, lecz jeżeli te wartości ze ścieżki przypiszę bezpośrednio jako nowa pozycja potworka (ghostX = path.removeLast();ghostY = path.removeLast();) porusza się on bardzo szybko, ponieważ porusza się on w każdym ruchu o 16px. Próbowałem nawet z porozbijaniem poniższej ścieżki na ruchy 1px, co dało mi upragniony efekt, lecz tylko jeżeli pacman nie zmienia swojej pozycji w przypadku zmiany pozycji dzieje się dokładnie to samo co wcześniej, czyli ruchy wykonywane są co 16px.
Przykład:
**Pogrubionym tekstem oznaczyłem moment, kiedy pacman się nie rusza i ścieżka jest wykonywana poprawnie, czyli px po px.
ghostX: 224, ghostY: 208
ghostX: 224, ghostY: 207
ghostX: 224, ghostY: 206
ghostX: 224, ghostY: 205
ghostX: 224, ghostY: 204
ghostX: 224, ghostY: 203
ghostX: 224, ghostY: 202
ghostX: 224, ghostY: 201
ghostX: 224, ghostY: 200
ghostX: 224, ghostY: 199
ghostX: 224, ghostY: 198
ghostX: 224, ghostY: 197
ghostX: 224, ghostY: 196
ghostX: 224, ghostY: 195
ghostX: 224, ghostY: 194
ghostX: 224, ghostY: 193
ghostX: 224, ghostY: 192
ghostX: 224, ghostY: 191
ghostX: 224, ghostY: 190
ghostX: 224, ghostY: 189
ghostX: 224, ghostY: 188
ghostX: 224, ghostY: 187
ghostX: 224, ghostY: 186
ghostX: 224, ghostY: 185
ghostX: 224, ghostY: 184
ghostX: 224, ghostY: 183
ghostX: 224, ghostY: 182
ghostX: 224, ghostY: 181
ghostX: 224, ghostY: 180
ghostX: 224, ghostY: 179
ghostX: 208, ghostY: 176
ghostX: 192, ghostY: 176
ghostX: 176, ghostY: 176
ghostX: 160, ghostY: 176
ghostX: 160, ghostY: 192
ghostX: 160, ghostY: 208
ghostX: 160, ghostY: 224
ghostX: 160, ghostY: 240
ghostX: 160, ghostY: 256
ghostX: 160, ghostY: 272
ghostX: 160, ghostY: 288
ghostX: 160, ghostY: 304
ghostX: 160, ghostY: 320
ghostX: 144, ghostY: 320
ghostX: 128, ghostY: 320
ghostX: 112, ghostY: 320
ghostX: 112, ghostY: 336
ghostX: 112, ghostY: 352
ghostX: 112, ghostY: 368
ghostX: 128, ghostY: 368
ghostX: 112, ghostY: 368