# leichte Java Aufgabe, kann mir wer helfen? Labyrinth



## jokergermany (10. Januar 2010)

Ich muss nächste Woche ne Java Aufgabe abgeben.
Das letzte Mal....

Aufgabe:


> Der Nutzer soll dabei Start- und Endpunkt (je einer) festlegen sowie beliebig viele Hindernisse zeichnen können (Vergleich Stift-Werkzeug aus Microsoft Paint). Die Größe einer "Zelle" des Feldes soll 8x8 Pixel betragen. Das Auswählen der drei Werkzeuge "Startpunkt", "Endpunkt" und "Hindernis" soll über eine Toolbar geschehen.
> 
> Der angezeigte Weg soll nach jeder Änderung (Setzen von Start- oder Endpunkt sowie Zeichnen von Hindernissen) automatisch neu berechnet und visualisiert werden. Überlegt euch bei der grafischen Umsetzung, wie die Start- und Endpunkte visuell von Hindernissen unterscheidbar gemacht werden können. Der A*-Algorithmus zur Berechnung des Pfades und die Datenstruktur zum Speichern von Start- und Endpunkten sowie Hindernissen sind in der Vorgabe bereits enthalten, es muss lediglich der grafische Part (in der Klasse Main) programmiert werden.


Vorgabe:
Main:

```
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Point;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;

/**
 * Hauptklasse, die vor allem fuer das Zeichnen der Elemente zustaendig ist.
 *
 */
public class Main {
    private static final long serialVersionUID = 1L;

    private JPanel drawPanel;

    /**
     * Einmaliges initialisieren des Applets.
     */
    public void init() {
        initValues();
        initToolbars();
        initDrawPanel();
        
        JPanel paneInIn = new JPanel(new BorderLayout());
        paneInIn.add(new JPanel(), BorderLayout.CENTER);
        paneInIn.add(this.drawPanel, BorderLayout.NORTH);
        
        JPanel paneIn = new JPanel(new BorderLayout());
        paneIn.add(paneInIn, BorderLayout.WEST);
        paneIn.add(new JPanel(), BorderLayout.CENTER);
        paneIn.add(new JPanel(), BorderLayout.SOUTH);
        JScrollPane pane = new JScrollPane(paneIn);
        pane.setPreferredSize(new Dimension(600,600));
        
        JPanel main = new JPanel(new BorderLayout());
        main.add(pane, BorderLayout.CENTER);
        
        JFrame mainFrame = new JFrame();
        mainFrame.setLayout(new BorderLayout());
        mainFrame.add(main, BorderLayout.CENTER);
        mainFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        mainFrame.pack();
        mainFrame.setVisible(true);
    }
    
    /**
     * Initialisiert das Panel, auf das die Map gezeichnet wird.
     * Beinhaltet MouseListener zum Clicken und Draggen.
     */
    private void initDrawPanel() {
        // TODO implementieren
        drawPanel = new JPanel();
        drawPanel.setPreferredSize(new Dimension(200, 200));
        drawPanel.setBackground(Color.WHITE);
    }
    
    /**
     * Initialisiert alle Toolbars.
     */
    private void initToolbars() {
        // TODO implementieren
    }

    /**
     * Initialisiert die Applikation mit Startwerten.
     * Wird auch beim Druecken des "Neu"-Buttons aufgerufen.
     */
    private void initValues() {
        // TODO implementieren
    }
    
    /**
     * Benutzt den Radiergummi unter Beachtung der ausgewaehlten
     * Radiergroesse, um Hindernisse zu loeschen.
     * @param thePoint der Mittelpunkt des zu radierenden Bereichs
     */
    @SuppressWarnings("unused")
    private void useEraser(Point thePoint) {
        // TODO implementieren fuer Aufgabe 2
    }
    
    /**
     * Hauptmethode
     * @param args
     */
    public static void main(String[] args) {
        Main me = new Main();
        me.init();
    }
}
```
GraphNode:

```
/**
 * Stellt einen Graphenknoten zur Verwendung mit dem A*-Algorithmus dar.
 *
 */
public class GraphNode implements Comparable<GraphNode>{
    private int x;
    private int y;
    private double fitness;
    private double distanceToPlayer = 99999999;
    
    private GraphNode home = null;
    private GraphNode north = null;
    private GraphNode south = null;
    private GraphNode west = null;
    private GraphNode east = null;
    
    public enum Type {EMPTY, START, END, PATH, OBSTACLE};
    
    public GraphNode(int x, int y) {
        this.x = x;
        this.y = y;
        calculateFitness();
    }
    
    /**
     * Knoten zu Ausgangszustand
     */
    public void reset(){
        home = null;
        distanceToPlayer = 99999999;
        calculateFitness();
    }
    
    /**
     * @return oberer Nachbar
     */
    public GraphNode getNorth() {
        return north;
    }

    /**
     * setzt oberen Nachbar
     * @param north oberer Nachbar
     */
    public void setNorth(GraphNode north) {
        this.north = north;
    }

    /**
     * @return unteren Nachbar
     */
    public GraphNode getSouth() {
        return south;
    }

    /**
     * setzt unteren Nachbar
     * @param south unterer Nachbar
     */
    public void setSouth(GraphNode south) {
        this.south = south;
    }

    /**
     * @return linker Nachbar
     */
    public GraphNode getWest() {
        return west;
    }

    /**
     * setzt linken Nachbar
     * @param west linker Nachbar
     */
    public void setWest(GraphNode west) {
        this.west = west;
    }

    /**
     * @return rechter Nachbar
     */
    public GraphNode getEast() {
        return east;
    }

    /**
     * setzt rechten Nachbar
     * @param east rechter Nachbar
     */
    public void setEast(GraphNode east) {
        this.east = east;
    }

    /**
     * setzt Vorgänger auf dem bisherigen Pfad
     * @param home Vorgänger
     */
    public void setHome(GraphNode home){
        this.home = home;
    }
    
    /**
     * @return den Vorgänger auf dem Pfad
     */
    public GraphNode getHome() {
        return home;
    }
    
    /**
     * berechnet momentane Wertigkeit
     */
    public void calculateFitness(){            
        fitness = distanceToPlayer + estimateDistanceToTarget();
    }
    
    /**
     * setzt die Entfernung zum Start
     * @param distance
     */
    public void setDistance(double distance){
        distanceToPlayer = distance;
    }

    /**
     * @return die Entfernung zum Start
     */
    public double getDistance(){
        return distanceToPlayer;
    }
    
    /**
     * berechnet die Entfernung zum Start
     */
    public void calculateDistance(){
        distanceToPlayer = 1 + home.distanceToPlayer;
    }
    
    /**
     * @return die Wertigkeit
     */
    public double getFitness(){
        return fitness;
    }
    
    /**
     * prüft ob dieser Knoten die gegeben Parameter hat
     * @param x Koordinate
     * @param y Koordinate
     * @return true wenn dieser Knoten mit den gegebenen Koordinaten übereinstimmt
     */
    public boolean isNode(int x, int y) {
        if (this.x == x && this.y == y)
            return true;
        else
            return false;
    }
    
    /**
     * @return x-Koordinate
     */
    public int getX() {
        return x;
    }

    /**
     * @return y-Koordinate
     */
    public int getY() {
        return y;
    }
    
    /**
     * schätzt die Entfernung zum Zielpunkt
     * @return die Schätzung
     */
    public double estimateDistanceToTarget() {
        int targetX = Map.getEnd().x;
        int targetY = Map.getEnd().y;
        
        return Math.sqrt((double) ((targetX-x)*(targetX-x) + (targetY-y)*(targetY-y)));
    }

    /**
     * vergleicht anhand der Wertigkeit
     */
    @Override
    public int compareTo(GraphNode node) {
        if (fitness == node.getFitness())
        return 0;
        else if (fitness > node.getFitness())
            return 1;
        else
            return -1;
    }
}
```
Map

