Anzahl der Züge von Feld zu Feld

[H2O]

Hallo alle zusammen und miteinander.

Mein Problem lässt sich nicht so leicht in Worte fassen, also erst mal ein Bild (57 KB).

Diese ganzen Kästchen stellt man sich als (Spiel-)Feld vor und jedes einzelne Feld hat eine Nummerierung. Das ganz oben links (1,1), das rechts daneben (2,1) usw.
Nun will ich eine PHP Funktion erstellen, die ausrechnet, wie groß der Weg vom einen Feld zum anderen ist.
Auf dem Bild sind drei Beispiele.
Es gibt natürlich verschiedene Wege um von einem Punkt zum anderen zu gelangen, aber ich suche eine Möglichkeit mit der man die wenigsten Züge rauszufindet.

Also ein Beispiel:
Man gibt an von (2,5) auf (4,2) und die Funktion gibt 4 aus.

Das Problem ist eben, das die Felder sechseckig sind und mir ist leider noch keine Idee gekommen wie ich das umsetzten könnte.
Bin daher für alle Ideen und Gedankensanstöße dankbar 8)

H2O

PS: Passt natürlich eigentlich auch in andere Kategorien aber ich will es am Ende in PHP umsetzen.

[lulu]

Huhu H2o

Bin daher für alle Ideen und Gedankensanstöße dankbar 8)

Da müsste es ja eine einfache Formel geben.

Wähle eine Feld in der Mitte des Spielplanes und gucke welche
Felder Du mit 1 Schritt erreichst.
Male diese grün an.
Dann alle Felder die Du mit zwei Schritten erreichst gelb anmalen.
Drei Schritt-Felder werden dann natürlich blau angestrichen.

Preisfrage zwischendurch: "Welche Farbe bekommen die Felder welche mit vier Schritten erreicht werden können?"

Wenn Du Dir dann die Koordinaten der gleichfarbigen Felder anguckst
sollte die gesuchte Formel laut "hallo hier bin ich" rufen.

Also mehr in "Radiüssen" denken.

Viele Grüße

lulu

[H2O]

Hallo lulu.

Ich befürchte fast, da gibt es eine einfach Lösung nur ich habe mal wieder ein Brett vorm Kopf...
Also ich habe das jetzt mal gemacht:
Das Resultat
Und was bringt mir das jetzt?

H2O

[nilsausworms]

Hallo H2O

Habs mit Mathe nicht so drauf (Bin aber Schachspieler ;) ), aber, warum behandelst du das spielfeld nicht so als wäre es dreidimensional ?
Stell dir diese Sechsecke als Würfel vor. (zieh von jeder zweiten Ecke einen Strich zum Mittelpunkt, ist dann ein Würfel, so betrachtet, das man drei Seiten zu gleichen Teilen sieht. Siehst Dus?) Das ergibt dann so ne Art Treppe...Dann hat jeder Würfel 3 Koordinaten, eine für jede Dimension, und wenn ich mich nicht täusche, hat jeder Würfel für z.B. die x-Koordinate einen unterschiedlichen Wert...
Das dürfte doch einfach zu Programmieren sein ?!

Gruss aus Worms

[nilsausworms]

Nachtrag: Das mit den unterschiedlichen Werten für eine einzelne Koordinate stimmt nicht :)

Gruss aus Worms

[H2O]

Hallo nilsausworms.

Habs mit Mathe nicht so drauf (Bin aber Schachspieler ;) ), aber, warum behandelst du das spielfeld nicht so als wäre es dreidimensional ?

Das würde die Sache meiner Meinung nach nur noch erschweren .oO

Stell dir diese Sechsecke als Würfel vor. (zieh von jeder zweiten Ecke einen Strich zum Mittelpunkt, ist dann ein Würfel, so betrachtet, das man drei Seiten zu gleichen Teilen sieht. Siehst Dus?) Das ergibt dann so ne Art Treppe...Dann hat jeder Würfel 3 Koordinaten, eine für jede Dimension, und wenn ich mich nicht täusche, hat jeder Würfel für z.B. die x-Koordinate einen unterschiedlichen Wert...

Ich verstehe dich nicht ganz. Meinst du, dass man die einzelnen Felder nochmal in 3 Felder unterteilt?

H2O

[nilsausworms]

Ach scheisse, mit meinem Linux krieg ich garnix hin! Ich würd dir das ganze gern als Bild zeigen, aber hab kein FTP-Programm... jedenfalls, wenn du's 3D machst, hättest du wieder deine gewünschten rechten Winkel ;)
               .
            .     .
         .           .
      .                 .
      .  .           .  .
      .     .     .     .
      .        .        .
      .        .        .
         .     .      .
            .  .  .
               .

(So hab ich das gemeint..)

