A* Algorithmus Problem mit Labyrinth


#1
Hallo,

ich hoffe ich kann mein Problem möglichst exakt schildern. Bitte fragt nach wenn ihr es nicht verstehen solltet.

Also, ich habe einen A* Algorithmus geschrieben und stelle diesen graphisch in einem Fenster dar.
Als Spielfeld habe ich ein aus 32x32 großen Rechtecken bestehendes Gitter generiert und lasse mir auf diesem mit dem Startpunkt 0,0 hin zu einem beliebigen mit der Maus geklickten Ziel den kürzesten Pfad ausgeben.

Nun ist das etwas langweilig und ich habe aus dem Spielfeld ein Labyrinth gemacht.
Hierbei habe ich dann abhängig von einer txt-Datei bestimmt, wo die nicht- bzw. begehbaren Felder liegen sollen. Das habe ich überprüft und es stimmt.

Das Problem ist nun, dass ich zwar punktuell den richtigen Wert, also begehbar oder nicht-begehbar, bekomme, aber NICHT bei der Überprüfung der Nachbarknoten im A*. Anstatt mir begehbare Felder anzuzeigen, werden mir nur die NICHT-begehbaren Felder(also blocked = true) angezeigt.

Hier mal die Levelklasse mit dem A*:

Java:
public class Level {

    private int xo;
    private int yo;
    private int width;
    private int height;
    private Tile[][] spielfeld;
    private int[][] mapData;
   
    private static Comparator<Node> nodeSorter = new Comparator<Node>(){
        public int compare(Node n0, Node n1) {
            if(n1.f < n0.f) return +1;
            if(n1.f > n0.f) return -1;
            return 0;
        }
    };
   
    public Level(int width,int height) {
        this.width = width;
        this.height = height;
        spielfeld = new Tile[width][height];
        mapData = MapLoader.loadMap("map",width,height);
        for(int i = 0;i<width;i++){
            for(int j = 0;j<height;j++){
                int tileID = mapData[i][j];
                tileID--;
                spielfeld[i][j] = new Tile(i*32,j*32,tileID);
            }
        }       
    }
   
    public ArrayList<Node> findPath(int startx,int starty,int goalx,int goaly){
       
        TreeSet<Node> openList = new TreeSet<Node>(nodeSorter);
        HashSet<Node> closedList = new HashSet<Node>();
       
        Node start = new Node(startx,starty,false);
       
        openList.add(start);
       
        while(!openList.isEmpty()){
            Node current = openList.first();
            openList.remove(current);
            closedList.add(current);
            if(current.getX() == goalx && current.getY() == goaly){
                ArrayList<Node> path = new ArrayList<Node>();
                while(current.parent != null){
                    path.add(current);
                    current = current.parent;
                }
                openList.clear();
                closedList.clear();
                return path;
            }
           
            Node[] neighbours = getNeighbours(current);
            for(Node successor : neighbours){
                double g = current.g + getDistance(current.x,current.y,successor.x,successor.y);
                double h = getDistance(successor.x,successor.y,goalx,goaly);
                double f = g + h;
                if(closedList.contains(successor))continue;
                successor.setParent(current);
                successor.setF(f);
                for(int i = 0;i<width;i++){
                    for(int j = 0;j<height;j++){
                        int tileID = mapData[i][j];
                       
                        if(tileID == 58){
                            successor.setBlocked(true);
                        }
                    }
                }
                if(successor.isBlocked())openList.add(successor);
               
                System.out.println(successor.isBlocked());
            }
        }
        closedList.clear();
        return null;
    }
   
    private double getDistance(int currentx, int currenty,int successorx,int successory) {
        double dx = currentx - successorx;
        double dy = currenty - successory;
        return Math.sqrt((dx*dx) + (dy*dy));
    }

    public Node[] getNeighbours(Node current){
       
        Node[] neighbours = new Node[8];
       
        neighbours[0] = new Node(current.getX()+32,current.getY(),current.isBlocked());
        neighbours[1] = new Node(current.getX()+32,current.getY()+32,current.isBlocked());
        neighbours[2] = new Node(current.getX(),current.getY()+32,current.isBlocked());
        neighbours[3] = new Node(current.getX()-32,current.getY()+32,current.isBlocked());
        neighbours[4] = new Node(current.getX()-32,current.getY(),current.isBlocked());
        neighbours[5] = new Node(current.getX()-32,current.getY()-32,current.isBlocked());
        neighbours[6] = new Node(current.getX(),current.getY()-32,current.isBlocked());
        neighbours[7] = new Node(current.getX()+32,current.getY()-32,current.isBlocked());
       
        return neighbours;
    }

