用于 pacman ghost 的 BFS

BFS for pacman ghost

这个问题困扰我好几天了。 我在这个论坛和 google 中搜索过没有任何运气的解决方案。 我的问题是我无法制作一个有效的 BFS 算法来管理 pacman ghost 的行为。我想我忽略了代码中的某些内容。 我会把代码贴在这里,如果你能帮助我,我将不胜感激:) pacman是2号,ghost是3号

Queue<Tile> path = new LinkedList<>();
Tile start = new Tile(canvas.g1.x, canvas.g1.y, 3);
Tile end = new Tile(canvas.pacman.x, canvas.pacman.y, 2);
start.distance = 1;
path.add(start);

while (!path.isEmpty()) {
    Tile current = path.remove();
    System.out.println(path.size());
    canvas.walls[current.y][current.x] = 0;
    if (canvas.walls[current.y][current.x] == canvas.walls[end.y][end.x]) {
        end = current;
        System.out.println("pacman found");
        break;
    }
    ArrayList<Tile> list = adyacent(current);
    for (Tile c : list) {
        if (c.distance == 0) {
            c.distance = current.distance + 1;
            path.add(c);
            canvas.walls[c.y][c.x] = 20;
            for (Tile v : path) {
                System.out.println("x: " + v.x + " / y: " + v.y + " / 
            distance: " + v.distance);
            }
        }
    }
}

int dist = end.distance;

System.out.println("Recolection ended, size: " + dist);

class 拼贴():

public class Tile {

    public int x;
    public int y;
    public int distance;
    public int personaje;

    public Tile(int x, int y, int personaje) {
        this.x = x;
        this.y = y;
        this.personaje = personaje;
        distance = 0;
    }
}

和方法 adyacent():

在这个方法中,我检查的数字是有墙的(每个都有不同的图纸))

public ArrayList<Tile> adyacent(Tile c) {

    ArrayList<Tile> surrounding = new ArrayList<>();
    int ant;
    ant = canvas.walls[c.y][c.x + 1];
    if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
            && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
            && (ant != 16)) {
        surrounding.add(new Tile(c.x + 1, c.y, 3));
    }
    ant = canvas.walls[c.y][c.x - 1];
    if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
            && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
            && (ant != 16)) {
        surrounding.add(new Tile(c.x - 1, c.y, 3));
    }
    ant = canvas.walls[c.y + 1][c.x];
    if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
            && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
            && (ant != 16)) {
        surrounding.add(new Tile(c.x, c.y + 1, 3));
    }
    ant = canvas.walls[c.y - 1][c.x];
    if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
            && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
            && (ant != 16)) {
        surrounding.add(new Tile(c.x, c.y - 1, 3));
    }
    return surrounding;
}

我观察到的是,它从未达到 System.out,其中我 return 路径的大小。 此外,在我看到队列大小的地方,它似乎是正确的,但是我看到 "x" 和 "y" 和 "distance" 的 System.out 每次都更大,很多更大。

我设置选中的瓷砖改变它的颜色,改变我在数组中得到的数字:0 是地板,20 是透明绿色。它仍然在中心,并开始越来越慢地工作。

