A* Algorithm

HerrInfo

Aktives Mitglied
Hallo zusammen,

ich versuche gerade, den A*-Algorithmus für ein Base-Defense-Spiel zu nutzen, aber leider funktioniert er nicht wie erwartet. Es scheint, dass kein passendes Feld als nächstes Ziel gewählt wird (Schleim springt und bewegt sich nur bis zu einem gewissen Punkt zum Ziel).
Anbei findet ihr den entsprechenden Code. Vielen Dank im Voraus für eure Hilfe.
Java:
package net.tim.Pathfinding;

import net.tim.gui.GamePanel;

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

public class Pathfinder {

    GamePanel gamePanel;
    Node[][] node;
    List<Node> openList = new ArrayList<>();
    public List<Node> pathList = new ArrayList<>();
    Node startNode, goalNode, currentNode;
    boolean goalReached = false;
    int step = 0;

    public Pathfinder(GamePanel gamePanel) {
        this.gamePanel = gamePanel;
        initNodes();
    }

    public void initNodes(){
        node = new Node[gamePanel.maxCol][gamePanel.maxRow];

        for (int row = 0; row < gamePanel.maxRow; row++) {
            for (int col = 0; col < gamePanel.maxCol; col++) {
                node[col][row] = new Node(col, row);
            }
        }
    }

    public void resetNodes(){
        for (int row = 0; row < gamePanel.maxRow; row++) {
            for (int col = 0; col < gamePanel.maxCol; col++) {
                node[col][row].open = false;
                node[col][row].checked = false;
                node[col][row].solid = false;
            }
        }

        openList.clear();
        pathList.clear();
        goalReached = false;
        step = 0;
    }

    public void setNode(int startCol, int startRow, int goalCol, int goalRow){
        resetNodes();

        startNode = node[startCol][startRow];
        currentNode = startNode;
        goalNode = node[goalCol][goalRow];
        openList.add(currentNode);


        //set solid nodes

        for (int row = 0; row < gamePanel.maxRow; row++) {
            for (int col = 0; col < gamePanel.maxCol; col++) {
                if (gamePanel.tile[row][col].isSolid()) {
                    node[col][row].solid = true;
                }

                getCost(node[col][row]);
            }
        }

    }

    public 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;
    }

    public boolean search(){
        while (!goalReached && step < 500){
            int col = currentNode.col;
            int row = currentNode.row;

            currentNode.checked = true;
            openList.remove(currentNode);

            //Open Up Node
            if (row - 1 >= 0) {
                openNode(node[col][row - 1]);
            }

            //Open Left Node
            if (col - 1 >= 0) {
                openNode(node[col - 1][row]);
            }

            //Open Down Node
            if (row + 1 < gamePanel.maxRow) {
                openNode(node[col][row + 1]);
            }

            //Open Right Node
            if (col + 1 < gamePanel.maxCol) {
                openNode(node[col + 1][row]);
            }

            //Find the best Node
            int bestNodeIndex = 0;
            int bestNodeFCost = Integer.MAX_VALUE;

            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;
                    }
                }
            }

            if (openList.isEmpty()) {
                break;
            }

            currentNode = openList.get(bestNodeIndex);
            if (currentNode == goalNode) {
                goalReached = true;
                trackThePath();
            }
            step++;
        }

        return goalReached;
    }

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

    public void trackThePath() {
        Node current = goalNode;
        while (current != startNode) {
            pathList.addFirst(current);
            current = current.parent;
        }
    }
}
Java:
package net.tim.gui;

import net.tim.Pathfinding.Pathfinder;
import net.tim.entity.Entity;
import net.tim.entity.Slime;

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

public class GamePanel extends JPanel {

    public final int maxCol = 30;
    public final int maxRow = 15;
    public final int TileSize = 75;

    public final int screenWidth = maxCol * TileSize;
    public final int screenHeight = maxRow * TileSize;

    public Tile[][] tile = new Tile[maxRow][maxCol];

    public final int goalCol = 28;
    public final int goalRow = 7;

    public Pathfinder pathfinder = new Pathfinder(this);

    public List<Entity> entityList = new ArrayList<>();

    public GamePanel(){

        setPreferredSize(new Dimension(screenWidth, screenHeight));
        setBackground(Color.BLACK);
        setLayout(new GridLayout(maxRow, maxCol));
        setFocusable(true);

        createTiles();
        createTestEntities();
    }

    private void createTestEntities() {
        entityList.add(new Slime(7, 1, this));
        entityList.getFirst().spawn();
    }

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

        while (col < maxCol && row < maxRow) {
            tile[row][col] = new Tile(row, col);
            this.add(tile[row][col]);

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

        tile[goalRow][goalCol].setAsBase();
        tile[7][1].setAsSpawn();
    }

    public void update() {
        for (Entity entity : entityList) {
            entity.moveOneTile();
        }
    }
}
Java:
package net.tim.entity;

import net.tim.gui.GamePanel;
import net.tim.gui.Tile;

import javax.swing.*;

public class Entity {
    GamePanel gamePanel;
    public int col;
    public int row;

