✔ Grafische Umsetzung des A*

[Federhalter]

Hallo,

mal wieder geht's um den A* nach sehr langer Arbeit daran, habe ich ihn jetzt endlich fertiggestellt.

Leider hat sich wieder ein neues Problem aufgetan.
Ich möchte nun, dass sich Einheiten ( mir reicht auch schon mal eine einzige ) als eine Art Figur, entlang des ermittelten Pfades bewegen.

Das ist allerdings alles nicht so einfach wie ich dachte. Zwar möchte ich schon wissen wie das funktioniert, allerdings tauchen mehrere Probleme auf.

1. Wie genau muss das Spielfeld aufgebaut sein, um Einheiten überhaupt wie gewohnt mit der üblichen Formel zu bewegen?
2. Mein A* verwendet Nachbarn, die genau 1x1 sind. Wie verhindert man dann Performanceprobleme bei größeren Spielfeldern?
3. (Analog zu 2 ) Gibt es noch andere Ansätze die zum Erfolg führen?

Nun nochmal etwas konkreteres:

Ich habe meinen Pfad in einer Liste, der via Mausklick auf das Spielfeld generiert und gezeichnet wird.

Das heißt ich kann auf jedes Element der Pfadliste zugreifen.
Natürlich weiß ich, dass ich nun meiner Einheit einfach nur die Position von den Elementen aus dem Pfad zuweisen müsste, allerdings klappt das nicht so ganz.
Denn, nachdem die Einheit das Ende des ersten Pfadelements der Liste erreicht hat, stürzt das gesamte Programm ab, ohne Fehlermeldung in der Konsole, aber mit Fehlermeldung von Windows.
Normalerweise lernt man ja aus Fehlern, aber wenn man nicht weiß, was genau der Fehler ist, wird es schwierig.

Also nochmal zusammengefasst:

In einer Methode move() soll eine Einheit entlang des ermittelten Pfades grafisch bis zum Ziel bewegt werden. Wie erreicht man das?

Hier mal meine fehlerhafte move()-Methode:

public void move(){
     
        if(Mouse.right){
            int startx = x / size;
            int starty = y / size;
            int endx = (Mouse.mousex-(Mouse.mousex%size))/size;
            int endy = (Mouse.mousey-(Mouse.mousey%size))/size;
         
            path = findPath(startx,starty,endx,endy);
        }
     
     
        if(path!=null){
            if(path.size() > 0){
                Node node = path.get(path.size()-1);
                x = node.i*size;
                y = node.j*size;
             
            }
        }
    }

Wie ordnet man die Positionen des Pfades besser den Positionen der Einheit zu und warum stürtzt das gesamte Programm ab?

Gruß Eichelhäer

 

[Technipion]

Hallo Eichelhäer,
ich erkläre zunächst, wie ich dein Problem verstanden habe, da ich mir nicht ganz sicher bin.
Also du hast eine m x n Matrix aus Spielfeldern. Diese Spielfelder sind entweder frei, oder besetzt (.isBlocked() = true). Du hast den A*-Algorithmus benutzt, um den kürzesten Pfad von einem gegebenen Punkt im "Labyrinth" zu einem anderen Punkt zu finden (wahrscheinlich indem du die Spielfelder als Knoten eines Graphen modelliert hast). Jetzt möchtest du auf Befehl deine Figur Feld-für-Feld von ihrer Startposition zu ihrer Endposition bewegen. Dafür soll sie dem von deinem Algo errechneten Pfad folgen. Das scheint auch für eine Weile ganz gut zu funktionieren, allerdings stürzt dann das Programm ab. Ist das soweit richtig?

Falls ja, dann brauchen wir:
- Deinen A*-Algorithmus, bzw. den Code davon.
- Den Code, in dem du deine Figur bewegst.
- Die exakte Codestelle die zum Absturz führt.

Wenn du uns das gibst, können wir sicher helfen .

Gruß Technipion

 

