Weg Berechnung / Karte / Meer / Browsergame

[Eclypse]

Zu der Variante mit Astar: Ich versuche mal die Maze so klein wie möglich zu bekommen und schaue ob die ungenauigkeiten sich irgendwie herausarbeiten lassen. Ein weiteres problem bleibt dann auch die Rechenzeit mit Astar. Pro route die berechnet wird muss eine halbe sekunde Rechenzeit eingerechnet werden. Bei komplizierteren/längeren strecken möglicherweise auch eine ganze sekunde. Wenn dann 5 user gleichzeitig eine route berechnen wollen entsteht für alle eine extrem lange wartezeit. Vor allem wenn man bedenkt das der server ja nicht nur damit beschäftigt ist, wie newwarrior das schon erwähnt hatte. Eine 5 sekunden pause+die arbeit die in der zeit sonst noch anfällt wäre prinzipiell nicht akzeptabel. Was tun wir dann wenn mal richtig viel los ist? :/

Hierzu habe ich mir überlegt wie ich die Rechenzeit reduzieren kann. Ich habe mir die Weltkarte genommen und straßen gezeichnet. Dann alles andere gelöscht und lasse die Straßen jetzt als mögliche wege von Astar berechnen. In meinem Beispiel mit ca 50 schritten komme ich hierbei von 0,667 sec auf 0,22 sec. Eine verbesserung also. Die Maze besteht also nur noch aus "W"s. Mit ausnahme der bereiche in denen gefahren werden darf. Das reduziert die möglichkeiten und damit die Rechenzeit. Sieht jemand ein problem darin das so zu machen?





Zu der Variante mit vordefinierten routen: Angenommen ich lasse die position der dampfer auf der Karte nicht anzeigen sondern führe nur das "battle script" aus sobald die schiffe ankommen brauche ich nur eine "traveltime". Die könnte ich von ort zu ort auch in einer DB abspeichern.

Abgesehen davon das es wahnsinnig viele einträge sind, ist mir nicht ganz klar ob die Auslastung des sql servers hier nicht dem ganzen einen riegel vorschiebt.

Angenommen: Möglich sind ca 200 häfen weltweit. Von 200 häfen zu 199 anderen Häfen routen vorzudefinieren bedeutet 40000 routen.

Selecten müsste ich alle routen VON hafen x. In diesem falle selecte ich 1 aus 40000. Wie lange würde eine solche operation dauern?
Ich könnte mir vorstellen das auch hier wieder newwarriors argument zieht das der SQL server in diesem moment in die knie geht. Hat da jemand einen anhalt wie lange soetwas dauern würde?

Eine alternative ist natürlich einen "ROUTEN-SERVER" einzurichten der sich nur damit beschäftigt, sodass andere operationen weiterlaufen können.


cba r-correction

Gruß Eclypse

 

[ZodiacXP]

Hab das hier alles mal schnell überflogen.

Achtet mir bitte n bisschen auf den Realismus
Die Karte von chmee ist nur ein Beispiel. Die Karten unten und oben müssten noch gespiegelt werden sonst sinds von Feuerland nach Grönland nur wenige km .
Zudem fällt die Erdkrümmung weg, was sich aber bestimmt ausbügeln lässt.

Was mich zu Anfang viel mehr gestört hat war, das ihr fleißig durch die Polarkappen schippert Da müsst noch ein nicht begehbarer Fleck hin.

 

[AperfectCircle]

Hallo ZodiacXP,

ja das habe ich mir schon gedacht. Selbstverständlich werden die Karten gespiegelt die Polarkappen unbefahrbar gemacht etc. Leider mangelt es hier im moment noch an ganz elementaren dingen die Rechenleistung überhaupt ^^.

Die Realisierung der Karte etc wird kein Problem sein wenn das Prinzip ersteinmal funktioniert ^^

 

[chmee]

Map falsch : Oh Je +schäm+ natürlich ABER bitte auch daran denken, die gespiegelte Map um 50% zu verschieben, denn aus Feuerland über den Südpol landet man im indischen Ozean, nicht wieder in Südamerika (wenn da nicht grad die Antarktis dazwischen wäre )

Möglich sind ca 200 häfen weltweit. Von 200 häfen zu 199 anderen Häfen routen vorzudefinieren bedeutet 40000 routen.

