Mav3N

Wie effizient sind die von dir verwendeten Algorithmen? A* hat entweder O(N^2) oder O(N * log(N)), je nach Implementierung. Weitere? Ich bin mir auch nicht sicher, ob die Heuristik für bewegte Kontrollbereiche über eine Runde hinaus monoton ist, das will der Algorithmus aber. Wie wertest Du die übergebenen Parameter aus? Ohne Code Review wird das wohl nix. Nun zur Komplexität des A* (der in meinem Script mit Abstand der am meisten Performance und Speicherfressende Algorithmus ist), kann ich nur sagen: Keine Ahnung! Ich hab mir den PseudoCode auf der Wikipediaseite angeguckt und einfach in PHP runtergescriptet. Den Code hast du in den vorherigen Beiträgen. Gut programmiert habe ich ihn nicht, aber er funktioniert mittlerweile. Alle meine Messungen lagen aber bei 10x10 Feldern immer unter 15ms. Andere Algorithmen habe ich nicht verwendet, ich habe mich an assoziative 2D Arrays gewöhnt, die ich immer und überall verwende. Diese verbrauchen denke ich auch eine ganze Menge Speicher in meiner fight.php, der Rest ist billiger Kinderkram if($actualChance + $Random >= 20) { ... } etc. Dementsprechend wäre der A* das performancefressendste Konstrukt in meinem Code, gefolgt von sehr großen, häufig verwendeten 2D Arrays. Mehr nicht. (Beim Statistikkampf wird die Situation 100mal durchsimuliert und der Mittelwert genommen). Das wären im schlimmsten Fall 100 * 15ms (astar.php) + 100 * 2ms (fight.php). Ich denke aber daran das demnächst auf 1000 Durchläufe anzuheben. Außerdem werde ich demnächst alles Sekundengenau berechnen, was nochmal den Aufwand in der fight.php um den Faktor 10 anhebt. Im Endausbau sollte das ganze also 1000 * 15ms + 1000 * 20ms = 35 Sekunden für einen Statistikkampf verbrauchen. (Werte richten sich für 10x10 Felder und ca. 5 Kämpfer in 2 Teams). Bei größeren Feldern und mehr Kämpfern steigt das ganze exponential. Bei allen Freehostern hast du ein execution time limit von meist unter 30 Sekunden. Also sehr, sehr wenig. Bei 100 Durchläufen ist das zwar noch machbar aber es wird knapp, wenn ich anfange sekundengenau zu simulieren. Das ganze Skript muss auf einen Server, der diese Beschränkung nicht hat (Elsa könnte das auf ihrem einstellen lassen denke ich) und der bessere Performance besitzt - ich mir die Performance nicht mit X Nutzern beim Freehoster teilen muss. An Elsa: Ich möchte einfach die fight.php, astar.php und insert.php auf deinem Server hosten, nachdem ich nochmal die Sicherheit des Skriptes überarbeitet habe und hoffe dadurch die Beschränkungen der Freehoster zu übergehen. Sicherheitstechnisch kann ich sagen, dass es ja alles von den Eingaben in der insert.php abhängt. Deswegen baue ich die Überprüfungen auch gerade Serverseitig und nicht Clientseitig auf. Derzeit ist es noch clientseitig. Diese könnte man nämlich umgehen, indem man sein eigenes JS Script anstelle von meinem platziert. Wenn die Eingaben abgesichert und überprüft sind, sehe ich kein Problem mehr. Sehr ihr erfahreneren Programmierer das ebenso? Elsa kann nur 2 Probleme bekommen: Sicherheitstechnisch (s. oben) und Performancetechnisch. Es würden Spitzen auftreten, in denen die CPU des Servers stark belastet ist. Diese würden bis zu 10 Sekunden andauern. Daran kann man aber nichts ändern. Jetzt bitte alle erfahrenen Progger äußern. Bamba

Wobei X und Y die Startposition angeben (X=0, Y=0 entspricht links oben) und B die Bewegungsweite ist. Ist es Absicht, dass man für die drei Werte maximal eine einstellige Zahl eingeben kann? D.h. du willst zunächst die sekundengenauen Regeln zur Abwicklung einer Kampfrunde umsetzen? Wäre es nicht sinnvoll, erstmal die 10-Sekunden Runde zu implementieren? Was mir noch aufgefallen: Es wäre schön, wenn man einstellen könnte, wie riskant ein Kämpfer kämpfen soll, d.h. ob er z.B. einen überstürzten Angriff macht oder nicht. Screenshots für Fehler sind etwas schwierig, da man hier im Forum als normaler Nutzer keine Bilder anhängen kann. Vielleicht überlegst du dir noch einen Debug-Modus, der ein Text-Debuglog erzeug, das man dann hier posten kann. CU FLo Das mit den Screenshots ist klar, deswegen bitte immer Eingaben und den gesamten Ausgaben Text bei Fehler mit Fehlerbeschreibung posten. Deine Anregung, dass man einstellen kann, wie riskant ein Kämpfer kämpfen soll, ist bereits auf meiner Todo-Liste und wir demnächst umgesetzt. Ich werde übrigens erstmal die sekundengenauen Regeln umsetzen, und auf Basis dessen die 10-Sekunden Regel anbieten. Ja, im moment ist es noch gewollt, dass man nur einstellige Werte (B kann zweistellige Werte annehmen) einstellen kann. Das hängt damit zusammen, dass nach der Umstellung intern einiges nicht mehr funktionierte und ich mehrstellige X und Y Eingaben derzeit noch nicht erlauben kann. Bamba