gruss aus Worms nach einer durchgezechten Nacht....

[lulu]

Huhu H2O

Also ich habe das jetzt mal gemacht:
Das Resultat

hübsch ;-)

Und was bringt mir das jetzt?

Tja, jetzt könntest Du im nächsten Schritt die relativen Koordinaten der
einzelnen Schrittweiten aufschreiben.
Das war meine Idee von gestern, aber anscheined ist das Problem doch etwas kniffliger.
Wie sieht es denn aus, hast Du schon eine (Teil-)Lösung?
Wenn ich Zeit hätte würde ich mich da glatt selbst mit beschäftigen.
Aber im Moment ist mal wieder "strohzugoldspinnen" angesagt :-(

Viele Grüße

lulu

[H2O]

Hallo lulu.

Wie sieht es denn aus, hast Du schon eine (Teil-)Lösung?

Naja, so ganz grob...

Ich werde wahrscheinlich die Koordinaten wirklich immer in die jeweilige Richtung angleichen. Das heißt die Funktion wird rekursiv ablaufen.

Also Beispiel:
Von 2,5 (x1,y1) auf 4,2(x2,y2) (Beispiel oben links)
Als erstes wird festgestellt, dass x erhöht werden muss, da x2 größer als x1 ist.
y muss in jedem Schritt verringert werden (da 5 > 2).

Also, los geht's:
1. Aufruf: 2,5 auf 3,4 möglich? Ja; 2,5 -> 3,4
2. Aufruf: 3,4 auf 4,3 möglich? Nein; Alternative: 3,4 auf 3,3 möglich? Ja; 3,4 -> 3,3
3. Aufruf: 3,3 auf 4,2 möglich? Nein; Alternative: 3,3 auf 3,2 möglich? Ja; 3,3 -> 3,2
4. Aufruf: 3,2 auf 4,2 möglich? Ja; 4,2
Ziel erreicht, Anzahl der gebrauchten Aufrufe: 4

Ich muss natürlich noch eine Möglichkeit finden zu prüfen ob der Zug möglich ist. Aber das dürfte sich ja einrichten lassen in dem man überprüft, ob x gerade oder ungerade ist.

Man liest sich, H2O

[dedlfix]

echo $begrüßung;

Bin daher für alle Ideen und Gedankensanstöße dankbar 8)

Na dann... ich stelle mir das so vor: Die Sechseckigkeit spielt eigentlich keine große Rolle, die lenkt nur ab. Interessanter scheinen mir die Koordinaten.
Gegeben ist die Start-Koordinate x1,y1 und die Zielkoordinate x2,y2. Mit jedem Berechnungsschritt wird der Wert von x1 in Richtung x2 angepasst. Dabei muss, gemäß Start und Ziel, inkrementiert oder dekrementiert werden. Das gleiche passiert mit y1 in Bezug auf y2. Wenn x oder y den Zielwert erreicht hat, wird logischerweise nur noch der andere behandelt.
Zu beachten ist noch, dass nicht alle Schritte erlaubt sind. Bei geradem x darf y nicht inkrementiert werden. Von 2,5 gibt es keinen direkten Weg zu 1,6 oder 3,6. Ebenso gilt bei ungeradem x darf y nicht dekrementiert werden.

echo "$verabschiedung $name";

[H2O]

echo $begrüßung;

Auchso ;)

Mit jedem Berechnungsschritt wird der Wert von x1 in Richtung x2 angepasst. Dabei muss, gemäß Start und Ziel, inkrementiert oder dekrementiert werden.

Inkrementieren oder dekrementieren bedeutet $varibale++ bzw. $varialbe--, oder?
Was meinst du mit "in Richtung anpassen" und wie meinst du das mit dem inkremetieren und dekrementieren? :-/

Das gleiche passiert mit y1 in Bezug auf y2. Wenn x oder y den Zielwert erreicht hat, wird logischerweise nur noch der andere behandelt.

Achso, ich glaube ich weiß was du meinst...

x und y sollen dann jeweils immer um eins vergrößert bzw. verkleinert werden, bis sie das Ziel erreicht haben (das meinst du doch), oder?

Zu beachten ist noch, dass nicht alle Schritte erlaubt sind. Bei geradem x darf y nicht inkrementiert werden. Von 2,5 gibt es keinen direkten Weg zu 1,6 oder 3,6. Ebenso gilt bei ungeradem x darf y nicht dekrementiert werden.

OK, hat mir weitergeholfen, ein Gedanke ist schon mal da. ;)

echo "$verabschiedung $name";

Ja, klappt ja fast *SCNR*

Vielen Dank, H2O

[dedlfix]

echo $begrüßung;

x und y sollen dann jeweils immer um eins vergrößert bzw. verkleinert werden, bis sie das Ziel erreicht haben (das meinst du doch), oder?

Ja, natürlich nur unter Berücksichtigung der genannten Ausnahmen.

echo "$verabschiedung $name";

[H2O]

Hallo dedlfix.

Ja, natürlich nur unter Berücksichtigung der genannten Ausnahmen.

OK, so werde ich es machen.
Vielen Dank.

Man liest sich, H2O

[Ashura]

Hallo H2O.

Inkrementieren oder dekrementieren bedeutet $varibale++ bzw. $varialbe--, oder?

Hilfe! Die Varibalen sind wieder da!

*sncr*

Einen schönen Mittwoch noch.

Gruß, Ashura

[dedlfix]

echo $begrüßung;

Inkrementieren oder dekrementieren bedeutet $varibale++ bzw. $varialbe--, oder?

Hilfe! Die Varibalen sind wieder da!

Beruhige dich erstmal wieder, zuerst müssen sie noch über die Varialben drüber.

echo "$verabschiedung $name";

[Ashura]

Hallo dedlfix.

Inkrementieren oder dekrementieren bedeutet $varibale++ bzw. $varialbe--, oder?

Hilfe! Die Varibalen sind wieder da!

Beruhige dich erstmal wieder, zuerst müssen sie noch über die Varialben drüber.

Also wenn es Varibal mit ein paar Elefanten geschafft hat, werden die das ja wohl auch schaffen...

*schluck*

Einen schönen Mittwoch noch.

Gruß, Ashura

[H2O]

Hallo Ashura.

Hallo dedlfix.

Inkrementieren oder dekrementieren bedeutet $varibale++ bzw. $varialbe--, oder?

*lol* Na da habe ich mir aber echt Mist zusammengeschrieben...

Und ihr zieht natürlich gleich drüber her... *gg*

Man liest sich, H2O

[Vinzenz Mai]

Hallo H2O

Inkrementieren oder dekrementieren bedeutet $varibale++ bzw. $varialbe--, oder?

*lol* Na da habe ich mir aber echt Mist zusammengeschrieben...

Und ihr zieht natürlich gleich drüber her... *gg*

Das Forumskurzzeitgedächtnis ist halt bei manchen hier gut ausgeprägt.

Freundliche Grüße

Vinzenz

[H2O]

Hallo Vinzenz.

Das Forumskurzzeitgedächtnis ist halt bei manchen hier gut ausgeprägt.

*lol* Klasse der Thread...
Und der Thread-Eröffner hat sich noch nicht mal zu seinen Variablen (ja! Richtig geschrieben!) geäußert *gg*

Man liest sich, H2O

[Christoph Zurnieden]

Hi,

such mal nach "Bresenham Algorithmus".
Trifft Dein Problem zwar nicht 100% im Detail, aber das Prinzip bleibt gleich.

so short

Christoph Zurnieden

[H2O]

Hallo Christoph.

such mal nach "Bresenham Algorithmus".

Also wenn ich das richtig verstanden habe, dann stellt man mit diesem Algorithmus Geraden da. Ich will sie ja aber nicht darstellen...

Trifft Dein Problem zwar nicht 100% im Detail, aber das Prinzip bleibt gleich.

Nunja, aber ich bin nicht wirklich dahinter gekommen, wie ich mit dem Prinzip ausrechnen kann, wieviele Züge man von einem Feld zum anderen braucht :(

Trotzdem danke,
H2O

[Christoph Zurnieden]

Hi,

such mal nach "Bresenham Algorithmus".

Also wenn ich das richtig verstanden habe, dann stellt man mit diesem Algorithmus Geraden da. Ich will sie ja aber nicht darstellen...

Doch, das möchtest Du, glaub's mir.

Der "Bresenham Algorithmus" dient dazu Vektoren in diskrete Schritte umzuformen damit sie mit Pixeln dargestellt werden können.

Mal ganz krumm erklärt (alle mal weghören bitte! ;-):
Ein Vektor bezeichnet die Richtung einer Strecke, ich bezeichne das mal als Luftlinie. Der "Bresenham Algorithmus" dient dann dazu, diese Luftlinie auf Straßen abzubilden.

Trifft Dein Problem zwar nicht 100% im Detail, aber das Prinzip bleibt gleich.

Nunja, aber ich bin nicht wirklich dahinter gekommen, wie ich mit dem Prinzip ausrechnen kann, wieviele Züge man von einem Feld zum anderen braucht :(

Dann hast Du Dir entweder nicht richtig Mühe gegeben oder Dir fehlt das nötige Grundwissen. Ich gehe mal vom zweitem aus, also: was genau hast Du nicht verstanden?

so short

Christoph Zurnieden

[H2O]

Hallo Christoph.

Doch, das möchtest Du, glaub's mir.

:~/

Der "Bresenham Algorithmus" dient dazu Vektoren in diskrete Schritte umzuformen damit sie mit Pixeln dargestellt werden können.

Jetzt wo du's sagst... Dann müsste ich eigentlich nur die Abschnitte zählen, in die die Linie unterteilt wird, oder?

Dann hast Du Dir entweder nicht richtig Mühe gegeben oder Dir fehlt das nötige Grundwissen. Ich gehe mal vom zweitem aus, also: was genau hast Du nicht verstanden?

Joah, ich denke mal von beidem ein bisschen ;)

Man liest sich, H2O

[Christoph Zurnieden]

Hi,

Doch, das möchtest Du, glaub's mir.

:~/

Tja, mitunter ist es wirklich und tatsächlich _so_ simpel, das man meint es könnt' nicht sein ;-)

Der "Bresenham Algorithmus" dient dazu Vektoren in diskrete Schritte umzuformen damit sie mit Pixeln dargestellt werden können.

Jetzt wo du's sagst... Dann müsste ich eigentlich nur die Abschnitte zählen, in die die Linie unterteilt wird, oder?

Nein, so ganz einfach funktioniert es natürlich nicht, denn dann gäbe es keine "Pixeligkeit", keine "Treppen" und andere unangenehm anzuschauende Sächelchen. Das zu verhindern wäre eine teilweise recht komplexe Optimierung, aber das wolltest Du ja eh nicht.

Die beiden einfachsten Fälle sind natürlich senkrechte bzw waagerechte Strecken. Komplizierter, aber auch nicht viel, wird es bei Diagonalen. Druck Dir einfach mal Deine Ebene aus und probiere ein wenig mit dem Lineal herum, dann wirst Du sehen, was gemeint ist. Aber genau dafür ist ja der Bresenham gedacht.

Dann hast Du Dir entweder nicht richtig Mühe gegeben oder Dir fehlt das nötige Grundwissen. Ich gehe mal vom zweitem aus, also: was genau hast Du nicht verstanden?

Joah, ich denke mal von beidem ein bisschen ;)

Bevor ich jetzt in die Tiefen der Graphentheorie verschwinde, um Deine Faulheit gar gräßlich zu bestrafen sei Dir ein beliebiges Tutorial anempfohlen, z.B. dieses hier:
http://turing.fh-landshut.de/~jamann/bresenham.html

so short

Christoph Zurnieden

[H2O]

Hallo Christoph.

Tja, mitunter ist es wirklich und tatsächlich _so_ simpel, das man meint es könnt' nicht sein ;-)

Na dann hoffe ich das mal *g*

Die beiden einfachsten Fälle sind natürlich senkrechte bzw waagerechte Strecken. Komplizierter, aber auch nicht viel, wird es bei Diagonalen. Druck Dir einfach mal Deine Ebene aus und probiere ein wenig mit dem Lineal herum, dann wirst Du sehen, was gemeint ist. Aber genau dafür ist ja der Bresenham gedacht.

Ja, ich glaube so langsam versteh ich's ;)

Bevor ich jetzt in die Tiefen der Graphentheorie verschwinde, um Deine Faulheit gar gräßlich zu bestrafen sei Dir ein beliebiges Tutorial anempfohlen, z.B. dieses hier:
http://turing.fh-landshut.de/~jamann/bresenham.html

Also entweder du bist dem Link auf Goo gle gefolgt oder aber du hast die Seite bei Wikipedia gefunden.
Ich bin bereits über beide Varianten auf die Seite gekommen, konnte mich aber keinmal dafür durchringen sie zu lesen (was auch damit zusammenhängt, dass ich das meiste überhaupt nicht verstehe... (also nicht nur Faulheit)) *gg*

Ich denke mal ich werde die von dedlfix angesprochene Methode verwenden...

Trotzdem vielen Dank für deine Hilfe ;)

H2O

PS: Ach ist das schön, dass man hier im Forum jetzt bei Links auch den Titel angeben kann ;)

[Vinzenz Mai]

Hallo H2O

PS: Ach ist das schön, dass man hier im Forum jetzt bei Links auch den Titel angeben kann ;)

Wie lange warst Du weg? Ich bin jetzt zu träge, die Suche zu bemühen.

Freundliche Grüße

Vinzenz

[H2O]

Hallo Vinzenz.

Wie lange warst Du weg? Ich bin jetzt zu träge, die Suche zu bemühen.

Ungefähr ein halbes bis ganzes Jahr (so genau weiß ich es nicht mehr) inaktiv...
Naja, zwischendurch immer mal wieder kurzzeitig im Forum aktiv, aber halt nur kurz...

Man liest sich, H2O