Непоследовательные результаты в BFS в Java - PullRequest
Новая
       11

Непоследовательные результаты в BFS в Java

0 голосов
/ 07 июня 2018

Этот код отлично работает при первом создании нового лабиринта.Однако, когда BFS завершена и игра возобновляется (давая пользователю возможность играть снова), алгоритм работает не так эффективно.Конечная цель все еще достигнута, однако координаты x и y добавляются в массив, которые не являются частью кратчайшего пути.Я никогда не видел, чтобы мой первый прогон завершал поиск неправильно, как это делают последующие экземпляры.Кажется, что каждый раз, когда создается новый объект лабиринта, лабиринт остается затронутым предыдущим экземпляром.Любой вход? 

public class Maze {

    public static List<Integer> fx;
    public static List<Integer> fy;
    public static int listSize;
    public static Point p;

    public Maze(int x, int y) {

        p = getPathBFS(x, y);
        fx = new ArrayList<>();
        fy = new ArrayList<>();
        addPoint();

        System.out.print("next");
    }

    private static class Point {
        int x;
        int y;
        Point parent;

        public Point(int x, int y, Point parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }

        public Point getParent() {
            return this.parent;
        }
    }

    public static Queue<Point> q = new LinkedList<>();

    public static Point getPathBFS(int x, int y) {

        q.add(new Point(x, y, null));

        while (!q.isEmpty()) {
            Point p = q.remove();

            if (Level.cells[p.x][p.y] == 9) {
                return p;
            }

            if (isFree(p.x + 1, p.y)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x + 1, p.y, p);
                q.add(nextP);
            }

            if (isFree(p.x - 1, p.y)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x - 1, p.y, p);
                q.add(nextP);
            }

            if (isFree(p.x, p.y + 1)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x, p.y + 1, p);
                q.add(nextP);
            }

            if (isFree(p.x, p.y - 1)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x, p.y - 1, p);
                q.add(nextP);
            }    
        }
        return null;
    }

    public static boolean isFree(int x, int y) {
        if ((x >= 0 && x < Level.cells.length) && (y >= 0 && y < Level.cells[x].length) && (Level.cells[x][y] == 0 || Level.cells[x][y] == 9)) {
            return true;
        }
        return false;
    }

    public static void addPoint() {

        while ((p != null)) {

            System.out.println("x is " + p.x + " - y is " + p.y);

            fy.add(p.x);
            fx.add(p.y);
            p = p.getParent();
        }

    }

    public static int getListSize() {
        listSize = fx.size();

        return listSize;
    }
}

1 Ответ

0 голосов
/ 07 июня 2018

Кажется, что каждый раз, когда создается новый объект лабиринта, лабиринт остается под влиянием предыдущего экземпляра

Да, точно.Все ваши поля объявлены как статические.Статические поля являются общими для всех экземпляров, а не только для одного.Вы можете удалить ключевое слово static во всех (или почти во всех) экземплярах. 

public static List<Integer> fx;
public static List<Integer> fy;
public static int listSize;
public static Point p;

Похоже, ваш класс Level испытывает те же проблемы: 

Level.cells.length

I 'Я бы посмотрел на что на самом деле означает «статический» , потому что кажется, что вы используете его, не понимая его.

...