A* Algorithm

H

HerrInfo

Mitglied
Hallo zusammen,

ich versuche seit ein paar Wochen für mich mit dem A* Algorithmus auseinander zu setzten. Leide tritt bei mir nun ein Fehler auf, welchen ich nicht erklären kann. Ich bitte um eure Hilfe. Hier ist der Code von dem Panel wo der Algorithmus läuft.

Java: 
package net.tim;

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.List;

public class DemoPanel extends JPanel {

  //screen Settings
  final int maxCol = 15;
  final int maxRow = 10;
  final int NodeSize = 75;

  final int screenWidth = maxCol * NodeSize;
  final int screenHeight = maxRow * NodeSize;

  //nodes
  Node[][] node = new Node[maxRow][maxCol];
  Node startNode, goalNode, currentNode;
  List<Node> openList = new ArrayList<>();
  List<Node> checkedList = new ArrayList<>();

  //other
  boolean goalReached = false;


  public DemoPanel() {
        setPreferredSize(new Dimension(screenWidth, screenHeight));
        setBackground(Color.BLACK);
        setLayout(new GridLayout(maxRow, maxCol));
        addKeyListener(new KeyHandler(this));
        setFocusable(true);

        //create nodes
        int col = 0;
        int row = 0;

        while (col < maxCol && row < maxRow) {

            node[row][col] = new Node(col, row);
            this.add(node[row][col]);

            col++;
            if (col == maxCol) {
                col = 0;
                row++;
            }
        }

        //set start and goal nodes
        setStartNode(3, 6);
        setGoalNode(11, 3);

        //set solid nodes
        setSolidNode(10,2);
        setSolidNode(10,3);
        setSolidNode(10,4);
        setSolidNode(10,5);
        setSolidNode(10,6);
        setSolidNode(10,7);
        setSolidNode(6,2);
        setSolidNode(7,2);
        setSolidNode(8,2);
        setSolidNode(9,2);
        setSolidNode(11,7);
        setSolidNode(12,7);
        setSolidNode(6,1);

        //set costs on nodes
        setCostOnNodes();
  }

  public void search(){
      if (goalReached == false) {

          int col = currentNode.col;
          int row = currentNode.row;

          currentNode.setAsChecked();
          checkedList.add(currentNode);
          openList.remove(currentNode);

          //open the node above
          if (row -1 >= 0) {
              openNode(node[col][row - 1]);
          }

          //open the left node
          if (col -1 >= 0) {
              openNode(node[col - 1][row]);
          }

          //open the node below
          if (row + 1 < maxRow) {
              openNode(node[col][row + 1]);
          }

          //open the right node
            if (col + 1 < maxCol) {
                System.out.println("col: " + col + " row: " + row);
                openNode(node[col + 1][row]);
            }

          int bestNodeIndex = 0;
          int bestNodeFCost = 999;

          for (int i = 0; i < openList.size(); i++) {
              if (openList.get(i).fCost < bestNodeFCost) {
                  bestNodeFCost = openList.get(i).fCost;
                  bestNodeIndex = i;
              } else if (openList.get(i).fCost == bestNodeFCost) {
                  if (openList.get(i).gCost < openList.get(bestNodeIndex).gCost) {
                      bestNodeIndex = i;
                  }

              }
          }

          currentNode = openList.get(bestNodeIndex);

          if (currentNode == goalNode) {
              goalReached = true;
          }

      }
  }

  private void setStartNode(int col, int row) {
      node[row][col].setAsStart();
      startNode = node[row][col];
      currentNode = startNode;
  }

    private void setGoalNode(int col, int row) {
        node[row][col].setAsGoal();
        goalNode = node[row][col];
    }

    private void setSolidNode(int col, int row) {
        node[row][col].setAsSolid();
    }

    private void setCostOnNodes() {
        int col = 0;
        int row = 0;

        while (col < maxCol && row < maxRow) {
            getCost(node[row][col]);

            col++;
            if (col == maxCol) {
                col = 0;
                row++;
            }
        }
    }
    private void getCost(Node node){
        //gCost
        int xDistance = Math.abs(node.col - startNode.col);
        int yDistance = Math.abs(node.row - startNode.row);
        node.gCost = xDistance + yDistance;

        //hCost
        xDistance = Math.abs(node.col - goalNode.col);
        yDistance = Math.abs(node.row - goalNode.row);
        node.hCost = xDistance + yDistance;

        //fCost
        node.fCost = node.gCost + node.hCost;

        //display costs
        if (node != startNode && node != goalNode) {
            node.setText("<html>F: " + node.fCost + "<br>G: " + node.gCost + "</html>");
        }
    }

