Pathfinding geht auch mit PHP

Hattet ihr nicht auch schonmal das Problem in einem eurer BGs, das ihr keine richtige Möglichkeit hattet den Weg zu bestimmen, den eure Truppen gehen sollen.

Ich hab mich wie versprochen hingesetzt und ein Script mittels dem Algorithmus A* geschrieben, die genau dieses aus der Welt schafft.

Ihr versteht immernoch nicht was ich meine?

Eure Truppen wollen von Punkt A nach Punkt B. Da liegen aber Flüsse dazwischen und auch andere Ortschaften, die man nicht durchqueren kann. Nun will man ja die Truppe nicht in die Wallachei schicken, sondern den effizientesten Weg.

Noch kann man nicht bestimmen, welches Terrain welche "punkte" hat (also Punkte zur Bevorzugung). Aber bis Version 1.0 ist dies eingebaut. Bis jetzt kann man eben Bit-Maps mit 0 und 1 machen, wo 0 ein weg ist und 1 eine "wand".

Wer Interesse hat: PHP-Pathfinder v0.8 (Seite im Aufbau)

Aber nur zur Info: Dieses Script steht unter der LGPL. Bitte nutzt es auch so und missbraucht es nicht.


Bis denne (zum nächsten Script, was wahrscheinlich ein Karteneditor für kartesische und isometrische Karten sein wird)


KoMtuR
- Programmierer von browsergames24.de -

P.S.: Wer Fehler im Script findet könnte mir nen Hinweis schicken


edit: Es gab einen kleinen Rechtschreibefehler in Zeile 49 der example.php

$test = $ki->FindPath(0,$startx,$stary,$endx,$endy);


muss natürlich so heissen

$test = $ki->FindPath(0,$startx,$starty,$endx,$endy);


edit2: License wurde auf LGPL geändert.

Das Script steht unter GPL oder LGPL?
Ersteres würde bedeuten, dass man den Code des GESAMTEN Browsergames freigeben müsste, wenn man dieses A* nutzt und keinen weiteren Algorithmus zur Verfügung hat und modular aus- und einladen könnte.

GPL und Konsorten sind allerdings für mich vollkommen uninteressant, wegen der hohen nachfolgenden Verpflichtung und dem Verlust meines Codes.

Wenn du den Code runtergeladen hättest würdest du sehen, dass es unter GPL steht. Steht ja am Anfang im Kommentar. Ich will nur damit bezwecken, dass Neuerungen für alle öffentlich steht. Warum sollte man nicht allen Browsergames die Möglichkeit geben etwas mehr Funktionen zu bekommen.
Ausserdem wächst durch die setigenden Zahlen der Browsergames das Erwartungsniveau der Spieler. Deswegen dachte ich GPL ist geeigneter als LGPL

Und solange du die Klasse nicht veränderst geht mich der Rest auch nichts an. Es geht ja nur um die Klasse und nicht um das Beispiel.

Gute Sache. Ich wollte neulich schon einen A* schreiben, aber nun wurde das ja erledigt. Ich werde mir bei Gelegenheit mal deine Implementation anschauen.

Leider ist es GPL also kann ich es nicht verwenden, LGPL wäre wohl doch eher angebracht gewesen. GPL bedeutet in diesem Fall nämlich wirklich die komplette Offenlegung des beteiligten BGs.

Naja vielleicht ändere ich es nochmal um. Ich wollte mich da nochmals richtig beraten lassen

Also wird sich vielleicht was machen lassen. ich will ja niemanden die Benutzung verweigern, weil es ja sonst keinen Sinn hätte. Es soll ja vielseitig genutzt werden.

edit: Ich hab es nun geändert. Ich möchte durch die Wahl der falschen Lizens nicht verhindern, dass es in Browsergames genutzt werden kann.

Hi,
seh ich das richtig, dass dies eine recht gute Lösung für mein Problem wär?

Mein Problem, finde den kürzesten weg auf dieser Karte von A nach B:

Link gelöscht
bzw.

Link gelöscht (gleiche Karte aber mit farbigem Hintergrund)
0 = befahrbar (Kosten = 1)
1,2,3 = unbefahrbar (Kosten = unendlich)

Wobei man von einem Feld nur 6 nicht 8 andere Felder ereichen kann.
gerade Spalten (vertikal) also Spalte 2,4,6,8,...,98,100:
(X,Y) {0,0 ist oben links}
Beispiel von (2,2) {gerade Spalte} kann ich folgenden Kords erreichen wenn diese alle den Wert 0 hätten:
(1,2);(1,3)
(2,1);(2,3)
(3,2);(3,3)

Beispiel von (3,2) {ungerade Spalte}
(2,1);(2,2) [quasi gleich wie gerade nur Y-1]
(3,1);(3,3) [quasi gleich wie gerade]
(4,1);(4,2) [quasi gleich wie gerade nur Y-1]

das man nur 6 Kästchen ereichen kann liegt daran, das die Karte eigentlich aus hexagons besteht. Als nicht Ascii version sieht die nämlich so aus:

Link gelöscht

Ooder ist da nen anderer Alghoritmus besser?

Naja das würde schon gehen, nur das man eben alles noch darauf anpassen müsste, dass man nur 6 wahlmöglichkeiten statt 8 hat. Mit ein wenig Programmieraufwand sollte dies zu schaffen sein.

Ok dein Koordinatensystem hab ich nicht ganz kapiert gerade, aber das liegt anscheinend daran, dass ich noch nichts mit hexagonen karten gemacht habe