Hallo, es gibt genau 2 Fehler wie es scheint bei deinen Werten und Eingaben. Ein Fehler hat mit dem A* Algorithmus zu tun, den ich gefunden und behoben habe - ich lade die Verbesserung bald hoch. Der andere Fehler (?) scheint sich um die Schadens und Lebenspunkte zu drehen. Das Problem ist, dass es mir nicht gelingt ihn mit deinen Eingaben nachzustellen und zu reproduzieren. Nenn mir daher bitte andere Konstellationen und die komplette Anzeige sowie alle eingegebenen Werte bei denen der Fehler auftritt. Sonst kann ich ihn nicht finden, sofern er existiert. Bamba

Zum Beispiel darüber, ob du den Simulator auf die offizielle Seite aufnehmen möchtest und wie. Ich hab dir ja bereits gesagt, dass die FreeServer auf denen ich ihn gerade lager nicht gerade die beste Performance haben und somit eine Simulation seeehr lange dauern kann, bisweilen gar nicht geht. Bei dir dürfte das besser sein. Das ist einer der Gründe warum ich ihn auf der offiziellen Seite haben möchte. Ich bin allerdings kein soo erfahrener PHP-Programmierer und kann nicht alle Vor- und Nachteile abwägen, deswegen wollte ich hier öffentlich darüber diskutieren, damit sich einige erfahrenere Programmierer (die es hier sehr wohl gibt) einschalten und ihren Senf dazugeben. Es geht dabei um Themen wie Sicherheit und Stabilität. Also zusammengefasst: Nenn mir (uns) mal bitte deine Bedingungen, damit er aufgenommen werden würde. Vllt. kann ich Einwände mit Hilfe anderer Programmierer hier entkräften. Bamba

Wo bleibt die Abstimmung? Ich stimme für die Farbe unsichtbar

Ich bin zu 100% Palpatine meinen die. Ähm ich meine ... Lasst uns Frieden in der Galaxis bringen! *hust*

TEST

Suche die richtige Farbe

Bin dabei die Fehler zu suchen, demnächst gibt es eine Fehlerbereinigte neue Version. Ich hab an Elsa eine PN geschickt, in der ich sie darum bitte den Simulator, nachdem ich noch ein wenig Funktionen zur Sicherheit hinzugefügt habe, auf die offizielle Seite zu nehmen. Ich fände es gut, wenn sie sich hier dazu äußert, dann können alle mitdiskutieren. Bamba

Ich weiß nicht, was du eingegeben hast, bei mir funktioniert das alles. EDIT: Alle Fehler, die ihr findet bitte mit Screenshot hier posten!

Alle Versionen sind auf lima hochgeladen und unter http://midwar.de.vu/ erreichbar. Bamba

So, hab jetzt endlich Version 2.0 fertig. Größte Veränderung ist natürlich die Möglichkeit, dass sich Spielerfiguren wie auf einem Schachbrett bewegen können und sich Wege anhand des A* Algorithmus suchen. Ich lade derzeit alle Daten von piranho auf Lima-city.de - der Server ist besser. http://midwar.lima-city.de/V2.0/insert.php Das ist erstmal gerade die Adresse. Folgende Features unterstützt der Simulator nun: - Angreifen - Abwehren - Abwehren nicht erlaubt wenn Verteidiger 0 AP hat - Schadenkalkulation - Kampfunfähig ab 3 LP - Rüstung - Nicht unter 0 AP erlaubt - Minus 2 auf Angriffe wenn Angreifer LP/2 hat - Minus 4 auf Angriffe wenn Angreifer 0 AP hat - Plus 4 auf Angriff, wenn Verteidiger 0 AP hat - Anzeige wer gestorben / Kampfunfähig ist - Namensgebung möglich - Zufällige Gegnerwahl - Kampfinformationen ausschaltbar - Rundenanzeige - Statistikkampf - Inputüberprüfung - Standardbelegungen für Kämpfer - Rundenkampf - Kämpfer können sich bewegen, suchen selbstständig Wege zum Ziel - Bewegungsweite - -6 auf EW:Angriff, wenn diese Runde mehr als die Hälfte der Bewegungsweite verbraucht wurde - -2 auf den EW:Verteidigung, wenn diese Runde mehr als die Hälfte der Bewegungsweite verbraucht wurde - Positionsanzeige ACHTUNG: Es gibt in dieser Version, weil sich intern im Quellcode immens viel geändert hat, noch einige Probleme. 1. Die Eingaben für die X,Y und B Werte in insert.php werden noch nicht überprüft! Hierüber sind derzeit noch Attacken möglich (Ich glaube aber mal nicht, dass sich ein Midgard-Spieler dazu durchringt ) Bitte achtet darauf, dass ihr vernünftige Werte eingebt. 2. Die Gegnerauswahl ist derzeit IMMER NOCH per Zufall, erst in der nächsten Version werde ich hinzufügen, dass er sie sich anhand des Kriteriums der Entfernung aussucht. Trotz alledem suchen sich die Spieler nun den richtigen Weg auf dem Schachbrett, gehen ihn und greifen dann an. Und ganz besonders wichtig: Derzeit lasse ich einen Spieler seine kompletten Aktionen ausführen und erst dann den nächsten Spieler. Das muss ich noch ändern. Es soll am Ende so ablaufen, dass Spieler 1 einen Schritt geht, dann Spieler 2 einen Schritt seines Weges, etc. Schließlich soll das ganze ja möglichst dem Begriff der Gleichzeitigkeit nahekommen. Derzeit läuft ein Spieler leider erst seinen ganzen Weg, greift dann an, und dann ist der nächste dran. Da hab' ich noch eine Menge zutun. Bitte fleißig Fehler suchen, ich vermute, dass eine ganze Menge drinnen sind, da ich so ziemlich die Hälfte des Simulators intern umschreiben musste. Bamba (Ich schaff' das noch alle M4 Regeln umzusetzen!)

Es gab wirklich einen Fehler in meiner astar.php, bei dem ich vergaß Vorgängerknoten zu aktualisieren. Das Problem ist nun dank Hilfe eines sehr erfahrenen Programmierers gelöst. Astar funktioniert, ich werde es nun mit der restlichen Codebibliothek zusammenfügen - bald können unsere Kämpfer auch auf Karten laufen.

Du solltest die Ausgabe im Debugmodus etwas mehr erzählen lassen. Wie lang ist der Weg laut Programm und wie lang sind die Alternativen? Ergänzend wäre eine Ausgabe von Open und Closed List mit den Werten für f und h. Solwac Also wenn ich mir die closedlist in der getWay() Funktion ausgeben lasse, sieht das so aus: array(19) { [0]=> array(2) { ["X"]=> int(1) ["Y"]=> int(2) } [1]=> array(2) { ["X"]=> int(1) ["Y"]=> int(3) } [2]=> array(2) { ["X"]=> int(2) ["Y"]=> int(2) } [3]=> array(2) { ["X"]=> int(3) ["Y"]=> int(2) } [4]=> array(2) { ["X"]=> int(2) ["Y"]=> int(0) } [5]=> array(2) { ["X"]=> int(2) ["Y"]=> int(1) } [6]=> array(4) { ["X"]=> int(4) ["Y"]=> int(0) ["VX"]=> int(-1) ["VY"]=> int(-1) } [7]=> array(4) { ["X"]=> int(3) ["Y"]=> int(1) ["VX"]=> int(4) ["VY"]=> int(0) } [8]=> array(4) { ["X"]=> int(3) ["Y"]=> int(0) ["VX"]=> int(4) ["VY"]=> int(0) } [9]=> array(4) { ["X"]=> int(4) ["Y"]=> int(1) ["VX"]=> int(4) ["VY"]=> int(0) } [10]=> array(4) { ["X"]=> int(4) ["Y"]=> int(2) ["VX"]=> int(3) ["VY"]=> int(1) } [11]=> array(4) { ["X"]=> int(3) ["Y"]=> int(3) ["VX"]=> int(4) ["VY"]=> int(2) } [12]=> array(4) { ["X"]=> int(2) ["Y"]=> int(3) ["VX"]=> int(3) ["VY"]=> int(3) } [13]=> array(4) { ["X"]=> int(4) ["Y"]=> int(3) ["VX"]=> int(4) ["VY"]=> int(2) } [14]=> array(4) { ["X"]=> int(2) ["Y"]=> int(4) ["VX"]=> int(3) ["VY"]=> int(3) } [15]=> array(4) { ["X"]=> int(3) ["Y"]=> int(4) ["VX"]=> int(3) ["VY"]=> int(3) } [16]=> array(4) { ["X"]=> int(1) ["Y"]=> int(4) ["VX"]=> int(2) ["VY"]=> int(3) } [17]=> array(4) { ["X"]=> int(0) ["Y"]=> int(3) ["VX"]=> int(1) ["VY"]=> int(4) } [18]=> array(4) { ["X"]=> int(0) ["Y"]=> int(2) ["VX"]=> int(0) ["VY"]=> int(3) } } Und die Openlist: array(8) { [0]=> array(6) { ["X"]=> int(0) ["Y"]=> int(2) ["F"]=> float(9.0710678118655) ["G"]=> float(9.0710678118655) ["VX"]=> int(0) ["VY"]=> int(3) } [1]=> array(6) { ["X"]=> int(4) ["Y"]=> int(4) ["F"]=> float(9.3005630797458) ["G"]=> float(5.6568542494924) ["VX"]=> int(3) ["VY"]=> int(3) } [2]=> array(6) { ["X"]=> int(0) ["Y"]=> int(4) ["F"]=> float(9.6568542494924) ["G"]=> float(7.6568542494924) ["VX"]=> int(1) ["VY"]=> int(4) } [3]=> array(6) { ["X"]=> int(1) ["Y"]=> int(5) ["F"]=> float(10.233345472034) ["G"]=> float(7.0710678118655) ["VX"]=> int(2) ["VY"]=> int(4) } [4]=> array(6) { ["X"]=> int(2) ["Y"]=> int(5) ["F"]=> float(10.262405524956) ["G"]=> float(6.6568542494924) ["VX"]=> int(2) ["VY"]=> int(4) } [5]=> array(6) { ["X"]=> int(3) ["Y"]=> int(5) ["F"]=> float(10.485281374239) ["G"]=> float(7.0710678118655) ["VX"]=> int(2) ["VY"]=> int(4) } [6]=> array(6) { ["X"]=> int(0) ["Y"]=> int(5) ["F"]=> float(11.071067811865) ["G"]=> float(8.0710678118655) ["VX"]=> int(1) ["VY"]=> int(4) } [7]=> array(6) { ["X"]=> int(4) ["Y"]=> int(5) ["F"]=> float(11.656854249492) ["G"]=> float(6.6568542494924) ["VX"]=> int(3) ["VY"]=> int(4) } } Zur Erklärung: Die jenigen in der Closedlist, die nur 2 Einträge besitzen nämlich X und Y sind die Hindernisse die anderen sind die Felder die möglicherweise begangen werden könnten. Hier steht mit VX und VY jeweils der Vorgänger mit den X und Y Koordinaten. Ich fange einfach beim Ziel an und verfolge die Liste zurück, bis ich beim Start bin und habe den Weg. Hier nochmal das ganze für dich aufgemalt: http://www.5load.de/img_67932_koh.gif Und irgendwie kann das einfach nicht sein - wo mache ich den Fehler, denn das ist wirklich nur suboptimal. Bamba