Ist meines Erachtens nur knapp die Hälfte, aber das ist immer noch ne Menge. Du hast scheinbar gerechnet 200*200, aber richtig müsste -glaub ich- (199 über 2) sein. Aufgabe 13 ist analog - Die Strecke Rio-NewYork entspricht auch NewYork-Rio). Kleine Pedantierie meinerseits

Aber : Wenn die Orte statisch sind, dann ist doch A-Star unnötig ressourcenaufwendig, dann muss eben eine DB-Tabelle her (und wenn es 20.000 Einträge sind.) A-Star macht doch nur Sinn, wenn dynamische Objekte (2 Schiffe zB) den Weg zueinander finden sollen. Oder wenn ein Schiff auch auf hoher See stehen bleiben kann (wenn also der Startpunkt und/oder Endpunkt über die ganze Map variabel ist). Dann sitzt man eben (zB mit Hilfe von AStar) ein Wochenende und lässt sich die Tabelle generieren, beim Zugriff im Spiel ist es dann aber pfeilschnell und es kostet Dich lediglich 0,02s anstatt 0,5s pro Spieler/Spielzug.

mfg chmee

 

[ZodiacXP]

Divide and Conquer wird doch immer so hoch gelobt.

Bei sowas wäre das erst eine Karte mit niedrigerer Auflösung (dünne Wege müssen nachträglich im Bild freigelegt werden).
Darauf lässt man eine Route berechnen und überträgt das auf die Karte mit der großen Auflösung.

Ich mach das hier mal als Bild in 3 Schritten, vielleicht liefert das etwas Performance. Bin mir sogar sicher, weil nicht mehr über die ganze Karte iteriert wird, sondern nur noch innerhalb von definierbaren Bereichen.
Schaut mal ob sowas möglich ist. Vom Original über die Vereinfachungen zum Pfad:

 

[AperfectCircle]

@ZodiakXp: Ja genau das war schon der anfangsplan. Einfach eine kleinere Maze zu erstellen und die auf das große coordination grid anzupassen. Ich zweifle bisher noch daran ob sich das so genau lösen lässt.

Die einzig akzeptable Maze hätte eine größe von 5% der ursprünglichen karte. Gedacht ist eine Source Karte (und damit auch ein grid) von 2800x1600px.

AStar akzeptiert Mazes in dieser größe nicht, wie oben bereits beklagt.

Eine entsprechende verkleinerung auf 10% der größe (also 280px in der Breite) wäre bereits zu groß. Nochmals die hälfte, also 5% der Ursprünglichen größe akzeptiert maze also verarbeitungsgröße.

Wenn ich ganz simpel die karte auf 5% verkleinere und eine Maze daraus mache ist die frage ob sie sich immernoch auf die große karte anpassen lässt. Schließlich ist die karte deutlich kleiner und ungenauer. Da ich gezwungen bin an die landmassen heranzufahren muss ich hier im zweifelsfall stark nacharbeiten und in der maze das Land an den stellen wo die häfen sind ausradieren. Aber möglich wäre diese methode natürlich.

Es verbleibt nur noch die etwas höhere berechnungszeit, die wie bereits erwähnt bei dieser größe bei mindestens 0,5 sec liegt. Die Maze noch mehr zu verkleinern halte ich für nicht realisierbar da die navigation auf der Ursprungskarte dann ja noch ungenauer wird.

Aber da du die möglichkeit mit der kleineren Karte in betracht ziehst mache ich mir die mühe mal und teste aus ob ich die 5% maze verwenden kann. Ich denke obs funktioniert oder nicht kann hier nur der praxistest zeigen.







@chmee: Natürlich sinds nur 20000. Auch ich hatte erstmal nur im Kopf überschlagen und den von dir genannten punkt ganz vergessen ^^

Du hälst es für möglich die Routen aus der Sql tabelle zu rufen? 20000 einträge durchzusuchen ist meiner Meinung nach ziemlich viel. Mich haben meine überlegungen aber auch schon in folgende richtung getrieben: Ich sortiere einfach die routen nach stützpunkten. Dann müssen nicht alle in eine tabelle und php kann vorselecten.

Beispiel: Ich suche eine route von Stützpunkt 1-50 nach Stützpunkt x, schaue ich table_1. Auf diese weise werdens schonmal nurnoch 10 000 datensätze die durchsucht werden müssen, und das beispiel lässt sich ja noch ein bisschen weiterspinnen.

Es bleibt die problematik das die Ziele alle statisch sein müssen. Das wird zwar OFT der fall sein, allerdings planmäßig nicht immer.

