Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
A* (Pathfinding) mit Sechsecken?
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

A* (Pathfinding) mit Sechsecken?

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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

Löst es das?

herbivore
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
Attachments
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

danke dir, ich bin schon etwas weiter gekommen!
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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)
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo ingram333,

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

herbivore
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo ingram333,

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

herbivore
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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);
			}
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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...
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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!
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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*.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Programmierhans
myCSharp.de - Experte

Avatar #avatar-1651.gif


Dabei seit:
Beiträge: 4318
Herkunft: Zentralschweiz

beantworten | zitieren | melden

@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...
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo ingram333,
Zitat
[...] 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
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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?
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo ingram333,

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

herbivore
private Nachricht | Beiträge des Benutzers
ingram333
myCSharp.de - Member



Dabei seit:
Beiträge: 72

Themenstarter:

beantworten | zitieren | melden

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

Danke nochmal
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Peter Bucher
myCSharp.de - Experte

Avatar #jVxXe7MDBPAimxdX3em3.jpg


Dabei seit:
Beiträge: 6141
Herkunft: Zentralschweiz

beantworten | zitieren | melden

Zitat
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

- https://peterbucher.ch/ - Meine persönliche Seite
- https://fpvspots.net/ - Spots für FPV Dronenflüge
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Peter Bucher
myCSharp.de - Experte

Avatar #jVxXe7MDBPAimxdX3em3.jpg


Dabei seit:
Beiträge: 6141
Herkunft: Zentralschweiz

beantworten | zitieren | melden

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

- https://peterbucher.ch/ - Meine persönliche Seite
- https://fpvspots.net/ - Spots für FPV Dronenflüge
private Nachricht | Beiträge des Benutzers
egrath
myCSharp.de - Member

Avatar #avatar-2119.jpg


Dabei seit:
Beiträge: 937
Herkunft: Österreich / Steyr

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers