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

Aktuelle Zeit: So Jul 13, 2025 14:27

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



Ein neues Thema erstellen Auf das Thema antworten  [ 7 Beiträge ] 
Autor Nachricht
 Betreff des Beitrags: Wegfindung in Rastern...
BeitragVerfasst: So Sep 19, 2010 14:26 
Offline
DGL Member

Registriert: Mo Aug 31, 2009 13:19
Beiträge: 151
Ja, wo wir gerade bei Rastern sind (Gruß an Finalspace :D), noch ein Problem in gerasterten Umgebungen: Die Wegfindung.

Beschäftige mich gerade mit der Wegfindung von SketchtowerWars (mal wieder). Mein Problem mit der alten Routine war, dass sie zwar einigermaßen funktionierte, aber viel zu viele Rechenschritte erforderte. Schaut euch die Skizze im Anhang an, ich fang derweil an zu erklären...
Die Koordinaten in den hellblauen, länglichen Kästchen sind die Koordinaten der Eckpunkte der Kästchen, die Zahlen in den dunkleren Kästchen sind die Indizes der Kästchen in dem 2D-Array, in dem die Begehbarkeitsinformationen stehen.
Mein alter Algorithmus funktionierte jetzt so: Ich hab über eine Variable, die in (relativ willkürlich gewählten) kleinen Schritten von 0 bis 1 lief zwischen den Endpunkten der Verbindungslinie interpoliert (n=0 -> P0, n=1 -> P1), die Nachkommastellen des interpolierten Punktes abgeschnitten und geprüft, ob das Feld an den so erhaltenen Koordinaten blockiert war, oder nicht. Mein Problem damit: Des öfteren mal hab ich Felder mehrfach überprüft, oder solche, die nur kurz "angeschnitten" wurden übersprungen. Letzterem bin ich Herr geworden, in dem ich die Schritte noch kleiner gewählt hab - was Ersteres natürlich verschlimmert.
Jetzt zur "Neuauflage" meines STW-Codes hab ich mir gedacht, ich bau dafür nen neuen Algorithmus - wie im Projektthread erwähnt hatte ich da ja auch was gefunden, was auf den Bresenham-Algorithmus zur Rasterung von Linien herauslief (der ist in der Wikipedia ganz gut erklärt). Der kommt mit meinem Problem leider allerdings nicht so 100%ig klar, weil Start- und Endpunkte meiner Rasterung Fließkomma-Koordinaten haben können.
Der Algorithmus lässt sich zwar derart verallgemeinern, dass er mit Fließkomma-Koordinaten am Endpunkt klarkommt, aber das Problem am Startpunkt bleibt bestehen. Zumindest hab ich keine Möglichkeit gefunden, es zu umgehen - den Startpunkt innerhalb der Routine auf 0/0 zu legen bereitet mir irgendwie Probleme, weil der Fehlerwert, der berechnet wird, um zu entscheiden, ob das östliche, oder das nordöstliche Feld getestet wird dann irgendwie nicht mehr stimmt. Zudem rastert der Bresenham-Algorithmus 8-verbunden (also "über Eck"), während mein Raster kantenverbunden sein muss.

Also bin ich hingegangen und hab das Pferd mal neu aufgezäumt, wenn auch sehr ähnlich. Der Code steht unten, ich hoffe er ist ausreichend kommentiert.
Code:
function TSTW_Pathfinder.CheckConnection(P0: TVector2f; P1: TVector2f): Boolean;
var
  dX, dY, Slope, Error: Single;
  StepX, StepY, Max:    Integer;
  TruncX0, TruncY0:     Integer;
  Count, Calc:          ^Integer;
begin
// Schrittvariablen initialisieren
StepX   := 0;
StepY   := 0;

// Differenzen aus den Koordinaten errechnen, und daraus die Steigung
// (ohne Vorzeichen)
dX      := P1.X - P0.X;
dY      := P1.Y - P0.Y;
Slope   := Abs(dY / dX);

// Feststellen, in welchem Feld der Karte der Startpunkt liegt (entspricht dem
// ganzzahligen Anteil der Koordinaten
TruncX0 := Trunc(P0.X);
TruncY0 := Trunc(P0.Y);