```
import java.awt.Point;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;

/**
 * Datenstruktur, die Hindernisse, Start- und Endpunkt sowie den Pfad zwischen diesen verwaltet.
 * Der kuerzeste Pfad zwischen Start- und Endpunkt kann mit der Methode findPath() per A*-Algorithmus
 * berechnet und in die Datenstruktur eingetragen werden.
 *
 */
public class Map {
    private static PriorityQueue<GraphNode> openNodes;
    private static HashSet<GraphNode> closedNodes;
    private static ArrayList<GraphNode> buildList;

    private static GraphNode.Type[][] mapArray;

    public final static int WIDTH = 65;
    public final static int HEIGHT = 65;
    
    private static Point start;
    private static Point end;
    private static Set<Point> obstacles;
    private static Set<Point> path;

    protected static GraphNode.Type[][] getMap() {
        return mapArray;
    }

    private static GraphNode targetNode;
    private static GraphNode playerNode;

    /**
     * Initialisiert die AStarMap.
     * Muss mindestens einmal aufgerufen worden sein, bevor
     * andere Methoden dieser Klasse verwendet werden koennen.
     */
    public static void init() {
        mapArray = new GraphNode.Type[Map.WIDTH][Map.HEIGHT];
        obstacles = new HashSet<Point>();
        path = new HashSet<Point>();
        start = new Point(3, 3);
        
        for (int i = 0; i < Map.WIDTH; i++) {
            for (int j = 0; j < Map.HEIGHT; j++) {
                mapArray[i][j] = GraphNode.Type.EMPTY;
            }
        }
        mapArray[0][0] = GraphNode.Type.START;
        end = null;
    }
    
    /**
     * Erstellt die Nachbarschaftsbeziehungen zwischen Knoten,
     * die fuer den A*-Algorithmus noetig sind.
     */
    private static void buildListForAStar() {
        buildList = new ArrayList<GraphNode>();

        for (int i = 0; i < WIDTH; i++) {
            for (int j = 0; j < HEIGHT; j++)
                buildList.add(new GraphNode(i, j));
        }

        for (int i = 0; i < WIDTH * (HEIGHT - 1); i++) {
            buildList.get(i).setSouth(buildList.get(i + WIDTH));
        }

        for (int i = WIDTH; i < WIDTH * HEIGHT; i++) {
            buildList.get(i).setNorth(buildList.get(i - WIDTH));
        }

        for (int i = 0; i < WIDTH * HEIGHT; i++) {
            if (i % WIDTH != 0)
                buildList.get(i).setWest(buildList.get(i - 1));
        }

        for (int i = 0; i < WIDTH * HEIGHT; i++) {
            if (i % WIDTH != (WIDTH - 1))
                buildList.get(i).setEast(buildList.get(i + 1));
        }
    }
    
    /**
     * Sucht den kuerzesten Pfad zwischen Start- und Endpunkt unter Beachtung
     * der Hindernisse und setzt ihn in das Feld.
     * (Kuerzester Pfad im Sinne des Manhattan-Abstands,
     * nicht euklidischer Abstand!)
     */
    public static void findPath() {
        long time = System.nanoTime();

        if (buildList == null)
            buildListForAStar();

        for (GraphNode n : buildList)
            n.reset();

        playerNode = buildList.get(start.x * WIDTH + start.y);
        targetNode = buildList.get(WIDTH * end.x + end.y);

        openNodes = new PriorityQueue<GraphNode>();
        closedNodes = new HashSet<GraphNode>();

        GraphNode startNode = buildList.get(start.x * WIDTH + start.y);
        startNode.setDistance(0);
        openNodes.add(startNode);
        GraphNode tmp;
        
        int i = 0;

        while (!openNodes.isEmpty()) {
            i++;
            tmp = openNodes.poll();

            if (tmp == targetNode)
                break;

            addFriends(tmp);
        }

        GraphNode tmp2 = targetNode.getHome();
        if (tmp2 != null) {
            while (tmp2 != playerNode) {
                mapArray[tmp2.getX()][tmp2.getY()] = GraphNode.Type.PATH;
                path.add(new Point(tmp2.getX(), tmp2.getY()));
                tmp2 = tmp2.getHome();
            }
        }

        System.out.println("Nodes checked: " + i);
        System.out.println("Time needed (ms): " + (System.nanoTime() - time) / (1000*1000));
    }

    /**
     * Finds out whether the specified GraphNode is an obstacle.
     * @return the GraphNode to examine
     */
    private static boolean isObstacle(GraphNode theNode) {
        return mapArray[theNode.getX()][theNode.getY()] == GraphNode.Type.OBSTACLE;
    }
    
    /**
     * A*-relevante Berechnungen (closed und open list)
     * @param node der aktuell zu berechnende Knoten
     */
    private static void addFriends(GraphNode node) {
        closedNodes.add(node);

        GraphNode north = node.getNorth();
        GraphNode south = node.getSouth();
        GraphNode west = node.getWest();
        GraphNode east = node.getEast();

        if (north != null && !closedNodes.contains(north) && !isObstacle(north)) {
            if (node.getDistance() + 1 < north.getDistance()) {
                north.setHome(node);
                north.calculateDistance();
                north.calculateFitness();
            }
            if (!openNodes.contains(north))
                openNodes.add(north);
        }

        if (south != null && !closedNodes.contains(south) && !isObstacle(south)) {
            if (node.getDistance() + 1 < south.getDistance()) {
                south.setHome(node);
                south.calculateDistance();
                south.calculateFitness();
            }
            if (!openNodes.contains(south))
                openNodes.add(south);
        }

        if (west != null && !closedNodes.contains(west) && !isObstacle(west)) {
            if (node.getDistance() + 1 < west.getDistance()) {
                west.setHome(node);
                west.calculateDistance();
                west.calculateFitness();
            }
            if (!openNodes.contains(west))
                openNodes.add(west);
        }

        if (east != null && !closedNodes.contains(east) && !isObstacle(east)) {
            if (node.getDistance() + 1 < east.getDistance()) {
                east.setHome(node);
                east.calculateDistance();
                east.calculateFitness();
            }
            if (!openNodes.contains(east))
                openNodes.add(east);
        }
    }
    
    /**
     * Setzt ein Hindernis.
     * @param thePoint der Punkt, an den das Hindernis gesetzt werden soll.
     */
    public static void createObstacle(Point thePoint) {
        if (!thePoint.equals(start) && !(thePoint.equals(end))) {
            obstacles.add(thePoint);
            mapArray[thePoint.x][thePoint.y] = GraphNode.Type.OBSTACLE;
        }
    }
    
    /**
     * Loescht ein eventuell vorhandenes Hindernis.
     * @param thePoint der Punkt, an dem das Hindernis gelöscht werden soll
     */
    public static void deleteObstacle(Point thePoint) {
        if (!thePoint.equals(start) && !(thePoint.equals(end))) {
            mapArray[thePoint.x][thePoint.y] = GraphNode.Type.EMPTY;
            obstacles.remove(thePoint);
        }
    }
    
    /**
     * Setzt den Startpunkt.
     * @param thePoint der neue Startpunkt.
     */
    public static void setStart(Point thePoint) {
        // alten Startpunkt loeschen
        mapArray[start.x][start.y] = GraphNode.Type.EMPTY;

        // Startpunkt setzen
        start = thePoint;
        mapArray[start.x][start.y] = GraphNode.Type.START;
    }
    
    /**
     * Setzt den Endpunkt.
     * @param thePoint der neue Endpunkt.
     */
    public static void setEnd(Point thePoint) {
        // evt. alten Endpunkt loeschen
        if (end != null)
            mapArray[end.x][end.y] = GraphNode.Type.EMPTY;
        
        // Endpunkt setzen
        end = thePoint;
        mapArray[end.x][end.y] = GraphNode.Type.END;
    }
    
    public static void resetPath() {
        // Pfad zuruecksetzen
        for (Point itPoint : path) {
            mapArray[itPoint.x][itPoint.y] = GraphNode.Type.EMPTY;
        }
        path.clear();
    }
    
    /**
     * Getter fuer den Startpunkt.
     * @return der Startpunkt
     */
    public static Point getStart() {
        return start;
    }
    
    /**
     * Getter fuer den Endpunkt.
     * @return der Endpunkt
     */
    public static Point getEnd() {
        return end;
    }
    
    /**
     * Getter fuer die Hindernisse.
     * @return alle Hindernisse auf der Map
     */
    public static Set<Point> getObstacles() {
        return obstacles;
    }
    
    /**
     * Getter fuer den Path.
     * Solle erst benutzt werden, wenn dieser mit findPath() berechnet wurde.
     * @return der kuerzeste Pfad zwischen Start- und Endpunkt
     */
    public static Set<Point> getPath() {
        return path;
    }
}
```
Ich glaube für jemanden der nur etwas mit Java umgehen kann sollte das ne einfache Aufgabe sein -__-
Ich hab schon rumexperimentiert, hab aber nur NullPointerExeptions bekommen...