Ich mal gerade den anderen Quellcode des Kampfsimulators angeguckt und mir überlegt wie man das ganze aufteilen könnte. Das heißt ich werde das ganze jetzt in kleinere Klassen aufteilen und besser verteilen. Dachte ich auch, aber starte mal mein Skript mit: $map = new astar(4,9); $map->main(4,0,0,2) und den Hindernissen: array_push($this->closedlist,array("X" => 1, "Y" => 2)); array_push($this->closedlist,array("X" => 1, "Y" => 3)); array_push($this->closedlist,array("X" => 2, "Y" => 2)); array_push($this->closedlist,array("X" => 3, "Y" => 2)); array_push($this->closedlist,array("X" => 2, "Y" => 0)); array_push($this->closedlist,array("X" => 2, "Y" => 1)); Normalerweise sollte er um diese Mauer rumgehen, allerdings läuft er direkt am Anfang einmal Zickzack, nämlich: Feld 0: 4,0 Feld 1: 3,1 Feld 2: 4,2 Feld 3: 3,3 Feld 4: 2,3 Feld 5: 1,4 Feld 6: 0,3 Feld 7: 0,2 (Debug Output von meinem astar.php). Schau dir die ersten 3 Felder an. Wäre er optimal müsste es doch 4,0 - 4,1 - 4,2 heißen und nicht 3,1. Kann mir das jemand erklären? Ich verwende A*, weil es ganz einfach derjenige war, den ich kannte. Eine zeitlang hab ich sogar einen eigenen Algorithmus hierfür entwickelt das ganze dann aber wieder verworfen. Ich denke das ist der bekannteste Algorithmus für soetwas und dann war es halt Zufall, dass ich ihn benutzt habe. Speicheraufwand? Hm, ja, das wird ein Problem aber ich glaube kaum, dass wir in Feldern mit 10.000 x 20.000 kämpfen werden. Also dürfte das noch machbar sein, wenn ich mir zum Debug die Openlist ausgeben lasse, ist sie bei 4 x 9 auch nicht so arg groß und bei 20x100, ist es auch noch überschaubar. Er findet nur einen kürzesten Weg? Na das macht doch nichts. Wie oben erwähnt werde ich das ganze in mehrere Klassen aufteilen die oberste Klasse wird dann die feindliche Kämpferliste durchgehen und für jeden den Weg berechnen von aktuelle Spielerfigur -> Feind, so dass ich eine Liste mit möglichen Wegen erhalten, deren kürzesten ich einfach nehme. So dürfte ja jeder Kämpfer in Echt in einer Schlacht auch denken. Problem gelöst. D* ist nicht optimal und wenn ich eines hasse, dann unzählige Exeptions festzulegen. Daher werde ich nicht auf D* ausweichen. Er ist nur suboptimal. Will heißen ich bleibe bei meinem derzeitigen Astar, werde das ganze noch in mehrere Klassen zwecks Übersichtlichkeit und Handling aufteilen und dann mit meinem bisherigen Simulator verschmelzen. Nun, ich habe mir diesen Aufbau der Openlist und der Closedlist aus mehreren Gründen so überlegt. Und ich habe eigentlich keine Lust das ganze Script umzubasteln, nur um dann eine kleine derartige Funktion inClosedlist() einzusparen und eine PHP-Standardfunktion verwenden zu können. Daher belasse ich es dabei. Es hätte bessere Wege gegeben aber was solls. Ich bin schließlich kein Profi. Wie oben erwähnt: Ich teile das ganze in mehrere Klassen auf und dann hat sich die Sache. Ich mache dann jetzt sofort weiter, nur kann mir bitte einer erklären was mit der Situation da oben ist, die nur suboptimal rechnet und warum und wie man das behebt? Kann ja sein, dass ich mich da gerade irre, aber ich glaube irgendwo müsste mir ein Fehler unterlaufen sein, sonst dürfte er einen derartigen Zickzackkurs nicht ausrechnen. Solwac schau doch noch mal. Bamba, der vorhat sämtliche M4 Regeln umzusetzen

