Ich versuche gerade *verzweifelt* seit einigen Tagen den
A* Alghorithmus im Bezug auf Wegpfindung zum laufen zu
kriegen, blicke aber einfach nicht ganz durch...
Nur verwendet er in dem Artikel oben ein 2D Feld, wie in
den meisten Artikeln die ich gefunden habe. Ich möchte das
Ganze aber mit "Sechsecken" machen, finde aber dazu leider
nirgens einen Ansatz
Jemand dazu eine Idee? Bin echt verzweifelt was das Thema
Pathfinding angeht gerade...
was ist dein Problem? Dem A* ist doch egal, ob es 4 (bzw. 8 ) oder 6 Abzweigungen gibt. Im Gegenteil: Der 6er Fall ist ja gegenüber dem 8er sogar symmertisch, also wahlweise einfacher oder adäquater.
hmm, ich glaub ich hab soviel gelesen, das ich nicht mehr
weiss wo vorne und hinten ist bei dem Thema,
kannst du mir einen PseudoCode posten was
ich tun müsste um mein Sechseckfeld mit A*
zu implementieren? Gerade diese Sache mit
den "Nachbarn" in Nodes macht mir Kopfzerbrechen...
Falls ich da was komplett missverstehe bitte, bitte aufklären
Vielleicht einfach mal die "korrekte" Vorgehensweise
bei der Implementierung von A* posten, denke ich
bring da noch was durcheinander irgendwie.
also nochmal. A* basiert auf Node-Listen. Ob diese Nodes Quadrate oder Rechtecke repräsentieren ist egal.
So steht denn auch in dem Artikel:
Zitat
No code in the actual AStarNode class does any calculations relating to coordinates and such, so it should be possible to use this class to solve any A* problem, not just relating to 2-dimensional grids.
Und weiter:
Zitat
In my test of the A* class, I let the character move in 8 possible directions on a 2-dimensional map, so I will be using the "Diagonal Distance" approach.
Sprich nur die Test-Klasse muss man ändern.
Oder ist das Problem, dass du noch gar keine Repäsentation deines Spielfeld gefunden hast?
Dazu kann man einfach ein zweidimensionales Array benutzen. Dabei sind die folgenden Array-Element Nachbarn des Array-Elements a[i,j]:
a[i,j-2]
a[i,j+2]
a[i,j-1]
a[i,j+1]
sowie
a[i+1,j-1]
a[i+1,j+1]
bei den ungeraden Zeilen bzw.
a[i-1,j-1]
a[i-1,j+1]
bei den geraden Zeilen.
Natürlich ist zu beachten, dass die Indices durch die Addition/Subtraktionen nicht OutOfRange werden.
ja das mit der Repräsentation war schonmal mein erstes Problem,
danke! Habs jetzt so in einem Array wie du vorgeschlagen hast
(derzeit 8x8 Felder zum test, also int HexArray[8,8]).
Aber ich muss doch wenn ich jetzt weiss welches die Nachbarn sind
so einen "Suchbaum" aufbauen (hat man mir gesagt), damit A*
weiss welche Felder Zugriff auf andere haben, oder?
In anderen Implementationen hab ich dafür auch solche "maps"
gesehen die ca. so aussahen "static map[,] = {1,1,1,1,1,1,-1,-1 ...}"
wobei -1 unpassabel und 1 passable war... oder brauch ich das nicht?
den Suchbaum baut ja A* (also die Klasse AStarNode, wenn ich das richtig sehe) selbst auf. Du muss lediglich angeben, ob es möglich ist, ein Feld zu betreten. Das ist m.E. gerade das, was du dir in HexArray merken musst.
Statt sich zu merken, ob ein Feld passierbar ist, kann man sich auch merken, wie schwer es ist das Feld zu passieren (Strasse ist leicher zu passieren, als Unterholz). Ich weiß aber nicht, ob der A* aus dem Artikel diese Verallgemeinungen direkt hergibt.
ok, die Koordinaten für ein StartFeld und EndFeld bekomme ich jetzt
aus dem HexArray[i,j] und kann sie an A* übergeben.
...nun ist mir nur noch nicht klar wo ich das:
a[i,j-2]
a[i,j+2]
a[i,j-1]
a[i,j+1]
sowie
a[i+1,j-1]
a[i+1,j+1]
bei den ungeraden Zeilen bzw.
a[i-1,j-1]
a[i-1,j+1]
bei den geraden Zeilen.
bei dem Beispiel einbauen muss, damit er versteht das
es sich bei mir um kein "normales" 2D Grid handelt, sondern
das er die Nachbarn eben mit dem von dir genannten Weg
berechnen muss...
etwa bei:
"public override void GetSuccessors(ArrayList ASuccessors)" ?
ich habe mir den Artikel nicht so genau angeguckt, dass ich dir die Stelle sagen könnte. Aber es muss ja eine Stelle im Test-Programm sein, eben da wo im Original die acht Nachfolger eingestellt werden (und die Diagonalenberechnung ausgeführt wird, die ja bei Hexagonen entfällt).
Meine Nachbarschaftsangaben bezogen sich auf liegende Hexagone, wie in deinem Beispielbild. Ich habe es jetzt noch mal mit stehenden Hexagonen überlegt (siehe Bild) und da ist es noch einfach und übersichtlicher.
Wenn ich nun sage, suche mir einen Weg von:
AStarNode2D GoalNode = new AStarNode2D(null,null,0,5,5);
AStarNode2D StartNode = new AStarNode2D(null,GoalNode,0,0,);
Also von [0,0] nach [5,5] gibt er mir fologendes aus:
Starting...
X: 0 Y: 0 Cost: 0 Est: 5 Total: 5
X: 0 Y: 1 Cost: 1 Est: 5 Total: 6
X: 1 Y: 2 Cost: 2 Est: 4 Total: 6
X: 1 Y: 0 Cost: 2 Est: 5 Total: 7
X: 1 Y: 1 Cost: 3 Est: 4 Total: 7
X: 2 Y: 2 Cost: 4 Est: 3 Total: 7
X: 2 Y: 3 Cost: 5 Est: 3 Total: 8
X: 3 Y: 4 Cost: 6 Est: 2 Total: 8
X: 2 Y: 1 Cost: 5 Est: 4 Total: 9
X: 3 Y: 3 Cost: 7 Est: 2 Total: 9
X: 4 Y: 4 Cost: 8 Est: 1 Total: 9
X: 4 Y: 5 Cost: 9 Est: 1 Total: 10
X: 4 Y: 3 Cost: 9 Est: 2 Total: 11
X: 5 Y: 4 Cost: 10 Est: 1 Total: 11
S S . . . . . . . .
S S . . . . . . . .
. . S . . . . . . .
. . S S S . . . . .
. . . S S S . . . .
. . . . . S . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
Scheint ja irgendwie nicht annähernd der schnellste Weg zu sein,
ist da noch ein Fehler in meiner abgeänderten Methode oben,
oder liegt das an der heuristic?
Die HeuristicMethode ist derzeit:
/// <summary>
/// Calculates the estimated cost for the remaining trip to the goal.
/// </summary>
public override void Calculate()
{
if(GoalNode != null)
{
double xd = FX - ((AStarNode2D)GoalNode).X;
double yd = FY - ((AStarNode2D)GoalNode).Y;
// "Euclidean distance" - Used when search can move at any angle.
//GoalEstimate = Math.Sqrt((xd*xd) + (yd*yd));
// "Manhattan Distance" - Used when search can only move vertically and
// horizontally.
//GoalEstimate = Math.Abs(xd) + Math.Abs(yd);
// "Diagonal Distance" - Used when the search can move in 8 directions.
GoalEstimate = Math.Max(Math.Abs(xd),Math.Abs(yd));
}
else
{
GoalEstimate = 0;
}
}
10000000000000 Dank, ich habs jetzt fast denke ich (hoffe)
hmm... müssten aber nicht die koordinaten zumindest
stimmen? Weil, andere als diese hab ich ja nicht als
Lösung irgendwo.
Ausgegeben wird es derzeit so, aber ich brauche ja
eigentlich nur die Koordinaten jedes einzelnen
hexfeldes um es dann später auf die echten
hexfelder anzuwenden:
Also auch wenn der Weg mit "S" falsch ist, müsste dann nicht trotzdem:
X: 0 Y: 0 Cost: 0 Est: 5 Total: 5
X: 0 Y: 1 Cost: 1 Est: 5 Total: 6
X: 1 Y: 2 Cost: 2 Est: 4 Total: 6
X: 1 Y: 0 Cost: 2 Est: 5 Total: 7
X: 1 Y: 1 Cost: 3 Est: 4 Total: 7
X: 2 Y: 2 Cost: 4 Est: 3 Total: 7
X: 2 Y: 3 Cost: 5 Est: 3 Total: 8
X: 3 Y: 4 Cost: 6 Est: 2 Total: 8
X: 2 Y: 1 Cost: 5 Est: 4 Total: 9
X: 3 Y: 3 Cost: 7 Est: 2 Total: 9
X: 4 Y: 4 Cost: 8 Est: 1 Total: 9
X: 4 Y: 5 Cost: 9 Est: 1 Total: 10
X: 4 Y: 3 Cost: 9 Est: 2 Total: 11
X: 5 Y: 4 Cost: 10 Est: 1 Total: 11
Korrekt sein? Weil die werden doch jetzt über die neu eingebaute
Nachbarmethode ermittelt, oder täusche ich mich jetzt!?
Wenn ich die Felder über X/Y nachverfolge, ist der Weg ziemlicher
blödsinn...
ach, kannst du mir den Code von dem Hexfeld mit der Nummerierung
geben, mit dem du oben das Bild gemacht hast?
Wäre mal interessiert wie sowas von einem Profi umesetzt wird so
zum Vergleich mit meinem Spaghetticode
Ist zudem recht praktisch zum nachvollziehen vom A*.
der "Profi" hat den Code auch nur so runtergeratzt (die Schrift, war z.B. durch feste Offsets händisch zentriert). Außerdem bin ich in Bezug auf OnPaint alles andere als ein Profi.
Momentan habe ich den Code in dieser Form auch nicht mehr, weil ich daraus einen kleinen "Geländeschwierigkeits"-Editor begonnen habe, der wiederrum noch nicht fertig ist.
Aber wenn du dich etwas geduldest, kann ich spätestens am nächsten Wochenende was posten.
Hehe, ja ging mir eigentlich primär darum wie du die Hexfelder
aufbaust und speicherst, wollte mal sehen ob das meinem
Kuddelmuddel etwas ähnelt, das mit den Zahlen drin währ halt
ein "nice Feature" um das A* ding schneller zu testen. Ich code
noch nicht sooo lange c#, daher dachte ich mir so mal einen
eine Blick auf einen etwas "besseren" code zu erhaschen
[...] einen Blick auf einen etwas "besseren" code zu erhaschen
also noch mal die Warnung, dass ich mit Zeichenroutinen und mit OnPaint bisher nicht viel am Hut hatte. Deshalb habe letzteres auch gar nicht verwendet :-) sondern bin auf PictureBoxen ausgewichen, habe mich also um die ganzen lästigen OnPaint-Probleme gedrückt.
Ich habe jetzt aus dem "Geländeschwierigkeits"-Editor erstmal wieder alles rausgeschmissen, dass wieder nur das reine Zeichnen der Karte übrig geblieben ist. Das ging schnell und dann musst du nicht so lange warten. Allerdings noch eine Warnung: Dadurch gibt es keine zu Grunde liegende Karte mehr. Es wird einfach ein Hexagonraster gezeichnet.
Der blaue Strich ist kein Bug, sondern ein Beispiel für eine Verbindungslinie.
So genug gewarnt :-) Hier der Code:
using System;
using System.Windows.Forms;
using System.Drawing;
using System.Drawing.Imaging;
using System.Drawing.Drawing2D;
//*****************************************************************************
public class HexagonWindow : Form
{
//--------------------------------------------------------------------------
const int iBaseX = 21;
const int iBaseY = 12;
const int iCols = 10;
const int iRows = 10;
const int iWidth = iCols*2*iBaseX+iBaseX+1;
const int iHeight = iRows*3*iBaseY+iBaseY+1;
//--------------------------------------------------------------------------
readonly Font _font = new Font ("Arial", 9);
//--------------------------------------------------------------------------
private Bitmap _bitmCanvasBehind;
private Bitmap _bitmCanvasAhead;
//--------------------------------------------------------------------------
private Graphics _gCanvasBehind;
private Graphics _gCanvasAhead;
//--------------------------------------------------------------------------
private Brush _brushBack;
private Brush _brushText;
private Pen _penBorder;
private Pen _penConnection;
//--------------------------------------------------------------------------
private PictureBox _picbCanvasBehind;
private PictureBox _picbCanvasAhead;
//==========================================================================
/// <summary>
/// Konstruktor
/// </summary>
public HexagonWindow ()
{
Control ctrlCurr;
Control ctrlPrev;
Control ctrlCurrContainer;
//-----------------------------------------------------------------------
// Fenstertitel und Größe setzen
//-----------------------------------------------------------------------
Text = "Hexagon";
ClientSize = new Size (iWidth, iHeight);
MaximumSize = Size;
MinimumSize = Size;
//-----------------------------------------------------------------------
// Bitmaps, Graphics & Co initialsieren
//-----------------------------------------------------------------------
_bitmCanvasBehind = new Bitmap (iWidth, iHeight,
PixelFormat.Format24bppRgb);
_bitmCanvasAhead = new Bitmap (iWidth, iHeight,
PixelFormat.Format32bppArgb);
_gCanvasBehind = Graphics.FromImage (_bitmCanvasBehind);
_gCanvasAhead = Graphics.FromImage (_bitmCanvasAhead);
_brushBack = Brushes.White;
_brushText = Brushes.Black;
_penBorder = Pens.Black;
_penConnection = Pens.Blue;
//-----------------------------------------------------------------------
// Steuerelemente erzeugen
// Die PictureBox _picbCanvasAhead liegt transparent über
// _picbCanvasBehind. Dadurch kann man die Verbindungslinien in
// _picbCanvasAhead und die Hexagone in _picbCanvasBehind zeichnen,
// ohne dass sich beide ins Gehege kommen.
//-----------------------------------------------------------------------
ctrlCurrContainer = this;
//-----------------------------------------------------------------------
ctrlCurr = _picbCanvasBehind = new PictureBox ();
ctrlCurr.Dock = DockStyle.Fill;
ctrlCurr.BackColor = Color.White;
((PictureBox)ctrlCurr).Image = _bitmCanvasBehind;
ctrlCurrContainer.Controls.Add (ctrlCurr);
ctrlPrev = ctrlCurr;
//-----------------------------------------------------------------------
ctrlCurrContainer = ctrlPrev;
//-----------------------------------------------------------------------
ctrlCurr = _picbCanvasAhead = new PictureBox ();
ctrlCurr.Dock = DockStyle.Fill;
((PictureBox)ctrlCurr).Image = _bitmCanvasAhead;
ctrlCurr.BackColor = Color.Transparent;
ctrlCurrContainer.Controls.Add (ctrlCurr);
ctrlPrev = ctrlCurr;
//-----------------------------------------------------------------------
// Karte initial zeichnen
//-----------------------------------------------------------------------
_gCanvasBehind.FillRectangle (_brushBack, 0, 0, iWidth, iHeight);
for (int iX = 0; iX < iCols; ++iX) {
for (int iY = 0; iY < iRows; ++iY) {
DrawHexagon (_gCanvasBehind, iX, iY);
}
}
//-----------------------------------------------------------------------
// Testausgabe: Zeichnen einer Verbindungslinie
//-----------------------------------------------------------------------
DrawHexagonConnection (_gCanvasAhead, 2, 2, 2, 3);
}
//==========================================================================
/// <summary>
/// Liefert zum (zweidimensionalen) Index die ClientKoordinaten
// des Hexagons
/// </summary>
protected Point GetHexagonPoint (int iX, int iY)
{
int iOffsetX;
int iOffsetY;
//-----------------------------------------------------------------------
// Berechnen der Bildschirmkoordinaten anhand des Index ([iX, iY])
// des Hexagons ...
//-----------------------------------------------------------------------
iOffsetX = iX*2*iBaseX;
iOffsetY = iY*3*iBaseY;
if (iY % 2 == 1) {
iOffsetX += iBaseX;
}
return new Point (iOffsetX, iOffsetY);
}
//==========================================================================
/// <summary>
/// Zeichnen einer Verbindungsline vom Mittelpunkt eines Hexagons
/// zu einem anderen.
/// </summary>
protected void DrawHexagonConnection (Graphics g,
int iXFrom, int iYFrom,
int iXTo, int iYTo)
{
Point ptFrom;
Point ptTo;
ptFrom = GetHexagonPoint (iXFrom, iYFrom);
ptFrom.X += iBaseX;
ptFrom.Y += 2*iBaseY;
ptTo = GetHexagonPoint (iXTo, iYTo);
ptTo.X += iBaseX;
ptTo.Y += 2*iBaseY;
g.DrawLine (_penConnection, ptFrom, ptTo);
}
//==========================================================================
/// <summary>
/// (Neu-)Zeichnen eines Hexagons
/// </summary>
protected void DrawHexagon (Graphics g, int iX, int iY)
{
Point pt;
int iOffsetX;
int iOffsetY;
GraphicsPath gpath;
Region region;
//-----------------------------------------------------------------------
// Erstmal herauskriegen, wo das Hexagon gezeichnet werden soll.
//-----------------------------------------------------------------------
pt = GetHexagonPoint (iX, iY);
iOffsetX = pt.X;
iOffsetY = pt.Y;
//-----------------------------------------------------------------------
// Dann legen wir die sechs Eckpunkte des Hexagons an (wobei der
// erste Punkt zweimal angegeben wird, damit das Polygon geschlossen
// ist).
//-----------------------------------------------------------------------
Point[] apt =
{
new Point (iOffsetX + 0*iBaseX, iOffsetY + 1*iBaseY),
new Point (iOffsetX + 1*iBaseX, iOffsetY + 0*iBaseY),
new Point (iOffsetX + 2*iBaseX, iOffsetY + 1*iBaseY),
new Point (iOffsetX + 2*iBaseX, iOffsetY + 3*iBaseY),
new Point (iOffsetX + 1*iBaseX, iOffsetY + 4*iBaseY),
new Point (iOffsetX + 0*iBaseX, iOffsetY + 3*iBaseY),
new Point (iOffsetX + 0*iBaseX, iOffsetY + 1*iBaseY)
};
//-----------------------------------------------------------------------
// Jetzt machen wir aus den Punkten einen (polygonen) Pfad.
//-----------------------------------------------------------------------
gpath = new GraphicsPath ();
gpath.AddPolygon (apt);
//-----------------------------------------------------------------------
// Eigentliches Zeichnen
//-----------------------------------------------------------------------
g.DrawPath (_penBorder, gpath);
//-----------------------------------------------------------------------
// Testausgabe ((zweidimensionaler) Index der Hexagone)
//-----------------------------------------------------------------------
String strText;
SizeF sizef;
strText = String.Format ("[{0},{1}]", iX, iY);
sizef = g.MeasureString (strText, _font);
g.DrawString(strText,
_font,
_brushText,
iOffsetX+(2*iBaseX-1-sizef.Width)/2+1,
iOffsetY+(4*iBaseY-1-sizef.Height)/2+1);
//-----------------------------------------------------------------------
// Jetzt sagen wir der PictureBox noch, dass sich was geändert hat
// (nämlich die den (polygonen) Pfad umschließende Region)
//-----------------------------------------------------------------------
region = new Region (gpath);
_picbCanvasBehind.Invalidate (region);
}
}
//*****************************************************************************
abstract class App
{
public static void Main (string [] astrArg)
{
Application.Run (new HexagonWindow ());
}
}
bevor du von mir was "falsches" lernst, noch folgender Hinweis dazu, wo ich gegen die MS Namenskonventionen verstoße: Namenskonventionen: Ja oder Nein? .
auch wenn ich mich als Totengräber längst vergessener Threads betätige, habe ich etwas gefunden dass thematisch hier rein passt:
Da ich mich seit einiger Zeit auch mit Pathfinding beschäftige bin ich auf einen interessanten Artikel gestossen welcher sich mit diversen Pathfinding Algorithmen für 2D und 3D Szenarien beschäftig. Ist zwar ein Free Chapter aus einem Java Buch, lässt sich aber Problemlos auf C# ummünzen.