----------



## xEbo (10. Januar 2010)

Map & Main hast du das gleiche gepostet?!


----------



## jokergermany (10. Januar 2010)

xEbo schrieb:


> Map & Main hast du das gleiche gepostet?!


****, sry korrigiert.


----------



## xEbo (11. Januar 2010)

was kriegst denn genau nicht hin? Wie viel hast du mit Java schon gearbeitet? Von wem stammt die Aufgabe?


----------



## jokergermany (6. April 2010)

Da ich per PN angefragt wurde, veröffentliche ich hier mal die fast komplette Lösung. Sie ist allerdings nicht von mir!

In dieser Lösunge fehlt das  Auswahlfeld der Größe vom löschen und integrieren als Applet.

Main

```
package aStar_Prog;

import java.awt.*;
import java.awt.event.*;
import java.util.Iterator;

import javax.swing.*;

/**
 * Hauptklasse, die vor allem fuer das Zeichnen der Elemente zustaendig ist.
 *
 */
public class Main {
    private static final long serialVersionUID = 1L;

    private JFrame mainFrame;
    private JPanel drawPanel;
    private JToolBar toolbar;
    
    /* Mouse events */
    private MouseAdapter mouseClick = null;
    private MouseMotionAdapter mouseMotion = null;
    
    /* Actions */
    private boolean[][] obstacles = new boolean[73][68];
    private enum Action {
        start,
        end,
        obstacle,
        erase,
        makeNew
    };
    Action action = Action.obstacle;
    
    /**
     * Einmaliges initialisieren des Applets.
     */
    public void init() {
        Map.init();
        Map.setStart( new Point ( 0, 0 ) );
        Map.setEnd( new Point ( 64, 64 ) );
        
        mouseClick = new MouseAdapter() {
            public void mousePressed ( MouseEvent e ) {    
                int x = (e.getX() - (e.getX() % 8)) / 8;
                int y = (e.getY() - (e.getY() % 8)) / 8;
                x = x>64 ? 64:x;
                y = y>64 ? 64:y;
                
                switch ( action ) {
                    case start:
                        Map.setStart( new Point ( x, y ) );
                        break;
                    case end:
                        Map.setEnd( new Point ( x, y) );
                        break;
                    case obstacle:
                        Map.createObstacle( new Point ( x, y ) );
                        break;
                    case erase:
                        Map.deleteObstacle( new Point ( x, y ) );
                        break;
                }
                
                drawPanel.repaint();
            }
        };
        
        mouseMotion = new MouseMotionAdapter() {
            public void mouseDragged ( MouseEvent e ) {
                int x = (e.getX() - (e.getX() % 8)) / 8;
                int y = (e.getY() - (e.getY() % 8)) / 8;
                
                switch ( action ) {
                    case obstacle:
                        Map.createObstacle( new Point ( x, y ) );
                        break;
                    case erase:
                        Map.deleteObstacle( new Point ( x, y ) );
                        break;
                }
                
                drawPanel.repaint();
            }
        };
        
        initValues();
        initToolbars();
        initDrawPanel();
        
        JPanel paneInIn = new JPanel(new BorderLayout());
        paneInIn.add(new JPanel(), BorderLayout.CENTER);
        paneInIn.add(this.toolbar, BorderLayout.NORTH);
        paneInIn.add(this.drawPanel, BorderLayout.CENTER);
        
        
        JPanel paneIn = new JPanel(new BorderLayout());
        paneIn.add(paneInIn, BorderLayout.WEST);
        paneIn.add(new JPanel(), BorderLayout.CENTER);
        paneIn.add(new JPanel(), BorderLayout.SOUTH);
        JScrollPane pane = new JScrollPane(paneIn);
        pane.setPreferredSize(new Dimension(560,565));
        
        JPanel main = new JPanel(new BorderLayout());
        main.add(pane, BorderLayout.CENTER);
        
        mainFrame = new JFrame();
        mainFrame.setLayout(new BorderLayout());
        mainFrame.add(main, BorderLayout.CENTER);
        mainFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        mainFrame.pack();
        mainFrame.setVisible(true);
    }
    
    
    /**
     * Initialisiert das Panel, auf das die Map gezeichnet wird.
     * Beinhaltet MouseListener zum Clicken und Draggen.
     */
    private void initDrawPanel() {
        // TODO implementieren
        drawPanel = new JPanel() {
            private static final long serialVersionUID = 1L;
            public void paint ( Graphics g ) {
                super.paint(g);
                
                /* Draw start and end point */
                g.setColor( Color.red );
                g.drawOval ( Map.getStart().x * 8, Map.getStart().y * 8, 8, 8);
                g.setColor( Color.blue );
                g.drawOval ( Map.getEnd().x * 8, Map.getEnd().y * 8, 8, 8);
                
                /* Draw path */
                Map.findPath();
    
                g.setColor( Color.green );
                Iterator<Point> it2 = Map.getPath().iterator();
                while (it2.hasNext()) {
                    Point point = it2.next();
                    g.fillRect(point.x*8, point.y*8, 8, 8);
                }
                
                /* Draw */
                g.setColor( Color.black );
                Iterator<Point> it = Map.getObstacles().iterator();
                while (it.hasNext()) {
                    Point point = it.next();
                    g.fillRect(point.x*8, point.y*8, 8, 8);
                }
                
                /* Reset path */
                Map.resetPath();

                
            }
        };
        drawPanel.setPreferredSize(new Dimension(521, 521));
        drawPanel.setBackground(Color.WHITE);
        
        drawPanel.addMouseListener ( mouseClick );
        drawPanel.addMouseMotionListener ( mouseMotion );

    }
    
    /**
     * Initialisiert alle Toolbars.
     */
    private void initToolbars() {
        // 
        JButton buttonStartPoint = new JButton("Startpunkt");
        JButton buttonEndPoint = new JButton("Endpunkt");
        JButton buttonObstaclePoint = new JButton("Hindernis");
        JButton buttonErasePoint = new JButton("Radieren");
        JButton buttonNewPoint = new JButton("Neu");
        
        buttonStartPoint.setBackground( Color.red );
        buttonEndPoint.setBackground( Color.blue );
        
        /* Actions */
        buttonStartPoint.addActionListener( new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                action = Action.start;
            }
        });
        
        buttonEndPoint.addActionListener( new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                action = Action.end;
            }
        });
        
        buttonObstaclePoint.addActionListener( new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                action = Action.obstacle;
            }
        });
        
        buttonErasePoint.addActionListener( new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                action = Action.erase;
            }
        });
        
        buttonNewPoint.addActionListener( new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                Map.init();
                Map.setStart( new Point ( 0, 0 ) );
                Map.setEnd( new Point ( 64, 64 ) );
                
                drawPanel.repaint();
            }
        });
        
        /* Add to toolbar */
        toolbar = new JToolBar();
        
        toolbar.add ( buttonStartPoint );
        toolbar.add ( buttonEndPoint );
        toolbar.add ( buttonObstaclePoint );
        toolbar.add ( buttonErasePoint );
        toolbar.add ( buttonNewPoint );
    }

    /**
     * Initialisiert die Applikation mit Startwerten.
     * Wird auch beim Druecken des "Neu"-Buttons aufgerufen.
     */
    private void initValues() {
        // TODO implementieren
    }
    
    /**
     * Benutzt den Radiergummi unter Beachtung der ausgewaehlten
     * Radiergroesse, um Hindernisse zu loeschen.
     * @param thePoint der Mittelpunkt des zu radierenden Bereichs
     */
    @SuppressWarnings("unused")
    private void useEraser(Point thePoint) {
        // TODO implementieren fuer Aufgabe 2
    }
    
    /**
     * Hauptmethode
     * @param args
     */
    public static void main(String[] args) {
        Main me = new Main();
        me.init();
    }

}
```
Map