Von mir erst mal ein paar kurze Anmerkungen... (Ist das die Portierung einer C-Version des Algorithmus? ) Die Methode inClosedList() durchsucht manuell das Array. Einer der wenigen Gründe, in PHP zu programmieren, ist der Wust von Array-Such- und Manipulationsfunktionen. Nimm lieber die, die sollten auch deutlich besser performen, wenn man nicht gerade einen Bytecodecompiler installiert hat. Natürlich muss dann die Datenstruktur ein wenig angepasst werden. Dazu passend der Konstruktor... besser wäre eine eigene Klasse, die das Spielfeld behandelt, dann kann man da auch über setter drauf zugreifen und muss dieses Gefummel mit array_push nicht weiter verfolgen. Ausserdem kann man dann auch gleich durch Anpassung der Spielfeldklasse das Problem mit den Kontrollbereichen erschlagen... Nein, ernsthaft: Strikt OOP-technisch kommst Du mit einer einzelnen Klasse wohl nicht aus. Hi, NEIN das ist keine Portierung einer C-Version, ich habe mir http://de.wikipedia.org/wiki/A*-Algorithmus genommen und das ganze in 2 Tagen frei runter programmiert. Funktioniert soweit ich das sehe relativ gut, ich will bloß sicher sein, dass es eine 100% Implementierung ist (An der Funktionstüchtigkeit nicht an der Geschwindigkeit gemessen). Vielen Dank für deine Anregungen, ich werde mal schauen was ich da noch drehen kann... Aber ich bin halt ein Hobbyprogrammierer und sonst nichts.

