我正在尝试在带有房间的地牢中找到一条小路,房间通过门连接起来。从一个房间到另一个房间总有一种方法。有人可以帮我构建一条路吗?我已经研究了路径搜索算法,但是由于只有一条可能的路径,所以它们很复杂,因此没有必要为房间增加重量。
这是我正在使用的Room对象:
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;
}
}
}
你的问题的标题包含'递归',所以我寻找一个递归的解决方案。对于每个房间,你可以说:如果我的一个邻居房间通往目标房间,那么我也是路径的一部分。当你的邻居都没有通往目标时,你也不会成为路径的一部分。
为了使它递归,我创建了一个从当前房间开始的新方法。访问的房间的总体路径和列表被定义为类变量,因此在调用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());
}
}
编辑:小优化:每个房间总是至少有一个邻居,即我们来自的房间,所以不需要检查是否有邻居。当迷宫只有一个房间但在这种情况下,开始和目标在之前已经测试过的情况下是一个例外。