Gebäude Adjazenz Grafik aus Schachbrett (für Dijkstra)

Question

Ich stieß auf ein Problem, wo ich ein kleines Feature zu meinen Hausaufgaben hinzufügen wollte und es erwies sich als überwältigend für mich (lesen Sie fetteste Sätze für Fragen ohne Kontext).

Mein Programm enthält eine Liste von ungefähr 35 Elementen, die Informationen über die Karte enthalten, mit der ich arbeiten soll. Es können die folgenden Elemente aufweisen:

• "Wand" mit seinen Koordinaten (X, Y), in der Dijkstra es soll an Gewicht 100.
• "Baum" mit Korden (X, Y) haben, 3 Gewicht

ich habe eine 10x10 Karte wie ein Schachbrett angelegt, die zu 100 Kacheln bedeuten, und 35 Elemente. "Nichts" in der Liste bedeutet Gewicht 1 in Dijkstra (es bedeutet eine normale Route)

Um die Dijkstra arbeiten zu lassen und in der Lage zu sein, den kürzesten Weg zwischen zwei Kacheln zu finden, muss ich ein Adjazenzdiagramm erstellen. Mein Problem hier ist, wie Kacheln "um" die aktuelle Kachel zu definieren, wenn alles, was ich habe, ist diese Liste?

Nur benachbarte Kacheln in Form von „+“ haben Kanten in der Grafik zwischen ihnen, aber ich habe durch die Liste laufen jedes Mal, um zu überprüfen, ob es etwas drauf ist?

Jeder Hinweis auf das Problem würde sehr geschätzt werden, auch wenn Sie mich auf eine Quelle mit einem Codebeispiel zeigen können, das könnte auch tun. Ich sehe nur wirklich chaotischen Code mit vielen "If-elseif-elseif ...", um das zu lösen.

Vielen Dank für Ihre Zeit!

Edit: Ich endete mit @kraskevichs vorgeschlagenen Weg, und es funktioniert ausgezeichnet, aber alle Antworten und Vorschläge waren wirklich nützlich, vielen Dank allen!

Answer 1

Sie brauchen nicht wirklich ein Diagramm zu erstellen. Erstellen Sie einfach einen 10x10 Tisch und setzen das Gewicht der entsprechenden Werte in sie:

board = 10x10 array filled with 1 
for item in list: 
    if item is a tree: 
     board[item.row][item.column] = 3 
    else if item is a wall: 
     board[item.row][item.column] = 100 

Danach kann man Paare von Koordinaten (row, col) als Ecken behandeln und den Abstand für die 4 benachbarte Zellen aktualisieren, wenn Sie eine Kachel zu verarbeiten. Das ist es. Sicher, Sie können auch einen Graphen mit 100 Scheitelpunkten erstellen und Kanten explizit aus einer Kachel zu allen 4 benachbarten Zellen hinzufügen (das Gewicht ist das Gewicht des Endes der Kantenkachel) und eine Standardimplementierung verwenden.

Der bequemste Weg ist benachbarte Zellen iterieren wie folgt:

delta_rows = [-1, 1, 0, 0] 
delta_cols = [0, 0, -1, 1] 
... 
for direction = 0 .. 3 
    new_row = row + delta_rows[direction] 
    new_col = col + delta_cols[direction] 
    if is_valid(new_row, new_col) 
      // do something 

Answer 2

Es sollte einfach sein Dijkstra auf dieser generische Graph-Schnittstelle zu implementieren basiert:

interface Graph<T> { 
    Iterable<T> adjacentNodes(T node); 
    double getDistance(T node, T adjacent); 
} 

Also alles, jetzt brauchen wir zu tun ist, es für Ihren Fall zu füllen:

class Field { 
    final int x; 
    final int y; 
    int value = 1; 
    Field (int x, int y) { 
    this.x = x; 
    this.y = y; 
    } 
} 

class ChessboardGraph implements Graph<Field> { 
    Field[][] board = new Filed[10][10]; 

    ChessboardGraph(List<Entry> list) { 
    for (int x = 0; x < 10; x++) { 
     for (int y = 0; y < 10; y++) { 
     board[x][y] = new Field(x, y); 
     } 
    } 
    for (Entry e: list) { 
     board[e.x][e.y].value = e.value == TREE ? 3 : 100; 
    } 
    } 

    Iterable<Field> adjacentNodes(Field node) { 
    ArrayList result = new ArrayList<>(); 
    int x = node.x; 
    int y = node.y; 
    if (x > 0) { 
     if (y > 0) { 
     result.add(board[x - 1][y - 1]); 
     } 
     if (y < 9) { 
     result.add(board[x - 1][y + 1]); 
     } 
    } 
    if (x < 9) { 
     if (y > 0) { 
     result.add(board[x + 1][y - 1]); 
     } 
     if (y < 9) { 
     result.add(board[x + 1][y + 1]); 
     } 
    } 
    } 

    double getDistance(Field node, Field adjacent) { 
    assert Math.abs(node.x - adjacent.x) + Math.abs(node.y - adjacent.y) == 1; 
    return board[adjacent.x][adjacent.y]; 
    } 
}