Hallo, ich hatte die letzten Wochen mit meinem Umzug nach Köln zutun und bin nicht zuviel gekommen. Da das ganze jetzt aber abgeschlossen ist, hatte ich Zeit mich die letzten Tage mal ausführlich mit dem A*-Algorithmus auseinander zusetzen. Ich habe es jetzt geschafft den A*-Algorithmus in PHP zu implementieren, was bedeutet, dass die automatisierte Wegfindung (Welche Optimal ist (Existiert ein Weg, wird er gefunden) - das ist mathematisch bewiesen) bereits funktioniert. Wenn ich mein astar.php also nun mit dem bisherigen Kampfsimulator zusammenschmeiße, kämpfen die Figuren nach den bisher umgesetzten Regeln und bewegen sich gleichzeitig realistisch auf einem Schachbrett. Hört sich erstmal gut an, oder? Bevor ich das zusammenfüge, werde ich aber meine astar.php erstmal ausführlich auf Fehler aller Art testen - schließlich bin ich nur Hobbyprogrammierer und bei mir kommt es öfter mal vor, dass sich ein Fehler einschleicht. Ich poste den PHP Quellcode hier einfach mal, da es hier einige gibt, die sich damit auskennen (Solwac war das glaube ich) und vllt. mit nach Fehlern suchen können. Erst wenn wir uns alle sicher sind, dass meine astar.php Fehlerfrei ist, füge ich sie mit dem bisherigen Kampfsimulator zusammen. Bamba Quellcode von astar.php: (Bitte bedenkt, dass das ganze noch nicht ausgereift ist, ich werde noch 'ne Menge ändern. Professionelle Programmierer würden von einer Beta-Version sprechen) <?php error_reporting(E_ALL); class astar { private $x; private $y; private $openlist = array(); private $closedlist = array(); private $tx; private $ty; public function __construct($x,$y) { // Zu übergebende Werte: $x = Anzahl Felder auf der X-Achse, // $y = Anzahl Felder auf der Y-Achse, Hindernisse // WICHTIG: IRGENDWIE NOCH DIE HINDERNISSE IN DIE CONSTRUCT FUNC EINBAUEN $this->x = $x; $this->y = $y; // Hier Hindernisse manuell einfügen, solange das noch nicht über die Construct Funktion geregelt wird array_push($this->closedlist,array("X" => 1, "Y" => 2)); array_push($this->closedlist,array("X" => 1, "Y" => 3)); array_push($this->closedlist,array("X" => 2, "Y" => 2)); array_push($this->closedlist,array("X" => 3, "Y" => 2)); } public function main($x,$y,$tx,$ty) { // Berechnet den Weg vom Start zum Zielnode // X = X-Koordinate, Y = Y-Koordinate // G = Bisherige Wegkosten // C = Kosten Vorgängernode -> currentNode // H = Geschätzte Restkosten (Luftlinien Heuristik) // F = Gesamtkosten // Vorbelegungen $Start = array(); $Start["X"] = $x; $Start["Y"] = $y; $Start["G"] = 0; $Start["VX"] = -1; $Start["VY"] = -1; $this->tx = $tx; $this->ty = $ty; // Ganz zu Anfang des Skriptes den Startnode in die Openlist einfügen array_push($this->openlist,$Start); do { // Die Openlist nach dem niedrigstem F-Wert sortieren usort($this->openlist,'Compare'); // Wenn der Aktuelle Node gleich dem Zielnode ist -> Weg gefunden $ActualNode = array("X" => $this->openlist[0]["X"],"Y" => $this->openlist[0]["Y"],"VX" => $this->openlist[0]["VX"],"VY" => $this->openlist[0]["VY"]); if($ActualNode["X"] == $this->tx && $ActualNode["Y"] == $this->ty) { array_push($this->closedlist,$ActualNode); $this->getWay(); die("PATHFOUND"); } else { // Wenn nicht, wird vom Punkt mit dem niedrigstem F-Wert weitergesucht $this->expandNode($ActualNode["X"],$ActualNode["Y"]); // Den fertig untersuchen Node auf die Closedlist setzen und aus der Openlist löschen array_push($this->closedlist,$ActualNode); unset($this->openlist[0]); } } // Bis die Openlist leer ist while(!empty($this->openlist)); // Ist die Openlist leer und es wurde nicht abgebrochen, existiert kein Weg die("ES GIBT KEINEN WEG"); } private function expandNode($x,$y) { // Expandiert den Node $i=0; $Successor = array(); $Successors = $this->getSuccessors($x,$y); foreach($Successors as $Index => $Current) { // Geht jeden Nachfolgenode einzeln durch array_push($Successor,$Current); if($i%2 != 0) { // Tritt nur jedes zweite mal in Kraft da immer erst BEIDE // Werte (X und Y Koordinate) $Successor hinzugefügt werden müssen // Überprüft, ob $Successor in der Closedlist ist $Inside = $this->inClosedList($Successor); if($Inside == TRUE) { // Wenn $Successor innerhalb der Closedlist ist, mache nichts außer $Successor zu leeren $Successor = array(); $i++; continue; } else { // F Wert von $Successor berechnen $g = 0; foreach($this->openlist as $Key) { // Holt den G Wert vom aktuellen Node if($x == $Key["X"] && $y == $Key["Y"]) { $g = $Key["G"]; break; } } switch($Index) { // Berechnet den C Wert zwischen aktuellem Node und Successor case "ol_y": $c = sqrt(2); break; case "om_y": $c = 1; break; case "or_y": $c = sqrt(2); break; case "ml_y": $c = 1; break; case "mr_y": $c = 1; break; case "ul_y": $c = sqrt(2); break; case "um_y": $c = 1; break; case "ur_y": $c = sqrt(2); break; } // Berechnet H Wert des Successors $XDifference = $Successor[0] - $this->tx; if($XDifference < 0) { $XDifference *= -1; } $YDifference = $Successor[1] - $this->ty; if($YDifference < 0) { $YDifference *= -1; } $h = sqrt($XDifference * $XDifference + $YDifference * $YDifference); // G, C und H Wert werden zum F Wert addiert $f = $g + $c + $h; $Exit = FALSE; for($n=0;$n<count($this->openlist);$n++) { if($Successor[0] == $this->openlist[$n]["X"] && $Successor[1] == $this->openlist[$n]["Y"]) { if($f > $this->openlist[$n]["F"]) { // Wenn Successor in der Openlist ist und der neue F Wert größer als // der alte F Wert ist, tue nichts $Exit = TRUE; } else { // Wenn Successor in der Openlist ist und der neue F Wert nicht größer als der // alte ist, den F Wert in der Openlist aktualisieren $this->openlist[$n]["F"] = $f; $Exit = TRUE; } break; } } if($Exit) { // Wenn der Successor bereits in der Openlist war und der F Wert falls nötig // aktualisiert wurde, $Successor leeren, $i inkrementieren und den Rest // des Schleifendurclaufes überspringen $Successor = array(); $i++; continue; } // War der Successor garnicht in der Openlist, füge ihn hinzu $NewNode = array("X" => $Successor[0],"Y" => $Successor[1],"F" => $f,"G" => ($g + $c),"VX" => $x,"VY" => $y); array_push($this->openlist,$NewNode); } // $Successor leeren, damit sich keine Werte überschneiden $Successor = array(); } $i++; } } private function getSuccessors($x,$y) { // Bestimmt alle Umgebungsnodes von $x,$y $Successors = array(); if(($x - 1 >= 0) && ($y + 1 <= $this->y)) { $Successors["ol_x"] = $x - 1; $Successors["ol_y"] = $y + 1; } if($y + 1 <= $this->y) { $Successors["om_x"] = $x; $Successors["om_y"] = $y + 1; } if(($x + 1 <= $this->x) && ($y + 1 <= $this->y)) { $Successors["or_x"] = $x + 1; $Successors["or_y"] = $y + 1; } if($x - 1 >= 0) { $Successors["ml_x"] = $x - 1; $Successors["ml_y"] = $y; } if($x + 1 <= $this->x) { $Successors["mr_x"] = $x + 1; $Successors["mr_y"] = $y; } if(($x - 1 >= 0) && ($y - 1 >= 0)) { $Successors["ul_x"] = $x - 1; $Successors["ul_y"] = $y - 1; } if($y - 1 >= 0) { $Successors["um_x"] = $x; $Successors["um_y"] = $y - 1; } if(($x + 1 <= $this->x) && ($y - 1 >= 0)) { $Successors["ur_x"] = $x + 1; $Successors["ur_y"] = $y - 1; } return $Successors; } private function inClosedlist($Successor) { // Überprüft, ob $Successor in der Closedlist vertreten ist $Inside = FALSE; for($j=0;$j<count($this->closedlist);$j++) { if($Successor[0] == $this->closedlist[$j]["X"] && $Successor[1] == $this->closedlist[$j]["Y"]) { $Inside = TRUE; } } return $Inside; } private function getWay() { // Berechnet aus $Closedlist den wirklichen Weg $Way = array(); array_push($Way,end($this->closedlist)); $Last = end($Way); do { foreach($this->closedlist as $Key) { if($Key["X"] == $Last["VX"] && $Key["Y"] == $Last["VY"]) { array_push($Way,$Key); break; } } $Last = end($Way); } while($Last["VX"] != -1 && $Last["VY"] != -1); $Way = array_reverse($Way); for($i=0;$i<count($Way);$i++) { echo "Feld $i: " . $Way[$i]["X"] . "," . $Way[$i]["Y"] . "<br>"; } return $Way; } } function Compare($first, $second) { if($first['F'] < $second['F']) return -1; else if($first['F'] > $second['F']) return 1; else return 0; } $map = new astar(4,9); $map->main(1,0,2,3) ?>

So, ich arbeite jetzt an Version 2.0 mit einem Positionssystem und dem implementiertem A* Algorithmus zur automatisierten Wegfindung. Das ganze wird ein wenig dauern. Bitte habt Geduld. Bamba

Das ist definitiv KEIN Fehler. Es läuft folgendermaßen ab: Kämpfer a greift Kämpfer x an und bringt die AP von Kämpfer x auf 0, wodurch er wehrlos ist und alle, die Kämpfer X angreifen nun +4 auf den EW:Angriff erhalten. Der Interne Wert im Programm für die AP von Kämpfer X ist nun 0. Jetzt greift Kämpfer B Kämpfer X an. Hierbei erhält er schon +4. Dann wird es auch angezeigt, da es jetzt ja relevant ist, greift keiner Kämpfer X an, steht da auch nicht "...erzählt +4 beim Angriff auf X...", weil es nicht relevant ist. => Kein Fehler! Hmm, ich hab hier keine Regelbücher, kann mal jemand nachgucken und mir sagen, ob man ne gewürfelte 20 auch nur mit ner gewürfelten 20 abwehren kann? Wenn das so ist, ist das ein Fehler, stimmt. Kann ich aber erst hinzufügen, wenn kritische Erfolge eingeführt werden. Es wird in beiden Fällen addiert, wurde meines Wissens nach doch im Schwampf geklärt? Wenn beides addiert wird, ist das ebenfalls kein Fehler! Falls ich falsch liegen sollte, klärt mich bitte auf. Trotzdem Danke fürs suchen. Bamba

Hi, ich hab jetzt ein bisschen länger gebraucht, da das ganze nun arg an die Grenze meines Könnens geht. Version 1.4 hat zwei neue Funktionen: Man kann einmal eingegebene Kämpfer mit einem Mausklick auf andere Kämpfer übertragen, außerdem gibt es den so genannten Rundenkampf, in dem jede Runde einzeln berechnet wird und man am Ende jeder Runde die Werte ändern kann. Weiter Updates in Kürze. ACHTUNG: Der Link hat sich geändert: http://php-learner.piranho.de/MidWar/home.htm Ich hab mal alle verschiedenen Versionen hochgeladen. Features von V1.4: - Angreifen - Abwehren - Abwehren nicht erlaubt wenn Verteidiger 0 AP hat - Schadenkalkulation - Kampfunfähig ab 3 LP - Rüstung - Nicht unter 0 AP erlaubt - Minus 2 auf Angriffe bei wenn Angreifer LP/2 hat - Minus 4 auf Angriffe bei wenn Angreifer 0 AP hat - Plus 4 auf Angriff, wenn Verteidiger 0 AP hat - Anzeige wer gestorben / Kampfunfähig ist - Namensgebung möglich - Zufällige Gegnerwahl - Kampfinformationen ausschaltbar - Rundenanzeige - Statistikkampf - Inputüberprüfung - Standardbelegungen für Kämpfer - Rundenkampf Bitte fleißig Fehler suchen! Bamba

Danke. Wer sich XAMPP installiert, kann auch den Quellcode von mir bekommen, so dass er MidWar lokal auf seinem Rechner auch ausführen kann, was dann die Execution Time Dauer auf 60 Sekunden anhebt, bzw. manuell noch weiter angehoben werden kann. Bamba

So, nach stundenlangem Suchen, habe ich endlich den Fehler ausfindig machen können. Jetzt dürfte der Simulator in der Version 1.3.2 fehlerfrei laufen. Funktionen an sich wurden im Vergleich zur Version 1.3.1 allerdings nicht hinzugefügt. Daher sind diese weiterhin: - Angreifen - Abwehren - Abwehren nicht erlaubt wenn Verteidiger 0 AP hat - Schadenkalkulation - Kampfunfähig ab 3 LP - Rüstung - Nicht unter 0 AP erlaubt - Minus 2 auf Angriffe bei wenn Angreifer LP/2 hat - Minus 4 auf Angriffe bei wenn Angreifer 0 AP hat - Plus 4 auf Angriff, wenn Verteidiger 0 AP hat - Anzeige wer gestorben / Kampfunfähig ist - Namensgebung möglich - Zufällige Gegnerwahl - Kampfinformationen ausschaltbar - Rundenanzeige - Statistikkampf - Inputüberprüfung - Standardbelegungen für Kämpfer Link: http://php-learner.piranho.de/MidWar/insert.php Ich habe die Statistikkampfberechnung von 1000 auf 100 Durchläufe vermindert, da es Rechenzeit spart. Ich habe zwar einige Optimierungen vorgenommen, allerdings reicht das alles nicht und da wir bei piranho nur eine Execution Time von 10 Sekunden haben (Normal ist 60), muss ich das runter drehen. Kennt jemand von euchen einen Freehoster mit PHP, der eine höhere Execution Time hat? Bzw. kann ich das Script bei jemandem von euch hosten, dessen Execution Time größer ist? Neue Funktionen kommen erst wieder in der nächsten Version. Auf meiner Todo Liste steht jetzt: - Individuelle Angaben für jedes Team (Team X ist neutral zu Team Y, Team Z zu Team A, etc.) - Individuelle Angaben für jeden Kämpfer, ob er mit 0 AP, LP/2, AP/2 etc. weiterkämpft - Kritische Erfolge und Auswirkungen - Schild - Rassenzpezifische Sachen (Wesen, die mit 1W6 gewürfelt werden, sind mit 0 LP noch Handlungsfähig) - Moralwert - Spezialaufgaben für jeden Kämpfer (Anführer, Beschützen, etc.) - Man darf nicht mehr als die Hälfte der AP haben, wenn man weniger als die Hälfte aller LP hat - Handlungsrang - Statusfeld um "aufgegeben" erweitern - Kopierfunktion für bereits eingegebene Kämpfer - Teams farbig unterscheiden Später: - Mit Positionen rechnen - Gegner anhand von Positionen suchen - Man darf nicht von mehr als 4 Gegnern gleichzeitig angegriffen werden Bamba (Bitte Fehler suchen, kann ja sein, dass ich immer noch was übersehen habe)

Ich habe hier keine Midgard Bücher in Reichweite, bitte einmal aufzählen was diese bringen. Auch bei der Verwendung eines Positionssystems ist es möglich dass man mehrere Gegner zur Auswahl hat. Ja, und erst NACHDEM der A* Algorithmus einen oder mehrere Ziele, also SEKUNDÄR, gefunden hat, wird der Zufall eingesetzt. Du meinst in der grauen Box "Kampfinformationen" sollen die Kämpfer eines Teams farbig markiert werden? Also Team X blau und Team Y rot? Bamba

Ich bitte alle Leute die Fehler finden: 1. den Textoutput, der den Fehler beinhaltet 2. die Werteingaben, die zu dem Fehler geführt haben zu posten. Anders kann ich die Fehler nicht reproduzieren und untersuchen. Bamba

Also dieser Fatal Error ist kein Error, sondern einfach der Abbruch des Kampfes, da die zulässige Berechnungszeit überschritten wurde. Nähmlich 10 Sekunden Was du da eingegeben hast (50 Kämpfer) ist eine große Anzahl und dementsprechend rechenintensiv. Stell dir vor du berechnest einen Kampf mit 50 Kämpfer, dieser dauert bei meinem Simulator zwischen 20 und 40 Runden im Surchschnitt bei den Standardwerten, die Anfangs eingestellt sind. Für jeden Kämpfer werden derzeit pro Runde um die 1000 Berechnungen ausgeführt. 50*30*1000 = 1,5 mio Berechnungen für den einen Kampf. Beim Statistikkampf wird die ganze Begebenheit 1000mal durchgerechnet. Also sind wir schon bei 1,5mia Berechnungen. Ich werde das daher nun auf 100 Durchläufe minimieren müssen und einen anderen Freeserver suchen, der eine längere execution Time erlaubt. Nein, ich werde derzeit nicht daran arbeiten, dass ein einmal ausgesuchter Gegner bis zur Vernichtung attackiert wird, da sich das Problem von selbst behebt, ist einmal das Positionssysthem integriert. Ja ist möglich und werde ich in der nächsten Version auch einbauen. Ja, ich weiß beim Statistikkampf läuft derzeit noch nicht alles Rund. Erstellt mal 2 Teams von denen jeder Kämpfer 1W6-4 Schaden hat. aus unerfindlichen Gründen passiert dann etwas ähnliches was du angesprochen hast. Ich suche derzeit noch nach der Ursache. Allgemein muss ich noch einige Sachen im Statistikkampf ändern, um ein wenig Performance herauszukitzeln, da das ganze mittlerweile schon arg Rechenintensiv geworden ist. Verbesserungen folgen in Kürze. Bamba