Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Jul 10, 2025 05:59

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 9 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Frage zu Pathfinding
BeitragVerfasst: Mo Dez 29, 2008 12:22 
Offline
DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710
Hallo,
ich habe da eine kleine Frage zum zweiten Pathfinding Tutorial, bzw Pathfinding generell.
Ich plane ein Pathfinding zu implementieren, bei welchem ich beliebige konvexe (vielleicht auch konkave) Polygone als Hindernisse habe.
Sicherlich lässt sich das dort genannte Prinzip auch hierfür erweitern, da es wie genannt auch bei UT verwendet wird.

Das Problem ist nun, dass ich beim durchlesen nicht erkennen kann, wie sichergestellt wird, dass die Akteure auch durch die Wege passen.
Ich habe mir den Code dazu noch nicht angesehen, da ich eigentlich vorhatte einen eigenen Ansatz zu implementieren, dann aber beim Nachdenken darüber an diesem Problem gescheitert bin.
Die Kollision meiner Spielfiguren wollte ich mit Kreisen lösen, damit das Ganze nicht zu kompliziert wird.

Meine Idee ist nun, das Polygon zu nehmen, zu skalieren, und zwar mit dem Radius der Spielfiguren. Dann werden die Vertices des neuen Polygons zu Nodes gemacht. So können die Figuren schonmal entlang des Polygons laufen. Man könnte nun prüfen, ob der Abstand einer dieser Nodes zu einem anderen Polygon kleiner als der Radius ist, dann wäre der Weg nicht begehbar, aber was tue ich dann? den Node einfach löschen?

Wie ließe sich sowas am besten umsetzen?

€: ich habe erstmal eine kleine demo-anwendung geschrieben, die die wege erzeugt, nun muss ich halt noch prüfen, ob meine Spieler da durch passen: http://exec-dev.de/Test2.jar Eigentlich müsste es ja reichen, zwei weitere parallele Geraden loszuschicken und die auf Schnitt zu prüfen, oder?

Vielen Dank schonmal,

mfg


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Di Dez 30, 2008 18:33 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Wenn du alle Knoten die von einem Startknoten aus direkt (ohne über andere Knoten zu gehen) in einer Liste speicherst, dann löschst du die Kante/Verbindung die nicht gegangen werden kann, indem du den Knoten aus der "Nachbarschaftsliste" entfernst.

Aus dem System darfst du den natürlich nicht löschen, denn unter umständen kommst du über einen Umweg ja trotzdem noch da hin.

_________________
Blog: kevin-fleischer.de und fbaingermany.com


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Mi Dez 31, 2008 09:57 
Offline
DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710
Eine Nachbarschaftsliste hab ich nicht direkt, ich habe eine die Verbindungen rekursiv implementiert.
Meine Node Klasse sieht so aus:
Code:
  1. import java.util.*;
  2.  
  3. public class Node {
  4.     Vector2d position = new Vector2d();
  5.     private ArrayList<Node> nodes = new ArrayList<Node>();
  6.     public Node(Vector2d position) {
  7.         this.position = position;
  8.     }
  9.     public int count() {
  10.         return nodes.size();
  11.     }
  12.     public void connectWith(Node n) {
  13.         if (n != this) {
  14.             nodes.add(n);
  15.             n.nodes.add(this);
  16.         }
  17.     }        
  18.     public void disconnectFrom(Node n) {
  19.         n.nodes.remove(n.nodes.indexOf(this)); // geht vielleicht auch ohne indexOf()
  20.         nodes.remove(nodes.indexOf(n));
  21.     }
  22.     public Node getNode(int index) {
  23.         return nodes.get(index);
  24.     }
  25. }


Und so erzeuge ich nun mein Netzwerk, Prüfung der Breite scheint auch schon zu funktionieren:
Code:
  1.     public void generateNetwork(double distance) {
  2.         Polygon tmp = new Polygon();
  3.         // Alle möglichen Wegpunkte erstellen
  4.         for (int i=0; i<polygons.size(); i++) {
  5.             tmp = polygons.get(i).outline(distance+1);
  6.             for (int j=0; j<tmp.count(); j++) {
  7.                 nodes.add(new Node(tmp.getVertexRotatedAbsolute(j)));
  8.             }
  9.         }
  10.         // Wegpunkte verbinden, zwischen denen kein Polygon liegt
  11.         Line l;
  12.         boolean hit;
  13.         for (int i=0; i<nodes.size(); i++) {
  14.             for (int j=i; j<nodes.size(); j++) {
  15.                 l = new Line(nodes.get(i).position, nodes.get(j).position);
  16.                 hit = false;
  17.                 for (int k=0; k<polygons.size(); k++) {
  18.                     // Prüfen, ob die Spielfiguren diesen Weg beschreiten können
  19.                     if (((l.intersectsWith(polygons.get(k), true)).count > 0) ||
  20.                         ((l.createLeftParallel(distance).intersectsWith(polygons.get(k), true)).count > 0) ||
  21.                         ((l.createRightParallel(distance).intersectsWith(polygons.get(k), true)).count > 0)) {
  22.                         hit = true;
  23.                         break;
  24.                     }
  25.                 }
  26.                 if (!hit) {
  27.                     nodes.get(i).connectWith(nodes.get(j));  
  28.                 }
  29.             }
  30.         }
  31.         // Wegpunkte ohne Verbindungen löschen
  32.         for (int i=0; i<nodes.size(); i++) {
  33.             if (nodes.get(i).count() == 0) {
  34.                 nodes.remove(i);
  35.             }
  36.         }
  37.     }

