Pixelkoordinaten eine Linie (canvas) ermitteln und speichern

[Hartkern]

Servus,

Ich sitz grad an der Problematik den Weg zwischen zwei Hexfeldern zu ermitteln, sprich welche Felder sind auf dem Weg zwischen Start Hexfeld und Ziel Hexfeld zu benutzen.
Mein Lösungsansatz ist eine Gerade zwischen die Mittelpunkte des Start und ZielFeldes zu legen und dann zu prüfen welche Felder von der Gerade geschnitten werden.
Mathematisch wäre es kein Problem eine Geradengleichung dafür zu ermitteln. Jedoch müsste hier wieder eine wilde Umrechnung von Mathe Koordinaten in Bildschirmkoordinaten (und dann noch relativ zur Zeichenfläche) erfolgen.
Gibt es jedoch die Möglichkeit, eine Linie per Canvas zu zeichnen und oder zumindest jede Pixelkoordinate dieser Linie in einen Array of TPoint zu speichern, am Besten ohne diese Linie wirklich zeichnen zu müssen? Dies würde enormen Rechenaufwand mir ersparen, da ich lediglich nur den Array durchprüfen müsste, statt gefühlt 100.000.000 mal mit meiner IsPointInPolygon Funktion zu prüfen ob ein Feld "getroffen" wurde.

[Komoluna]

Sorry, dass ich nur kurz einen Link reinwerfe, aber diese Seite ist einfach zu perfekt dafür:
http://www.redblobgames.com/grids/hexag ... ne-drawing
(sogar schon der richtige Absatz, wenn ich richtig verstanden habe, was du vorhast )

MFG

Komoluna

[Hartkern]

Moin...

Danke für den Link..da steht irgendwie alles drinne was ich mir bis jetzt erarbeitet hab. Jedoch schreibt der bloss nach dem die Linie gezeichnet wurde, das man nun noch auszuklamüsern muss, welche Felder geschnitten werden. Aber nicht das wie.

Na ich werd wohl mich an den mathematischen Ansatz setzen wenn ich die Punkte der Linie nicht bekomme

[wp_xyz]

Ich nehme mal an, ein "Hexfeld" ist sowas wie ein Maschendrahtzaun, also ein Feld aneinanderangrenzender Sechsecke, und deine Aufgabe ist es zu bestimmen, über welche Sechsecke der kürzeste Weg von dem einen Sechseckmittelpunkt A zum anderen Sechseckmittelpunkt b führt.

Eine Linie zu zeichnen und die gezeichneten Pixel abzufragen erscheint mir sehr ineffektiv. Das mit der Geraden ist schon richtig, nur muss man sich von Sechseck zu Sechseck vorwärts hangeln, dann ist man mit wenigen Schnittpunktberechnungen am Ziel.

Zunächst muss der Datentyp TSechseck so definiert werden, dass man weiß, welches Sechseck an jeder Kante angrenzt. Also: jedes Sechseck erhält eine Nummer und jede Kante erhält die Nummer des Nachbar-Sechsecks, etwa so:

Code: Alles auswählen

 
type
  TSechseck = class // oder record, ist egal
    ID: integer;
    Mittelpunkt: TPoint;
    Ecken: array[0..5] of TPoint;
    NachbarIDs: array[0..5] of Integer;
  end;

Dabei gehört die NachbarID[0] zur Kante zwischen Ecken[0] und Ecken[1], etc. Also NachbarID gehört zur Kante, die bei Ecke beginnt.

Zu Beginn der Rechnung machst du dir klar, wie die Gleichung der Geraden zwischen A und B lautet: y = cx+d, wobei c und aus den Koordinaten von A und B zu ermitteln sind.

Dann beginnst du mit dem Sechseck, dessen Mittelpunkt A ist: du läufst von Ecke 0 bis Ecke 5 und berechnest jedes Mal den Schnittpunkt der Verbindungslinie Ecke-Ecke[i+1] mit der Geraden (wobei im Fall der letzten Kante statt Ecke[6] wieder Ecke[0] zu nehmen ist --> (i+1) mod 6). Es wird in der Regel immer einen Schnittpunkt geben, merke dir das i derjenigen Ecke, zu der der Schnittpunkt zwischen Ecke und Ecke[i+1] liegt. Du wirst zwei solche Schnittpunkte erhalten, nimm denjenigen, bei dem die Strecke vom Schnittpunkt zu B am kürzesten ist. Da die Nummerierung der Ecken und Nachbarn miteinander korreliert, kennst du jetzt das Nachbarsechseck, bei dem die Suche weitergeht. Gehe zu dessen Mittelpunkt und wiederhole das ganze, solange bis zu am Ziel bist.

Anmerkung: Die Speicherung der Eckpunkt-Koordinaten in jedem Sechseck ist natürlich extrem ineffektiv, weil jeder Eckpunkt dreimal (in jedem angrenzenden Sechseck) gespeichert ist. Eigentlich musst du den Eckpunkt überhaupt nicht speichern, sondern du kannst ihn dir aus den Mittelpunktskoordinaten, dem Sechseckdurchmesser und dem Eckenindex jeweils ausrechnen.