在不同楼层的路径搜索A到B

Question

我有一个问题，我将考虑什么算法或方法来解决从点A到点B的路径的特定问题，其中两个点不在同一平面上(位于院落的不同楼层/楼层-可能不在同一建筑物上)。

我正在考虑A*和Dijkstra's算法。然而，基于这个算法，这只是(如果我错了，请纠正我)只关注一个地图图。对于上述两种算法，具有不同的地图图(由于多个楼层和许多建筑物)可能会有不同的故事。

为了应对这一困难，我设计了一种格式来处理我所有的地图，以保持数据的一致性。在每个地图中存在建筑物名称、楼层编号和每个楼层可能具有的部分的数据，以及与楼层平面图(转换为二维单字符数组)的数据。例如(两个贴图位于不同的文件中)：

//MainFloor1             //MainFloor2
Main                    Main
1st                     2nd
1:Wall                  1:Wall
2:Door                  2:Door
3:Elevator              3:Elevator
#                       4:Room1
1111441111              5:Room2
1        1              #
1        1              1111441111
1        1              1552  2441
1111221111              1551  1441
#                       1551  1441
//End-MainFloor1        1111221111
                        #
                        //End-MainFloor2

从给定的地图中，如果我想要考虑从点A(位于MainFloor1的lest的第一个“2”下方)到点B(从MainFloor2的左上角开始的第一个“4”)，将返回结果。

// X is the path from Point A to Point B
1111X41111 1111X41111
1   X    1 1552XXXB41 
1   X    1 1551  1441 
1   X    1 1551  1441 
1111A21111 1111221111

为了从给定的地图输入中产生这样的结果，我应该考虑或采取什么方法？

谢谢

Answer 1

BFS和其他算法都是在graphs上工作的算法。您的问题可以看作是一个图，其中，如果两个节点(顶点)相邻且位于同一楼层，则在它们之间存在一条边；如果两个节点(顶点)表示同一电梯，但位于不同楼层，则可以将其视为或。

请注意，您可以显式地在内存中构建图形，但您不必这样做-您可以从探路者的角度简单地将其视为一个图形。

Answer 2

// X is the path from Point A to Point B

1111B11111
1   X    1
1   X    1
1   X    1
1111A11111

这是一个仅适用于单层的解决方案，

这个机器人只能在4个方向上移动。

所提出的解决方案是使用禁忌列表的广度优先搜索

使用这些类：https://stackoverflow.com/a/15549604/2128327

class Floor
{
    public ArrayList<Point> points;

    public int minX, minY, maxX, maxY;

    public Floor ()
    {
        p = new ArrayList<Point>();
    }
}

单层解决方案：

class PathFinder
{
    public static Floor floor;

    public static Point location;

    public static void search (Floor floor, Point dest, Point initial_location)
    {
        QueueSet<Point> fringe = new QueueSet<Point>();

        ArrayList<Point> taboo = new ArrayList<Point>();

        boolean solution_found = false;

        Point p = null;

        fringe.enqueue(initial_location);

        while (fringe.size() > 0)
        {
            p = fringe.dequeue();
            taboo.add(p);

            if (p.x == dest.x && p.y == dest.y)
            {
                    solution_found = true;
                    break;
            }

            if (p.x > floor.minX && !taboo.contains(new Point(p.x-1,p.y))
                fringe.enqueue(new Point(p.x-1,p.y));

            if (p.x < floor.maxX && !taboo.contains(new Point(p.x+1,p.y))
                fringe.enqueue(new Point(p.x+1,p.y));

            if (p.y > floor.minY && !taboo.contains(new Point(p.x,p.y-1))
                fringe.enqueue(new Point(p.x,p.y-1));

            if (p.y < floor.maxY && !taboo.contains(new Point(p.x,p.y+1))
                fringe.enqueue(new Point(p.x,p.y+1));
        }

        // taboo list represent the path taken so far

        fringe.clear();
    }
}

Answer 3

根据您的实现，应该可以将多个地图组合到一个单独的图中，并在特定点进行互连。我认为这就是BlueRaja一直试图解释的想法。

A*算法(以及Djkstra )基于查询离开图的节点的边以及它们各自的权重。在大多数语言中，这个图形对象可以抽象为一个不透明的类型和一组操作来查询其内容:例如，在Java中，这组操作将构成一个接口，而实现该接口的类的不透明类型将被转换回该接口。其他语言可以不同地提供这种机制，例如在具有结构、签名和函数符的ML方言中。

如果算法是围绕这个接口构建的，那么应该很容易将实现图形接口的楼层图类替换为另一种类型，该类型的内容将是几个楼层图，以及在楼层内传达均匀规则边以及楼层之间特殊边所需的函数或方法。有了这个新的building类，人们可以想象封装(遵循相同的模式)几个建筑物实例，并使用即席代码将建筑物内部和外部连接提供为图形边。

如果抽象良好，A*算法实现应该与图、节点和边的实现细节完全正交，并且它应该能够与支持图形接口的任何对象一起执行。

例如，下面是Graph的一个可能的接口：

interface Graph<Node, Scalar> {
    int compare(Node n1, Node n2);
    Collection<Node> getNeighbourgs(Node n);
    Scalar getCost(Node n1, Node n2);
}

其中Node是图形中的节点，Scalar是表示节点之间的成本(或距离)的类型。

class Cell<Position extends Comparable<Position>> implements Comparable<Cell<Position>> {
    private Position position;
    public Cell(Position p){
         position = p;
    }
    Position getPosition(){
         return position;
    }
    int compareTo(Cell<Position> c){
         return position.compareTo(c.getPosition());
    }
}

abstract class WorldCell extends Cell<Position> {
    public WorldCell(Position p){
        super(p);
    }
}

abstract class World implements Graph<WorldCell, Integer> {
     private Building [] buildings;
     private HashMap<WorldCell, LinkedList<WorldCell>> gateways;
     int compare(WorldCell n1, WorldCell n2){
           return n1.compareTo(n2);
     }
     public Collection<WorldCell> getNeighbourgs(WorldCell c){
           // build the collections of cells from the building it belongs to
           // and the gateways (connections between buildings
     }
     Scalar getCost(Node n1, Node n2){
           // compute the cost based on the node positions in space
     }       
}


abstract class Building implements Graph<WorldCell, Integer> {
     private Floor [] floors;
     private HashMap<WorldCell, LinkedList<WorldCell>> gateways;
     int compare(WorldCell n1, WorldCell n2){
           return n1.compareTo(n2);
     }
     public Collection<WorldCell> getNeighbourgs(WorldCell c){
           // build the collections of cells from the floor it belongs to
           // and the gateways (connections between floors)
     }

这个部分类集提供了Graph的多个实现的初始草图。Floor类将使用一组Room类实例复制与World或Building中或多或少相同的代码。

当然，我们可以在这里看到一个类似容器的“俄罗斯玩偶”模式，它当然可以以某种方式抽象出来，但这个示例的目的是展示如何由您想要建模的世界的不同部分实现相同的接口。