    int health;
    int maxHealth;
    ImageIcon icon;
    Tile currentTile;
    Tile lastTile;

    public Entity(GamePanel gamePanel) {
        this.gamePanel = gamePanel;
    }

    private Tile searchNextTile(int goalCol, int goalRow) {

        int startCol = col;
        int startRow = row;

        gamePanel.pathfinder.setNode(startCol, startRow, goalCol, goalRow);
        if (gamePanel.pathfinder.search()){

            //next Col and Row
            int nextCol = gamePanel.pathfinder.pathList.get(0).col;
            int nextRow = gamePanel.pathfinder.pathList.get(0).row;

            return gamePanel.tile[nextCol][nextRow];
        }

        return null;
    }

    public void moveOneTile() {
        Tile nextTile = searchNextTile(gamePanel.goalCol, gamePanel.goalRow);
        if (nextTile != null) {
            col = nextTile.col;
            row = nextTile.row;
        }

        lastTile = currentTile;
        currentTile = nextTile;

        if (lastTile != null) {
            lastTile.setAsDefault();
        }
        if (currentTile != null) {
            currentTile.setIcon(icon);
        }
    }

    public void spawn() {
        currentTile = gamePanel.tile[col][row];
        currentTile.setIcon(icon);
    }

}

Falls sonst noch weitere Klassen benötigt werden, lasst es mich gerne wissen.
 

mihe7

Top Contributor
Dein getCost ist falsch. Du brauchst die tatsächlichen Kosten und eine Heuristik für die "künftigen" Kosten. Du berechnest ja einfach die "Luftlinie" (in der Manhatten Metrik) vom Startpunkt zum aktuellen Punkt und vom aktuellen Punkt zum Zielpunkt. Tatsächlich müsstest Du die bislang zurückgelegten Schritte plus 1 (der Schritt zum Nachbarn) und vom Nachbarfeld aus die Entfernung ("Luftlinie") zum Ziel.
 

HerrInfo

Aktives Mitglied
Erst einmal vielen Dank für die schnelle Antwort. Ich glaube leider, dass dies nicht der Grund ist, da ich die gleiche 'getCost'-Methode bereits in einem anderen Projekt verwendet habe und dort hat sie einwandfrei funktioniert.
 

mihe7

Top Contributor
An dem Algorithmus ist nicht nur die Funktion falsch, wenn ich es richtig sehe. Du hast ein statisches Kostenmodell aus zwei hypothetischen Kosten. Du musst Dir während des Ziehens die Kosten bis zum aktuellen Knoten merken, dann die Kosten zum Nachbarn und von diesem die hypothetischen Kosten zum Ziel addieren.
 

HerrInfo

Aktives Mitglied
Okay, aber dann weiß ich noch nicht genau woran es liegt. Was muss ich denn ändern, damit es dann funktioniert?
Laut Debug-Mode wechselt er col und row irgendwann.
 

Anhänge

  • Bild_2024-02-10_152337245.png
    Bild_2024-02-10_152337245.png
    120 KB · Aufrufe: 0
Zuletzt bearbeitet:

HerrInfo

Aktives Mitglied
Außerdem scheint wie schon gesagt die G-Cost Falsch zu sein
Zahlen-Reihenfolge ist wie folgt: G-Cost, H-Cost, F-Cost
 

Anhänge

  • Bild_2024-02-10_153414909.png
    Bild_2024-02-10_153414909.png
    64,3 KB · Aufrufe: 0

mihe7

Top Contributor
Wie schon geschrieben: das ist nicht einfach nur ein kleiner Fehler, wo man nur ein wenig zu ändern braucht, damit es funktioniert. Fang von vorne an, implementiere den Algorithmus aus dem Wikipedia-Artikel, dann funktioniert das auch.
 

Blender3D

Top Contributor
Ok, aber dann weiß ich nicht genau, was falsch ist. Wo genau muss ich etwas ändern damit es dann klappt?
Also der Link von @LimDul beschreibt was genau zu tun ist.
Eine Andere Herangehensweise wäre bei Basedefens auf einen Pfadsuchalgorithmus zu verzichten und verschiedene fixe Pfade für die jeweilge Map für die Einheiten vorzugeben. Dann kannst du diesen Pfaden folgen was nebenbei sehr viel schneller und einfacher ist.
Bei Basedefense geht es darum die Basis vor heranstürmenden Einheiten mit Waffen zu verdeitigen. Da genügt es Pfade vorzugeben. ;)
 

HerrInfo

Aktives Mitglied
Das Problem wurde mittlerweile behoben, und das Projekt ist abgeschlossen. Es stellte sich heraus, dass ich einmal "Coll" und "Row" verwechselt habe. Dennoch vielen Dank für die Antwort.
 

mihe7

Top Contributor
Ja, das Vertauschen von col und row war ein Problem in Deinem Code, allerdings hat der nun einmal nichts mit A* zu tun, wie in #2, #3 und #5 beschrieben wurde.
 

Ähnliche Java Themen

Neue Themen


Oben