[Federhalter]

Das hört sich sehr vielversprechend an.
Und ja du hast mein Problem verstanden und auch mein Vorgehen.
So hier mal der Code der Levelklasse und die Nodeklasse, ich denke der Rest ist nicht relevant:

package main;

import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Level{
   
    public int x;
    public int y;
   
    public int k;
   
    public int w;
    public int h;
   
    public int cols = 50;
    public int rows = 50;
   
    public int startx;
    public int starty;
   
    public Node[][] grid = new Node[cols][rows];
   
    List<Node> openList = new ArrayList<Node>();
    List<Node> closedList = new ArrayList<Node>();
    List<Node> path = new ArrayList<Node>();
   
    Node start;
    Node end;
    Node node;
   
    public Level(int WIDTH,int HEIGHT){

        w = WIDTH / cols;
        h = HEIGHT / rows;
       
        for(int i = 0;i<cols;i++){
            for(int j = 0;j<rows;j++){
                grid[i][j] = new Node(i,j);
            }
        }
       
        for(int i = 0;i<cols;i++){
            for(int j = 0;j<rows;j++){
                grid[i][j].addNeighbours(grid);
            }
        }
    }
   
    public ArrayList<Node> findPath(int sx,int sy,int ex,int ey){
       
        start = grid[sx][sy];
        end = grid[ex][ey];
       
        openList.add(start);
       
        while(openList.isEmpty()==false){
           
            int winner = 0;
            for(int i = 0;i <openList.size();i++){
                if(openList.get(i).f < openList.get(winner).f){
                    winner = i;
                }
            }
           
            Node current = openList.get(winner);
            openList.remove(current);
            closedList.add(current);
           
            if(current == end){
                ArrayList<Node> path = new ArrayList<Node>();
                Node tmp = current;
                path.add(tmp);
                while(tmp.previous!=null){
                    path.add(tmp.previous);
                    tmp = tmp.previous;
                }
                openList.clear(); // wenn ich diesen Befehl
                closedList.clear();// und diesen Befehl weglasse kommt ne brutale nullpointerException und keine Ahnung warum
                Collections.reverse(path);
                return path;
            }
           
            List<Node> neighbours = current.neighbours;
           
            for(Node neighbour : neighbours){
                int cost = current.g + heuristic(current,neighbour);
                if(openList.contains(neighbour) && cost < neighbour.g){
                    openList.remove(neighbour);
                }
                if(closedList.contains(neighbour) && cost < neighbour.g){
                    closedList.remove(neighbour);
                }
                if(openList.contains(neighbour) == false && closedList.contains(neighbour) == false && neighbour.obstacle == false){
                    neighbour.g = cost;
                    openList.add(neighbour);
                    neighbour.f = neighbour.g + neighbour.h;
                    neighbour.previous = current;
                }
            }
        }
       
        return null;
    }
   
    public void render(Graphics g){
        if(Mouse.right){
            int endx = (Mouse.mousex-(Mouse.mousex%w))/w;
            int endy = (Mouse.mousey-(Mouse.mousey%h))/h;
            path = findPath(0,0,endx,endy); //wenn ich hier statt 0,0 x,y einsetzte kommt der krasse Absturz.
        }
        if(path!=null){
            if(path.size() > k){
                node = path.get(k);
                if(node.j*h > y)y++;
                if(node.j*h < y)y--;
                if(node.i*w > x)x++;
                if(node.i*w < x)x--;
                if(x == node.i*w && y == node.j*h){
                    k++;
                }
            }
        }
       
        for(int i = 0;i<cols;i++){
            for(int j = 0;j<rows;j++){
               
                if(grid[i][j].obstacle){
                    g.setColor(Color.BLACK);
                    g.fillRect(grid[i][j].i*w,grid[i][j].j*h,w,h);
                }
                if(!grid[i][j].obstacle){
                    g.setColor(Color.BLACK);
                    g.drawRect(grid[i][j].i*w,grid[i][j].j*h,w,h);
                }
            }
        }
       
        for(int i = 0;i<openList.size();i++){
            g.setColor(Color.GREEN);
            g.fillRect(openList.get(i).i*w,openList.get(i).j*h,w,h);
        }
       
        for(int i = 0;i<closedList.size();i++){
            g.setColor(Color.RED);
            g.fillRect(closedList.get(i).i*w,closedList.get(i).j*h,w,h);
        }
       
        for(int i = 0;i<path.size();i++){
            g.setColor(Color.BLUE);
            g.fillRect(path.get(i).i*w,path.get(i).j*h,w,h);
        }
       
        g.setColor(Color.CYAN);
        g.fillRect(x,y,w,h);
    }
   
    public int heuristic(Node A,Node B){
        // 4-Direction-Manhattendistance
        int dx = Math.abs(A.i-B.i);
        int dy = Math.abs(A.j-B.j);
        return 1 * (dx + dy);
       
        // 8-Direction-Chebyshevdistance
        //int dx = Math.abs(A.i-B.i);
        //int dy = Math.abs(A.j-B.j);
        //return 1 * (dx + dy) + ( 1 - 2 * 1) * Math.min(dx,dy);
       
        // 8-Direction-Octiledistance
        //int dx = Math.abs(A.i-B.i);
        //int dy = Math.abs(A.j-B.j);
        //return 1 * (dx + dy) + ( Math.sqrt(2) - 2 * 1) * Math.min(dx,dy);
       
        // Euclidiandistance
        //int dx = Math.abs(A.i-B.i);
        //int dy = Math.abs(A.j-B.j);
        //return 1 * Math.sqrt(dx * dx + dy * dy);
    }
}