    public void render(Graphics g){
       
        for(int i = 0;i<width;i++){
            for(int j = 0;j<height;j++){
                spielfeld[i][j].render(g,xo,yo);
            }
        }
       
        int startx = 0;
        int starty = 0;
        int goalx = Mouse.mousex-(Mouse.mousex%32);
        int goaly = Mouse.mousey-(Mouse.mousey%32)-32;
       
        ArrayList<Node> path = findPath(startx,starty,goalx,goaly);
        if(Mouse.right){
            if(path!=null){
                for(Node node : path){
                    g.setColor(Color.BLUE);
                    g.fillRect(node.getX(), node.getY(),32,32);
                   
                }
            }
        }
    }
}
Wo liegt mein Fehler?

Ich möchte einfach nur, dass er mir den kürzesten Weg durch das Labyrinth anzeigt.


Wäre für schnelle Hilfe dankbar

MfG
 
#2
Sorry hab noch was vergessen:

Ab Zeile 67 muss natürlich noch das rein:

Java:
if(tileID == 6){
                            successor.setBlocked(true); //nicht begehbar
                        }
                        if(tileID == 58){
                            successor.setBlocked(false); // begehbar
                        }
                    }
                }
                if(!successor.isBlocked())openList.add(successor); wenn begehbar füge den Knoten hinzu
               
                System.out.println(successor.isBlocked());
MfG
 

*DJ*

Grünschnabel
#3
Hallo Federhalter,
schnelle Hilfe ist es zwar nicht mehr aber vielleicht stehst du ja immer noch vor dem Problem
Java:
for(int i = 0;i<width;i++){
                    for(int j = 0;j<height;j++){
                        int tileID = mapData[i][j];
                      
                        if(tileID == 58){
                            successor.setBlocked(true);
                        }
         
}
warum iterierst du dein Feld hier vollständig durch?
so wie du es machst wird jedes Tile in deiner mapData nach der ID 58 bzw 6 überprüfen und bei jeder gefundener Übereinstimmung deinen succesor erneut auf blocked oder nicht blocked setzen.

du willst doch nur wissen ob dein aktuelle Nachfolger geblockt ist oder nicht
warum schreibst du dann nicht: ?
Java:
     int tileID = mapData[successor.x][successor.y];
        
               if(tileID == 6){
                        successor.setBlocked(true);
               }
               if(tileID == 58){
                        successor.setBlocked(false);
               }
         
}
VG
 
#4
Ja danke, ach egal wie weit man kommt beim programmieren, am Ende landet man immer wieder bei den Grundlagen der Sprache Java.
Btw, wenn wir schon dabei sind. Es geht bei mir momentan immer noch um den A* ( der lässt mich einfach nicht in Ruhe) .
Man stelle sich ein Isometrisches Spielfeld vor, in dessen inneren begehbare und nicht begehbare Kacheln sind. Nun sind die nicht begehbaren Kacheln innerhalb des Spielfeldes ja nicht immer gleich groß oder als einzelne Kachel irgendwo auf dem Spielfeld, sondern es gibt auch größere Blöcke zusammenhängender Kacheln, die nicht begehbar sind.
Ich nehme hier an dieser Stelle einfach mal League of Legends her, das zwar in 3D ist, aber man gut mein Problem erkennen kann.

Nämlich folgendes:

Wenn man mit der Maus auf ein begehbares Feld klickt wird der A* berechnet. Soweit habe ich es bereits. Was ist jetzt aber wenn man auf ein nicht begehbares Feld klickt?
Ich strebe eine Lösung an die der von League of Legends am ähnlichsten ist, nämlich, dass egal auf welches nicht begehbare Feld ich klicke, der bestmögliche Weg oder Pfad dorthin berechnet wird. Wer League of Legends kennt weiß was ich meine. Und hier habe ich Probleme bei der konkreten Implementierung. Ich weiß das Forum soll hauptsächlich nur Denkanstöße geben, aber ich sitze schon geraume Zeit vor diesem Problem ( seit ca. 2 Wochen), und habe neben ausführlichen Durchdenkens meines Codes, auch TRY BY ERROR versucht aber es will nicht so wie ich will.

Doch bevor ich hier irgendwelchen Code poste, mit dem kein Mensch was anfangen kann, hier erstmal wie ich an das Problem rangegangen bin.

Ich suche mithilfe des A*-Algorithmus den Knoten aus der Closed List, der dem Ziel am nächsten ist und lass mir den Pfad dorthin ausgeben.

Aber alle meine Versuche schlugen fehl, also wenn sich hier keiner erbarmt und sich ebenso mit meinem Code beschäftigt, der mehr Erfahrung mit Java und dem A* hat, werde ich wohl noch länger allein daran knabbern müssen.

Gruß Federhalter