```
package aStar_Prog;

import java.awt.Point;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;

/**
 * Datenstruktur, die Hindernisse, Start- und Endpunkt sowie den Pfad zwischen diesen verwaltet.
 * Der kuerzeste Pfad zwischen Start- und Endpunkt kann mit der Methode findPath() per A*-Algorithmus
 * berechnet und in die Datenstruktur eingetragen werden.
 *
 */
public class Map {
    private static PriorityQueue<GraphNode> openNodes;
    private static HashSet<GraphNode> closedNodes;
    private static ArrayList<GraphNode> buildList;

    private static GraphNode.Type[][] mapArray;

    public final static int WIDTH = 65;
    public final static int HEIGHT = 65;
    
    private static Point start;
    private static Point end;
    private static Set<Point> obstacles;
    private static Set<Point> path;

    protected static GraphNode.Type[][] getMap() {
        return mapArray;
    }

    private static GraphNode targetNode;
    private static GraphNode playerNode;

    /**
     * Initialisiert die AStarMap.
     * Muss mindestens einmal aufgerufen worden sein, bevor
     * andere Methoden dieser Klasse verwendet werden koennen.
     */
    public static void init() {
        mapArray = new GraphNode.Type[Map.WIDTH][Map.HEIGHT];
        obstacles = new HashSet<Point>();
        path = new HashSet<Point>();
        start = new Point(3, 3);
        
        for (int i = 0; i < Map.WIDTH; i++) {
            for (int j = 0; j < Map.HEIGHT; j++) {
                mapArray[i][j] = GraphNode.Type.EMPTY;
            }
        }
        mapArray[0][0] = GraphNode.Type.START;
        end = null;
    }
    
    /**
     * Erstellt die Nachbarschaftsbeziehungen zwischen Knoten,
     * die fuer den A*-Algorithmus noetig sind.
     */
    private static void buildListForAStar() {
        buildList = new ArrayList<GraphNode>();

        for (int i = 0; i < WIDTH; i++) {
            for (int j = 0; j < HEIGHT; j++)
                buildList.add(new GraphNode(i, j));
        }

        for (int i = 0; i < WIDTH * (HEIGHT - 1); i++) {
            buildList.get(i).setSouth(buildList.get(i + WIDTH));
        }

        for (int i = WIDTH; i < WIDTH * HEIGHT; i++) {
            buildList.get(i).setNorth(buildList.get(i - WIDTH));
        }

        for (int i = 0; i < WIDTH * HEIGHT; i++) {
            if (i % WIDTH != 0)
                buildList.get(i).setWest(buildList.get(i - 1));
        }

        for (int i = 0; i < WIDTH * HEIGHT; i++) {
            if (i % WIDTH != (WIDTH - 1))
                buildList.get(i).setEast(buildList.get(i + 1));
        }
    }
    
    /**
     * Sucht den kuerzesten Pfad zwischen Start- und Endpunkt unter Beachtung
     * der Hindernisse und setzt ihn in das Feld.
     * (Kuerzester Pfad im Sinne des Manhattan-Abstands,
     * nicht euklidischer Abstand!)
     */
    public static void findPath() {
        long time = System.nanoTime();

        if (buildList == null)
            buildListForAStar();

        for (GraphNode n : buildList)
            n.reset();

        playerNode = buildList.get(start.x * WIDTH + start.y);
        targetNode = buildList.get(WIDTH * end.x + end.y);

        openNodes = new PriorityQueue<GraphNode>();
        closedNodes = new HashSet<GraphNode>();

        GraphNode startNode = buildList.get(start.x * WIDTH + start.y);
        startNode.setDistance(0);
        openNodes.add(startNode);
        GraphNode tmp;
        
        int i = 0;

        while (!openNodes.isEmpty()) {
            i++;
            tmp = openNodes.poll();

            if (tmp == targetNode)
                break;

            addFriends(tmp);
        }

        GraphNode tmp2 = targetNode.getHome();
        if (tmp2 != null) {
            while (tmp2 != playerNode) {
                mapArray[tmp2.getX()][tmp2.getY()] = GraphNode.Type.PATH;
                path.add(new Point(tmp2.getX(), tmp2.getY()));
                tmp2 = tmp2.getHome();
            }
        }

        System.out.println("Nodes checked: " + i);
        System.out.println("Time needed (ms): " + (System.nanoTime() - time) / (1000*1000));
    }

    /**
     * Finds out whether the specified GraphNode is an obstacle.
     * @return the GraphNode to examine
     */
    private static boolean isObstacle(GraphNode theNode) {
        return mapArray[theNode.getX()][theNode.getY()] == GraphNode.Type.OBSTACLE;
    }
    
    /**
     * A*-relevante Berechnungen (closed und open list)
     * @param node der aktuell zu berechnende Knoten
     */
    private static void addFriends(GraphNode node) {
        closedNodes.add(node);

        GraphNode north = node.getNorth();
        GraphNode south = node.getSouth();
        GraphNode west = node.getWest();
        GraphNode east = node.getEast();

        if (north != null && !closedNodes.contains(north) && !isObstacle(north)) {
            if (node.getDistance() + 1 < north.getDistance()) {
                north.setHome(node);
                north.calculateDistance();
                north.calculateFitness();
            }
            if (!openNodes.contains(north))
                openNodes.add(north);
        }

        if (south != null && !closedNodes.contains(south) && !isObstacle(south)) {
            if (node.getDistance() + 1 < south.getDistance()) {
                south.setHome(node);
                south.calculateDistance();
                south.calculateFitness();
            }
            if (!openNodes.contains(south))
                openNodes.add(south);
        }

        if (west != null && !closedNodes.contains(west) && !isObstacle(west)) {
            if (node.getDistance() + 1 < west.getDistance()) {
                west.setHome(node);
                west.calculateDistance();
                west.calculateFitness();
            }
            if (!openNodes.contains(west))
                openNodes.add(west);
        }

        if (east != null && !closedNodes.contains(east) && !isObstacle(east)) {
            if (node.getDistance() + 1 < east.getDistance()) {
                east.setHome(node);
                east.calculateDistance();
                east.calculateFitness();
            }
            if (!openNodes.contains(east))
                openNodes.add(east);
        }
    }
    
    /**
     * Setzt ein Hindernis.
     * @param thePoint der Punkt, an den das Hindernis gesetzt werden soll.
     */
    public static void createObstacle(Point thePoint) {
        if (!thePoint.equals(start) && !(thePoint.equals(end))) {
            obstacles.add(thePoint);
            mapArray[thePoint.x][thePoint.y] = GraphNode.Type.OBSTACLE;
        }
    }
    
    /**
     * Loescht ein eventuell vorhandenes Hindernis.
     * @param thePoint der Punkt, an dem das Hindernis gelscht werden soll
     */
    public static void deleteObstacle(Point thePoint) {
        if (!thePoint.equals(start) && !(thePoint.equals(end))) {
            mapArray[thePoint.x][thePoint.y] = GraphNode.Type.EMPTY;
            obstacles.remove(thePoint);
        }
    }
    
    /**
     * Setzt den Startpunkt.
     * @param thePoint der neue Startpunkt.
     */
    public static void setStart(Point thePoint) {
        // alten Startpunkt loeschen
        mapArray[start.x][start.y] = GraphNode.Type.EMPTY;

        // Startpunkt setzen
        start = thePoint;
        mapArray[start.x][start.y] = GraphNode.Type.START;
    }
    
    /**
     * Setzt den Endpunkt.
     * @param thePoint der neue Endpunkt.
     */
    public static void setEnd(Point thePoint) {
        // evt. alten Endpunkt loeschen
        if (end != null)
            mapArray[end.x][end.y] = GraphNode.Type.EMPTY;
        
        // Endpunkt setzen
        end = thePoint;
        mapArray[end.x][end.y] = GraphNode.Type.END;
    }
    
    public static void resetPath() {
        // Pfad zuruecksetzen
        for (Point itPoint : path) {
            mapArray[itPoint.x][itPoint.y] = GraphNode.Type.EMPTY;
        }
        path.clear();
    }
    
    /**
     * Getter fuer den Startpunkt.
     * @return der Startpunkt
     */
    public static Point getStart() {
        return start;
    }
    
    /**
     * Getter fuer den Endpunkt.
     * @return der Endpunkt
     */
    public static Point getEnd() {
        return end;
    }
    
    /**
     * Getter fuer die Hindernisse.
     * @return alle Hindernisse auf der Map
     */
    public static Set<Point> getObstacles() {
        return obstacles;
    }
    
    /**
     * Getter fuer den Path.
     * Solle erst benutzt werden, wenn dieser mit findPath() berechnet wurde.
     * @return der kuerzeste Pfad zwischen Start- und Endpunkt
     */
    public static Set<Point> getPath() {
        return path;
    }
}
```
GraphNode