    private void openNode(Node node) {
        if (!node.open && !node.checked && !node.solid) {
            node.setAsOpen();
            node.parent = currentNode;
            openList.add(node);
        }
    }

}

Hier ist noch die dazu gehörende Node Klasse:
Code: 
package net.tim;

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.List;

public class DemoPanel extends JPanel {

  //screen Settings
  final int maxCol = 15;
  final int maxRow = 10;
  final int NodeSize = 75;

  final int screenWidth = maxCol * NodeSize;
  final int screenHeight = maxRow * NodeSize;

  //nodes
  Node[][] node = new Node[maxRow][maxCol];
  Node startNode, goalNode, currentNode;
  List<Node> openList = new ArrayList<>();
  List<Node> checkedList = new ArrayList<>();

  //other
  boolean goalReached = false;


  public DemoPanel() {
        setPreferredSize(new Dimension(screenWidth, screenHeight));
        setBackground(Color.BLACK);
        setLayout(new GridLayout(maxRow, maxCol));
        addKeyListener(new KeyHandler(this));
        setFocusable(true);

        //create nodes
        int col = 0;
        int row = 0;

        while (col < maxCol && row < maxRow) {

            node[row][col] = new Node(col, row);
            this.add(node[row][col]);

            col++;
            if (col == maxCol) {
                col = 0;
                row++;
            }
        }

        //set start and goal nodes
        setStartNode(3, 6);
        setGoalNode(11, 3);

        //set solid nodes
        setSolidNode(10,2);
        setSolidNode(10,3);
        setSolidNode(10,4);
        setSolidNode(10,5);
        setSolidNode(10,6);
        setSolidNode(10,7);
        setSolidNode(6,2);
        setSolidNode(7,2);
        setSolidNode(8,2);
        setSolidNode(9,2);
        setSolidNode(11,7);
        setSolidNode(12,7);
        setSolidNode(6,1);

        //set costs on nodes
        setCostOnNodes();
  }

  public void search(){
      if (goalReached == false) {

          int col = currentNode.col;
          int row = currentNode.row;

          currentNode.setAsChecked();
          checkedList.add(currentNode);
          openList.remove(currentNode);

          //open the node above
          if (row -1 >= 0) {
              openNode(node[col][row - 1]);
          }

          //open the left node
          if (col -1 >= 0) {
              openNode(node[col - 1][row]);
          }

          //open the node below
          if (row + 1 < maxRow) {
              openNode(node[col][row + 1]);
          }

          //open the right node
            if (col + 1 < maxCol) {
                System.out.println("col: " + col + " row: " + row);
                openNode(node[col + 1][row]);
            }

          int bestNodeIndex = 0;
          int bestNodeFCost = 999;

          for (int i = 0; i < openList.size(); i++) {
              if (openList.get(i).fCost < bestNodeFCost) {
                  bestNodeFCost = openList.get(i).fCost;
                  bestNodeIndex = i;
              } else if (openList.get(i).fCost == bestNodeFCost) {
                  if (openList.get(i).gCost < openList.get(bestNodeIndex).gCost) {
                      bestNodeIndex = i;
                  }

              }
          }

          currentNode = openList.get(bestNodeIndex);

          if (currentNode == goalNode) {
              goalReached = true;
          }

      }
  }

  private void setStartNode(int col, int row) {
      node[row][col].setAsStart();
      startNode = node[row][col];
      currentNode = startNode;
  }

    private void setGoalNode(int col, int row) {
        node[row][col].setAsGoal();
        goalNode = node[row][col];
    }

    private void setSolidNode(int col, int row) {
        node[row][col].setAsSolid();
    }

    private void setCostOnNodes() {
        int col = 0;
        int row = 0;

        while (col < maxCol && row < maxRow) {
            getCost(node[row][col]);

            col++;
            if (col == maxCol) {
                col = 0;
                row++;
            }
        }
    }
    private void getCost(Node node){
        //gCost
        int xDistance = Math.abs(node.col - startNode.col);
        int yDistance = Math.abs(node.row - startNode.row);
        node.gCost = xDistance + yDistance;

        //hCost
        xDistance = Math.abs(node.col - goalNode.col);
        yDistance = Math.abs(node.row - goalNode.row);
        node.hCost = xDistance + yDistance;

        //fCost
        node.fCost = node.gCost + node.hCost;

        //display costs
        if (node != startNode && node != goalNode) {
            node.setText("<html>F: " + node.fCost + "<br>G: " + node.gCost + "</html>");
        }
    }

    private void openNode(Node node) {
        if (!node.open && !node.checked && !node.solid) {
            node.setAsOpen();
            node.parent = currentNode;
            openList.add(node);
        }
    }

}

Folgender Fehler wird dann nach einigem Drücken der Enter Taste, welche die Methode search() Triggert ausgegeben.
Code: 
Exception in thread "AWT-EventQueue-0" java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10
    at net.tim.DemoPanel.search(DemoPanel.java:102)
    at net.tim.KeyHandler.keyPressed(KeyHandler.java:24)
    at java.desktop/java.awt.Component.processKeyEvent(Component.java:6579)
    at java.desktop/javax.swing.JComponent.processKeyEvent(JComponent.java:2905)
    at java.desktop/java.awt.Component.processEvent(Component.java:6398)
    at java.desktop/java.awt.Container.processEvent(Container.java:2266)
    at java.desktop/java.awt.Component.dispatchEventImpl(Component.java:4996)
    at java.desktop/java.awt.Container.dispatchEventImpl(Container.java:2324)
    at java.desktop/java.awt.Component.dispatchEvent(Component.java:4828)
    at java.desktop/java.awt.KeyboardFocusManager.redispatchEvent(KeyboardFocusManager.java:1952)
    at java.desktop/java.awt.DefaultKeyboardFocusManager.dispatchKeyEvent(DefaultKeyboardFocusManager.java:883)
    at java.desktop/java.awt.DefaultKeyboardFocusManager.preDispatchKeyEvent(DefaultKeyboardFocusManager.java:1146)
    at java.desktop/java.awt.DefaultKeyboardFocusManager.typeAheadAssertions(DefaultKeyboardFocusManager.java:1020)
    at java.desktop/java.awt.DefaultKeyboardFocusManager.dispatchEvent(DefaultKeyboardFocusManager.java:848)
    at java.desktop/java.awt.Component.dispatchEventImpl(Component.java:4877)
    at java.desktop/java.awt.Container.dispatchEventImpl(Container.java:2324)
    at java.desktop/java.awt.Window.dispatchEventImpl(Window.java:2780)
    at java.desktop/java.awt.Component.dispatchEvent(Component.java:4828)
    at java.desktop/java.awt.EventQueue.dispatchEventImpl(EventQueue.java:775)
    at java.desktop/java.awt.EventQueue$4.run(EventQueue.java:720)
    at java.desktop/java.awt.EventQueue$4.run(EventQueue.java:714)
    at java.base/java.security.AccessController.doPrivileged(AccessController.java:400)
    at java.base/java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:87)
    at java.base/java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:98)
    at java.desktop/java.awt.EventQueue$5.run(EventQueue.java:747)
    at java.desktop/java.awt.EventQueue$5.run(EventQueue.java:745)
    at java.base/java.security.AccessController.doPrivileged(AccessController.java:400)
    at java.base/java.security.ProtectionDomain$JavaSecurityAccessImpl.doIntersectionPrivilege(ProtectionDomain.java:87)
    at java.desktop/java.awt.EventQueue.dispatchEvent(EventQueue.java:744)
    at java.desktop/java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:203)
    at java.desktop/java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:124)
    at java.desktop/java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:113)
    at java.desktop/java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:109)
    at java.desktop/java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:101)
    at java.desktop/java.awt.EventDispatchThread.run(EventDispatchThread.java:90)
 
KonradN

KonradN

Super-Moderator
Mitarbeiter
Du prüfst nur col+1 und nicht row. Bei Zeile 102 ist row 10 und da der Index von row nur bis 9 geht bekommst Du diese Exception.

Wieso row einen Wert ausserhalb des gültigen Bereichs hat, kann ich nicht sagen - so genau habe ich jetzt nicht geschaut.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
H A* Algorithm Allgemeine Java-Themen 14
Meeresgott 2D-Grafik Bresenham's line algorithm Allgemeine Java-Themen 37
M kruskals-algorithm-minimum-spanning-tree Allgemeine Java-Themen 5
N Prim's Algorithm - wo ist der Fehler? Allgemeine Java-Themen 3
T Algorithm TLS not available Allgemeine Java-Themen 3

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben