Laden...

A* (Pathfinding) mit Sechsecken?

Erstellt von ingram333 vor 18 Jahren Letzter Beitrag vor 16 Jahren 12.073 Views
I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren
A* (Pathfinding) mit Sechsecken?

Hi folks!

Ich versuche gerade verzweifelt seit einigen Tagen den
A* Alghorithmus im Bezug auf Wegpfindung zum laufen zu
kriegen, blicke aber einfach nicht ganz durch...

Gefunden habe ich folgende Implementierung für C#:
http://www.codeproject.com/csharp/CSharpPathfind.asp

(wer andere für C# kennt bitte posten!)

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...

Ein Bild wofür ich es brauche:
http://www.nux-acid.org/hexfeld.gif

Son Game ala "Battle Isle", geht darum wie eine Einheit
sich nun auf dem Feld bewegt.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

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.

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

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.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

also nochmal. A* basiert auf Node-Listen. Ob diese Nodes Quadrate oder Rechtecke repräsentieren ist egal.

So steht denn auch in dem Artikel:

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:

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.

Löst es das?

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

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?

2000 Dank 😉

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

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.

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

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)" ?

10000 Dank!

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

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.

Nachbarn von a[i,j] sind:

a[i-1,j]
a[i+1,j]
a[i,j-1]
a[i,j+1]

sowie
a[i+1,j-1]
a[i+1,j+1]
wenn j%2==1

bzw.
a[i-1,j-1]
a[i-1,j+1]
wenn j%2==0

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

danke dir, ich bin schon etwas weiter gekommen!

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

Hi nochmal!

Also eine Kleinigkeit in der Logik scheint noch nicht zu funktionieren.

Die Originalfunktion war:


public override void GetSuccessors(ArrayList ASuccessors)
		{
			ASuccessors.Clear();
			AddSuccessor(ASuccessors,FX-1,FY  );
			AddSuccessor(ASuccessors,FX-1,FY-1);
			AddSuccessor(ASuccessors,FX  ,FY-1);
			AddSuccessor(ASuccessors,FX+1,FY-1);
			AddSuccessor(ASuccessors,FX+1,FY  );
			AddSuccessor(ASuccessors,FX+1,FY+1);
			AddSuccessor(ASuccessors,FX  ,FY+1);
			AddSuccessor(ASuccessors,FX-1,FY+1);
		}	

Ich hab sie jetzt so abgeändert:


public override void GetSuccessors(ArrayList ASuccessors)
		{
			ASuccessors.Clear();
			/*
			Für HexFelder:
			a[i,j-2]
			a[i,j+2]
			a[i,j-1]
			a[i,j+1]
			sowie 
			[i+1,j-1]
			a[i+1,j+1]
			bei den ungeraden Zeilen bzw.
			i-1,j-1]
			a[i-1,j+1]
			bei den geraden Zeilen. 
			  */
			AddSuccessor(ASuccessors,FX,FY-2);
			AddSuccessor(ASuccessors,FX,FY+2);
			AddSuccessor(ASuccessors,FX,FY-1);
			AddSuccessor(ASuccessors,FX,FY+1);
			if(FY%2 != 0)
			{
				AddSuccessor(ASuccessors,FX+1,FY-1);
				AddSuccessor(ASuccessors,FX+1,FY+1);
			}
			else
			{
				AddSuccessor(ASuccessors,FX-1,FY-1);
				AddSuccessor(ASuccessors,FX-1,FY+1);
			}
			
			
		}	

Wäre doch so richtig eingebaut, oder?

Mein HexArray wird gerade durch eine statische map dargestellt:


static int[,] Map = {
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 },
			{ 1,1, 1,1, 1,1, 1, 1, 1, 1 }
		};

Problem:

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) 🙂

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

die Ausgabe ist irreführend, da Hexagone als Quadrate ausgegeben werden.

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

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:


static public void PrintSolution(ArrayList ASolution)
		{
			for(int j=0;j<10;j++) 
			{
				for(int i=0;i<10;i++) 
				{
					bool solution = false;
					foreach(AStarNode2D n in ASolution) 
					{
						AStarNode2D tmp = new AStarNode2D(null,null,0,i,j);
						solution = n.IsSameState(tmp);
						if(solution)
							break;
					}
					if(solution)
						Console.Write("S ");
					else
						if(MainClass.GetMap(i,j) == -1)
						Console.Write("X ");
					else
						Console.Write(". ");
				}
				Console.WriteLine("");
			}
		}

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...

Danke!

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

probier mal die Nachbarschaftsbeziehung, die ich als zweites gepostet habe, also die, die zu meinem Bild passt.

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

ok hab ich, jetzt ist die Ausgabe:

X:0Y:0
X:0Y:1
X:1Y:2
X:2Y:2
X:2Y:3
X:2Y:4
X:3Y:4
X:4Y:4
X:4Y:5
X:5Y:5

(hab nur die Felder ausgeben lassen)

Da verwirrt mich nur [2,4] weil der Schritt IMHO wenn man
dein Bild betrachtet unnötig währe (es gibt noch keine
TerrainKosten, ist alles auf 1).

Danke dir 1000000x!!!

EDIT:

der Code:


AddSuccessor(ASuccessors,FX-1,FY);
			AddSuccessor(ASuccessors,FX+1,FY);
			AddSuccessor(ASuccessors,FX,FY-1);
			AddSuccessor(ASuccessors,FX,FY+1);
			if(FY%2 == 1)
			{
				// ungerade Zeilen
				AddSuccessor(ASuccessors,FX+1,FY-1);
				AddSuccessor(ASuccessors,FX+1,FY+1);
			}
			else
			{
				// gerade Zeilen
				AddSuccessor(ASuccessors,FX-1,FY-1);
				AddSuccessor(ASuccessors,FX-1,FY+1);
			}

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

Hab etwas...

Wenn man die Heuristic umstellt auf:


// "Manhattan Distance" - Used when search can only move vertically and 
// horizontally.
GoalEstimate = Math.Abs(xd) + Math.Abs(yd); 

Gibt er einen sinnvollen weg aus:
Starting...
X:0Y:0
X:0Y:1
X:1Y:2
X:1Y:3
X:2Y:4
X:2Y:5
X:3Y:5
X:4Y:5
X:5Y:5

Mich irritiert allerdings das Kommentar:
// "Manhattan Distance" - Used when search can only move vertically and
// horizontally.

Das ja bei mir nicht unbedingt der Fall...

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

das heißt ja vermutlich nur, dass er keine Berechnung macht, beider die Diagonalen länger sind als die Horizontalen und Vertikalen.

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

ok, denke dann hab ichs gelöst 🙂

Danke dir vielmals, ...man kann User in diesem Forum nicht
bewerten, oder? Ansonsten würd ich dir die absolute
Höchstwertung geben 😉

Danke nochmal!

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

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*.

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

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.

herbivore

4.221 Beiträge seit 2005
vor 18 Jahren

@herbivore

Mach doch mal ein paar Tierchen für das Terrarium.... dort musste auch zum Futter navigieren usw...

😉

Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

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 😉

Poste ruhig irgendwann mal, würd mich freuen 🙂

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

[...] 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 ());
   }
}

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

danke dir, da kann ich mir schonmal alleine ne Menge an
Formatierung und Kommentaren abschaun (schieltvorsichtigaufseinkuddelmuddel)

1000 Dank für den Code! 🙂

...kleine Frage warum machst du das _ vor manchen Variablen?

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

ich schreibe einen Unterstrich genau vor die Exemplarvariablen (= Inzanzvariablen).

herbivore

I
ingram333 Themenstarter:in
72 Beiträge seit 2005
vor 18 Jahren

jo habs auch gerade rausbekommen, sollte ich mir auchmal angewöhnen...

Danke nochmal 🙂

49.485 Beiträge seit 2005
vor 18 Jahren

Hallo ingram333,

bevor du von mir was "falsches" lernst, noch folgender Hinweis dazu, wo ich gegen die MS Namenskonventionen verstoße: Namenskonventionen: Ja oder Nein? .

herbivore

5.941 Beiträge seit 2005
vor 17 Jahren

Original von herbivore
Aber wenn du dich etwas geduldest, kann ich spätestens am nächsten Wochenende was posten.

Hallo Herbivore

Hast du es schon fertig?
Würde mich auch interessieren.

Gruss Peter

--
Microsoft MVP - Visual Developer ASP / ASP.NET, Switzerland 2007 - 2011

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Peter Bucher,

ich habe den Code doch schon oben gepostet . Außerdem habe ich was das OnPaint angeht ein Tutorial geschrieben: [Tutorial] Zeichnen in Windows-Programmen (Paint/OnPaint, PictureBox) .

herbivore

5.941 Beiträge seit 2005
vor 17 Jahren

Ach.... hmpf, ich hab den Code ja schon mal gesehen, stimmt.
Bin noch nicht ganz wach 😉

--
Microsoft MVP - Visual Developer ASP / ASP.NET, Switzerland 2007 - 2011

871 Beiträge seit 2005
vor 17 Jahren

Hallo,

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.

http://www.peachpit.com/content/images/1592730051/samplechapter/1592730051c.pdf

Grüsse, Egon

B
214 Beiträge seit 2005
vor 16 Jahren

@egrath,
hättest du die PDF bei dir noch rumliegen? Online ist sie nicht verfügbar, über google komme ich nur an die html Version davon, sieht etwas unsauber aus.
Solltest du eine Kopie noch haben, wäre ich dir dankbar, wenn du sie mir per E-Mail schicken könntest 🙂

Grüße Bionic

.:: SilvrGame - Browsergame Development with Silverlight
.:: Bionic's blOg

871 Beiträge seit 2005
vor 16 Jahren

Hallo,

der im vorherigen Post von mir genannte Link funktioniert bei mir tadellos. Probier mal mit "Speichern unter ...", eventuell hat dein Browser irgendwelche macken.

Grüsse,
Egon

B
214 Beiträge seit 2005
vor 16 Jahren

Strange, auf der Arbeit gings nicht und hier daheim funktionierts tadellos. Danke dir nochma 😉

.:: SilvrGame - Browsergame Development with Silverlight
.:: Bionic's blOg