Hallo
Habe folgenden Code, der den kürzesten Pfad zwischen Zwei Knoten in einem 2D-Array herausfindet. Allerdings kann es vorkommen, dass es mehrere kürzeste Pfade zwischen den Knoten gibt, und ich brauche immer einen bestimmten, von der Aufgabenstellung verlangten Pfad.
und so sieht das Feld aus
Hierbei muss ich das 'E' auf das nächstgelegene Ausrufezeichen transportieren. (ist nur ein kleines Beispiel, in der Aufgabe gibt es mehrere 'E' und 'G' Zeichen auf dem Feld). Falls zwei Ausrufezeichen dieselbe Distanz vom 'E' haben, muss das Ausrufezeichen gewählt werden, welches von links nach rechts gelesen als erstes vorkommt.
Der Pfad der für das Beispiel berechnet wird, ist folgender
Ich möchte aber diesen Pfad haben
Ich hab mir überlegt, dass jeder Knoten ja mehrere Eltern hat. In meinem Codebeispiel setze ich allerdings immer nur 1 Elternknoten. Dann müsste ich ja eine Liste von Eltern für jeden Knoten führen oder gibt es einen anderen Weg?
Habe folgenden Code, der den kürzesten Pfad zwischen Zwei Knoten in einem 2D-Array herausfindet. Allerdings kann es vorkommen, dass es mehrere kürzeste Pfade zwischen den Knoten gibt, und ich brauche immer einen bestimmten, von der Aufgabenstellung verlangten Pfad.
Java:
Node optimalNode = null;
Queue<Node> nodes = new LinkedList<Node>();
nodes.offer(new Node(startingPos, null));
Set<Point> examinedPoints = new HashSet<Point>();
while(!nodes.isEmpty())
{
Node current = nodes.poll();
examinedPoints.add(current.point);
//check if we found a target
for(int i = 0; i < possibleTargets.size(); i++)
{
if(current.point.equals(possibleTargets.get(i)))
{
optimalNode = current;
break;
}
}
//add all relevant nodes in the vicinity (up, left, right, down) to the queue (the way the grid is set-up makes it impossible to be out of bounds here)
if(grid[current.point.y - 1][current.point.x]== '.' && !examinedPoints.contains(new Point(current.point.x, current.point.y - 1)))
{
nodes.offer(new Node(new Point(current.point.x, current.point.y - 1), current));
}
if(grid[current.point.y][current.point.x - 1] == '.' && !examinedPoints.contains(new Point(current.point.x - 1, current.point.y)))
{
nodes.offer(new Node(new Point(current.point.x - 1, current.point.y), current));
}
if(grid[current.point.y][current.point.x + 1] == '.' && !examinedPoints.contains(new Point(current.point.x + 1, current.point.y)))
{
nodes.offer(new Node(new Point(current.point.x + 1, current.point.y), current));
}
if(grid[current.point.y + 1][current.point.x] == '.' && !examinedPoints.contains(new Point(current.point.x, current.point.y + 1)))
{
nodes.offer(new Node(new Point(current.point.x, current.point.y + 1), current));
}
}
und so sieht das Feld aus
Code:
#######
#.E...#
#...!.#
#..!G!#
#######
Hierbei muss ich das 'E' auf das nächstgelegene Ausrufezeichen transportieren. (ist nur ein kleines Beispiel, in der Aufgabe gibt es mehrere 'E' und 'G' Zeichen auf dem Feld). Falls zwei Ausrufezeichen dieselbe Distanz vom 'E' haben, muss das Ausrufezeichen gewählt werden, welches von links nach rechts gelesen als erstes vorkommt.
Der Pfad der für das Beispiel berechnet wird, ist folgender
Code:
#######
#.E...#
#.+++.#
#...G.#
#######
Ich möchte aber diesen Pfad haben
Code:
#######
#.E++.#
#...+.#
#...G.#
#######
Ich hab mir überlegt, dass jeder Knoten ja mehrere Eltern hat. In meinem Codebeispiel setze ich allerdings immer nur 1 Elternknoten. Dann müsste ich ja eine Liste von Eltern für jeden Knoten führen oder gibt es einen anderen Weg?