Und die zweite:

package main;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Node{

    public int i;
    public int j;
    public int g;
    public int h;
    public int f;
    public List<Node> neighbours;
    public Node previous;
    public boolean obstacle;
    public Random random = new Random();
   
    public Node(int i,int j) {
        this.i = i;
        this.j = j;
        this.g = 0;
        this.h = 0;
        this.f = 0;
        this.previous = null;
        this.obstacle = false;
        this.neighbours = new ArrayList<Node>();
       
        if(random.nextInt(100) < 10){
            this.obstacle = true;
        }
    }
   
    public List<Node> addNeighbours(Node[][] grid){
       
        int i = this.i;
        int j = this.j;
               
        if(i < 50 - 1){
            neighbours.add(grid[i+1][j]);
        }
        if(i > 0){
            neighbours.add(grid[i-1][j]);
        }       
        if(j < 50 - 1){
            neighbours.add(grid[i][j+1]);
        }
        if(j > 0){
            neighbours.add(grid[i][j-1]);
        }
       
        return neighbours;
       
    }
}

Ich habe Kommentare eingefügt wo ich Probleme habe.

 

[Federhalter]

Hallo nochmal,
ich glaube ich weiß jetzt woran es liegt.
Die Nodes und die Nachbarnodes müssen alle zur LAUFZEIT bekannt sein, was bei meinem Code NICHT der Fall ist, denn das grid und die nachbarn werden nur EINMAL durch den Konstruktoraufruf des Levels geladen.
D.h. jetzt im Klartext, dass mein Programmaufbau sehr schlecht ist.
Ich werde mich gleich an die Arbeit machen.
Falls jemand spontan Lust hat hier kurz ein paar grundlegende Objektorientierte einfache Programmaufbauten für mein Beispiel zu posten, dann immer her damit.
Es reicht auch eine Art PseudoCode.
Falls das am Ende doch nicht klappen sollte und der A* dennoch nicht funktioniert, dann melde ich mich nochmal.
Gruß Federhalter.

 

[Federhalter]

Hallo und jetzt das letzte mal:

Es lag tatsächlich daran und ich habe es jetzt und es funktionier tadellos.

Damit wäre das Thema geschlossen.