Ich überlege also gerade eine Kombination aus beidem zu machen.

case: postion = hafen ->suche in table
case: positon != hafen-> astar();

Dafür muss ich aber erstmal die Maze zum laufen bringen und schauen ob die 5% Maze auf die große karte (ungenauigkeitsbedingt) anwendbar ist.

Daran arbeite ich mal

cba r-correction

Eclypse of A perfect circle

 

[chmee]

20000 einträge durchzusuchen ist meiner Meinung nach ziemlich viel.

Die Abfrage ist ja recht simpel und in meiner DB (dslr Kleinanzeigen) sind auch knapp über 20.000 Einträge drin. Ich frage auf Stringbasis mit LIKE ab, das sicherlich sehr viel langsamer ist als die Abfrage über indizierte Pos.Pos-Abfrage, Also nur ein Eintrag mit zB 1.199, welchen die Fahrt von Hafen 1 zu 199 (und 199 zu 1) beschriebt. Das sollte schneller gehen.

Aber : Da ich nicht in Deinem Game stecke, wirst Du am Besten wissen, welche Codingstrategie die Bessere sein wird, ergo gebe ich nur Tipps, will auf keinen Fall als Besserwisser verschrien sein.

mfg chmee

 

[ZodiacXP]

Achso. Ich hatte es so gedacht, das man durch Grobstruktur einen Pfad mit einer machbaren Umgebung vorgibt und schrittweise das Raster verfeinert. Dadurch nähert sich der Pfad dem insgesamt Optimalen an und durch die immer feinere Struktur wird die um den Pfad Umgebung auch immer kleiner, was A* wieder packen könnte.

 

[AperfectCircle]

@chmee: Leider fehlen mir erfahrungswerte in dieser größe. War auch zu faul das einfach mal zu testen indem ich meine db mit 20000 datensätzen füttere. Aber wenn du sagst das das kein problem darstellt glaube ich das gerne. Ist auch gut vorstellbar, wenn man bedenkt das die SuFu hier im Forum sicher deutlich arbeitsintensivere Aufträge bekommt, und auch in der Lage ist den Auftrag zu bewältigen.

@ZodiakXp: ja die grobstruktur lege ich ja mit der kleinen Maze an. soweit klar.

Jetzt begreife ich erst was du vorhast. Du planst den bereich einzugrenzen in dem Astar arbeitet. Also quasi eine interaktiv erstellende maze?

Eine groß angelegte Karte aus der immer nur der teilbereich als maze erstellt wird der gerade gebraucht wird, um aus dieser Maze dann den Weg zu berechnen? Die idee erscheint fürs erste genial. Die rechendauer um aus einer Karte eine Maze zu erstellen ist lächerlich gering, erst recht wenn man fürs erste im groben Raster arbeiten kann.

Auf der Idee muss ich mal herumdenken.

 

[AperfectCircle]

Hallo zusammen,

ich bin mittlerweile soweit das ich die Karte in einem Javsscript darstelle das ich auf 5% verkleinert habe. Dieses benutze ich mit AStar um die Wegberechnung zu machen. Die Rechenzeit liegt hier abhängig von der länge der Route knapp unter einer Sekunde die ich aber akzeptiere. Im notfall lagere ich die Berechnung der routen auf einen zweitserver aus.

Ein anderes Problem stellt sich mit aber leider immernoch. Zwar haben wir es schon angesprochen aber eine funktionierende Lösung habe ich noch nicht gefunden.

Und zwar dreht es sich darum das der User nicht über den linken Kartenrand hinaus auf dem rechten Kartenrand wieder auftaucht. Wir haben zwar hier die möglichkeit in der Maze einfach die Weltkarte neu anzufügen, jedoch ist de facto der Punkt 20 Pixel neben den Linken kartenrand NICHT gleich mit dem 20 Pixel vor dem Rechten. Auch wenn Maze technisch diese Punkte gleich aussehen.

Das Problem ist: Wenn der User zu einem Punkt auf der Karte möchte, klickt er diesen Punkt an. Die Maze wird dann den weg über die gesamte Karte berechnen. Nicht über den Kartenrand.

Ich überlege und überlege aber mir fällt nichts ein wie ich das lösen könnte. Es wäre kein problem den User wenn er sich auf Position -20 befindet auf die Korrekte Position zu setzen. Aber der Weg den er erstmal nimmt dauert trotzdem länger als notwendig.

Jemand eine Idee?

Gruß Eclypse