```
package aStar_Prog;

/**
 * Stellt einen Graphenknoten zur Verwendung mit dem A*-Algorithmus dar.
 *
 */
public class GraphNode implements Comparable<GraphNode>{
    private int x;
    private int y;
    private double fitness;
    private double distanceToPlayer = 99999999;
    
    private GraphNode home = null;
    private GraphNode north = null;
    private GraphNode south = null;
    private GraphNode west = null;
    private GraphNode east = null;
    
    public enum Type {EMPTY, START, END, PATH, OBSTACLE};
    
    public GraphNode(int x, int y) {
        this.x = x;
        this.y = y;
        calculateFitness();
    }
    
    /**
     * Knoten zu Ausgangszustand
     */
    public void reset(){
        home = null;
        distanceToPlayer = 99999999;
        calculateFitness();
    }
    
    /**
     * @return oberer Nachbar
     */
    public GraphNode getNorth() {
        return north;
    }

    /**
     * setzt oberen Nachbar
     * @param north oberer Nachbar
     */
    public void setNorth(GraphNode north) {
        this.north = north;
    }

    /**
     * @return unteren Nachbar
     */
    public GraphNode getSouth() {
        return south;
    }

    /**
     * setzt unteren Nachbar
     * @param south unterer Nachbar
     */
    public void setSouth(GraphNode south) {
        this.south = south;
    }

    /**
     * @return linker Nachbar
     */
    public GraphNode getWest() {
        return west;
    }

    /**
     * setzt linken Nachbar
     * @param west linker Nachbar
     */
    public void setWest(GraphNode west) {
        this.west = west;
    }

    /**
     * @return rechter Nachbar
     */
    public GraphNode getEast() {
        return east;
    }

    /**
     * setzt rechten Nachbar
     * @param east rechter Nachbar
     */
    public void setEast(GraphNode east) {
        this.east = east;
    }

    /**
     * setzt Vorgnger auf dem bisherigen Pfad
     * @param home Vorgnger
     */
    public void setHome(GraphNode home){
        this.home = home;
    }
    
    /**
     * @return den Vorgnger auf dem Pfad
     */
    public GraphNode getHome() {
        return home;
    }
    
    /**
     * berechnet momentane Wertigkeit
     */
    public void calculateFitness(){            
        fitness = distanceToPlayer + estimateDistanceToTarget();
    }
    
    /**
     * setzt die Entfernung zum Start
     * @param distance
     */
    public void setDistance(double distance){
        distanceToPlayer = distance;
    }

    /**
     * @return die Entfernung zum Start
     */
    public double getDistance(){
        return distanceToPlayer;
    }
    
    /**
     * berechnet die Entfernung zum Start
     */
    public void calculateDistance(){
        distanceToPlayer = 1 + home.distanceToPlayer;
    }
    
    /**
     * @return die Wertigkeit
     */
    public double getFitness(){
        return fitness;
    }
    
    /**
     * prft ob dieser Knoten die gegeben Parameter hat
     * @param x Koordinate
     * @param y Koordinate
     * @return true wenn dieser Knoten mit den gegebenen Koordinaten bereinstimmt
     */
    public boolean isNode(int x, int y) {
        if (this.x == x && this.y == y)
            return true;
        else
            return false;
    }
    
    /**
     * @return x-Koordinate
     */
    public int getX() {
        return x;
    }

    /**
     * @return y-Koordinate
     */
    public int getY() {
        return y;
    }
    
    /**
     * schtzt die Entfernung zum Zielpunkt
     * @return die Schtzung
     */
    public double estimateDistanceToTarget() {
        int targetX = Map.getEnd().x;
        int targetY = Map.getEnd().y;
        
        return Math.sqrt((double) ((targetX-x)*(targetX-x) + (targetY-y)*(targetY-y)));
    }

    /**
     * vergleicht anhand der Wertigkeit
     */
    
    public int compareTo(GraphNode node) {
        if (fitness == node.getFitness())
        return 0;
        else if (fitness > node.getFitness())
            return 1;
        else
            return -1;
    }
}
```


----------