忘了说它从来没有找到 pacman :( 谢谢!

今天早上我得到了启示,解决了我自己的问题。

我必须创建一个布尔数组来检查是否访问过图块,并创建一个用于距离的 int 数组。

使用布尔数组,我可以不再访问访问过的图块,因此算法可以完成。 使用距离数组,我能够比较距离以在第二次检查时取较小的距离。这样我就找到了路径。

更改代码中的一些内容使我能够使用两个数组来最终完成程序。

这是代码(变量名是西班牙语,因为我来自西班牙,它是为了 class,但我知道我应该用英语编码,而且我通常在制作自己的项目时这样做):

    package comecocos;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Ghost1Thread extends Thread {

    int x;
    int y;
    Juego canvas;
    Ventana ventana;
    boolean pause;
    int[][] control;
    int anterior;
    int acelerar;
    Pacman pacman;
    int ignorar;
    int salir;
    /*AUMENTA DE VELOCIDAD CUANDO PACMAN COME VARIOS PUNTOS*/

    public Ghost1Thread(Juego canvas, Ventana ventana) {
        this.canvas = canvas;
        this.ventana = ventana;
        this.pacman = canvas.pacman;
        this.control = canvas.paredes;
        pause = true;
    }

    @Override
    public void run() {
        while(true) {
            mover();
            canvas.repaint();
            try {
                sleep(acelerar);
            } catch (InterruptedException ex) {
                System.out.println("Error durmiendo.");
            }
        }
    }

    public void mover() {
        if (!pause) {
            if (canvas.bolitas < 100 && canvas.g1.owned == false) {
                acelerar = 200;
            } else if ((canvas.bolitas < 100 && canvas.g1.owned == true) || (canvas.bolitas >= 100 && canvas.g1.owned == true)) {
                acelerar = 450;
            } else if (canvas.bolitas > 100 && canvas.g1.owned == false) {
                acelerar = 300;
            }
            if (canvas.g1.owned == false) {
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
                canvas.g1.x = buscar(canvas.pacman.x, canvas.pacman.y).x;
                canvas.g1.y = buscar(canvas.pacman.x, canvas.pacman.y).y;
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 3;
            } else {
                if (canvas.pacman.x > canvas.g1.x) {
                    izquierda();
                } 
                if (canvas.pacman.x < canvas.g1.x) {
                    derecha();
                }
                if (canvas.pacman.y < canvas.g1.y) {
                    abajo();
                } 
                if (canvas.pacman.y > canvas.g1.y) {
                    arriba();
                }
            }
        }
    }

    public Casilla buscar(int x, int y) {
        this.x = x;
        this.y = y;
        Queue<Casilla> camino = new LinkedList<>();
        boolean [][] descubierto = new boolean[canvas.columnas][canvas.filas];
        int [][] distancias  = new int[canvas.columnas][canvas.filas];
        for (int i = 0; i < canvas.columnas; i++) {
            for (int j = 0; j < canvas.filas; j++) {
                descubierto[i][j] = false;
            }
        }
        for (int i = 0; i < canvas.columnas; i++) {
            for (int j = 0; j < canvas.filas; j++) {
                distancias[i][j] = 0;
            }
        }
        Casilla inicio = new Casilla(canvas.g1.x, canvas.g1.y, 3);
        Casilla fin = new Casilla(x, y, 2);
        inicio.distancia = 1;
        camino.add(inicio);
        while (!camino.isEmpty()) {
            Casilla actual = camino.remove();
            if (canvas.paredes[actual.y][actual.x] == canvas.paredes[fin.y][fin.x]) {
                fin = actual;
            }
            ArrayList<Casilla> lista = adyacente(actual);
            for (Casilla c : lista) {
                if (c.distancia == 0 && descubierto[c.x][c.y] == false) {
                    c.distancia = actual.distancia + 1;
                    descubierto[c.x][c.y] = true;
                    distancias[c.x][c.y] = c.distancia;
                    camino.add(c);
                }
            }
        }
        int dist = fin.distancia;
        camino.add(fin);
        while (!camino.isEmpty()) {
            Casilla actual = camino.remove();
            ArrayList<Casilla> lista = adyacente(actual);
            for (Casilla c : lista) {
                if (distancias[c.x][c.y] < dist) {
                    if (distancias[c.x][c.y] == 2){
                        return c;
                    } else {
                        dist = distancias[c.x][c.y];
                        descubierto[c.x][c.y] = false;
                        camino.add(c);
                    }
                }
            }
        }
        return fin;
    }

    public ArrayList<Casilla> adyacente(Casilla c) {
        ArrayList<Casilla> alrededor = new ArrayList<>();
        int ant;
        if (c.x > 0 && c.x < canvas.columnas - 1 && c.y > 0 && c.y < canvas.filas) {
            ant = canvas.paredes[c.y][c.x + 1];
            if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
                    && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
                    && (ant != 16)) {
                alrededor.add(new Casilla(c.x + 1, c.y, 3));
            }
            ant = canvas.paredes[c.y][c.x - 1];
            if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
                    && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
                    && (ant != 16)) {
                alrededor.add(new Casilla(c.x - 1, c.y, 3));
            }
            ant = canvas.paredes[c.y + 1][c.x];
            if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
                    && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
                    && (ant != 16)) {
                alrededor.add(new Casilla(c.x, c.y + 1, 3));
            }
            ant = canvas.paredes[c.y - 1][c.x];
            if ((ant != 7) && (ant != 8) && (ant != 9) && (ant != 11)
                    && (ant != 12) && (ant != 13) && (ant != 14) && (ant != 15)
                    && (ant != 16)) {
                alrededor.add(new Casilla(c.x, c.y - 1, 3));
            }
        }
        return alrededor;
    }

    private void arriba() {
        anterior = canvas.paredes[canvas.g1.y - 1][canvas.g1.x];
        if ((anterior != 7) && (anterior != 8) && (anterior != 9) && (anterior != 11)
                && (anterior != 12) && (anterior != 13) && (anterior != 14) && (anterior != 15)
                && (anterior != 16) && noFantasma(canvas.gh1[canvas.g1.y - 1][canvas.g1.x],
                        canvas.gh2[canvas.g1.y - 1][canvas.g1.x],
                        canvas.gh3[canvas.g1.y - 1][canvas.g1.x],
                        canvas.gh4[canvas.g1.y - 1][canvas.g1.x])) {//Si no hay muro ni otro fantasma
            canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
            canvas.g1.y = canvas.g1.y - 1;//Cambio fila
            canvas.gh1[canvas.g1.y][canvas.g1.x] = 3;//Dibulo
        } else if (anterior == 2) {
            if (canvas.g1.owned) {
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
                canvas.g1.x = 12;
                canvas.g1.y = 15;
                canvas.gh1[15][12] = 3;
                canvas.g1.owned = false;
                ventana.npuntuacion += 200;
            } else if (canvas.g1.owned == false) {
                if (canvas.vidas <= 1) {
                    canvas.vidas = 0;
                } else {
                    vidaMenos();
                }
                ventana.npuntuacion -= 200;
            }
        }
    }

    private void derecha() {
        try {
            anterior = canvas.paredes[canvas.g1.y][canvas.g1.x + 1];
        } catch (Exception e) {
            anterior = 17;
        }
        if ((anterior != 7) && (anterior != 8) && (anterior != 9) && (anterior != 11)
                && (anterior != 12) && (anterior != 13) && (anterior != 14) && (anterior != 15)
                && (anterior != 16) && noFantasma(canvas.gh1[canvas.g1.y][canvas.g1.x + 1],
                        canvas.gh2[canvas.g1.y][canvas.g1.x + 1],
                        canvas.gh3[canvas.g1.y][canvas.g1.x + 1],
                        canvas.gh4[canvas.g1.y][canvas.g1.x + 1])) {//Si no hay muro
            try {
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
                canvas.g1.x = canvas.g1.x + 1;//Cambio fila
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 3;//Dibulo
            } catch (Exception e) {
                canvas.g1.x = canvas.g1.x - 1;
                canvas.paredes[canvas.g1.y][canvas.g1.x] = 17;
                canvas.g1.x = canvas.g1.x - 27;
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 3;//Dibulo
            }
        } else if (anterior == 2) {
            if (canvas.g1.owned) {
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
                canvas.g1.x = 12;
                canvas.g1.y = 15;
                canvas.gh1[15][12] = 3;
                canvas.g1.owned = false;
                ventana.npuntuacion += 200;
            } else if (canvas.g1.owned == false) {
                if (canvas.vidas <= 1) {
                    canvas.vidas = 0;
                } else {
                    vidaMenos();
                }
                ventana.npuntuacion -= 200;
            }
        }
    }

    private void abajo() {
        anterior = canvas.paredes[canvas.g1.y + 1][canvas.g1.x];
        if ((anterior != 7) && (anterior != 8) && (anterior != 9) && (anterior != 11)
                && (anterior != 12) && (anterior != 13) && (anterior != 14) && (anterior != 15)
                && (anterior != 16) && noFantasma(canvas.gh1[canvas.g1.y + 1][canvas.g1.x],
                        canvas.gh2[canvas.g1.y + 1][canvas.g1.x],
                        canvas.gh3[canvas.g1.y + 1][canvas.g1.x],
                        canvas.gh4[canvas.g1.y + 1][canvas.g1.x])) {//Si no hay muro
            canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
            canvas.g1.y = canvas.g1.y + 1;//Cambio fila
            canvas.gh1[canvas.g1.y][canvas.g1.x] = 3;//Dibulo
        } else if (anterior == 2) {
            if (canvas.g1.owned) {
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
                canvas.g1.x = 12;
                canvas.g1.y = 15;
                canvas.gh1[15][12] = 3;
                canvas.g1.owned = false;
                ventana.npuntuacion += 200;
            } else if (canvas.g1.owned == false) {
                if (canvas.vidas <= 1) {
                    canvas.vidas = 0;
                } else {
                    vidaMenos();
                }
                ventana.npuntuacion -= 200;
            }
        }
    }

    private void izquierda() {
        try {
            anterior = canvas.paredes[canvas.g1.y][canvas.g1.x - 1];
        } catch (Exception e) {
            anterior = 18;
        }
        if ((anterior != 7) && (anterior != 8) && (anterior != 9) && (anterior != 11)
                && (anterior != 12) && (anterior != 13) && (anterior != 14) && (anterior != 15)
                && (anterior != 16) && noFantasma(canvas.gh1[canvas.g1.y][canvas.g1.x - 1],
                        canvas.gh2[canvas.g1.y][canvas.g1.x - 1],
                        canvas.gh3[canvas.g1.y][canvas.g1.x - 1],
                        canvas.gh4[canvas.g1.y][canvas.g1.x - 1])) {//Si no hay muro
            try {
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
                canvas.g1.x = canvas.g1.x - 1;//Cambio fila
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 3;//Dibulo
            } catch (Exception e) {
                canvas.g1.x = canvas.g1.x + 1;
                canvas.paredes[canvas.g1.y][canvas.g1.x] = 17;
                canvas.g1.x = canvas.g1.x + 27;
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 3;//Dibulo
            }
        } else if (anterior == 2) {
            if (canvas.g1.owned) {
                canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
                canvas.g1.x = 12;
                canvas.g1.y = 15;
                canvas.gh1[15][12] = 3;
                canvas.g1.owned = false;
                ventana.npuntuacion += 200;
            } else if (canvas.g1.owned == false) {
                if (canvas.vidas <= 1) {
                    canvas.vidas = 0;
                } else {
                    vidaMenos();
                }
                ventana.npuntuacion -= 200;
            }
        }
    }

    private boolean noFantasma(int f1, int f2, int f3, int f4) {
        if (f1 != 3 && f2 != 4 && f3 != 5 && f4 != 6) {
            return true;
        }
        return false;
    }

    private void vidaMenos() {
        canvas.vidas--;
        canvas.gh1[canvas.g1.y][canvas.g1.x] = 0;
        canvas.g1.x = 12;
        canvas.g1.y = 15;
        canvas.gh1[15][12] = 3;
        canvas.gh2[canvas.g2.y][canvas.g2.x] = 0;
        canvas.g2.x = 13;
        canvas.g2.y = 15;
        canvas.gh2[15][13] = 4;
        canvas.gh3[canvas.g3.y][canvas.g3.x] = 0;
        canvas.g3.x = 14;
        canvas.g3.y = 15;
        canvas.gh3[15][14] = 5;
        canvas.gh4[canvas.g4.y][canvas.g4.x] = 0;
        canvas.g4.x = 15;
        canvas.g4.y = 15;
        canvas.gh4[15][15] = 6;
        canvas.paredes[canvas.pacman.y][canvas.pacman.x] = 0;
        canvas.pacman.x = 13;
        canvas.pacman.y = 23;
        canvas.paredes[23][13] = 2;
    }
}

我也知道它可以做得更好,可能你们中的许多人会想要踢我的屁股......但我只有一个星期的时间来完成整个项目而且我在 java,所以我尽力了。 祝你有美好的一天:)