Eigentlich müsste ich jetzt nur noch das Pathfinding selbst implementieren. Nur welcher Algo eignet sich dafür am besten?

mfg


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Mi Dez 31, 2008 13:19 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Natürlich hast du eine Nachbarschaftsliste. Das ist "nodes".
Die enthält für jeden Knoten alle Nachbarn.
Wenn du jetzt feststellst, dass deine Einheiten durch einen Zwischenraum nicht durchpassen, dann löscht du die Verbindung zwischen den Nodes indem du bei beiden beteiligten Nodes, die jeweils andere aus der Nachbarschaftsliste entfernst.

Falls du unterschiedlich dicke Einheiten hast, ist die Sache nicht so einfach. Eventuell kannst du ja in der Nodesliste keine direkten Nodes speichern sondern verbindungsdaten. Da steht dann drinnen, wo der Weg hingeht (zielnode), wie breit er ist und eventuell noch wie hoch die Kosten sind ihn zu gehen. So könntest du z.B. auch wege über unwegsames Gelände simulieren. Da sind dann die Kosten einfach höher.

_________________
Blog: kevin-fleischer.de und fbaingermany.com


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Mi Dez 31, 2008 13:41 
Offline
DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710
Naja ich mache es ja jetzt so, dass ich vorm erzeugen der Verbindungen bereits prüfe, ob Hindernisse existieren, somit muss ich auch keine Verbindungen löschen. Leider gibt es im Tutorial keine Beschreibung dazu, wie die eigentliche Wegfindungsroutine implementiert wurde.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Mi Dez 31, 2008 17:23 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Welches Pathfinding Tutorial meinst du? Wir haben 2. Das erste beschreibt den A* Algorithmus.

_________________
Blog: kevin-fleischer.de und fbaingermany.com


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Jan 02, 2009 11:52 
Offline
DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710
Ich meinte eigentlich das zweite. Das erste beginnt mit den Worten:
Zitat:
Diese Methode geht davon aus das sich unsere virtuelle Welt aus lauter Quadraten zusammensetzt.
Da dachte ich mir, dass das für meine Zwecke wohl nicht das richtige ist. Aber soweit ich weiß ist der A* universell einsetzbar, nur so wirklich verstehen tut man den (sofern es sich um A* handelt wie du sagst) durch das Tutorial nicht. Vor allem wenn man ihn auf ein anderes Problem übertragen möchte.

mfg


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Jan 02, 2009 12:12 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Naja, der A* ist eigentlich ein ganz simpler Algorithmus. Er arbeitet mit einer Heuristik, also einer Abschätzung der noch kommenden Kosten.

Wenn wir mal einen "Vorgänger" vom A* betrachten, nämlich einer Kostenbasierten Wegsuche, dann funktioniert die ja nach dem Prinzip:

1.Nehme alle Nachbarn des aktuellen Knotens
2.Addiere die Kosten bis zum aktuellen knoten mit den Kosten die nötig sind den Nachbarn zu erreichen und sortiere den Nachbarknoten in eine Liste der entdeckten Knoten ein. Kleinste Kosten zuerst.
3.Nehme den nächsten Knoten aus der liste als aktuellen Knoten.

Kosten können z.B. die Wegstrecke sein, Aber auch abstractere Sachen z.B. die Wegdauer oder Aufwand einen Weg zu gehen.

Wenn du den obigen Ansatz verfolgst, läufst du die "schnellsten"/"günstigsten" Wege zuerst ab. Das kann aber sinnlos sein, wenn die Wege z.B. vom Ziel weg zeigen. Wir wollen ja zum Ziel hin. Und hier setzt die Heuristik von A* ein.
Die Heuristik schätzt nämlich ab, wie weit ein Knoten mindestens vom Ziel entfernt ist. (Wichtig: Eine gültige Heuristik DARF NIE die tatsächliche Entfernung überschätzen, nur unterschätzen.)
Die einfachste Heuristik ist die Berechnung des Luftlinienabstands per Satz des Pythagoras.

Wenn wir nun den obigen algorithmus zum A* ausbauen wollen, addierst du das Ergebnis der Heuristik auf den Wert von Punkt 2 mit auf. Der Rest bleibt gleich.

A* funktioniert auch auf "nicht gerasterten" Flächen. Du musst du irgend eine Möglichkeit haben den Abstand zum ziel zu bestimmen. Wenn du nur einzelne Knoten in deinem Level liegen hast, die kein quadratisches Netz bilden, dann geht das trotzdem, wenn du die 2D Koordinaten der Knoten zum Berechnen der Heuristik verwendest.

_________________
Blog: kevin-fleischer.de und fbaingermany.com


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: Fr Jan 02, 2009 12:49 
Offline
DGL Member

Registriert: Di Mai 24, 2005 16:43
Beiträge: 710
Vielen Dank, das war die bisher verständlichste Erklärung die ich gelesen hab ;) ich werde mal schauen ob ich das umsetzen kann.

€: Ich hab die Beschreibung von Wikipedia.de verwendet und konnte damit meinen A* zum Laufen bringen :D


mfg


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 9 Beiträge ] 
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 6 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.009s | 16 Queries | GZIP : On ]