Рекурсивный поиск пути в Arraylist комнат - PullRequest
Новая
       23

Рекурсивный поиск пути в Arraylist комнат

0 голосов
/ 30 апреля 2019

Я пытаюсь найти дорогу в темнице с комнатами, комнаты соединены дверями. Всегда есть только один способ попасть из одной комнаты в другую. Может ли кто-нибудь помочь мне построить путь? Я посмотрел на алгоритмы поиска пути, но они сложны для этого примера, потому что есть только один возможный путь, и поэтому нет необходимости добавлять вес в комнаты.

Это объект комнаты, который я использую: 

public Room(int id, Tile centerTile, ArrayList<Room> neighbours, ArrayList<Door> doors) 

  id = unique room id

  centerTile = center of the room.

  neighbours = list of neighbouring rooms

  doors = list of doors leading to the neighbouring rooms

Комнаты хранятся в Arraylist, называемом исследованными комнатами.

Это то, что я получил до сих пор, но оно не работает. 

package pathing;

import room.Room;
import room.RoomUtils;

import java.util.ArrayList;
import java.util.Iterator;

public class Path {

public static ArrayList<Room> findPath(Room start, Room target) {

    ArrayList<Room> frontier = new ArrayList<>();
    ArrayList<Node> visited = new ArrayList<>();
    ArrayList<Room> path = new ArrayList<>();

    frontier.add(RoomUtils.getRoomById(start.getId()));
    visited.add(new Node(RoomUtils.getRoomById(start.getId()), null));

    if (start.equals(target)) {
        path.add(RoomUtils.getRoomById(start.getId()));
    } else {
        Iterator frontierIterator = frontier.listIterator();
        while (frontierIterator.hasNext()) {
            Room front = (Room) frontierIterator.next();
            front = RoomUtils.getRoomById(front.getId());
            if (front.getNeighbours().size() > 0) {
                for (Room room : front.getNeighbours()) {
                    if (room.equals(target)) {
                        frontier.clear();
                        visited.add(new Node(RoomUtils.getRoomById(room.getId()), RoomUtils.getRoomById(front.getId())));
                        frontierIterator = frontier.listIterator();
                    } else {
                        frontier.remove(RoomUtils.getRoomById(front.getId()));
                        visited.add(new Node(RoomUtils.getRoomById(room.getId()), RoomUtils.getRoomById(front.getId())));
                        frontierIterator = frontier.listIterator();
                    }
                }
            }
        }

        Node startNode = visited.get(0);
        Node backtrackNode = getFrom(visited, target);

        if (backtrackNode != null && backtrackNode.getCurrent() != null) {
            path.add(backtrackNode.getCurrent());
        }

        while (backtrackNode != null && backtrackNode.getFrom() != null && !backtrackNode.equals(startNode)) {
            path.add(backtrackNode.getFrom());
            backtrackNode = getFrom(visited, backtrackNode.getFrom());
        }
    }
    return path;
}

private static Node getFrom(ArrayList<Node> nodes, Room from) {
    for (Node node : nodes) {
        if (node.getCurrent().equals(from)) {
            return node;
        }
    }
    return null;
}

private static class Node {
    private final Room current;
    private final Room from;

    public Node(Room current, Room from) {
        this.current = current;
        this.from = from;
    }

    public Room getCurrent() {
        return current;
    }

    public Room getFrom() {
        return from;
    }
}

}

1 Ответ

0 голосов
/ 02 мая 2019

Название вашего вопроса содержит «рекурсивный», поэтому я искал рекурсивное решение.Для каждой комнаты вы можете сказать: если одна из соседних комнат ведет к целевой комнате, то я тоже часть пути.Когда ни один из ваших соседей не ведет к цели, вы также не участвуете в пути.

Чтобы сделать его рекурсивным, я создал новый метод, который начинается с текущей комнаты.Общий путь и список посещенных комнат определяются как переменные класса, поэтому они все еще доступны после всех вызовов checkRoom. 

package pathing;

import java.util.ArrayList;
import java.util.List;

import room.Room;

public class Path {

    // list of all visited rooms to detect loops
    List<Room> visited = new ArrayList<>();
    // path from start to the current room
    List<Room> path = new ArrayList<>();
    Room target;
    boolean pathFound=false;

    public void checkRoom(Room current) {
        if(pathFound) {
            return;
        }
        if(visited.contains(current))
        {
            // we've been here before, we have detected a loop
            return;
        }
        path.add(current);
        visited.add(current);
        if (current.equals(target)) {
            pathFound=true;
        } else {
            // there are always neighbours (at least the room we come from
            for (Room room : current.getNeighbours()) {
                checkRoom(room);
                if(pathFound) {
                    return;
                }
            }
            // all neighbours processed without success
            path.remove(current);
        }
    }

    public static List<Room> findPath(Room start, Room target) {
        Path p=new Path();
        p.target=target;
        p.checkRoom(start);
        return p.path;
    }

    public static void main (String args[])
    {
        //      2 - 3 - 4
        //      |   |
        //      1 - 5
        //      |
        //      6 - 7 - 9
        //          |
        //          8
        Room room1=new Room(1,new ArrayList<Room>());
        Room room2=new Room(2,new ArrayList<Room>());
        Room room3=new Room(3,new ArrayList<Room>());
        Room room4=new Room(4,new ArrayList<Room>());
        Room room5=new Room(5,new ArrayList<Room>());
        Room room6=new Room(6,new ArrayList<Room>());
        Room room7=new Room(7,new ArrayList<Room>());
        Room room8=new Room(8,new ArrayList<Room>());
        Room room9=new Room(9,new ArrayList<Room>());
        room1.getNeighbours().add(room2);
        room1.getNeighbours().add(room5);
        room1.getNeighbours().add(room6);
        room2.getNeighbours().add(room1);
        room2.getNeighbours().add(room3);
        room3.getNeighbours().add(room2);
        room3.getNeighbours().add(room4);
        room4.getNeighbours().add(room3);
        room5.getNeighbours().add(room3);
        room5.getNeighbours().add(room1);
        room6.getNeighbours().add(room1);
        room6.getNeighbours().add(room7);
        room7.getNeighbours().add(room6);
        room7.getNeighbours().add(room9);
        room7.getNeighbours().add(room8);
        List<Room> path=Path.findPath(room1, room9);
        for(Room room:path)
            System.out.println("Room:"+room.getId());
        }
}

РЕДАКТИРОВАТЬ: небольшая оптимизация: в каждой комнате всегда есть по крайней мере один сосед, а именнономер, откуда мы родом, поэтому не нужно проверять, есть ли соседи.Единственное исключение возможно, когда в лабиринте есть только одна комната, но в этом случае начало и цель совпадают, что уже было проверено ранее.

...