路徑在不同的樓層找到A點到B

Question

我有什麼算法或方法這個問題我會考慮的，其中兩個點都不在同一平面上（要解決尋找到B點，從A點的路徑的一個特殊問題在不同的樓層/樓層上 - 可能不在同一棟樓裏）。

我正在考慮這兩個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的第一個「2」）到B點（第一個' 4「從MainFloor2的左上角）將返回給我的結果。

// 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

A *，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個方向..

提出的解決方案是BFS（廣度-First Search）使用禁忌列表

使用這些類：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方言。

如果算法是圍繞這個接口構建的，應該很容易用其他類型的實現圖形接口的地圖類替換爲另一種類型，其內容將是幾個樓層地圖，並且必須的函數或方法傳遞均勻的常規邊在地板內，以及在地板之間的特殊邊緣。有了這個新的建築類，人們可以想象封裝（遵循相同的模式）幾個建築物的實例，使用專用代碼來提供建築物內部和外部連接作爲圖形邊緣。

如果抽象得很好，A *算法的實現應該完全正交於圖，節點和邊的實現細節，並且它應該能夠用支持圖接口的任何對象來執行。

例如，這裏爲一個圖形接口可能：

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或多或少相同的代碼。

當然，我們可以在這裏看到像容器這樣的「俄羅斯娃娃」模式，這當然可以抽象出來，但這個例子的目的是展示如何通過世界的不同部分來實現相同的接口你打算建模。