Best Practice A Stern und die Kollisionsabfrage

DefconDev

Bekanntes Mitglied
Hallo zusammen,
habe für mein Spiel auf LibGDX und Box2d Basis einen A Stern Algo implementiert, funktioniert in der Theory ganz erfolgreich.

Nur wäre die Liste der Kollionsnodes die nicht betretbar sind, enorm groß. Ich denke mal ich gehe recht in der Annahme dass bevor der A Stern-Algo anfängt alle Kollionsnodes bekannt gemacht werden müssen oder?
Zurzeit werden meine Kollionsfelder mit rectangle Objekten symbolisiert und auch gezeichnet in meinem Spiel dargestellt.
Für jedes rectangle Objekt speichere ich jeweils seine x und y Koordinaten ab. Das können bei großen rectangles enorm viele Koordinaten sein.
Bedeutet: Rectangle Breite = 200x und Höhe = 200y das bdeutet dann 40000 Koordinaten.

Hat jemand eine Idee wie ich das anders behandeln könnte?
 

mrBrown

Super-Moderator
Mitarbeiter
Indem du sinnvolle Datenstrukturen nutzt.

Alle "Kollionsnodes" müssen gar nicht direkt bekannt sein, du brauchst nur jeweils die Nachbarnodes deines aktuellen Nodes.
Vermutlich kann man da auch Quadtrees nutzen, kommt aber auch auf deine Datenstrukturen an...
 

DefconDev

Bekanntes Mitglied
Ich verstehe nicht ganz worauf du hinauf willst, also sobald ein nachbarnode untersucht wird muss doch festgestellt werden ob dieser sich entweder in der openlist befindet oder ein Node ist der nicht begehbar ist. Und wenn ich zu dieser Überprüfung komme muss ich doch einen Vergleich machen mit einer Liste an Nodes die nicht begehbar sind.

Wie sähe dein Ansatz aus mit Quadtrees aus?

P.S. Es geht nicht um kollisionserkennung zweierobjekte sondern um wegfindung.
 
Zuletzt bearbeitet:

mrBrown

Super-Moderator
Mitarbeiter
Ich verstehe nicht ganz worauf du hinauf willst, also sobald ein nachbarnode untersucht wird muss doch festgestellt werden ob dieser sich entweder in der openlist befindet oder ein Node ist der nicht begehbar ist. Und wenn ich zu dieser Überprüfung komme muss ich doch einen Vergleich machen mit einer Liste an Nodes die nicht begehbar sind.
Dazu muss man aber nicht eine ganze Liste haben, dazu reicht es, zu prüfen ob der Node selbst begehbar ist, das geht oft besser, als alle nicht begehbaren in einer Liste zu sammeln.

Wie sähe dein Ansatz aus mit Quadtrees aus?
Naja, ein QuadTree in dem die Nodes liegen. Vermutlich reicht da aber auch ein HashSet, wenn du alle nicht begehbaren in einer Liste sammeln willst

P.S. Es geht nicht um kollisionserkennung zweierobjekte sondern um wegfindung.
Das ist mir schon klar^^
 

DefconDev

Bekanntes Mitglied
Dazu muss man aber nicht eine ganze Liste haben, dazu reicht es, zu prüfen ob der Node selbst begehbar ist, das geht oft besser, als alle nicht begehbaren in einer Liste zu sammeln.
Ich stehe immer noch auf dem Schlauch.

Diesen Vorgang den du meinst verstehe ich nicht, wie überprüfe ich denn ein Node ob dieser begehbar ist ohne zu vergleichen. Meine rectangle Objekte besitzen ihre x/y Pos und die Breite/Höhe und die sind nicht begehbar sonst habe ich nirgendwo gespeichert was begehbar ist. Jetzt könnte man lediglich die rectangle Objekte nehmen aber da müsste ich ebenfalls vergleichen.
 

DefconDev

Bekanntes Mitglied
Ich hoffe der Code definiert das besser als meine Worte:
Java:
public class Node implements Comparable<Node> {

    private int posX, posY;
    private Node parentNode;
    private boolean closed;
    private boolean walkable;

    private int f_Cost;
    private int g_Cost;
    private int h_Cost;

    public Node(Vector2 vector) {
        this.posX = (int) vector.x;
        this.posY = (int) vector.y;
        this.closed = false;
        this.f_Cost = 0;
        this.g_Cost = 0;
        this.h_Cost = 0;
        this.walkable = true;
    }

    public int getPosX() {
        return posX;
    }

    public int getPosY() {
        return posY;
    }

    public Node getParentNode() {
        return parentNode;
    }

    public void setParentNode(Node parentNode) {
        this.parentNode = parentNode;
    }

    public boolean isClosed() {
        return closed;
    }

    public void setClosed(boolean closed) {
        this.closed = closed;
    }

    public int getF_Cost() {
        return f_Cost;
    }

    public void setF_Cost(int f_Cost) {
        this.f_Cost = f_Cost;
    }

    public int getG_Cost() {
        return g_Cost;
    }

    public void setG_Cost(int g_Cost) {
        this.g_Cost = g_Cost;
    }

    public int getH_Cost() {
        return h_Cost;
    }

    public void setH_Cost(int h_Cost) {
        this.h_Cost = h_Cost;
    }

    public boolean isWalkable() {
        return walkable;
    }

    public void setWalkable(boolean walkable) {
        this.walkable = walkable;
    }

    @Override
    public int compareTo(Node node) {
        if (this.f_Cost > node.f_Cost) {
            return 1;
        }
        if (this.f_Cost < node.f_Cost) {
            return -1;
        }
        return 0;
    }
  
    @Override
    public int hashCode() {
        int hash = 3;
        hash = 17 * hash + this.posX;
        hash = 17 * hash + this.posY;
        return hash;
    }

}


Die Node Klasse wird dann in eine anderen Klasse verwendet die nach dem Prinzip des A Stern voran geht.

Also ich habe nicht von jeder Koordinate ein Node erstellt. Sondern es werden nur Nodes erstellt wenn es zur Berechnung des Pfades und seinen Nachbarnfelder geht.
 

Ähnliche Java Themen

Neue Themen


Oben