if Slope < 1 then
  begin
// Wenn die Steigung kleiner ist als eins...
//    ...Fehlervariable als Schnittpunkt der Geraden zwischen den beiden Punkten
//    mit dem linken "Rand" des Startfeldes initialiseren. -1 wäre die linke untere Ecke,
//    0 ist die Ecke links oben. (Um leichter darauf testen zu können, ob ich nah an der
//    oberen Ecke bin diese seltsame Konvention - bei Fließkommazahlen ist ein Test x = -1?
//    ja immer ungenau.
  Error   := Frac(P0.Y) - Slope * Frac(P0.X) - 1;
  Count   := @StepX;  // Pointerzuweisungen, sorgen dafür das später
  Calc    := @StepY;  // der x-Wert als Schleifenvariable dient und der y-Wert berechnet wird
  Max     := Abs(Trunc(P1.X) - TruncX0);  // Maximalwert für die Zählvariable in der Schleife
  end
  else
  begin
//  Wenn nicht - machen wir das gleiche, vertauschen aber x- und y-Koordinaten,
//  um den selben Algorithmus benutzen zu können
  Slope   := 1 / Slope;
  Error   := Frac(P0.X) - Slope * Frac(P0.Y) - 1;
  Count   := @StepX;
  Calc    := @StepY;
  Max     := Abs(Trunc(P1.Y) - TruncY0);
  end;

while Count^ < Max do // Schleife über die Zählvariable
  begin
  // Der eigentliche Feldtest: da wo FPathmax[x, y] = false ist, ist der Weg frei.
  Result := not FPathmap[TruncX0 + Sign(dX) * StepX, TruncY0 + Sign(dY) * StepY];
  if not Result then
    Exit;

  // Wenn ein Feld getestet ist, addieren wir die Steigung zur Fehlervariablen -
  // so bekomm ich dann den Schnittpunkt mit der nächsten "Feldkante".
  Error := Error + Slope;
  if Abs(Error) <= 0.05 then
    // Ist die Fehlervariable nah an 0, geht die gerade quasi genau durch den Punkt,
    // an dem sich 4 Felder treffen - zusätzlich zu dem Feld, das im nächsten Durchlauf
    // eh getestet wird muss ich mich also auch um das darunter und das links daneben kümmern.
    begin
    Result := not FPathmap[TruncX0 + Sign(dX) * StepX,
                  TruncY0 + Sign(dY) * (StepY + 1)];
    Result := Result and not FPathmap[TruncX0 + Sign(dX) * (StepX + 1),
                                      TruncY0 + Sign(dY) * StepY];
    if not Result then
      Exit;

    if Error > 0 then
      // Wenn die Fehlervariable größer ist als null wandere ich ein Feld höher
      // und betrachte den Schnittpunkt mit der Kante des Feldes darüber ->
      // Die Fehlervariable wird wieder um eins gesenkt
      Error := Error - 1;

    // Bin ich nah an null lande ich auf jeden Fall auch auf der y-Achse eine Einheit
    // weiter "oben" - außer dX wäre sehr groß und dY sehr, sehr klein - das sollte aber nicht passieren.
    Calc^ := Calc^ + 1;
    end
    else
    if Error > 0 then
      // Wenn wir nicht nah an null sind, aber größer als null, interessiert mich nur das Feld
      // über dem gerade getesteten - Error um eins senken, die berechnete Variable um eins erhöhen,
      // testen, fertig.
      begin
      Calc^ := Calc^ + 1;
      Error := Error - 1;
      Result := not FPathmap[TruncX0 + Sign(dX) * StepX,
                             TruncY0 + Sign(dY) * StepY];
      if not Result then Exit;
      end;

  // Zählvariable um eins erhöhen, rinse, repeat.
  Count^ := Count^ + 1;
  end;
end;


Die Sache ist zugegebenermaßen vielleicht trotz der Kommentare etwas verwirrend, ich hoffe jemand macht sich die Mühe es sich trotzdem zu Gemüte zu führen. Die Multiplikationen mit Sign(dX) bzw. Sign(dY) dienen übrigens auch dazu, möglichst alle auftretenden Fälle auf den Fall 0 <= m < 1 zurückzuführen.

Und genau da liegt (denke ich) mein Problem, welches im zweiten Screenshot zu sehen ist. Die meisten Oktanden funktionieren super - der Achte (also der Fall dY < 0; 0 <= |m| < 1) zickt rum. In der Skizze sind die Felder, die der Algorithmus testet grau, blockierte rot und freie hellblau. Vertauschen der Punkte bringt übrigens nicht wirklich Besserung, er teste zwar andere Felder, und darunter auch die richtigen, aber zusätzlich solche, die er nicht testen sollte. (Das heißt natürlich, dass der *grübel* Vierte Oktand auch zankt.

Ich schätze, mein Fehler liegt darin, dass ich in den Fällen die Fehlervariable anders berechnen muss, stehe aber völlig auf dem Schlauch, und weiß nicht, was genau ich ändern soll. Ich hoffe irgendjemand steigt durch diese Wall-of-Text durch und kann mir helfen :)


Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Wegfindung in Rastern...
BeitragVerfasst: So Sep 19, 2010 15:03 
Offline
DGL Member
Benutzeravatar

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java
Bresenham-Algorithmus zur Wegfindung...mal was neues ;)
Den A*-Algorithmus (aka A-Stern, eine Variante des Dijkstra-Algorithmus) kennst du schon?

P.S. Ich glaube du hast zweimal das gleiche Bild hochgeladen.

_________________
Yeah! :mrgreen:


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Wegfindung in Rastern...
BeitragVerfasst: So Sep 19, 2010 20:55 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Alles was Coolcat sagt wollte ich auch schreiben.

Ließ dich mal ins Thema Wegfindung ein. Das ist ein Standardproblem der (Theoretischen) Informatik.
http://de.wikipedia.org/wiki/Wegfindung

Der A* Algorithmus ist schonmal sehr geeignet. Er geht so vor wie auch ein Mensch vorgehen würde.
Also er läuft richtung Ziel und bei Hindernissen wählt er einen nächsten Schritt der am ehesten wieder Richtung ziel führt. Es gibt da natürlich Fälle wo der A* etwas "Kurzsichtig" ist. Aber das ist vielleicht näher an der Realität als ein Godlike Algo, der am Start schon weiß, wie es am Ziel aussieht.

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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Wegfindung in Rastern...
BeitragVerfasst: So Sep 19, 2010 22:28 
Offline
DGL Member

Registriert: Mo Aug 31, 2009 13:19
Beiträge: 151
Ja, der Wegfindungsalgorithmus ansich ist der Djikstra-Algorithmus.
Ich folge einigen Schritten:

Schritt eins: Finde sinnvolle Punkte, die geeignete "Knotenpunkte" für einen Pfad darstellen
Schritt zwei: Stelle fest, welche Punkte durch gerade Linien verbunden werde können, ohne, dass die Linie über ein Hindernis verläuft
Schritt drei: Bewerte die Punkte nach dem Djikstra-Algorithmus
Schritt vier: Baue für jeden Zielpunkt (die ändern sich bei mir ja nicht) einen Baum auf, über welche Knoten er am günstigsten erreicht werden kann
Schritt fünf: Wenn ein Creep "fragt", wie es von seinem Punkt zum Ziel kommt, teile ihm einfach mit, welcher Knotenpunkt, den es erreichen kann die niedrigste Wertung hat. Von da an enthält der Knoten selbst alle nötigen Informationen dazu, wie es weiter geht

So, Schritt eins klappt wunderbar - ich stelle einfach fest, an welchen Eckpunkten nur ein Hindernis anliegt und setze über die Spitze dieses Hindernisses in einigem Abstand einen Knotenpunkt.
Schritt drei - der Djikstra-Algorithmus ist ja fast idiotensicher xD
Schritt vier - joar, Punkte nach ihrer Wertung sortieren ist auch überhaupt kein Problem
Schritt fünf: Siehe Schritt vier

Und für Schritt zwei muss ich wissen, über welche Felder die Verbindungslinie zwischen zwei Knoten verläuft - dafür erschien mir der Bresenham-Algorithmus ganz gut (mit der eigentlichen Wegfindung hatter halt nix zu tun). Leider klappts nicht ganz so, wie gedacht, weils halt nicht direkt der Anwendungszweck des Algorithmus ist. Wenn jemand ne andere gute Idee hat, oder weiß, welche Anpassungen ich vergessen hab, immer her damit :D

A* klingt nach einer brauchbaren Alternative, werd mich da mal einlesen - am Ende ist ne Neuimplementation einfacher, als den Algorithmus zu "erziehen". Ich hab mich nur damals so in den Djikstra-Algorithmus verliebt, und für ne TD klingt er auch so unheimlich brauchbar, weil praktisch jede Einheit immer der gleichen Pfad benutzt, und Anpassungen am einmal gefundenen Pfad nur sehr selten nötig sind.

Wichtig zu wissen ist vllt. noch, dass meine EInheiten nicht nur über Kanten von Feld zu Feld laufen können, sondern sich in beliebigen Winkeln "stufenlos" bewegen...es reicht also nicht, einfach die Felder zu bewerten und das Creep von Feld A über B,C,D,E nach F zu schicken.

Zu den Bildern: Bin gerade am Laptop meiner Freundin, ich guck später nochmal danach.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Wegfindung in Rastern...
BeitragVerfasst: Mo Sep 20, 2010 15:56 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Moment...
du hast beliebige Positionen? Wieso willst du dann ein grobes Raster drauf legen?

Nimm doch einfach das koordinatenraster. Wir hatten ein Wegfindungstutorial bei uns, welches ein eigenes Raster anhand den Hindernissen aufbaut. Die Idee ist quasi, dass man alle Eckpunkte von Hindernissen als Knoten annimmt (bzw. einen gewissen abstand von diesen damit nicht "in" der Wand gelaufen wird) und dann festgestellt wird, wer eine Sichtverbindung zu einander hat. Man muss dann quasi nur noch vom Spawning-Punkt aus eine Sichtprüfung auf die nächsten Knoten machen. Von dort aus gehts dann weiter.

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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Wegfindung in Rastern...
BeitragVerfasst: Mo Sep 20, 2010 18:51 
Offline
DGL Member

Registriert: Mo Aug 31, 2009 13:19
Beiträge: 151
Die Hindernisse befinden sich immer innerhalb des groben Rasters (Creeps behindern sich nicht gegenseitig, nur Türme behindern Creeps) und belegen ein Rasterfeld. Das Konzept steht so fest und resultiert auch nicht aus irgendwelchen Problemen mit der Wegfindung, auch wenn der nächste Satz so klingt. Das Wegfindungstutorial kenn ich, hab mich auch mal damit beschäftigt, fand es aber sehr aufwändig, die "Grenzen" der Hindernisse festzustellen. Ecken finden, kein Problem - ALLE Verbindungen zwischen den Ecken festzustellen, kein Problem - ALLE Verbindungen zwischen solchen Ecken festzustellen, die zum selben Hindernis gehören, also die Begrenzungslinien des Hindernissen, großes *würg*. Also dachte ich mir, ich nutze aus, dass alle meine Hindernisse sich sowieso in einem groben Raster befinden, das schien viel einfacher. Entwickelt sich aber auch immer mehr zum *würg*.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Wegfindung in Rastern...
BeitragVerfasst: Di Sep 21, 2010 13:55 
Offline
Guitar Hero
Benutzeravatar

Registriert: Do Sep 25, 2003 15:56
Beiträge: 7810
Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Eigentlich ist das gar nicht so schwer die Kanten zu finden die zu einem Hindernis gehören.
Du darfst die Sachen nur nicht getrennt sehen.

Wenn ein Turm gesetzt wird, dann werden nicht nur die Eckpunkte platziert, sondern auch die "Blockierenden Kanten" (also Wände).
Die Kannst du direkt in einer Liste festhalten.
Wenn du 2 Türme Wand an Wand setzt, kannst du identische Eckpunkte ermitteln und damit "Wände" herausfallen lassen - oder du ignorierst diese Optimierung. Sollte trotzdem gehen.

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


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


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 4 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:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.012s | 15 Queries | GZIP : On ]