# Weg Berechnung / Karte / Meer / Browsergame



## newwarrior (26. Januar 2010)

Moin,

ich würde gerne mit einem Kollegen ein Browsergame programmieren.
Zur Zeit sind wir an der Planung und Erstellung unseres Konzeptes.
Des weiteren, versuchen wir zur Zeit schon die meisten Fragen oder Problemzonen später im Game zu klären.

Doch bei einer kleinen Sachen geraten wir ziemlich an unsere Grenzen.
Und zwar haben wir eine Karte, wie diese zum Beispiel:

http://www.webresourcesdepot.com/wp-content/uploads/image/free-vector-world-map.gif

So, jetzt soll das Schiff, von Amerika nach Asien fahen.
Kein Probelm, eigentlich doch unser script nimmt den direkten weg und fährt über Afrika.

Unsere Frage ist jetzt, wie können wir es so machen, (arbeiten mti imagecreate()), dass ein Schiff bestimmte Punkte in der Karte nicht befahren darf.
Achja, je Pixel des Bildes eine Seemeile.
Wir haben schon überlegt ejden Pixel der eine Landmasse ist in die DB einzutragen und dann bei der Berechnung des Weges zu prüfen ob da Land ist.
Aber das ist eine unglaubliche Datenmenge in der DB und auch eine unglaubliche Rechenleistung jedes mal.

Gibt es da vielleicht einen anderen Weg?

Danke


----------



## Thomasio (26. Januar 2010)

Da gibt es nur 2 Möglichkeiten.
Entweder das Programm rechnet sich den Weg selber aus, was bedeutet, ihr müsst Land als Land definieren und mitberechnen (wobei es aber reicht nur die Umrisse vom Land zu definieren), oder ihr müsst von jedem möglichen Ausgangspunkt zu jedem möglichen Endpunkt die Route fest definieren.


----------



## Marius Heil (26. Januar 2010)

Falls ihr es dann wirklich mit Wegberechnung machen solltet gibt es einige gute Wegfindungsalgorithmen, zB könnt ihr da nach A* (A star) suchen, dazu brauchts allerdings eine Map von Begehbaren und nicht begehbaren Pixeln.

Hier wäre ne PHP implementation: http://codezilla.com/projects/a-star/
Oder aber du lagerst das gnaze am besten zum Benutzer aus und nimmst ne JavaScript implementation, dann habt ihr keine Rechenarbeit damit.


----------



## newwarrior (27. Januar 2010)

moin,

gibt es vielleicht ein Programm oder sonst eine Möglichkeit ein Bild (png, jpg) in ein Maze umzuwandeln?

Danke


----------



## chmee (27. Januar 2010)

Wurde schon genannt  *a-Star*! (oh,Antwort zur ersten Frage )

mfg chmee


----------



## newwarrior (27. Januar 2010)

ja, aber da gibt es nicht die möglichkeit ein Bild in ein Maze umzuwandeln, die Datei muss bereits ein Maze sein


----------



## holzmensch (27. Januar 2010)

Hi,
schreib dir doch selber eine Funktion, so schwer ist das eig nicht (wenn die Karte zweifarbig ist). Überprüfst jeden Pixel, speicherst die Koordinaten davon sowie die "Begehbarkeit", indem du die Farbe überprüfst. Fertisch!


----------



## chmee (27. Januar 2010)

Ein Maze kann man doch selbst erstellen.. Erstmal würde ich die Weltkarte kleiner skalieren (Du brauchst ja nicht jedes Pixel zur Wegfindung, das Raster vergröbern, heisst auch ->schneller berechnen und kleinere Datenmenge bei viel gröberem Raster)

zB
Angenommen : Diese Karte
In Photoshop verkleinert (auf 12,5%) und auf das wichtige Schwarz/weiss herbgesetzt.
Also Rastermaß 1427px*628px auf 179*79 herabgesetzt und trotzdem genug Daten (denk ich), um ein Schiff loszuschicken.



Dieses mit php und gdlib auslesen und das Maze generieren, welcher Form auch immer..Feddich, der Lack 

edit: http://www.policyalmanac.org/games/aStarTutorial_de.html

mfg chmee


----------



## saftmeister (27. Januar 2010)

Dijkstra ist auch eine Möglichkeit. Aber auch da braucht man Wegpunkte (Maze).


----------



## Marius Heil (27. Januar 2010)

@saftmeisster: Dijkstra ist genaugenommen das gleiche wie A*, nur dass mit einem unbekannten Ziel gesucht wird indem man die verbleibenden Wekosten auf 0 schätzt. Das ist praktisch wenn die Walzen wie bei Command und Conquer zB nach Tiberium suchen aber das erst finden müssen. (Zumindest hab ich das so aus chmees sehr hilfreichem Link zu einem super Artikel rausgelesen ;-)


----------



## Eclypse (16. Februar 2010)

Hallo erstmal,

mit Mazes zu arbeiten klingt hier zwar sehr gut, die Maze Karte in einem gröberen Raster zu halten auch. 

Ein Problem sehe ich hier allerdings noch: Eine Karte hat immer einen Anfang und ein Ende. Die Welt ist allerdings rund.

Wie verhindere ich das AStar den Weg über die ganze Karte berechnet, wenn es doch einfach über den linken Rand hinausfahren kann und beim rechten wieder rausfahren könnte.  Ich hab in der Dokumentation von Astar hierzu nichts gefunden. Kann mir da jemand weiterhelfen?

Gruß Pinky


----------



## chmee (16. Februar 2010)

Die einfachste Variante wäre es, sich die Karte mehrmals zusammenzulegen (9xWorldmap, um genau zu sein), so hat man in jede Richtung den optimalen Weg. Die Karte würde von den Ausmaßen doppelt so groß werden (habe den Teil ausgegraut, der mM keine Verbesserung bringt). Man muss dann eben nur bei der Anzeigeumsetzung darauf achten, dass die Koordinaten passen, quasi ein Modulo am Map-Rand (blau umrahmt, alte Map).




mfg chmee


----------



## Eclypse (16. Februar 2010)

Hallo,

danke für die schnelle Antwort. Ja daran habe ich auch schon gedacht. Mein Problem war die transferleistung der Koordinaten.

Angezeigt bekomme ich ja immer nur die aktuelle Karte. Wenn ich mich am linken Rand der Karte befinde und zum rechten Rand möchte übergebe ich als Zielort die Koordinaten des rechten Randes. Dorthin werde ich dann auch einmal quer über die ganze Welt navigiert.

Klar kann ich mithilfe der 9xWorldscales die "Wegberechnung" korrekt machen, lande auch an einem Punkt der exakt dem Punkt am Rechten Kartenrand entspricht, der aber de facto nicht den Koordinaten des Rechten Randes entspricht. Der Weg der gefahren wird wäre also Praktikabel. Der Ankunftsort aber nicht der gewünschte sondern ein zweiter, wenn auch Physisch gleicher.

Das Problem ist hier nicht die koordinaten im nachhinein umzurechnen. In der Theorie wäre es ohne Probleme möglich den Ankunftsort nach dem ankommen auf die korrekten Koordinaten zu setzen.


Das Problem ist die Zielführung. Da der User bei der Zieleingabe auf die Koordinaten am RECHTEN Bildschirmrand klickt und nicht auf die (physisch gleichen) Koordinaten neben dem linken Rand wird der User immer den langen Weg fahren. :/


Ich hoffe ich konnte das Problem verständlich erläutern ^^

Die einzige möglichkeit das Problem zu beheben sehe ich im moment darin die "künstliche" maze umgebung außerhalb der eigentlichen Karte mit "doppelten" Koordinaten auszustatten. Den "eigentlichen" und denen die sie in der eigentlichen Map entsprechen würden. Das halte ich jedoch für sehr umständlich und einen heiden Arbeitsaufwand sodass ich denke es muss einen einfacheren Weg geben.


Gruß Eclypse


----------



## chmee (16. Februar 2010)

> Das Problem ist die Zielführung. Da der User bei der Zieleingabe auf die Koordinaten am RECHTEN Bildschirmrand klickt und nicht auf die (physisch gleichen) Koordinaten neben dem linken Rand wird der User immer den langen Weg fahren. :/


Ja, das Problem ist verständlich. Man könnte erstmal eine Pixelentfernung auf Mapbasis in Betracht ziehen (zB Ist Punkt Aa mindestens doppelt/dreimal so weit wie Punkt Ab,Ac etc..), so hätte man die erste Fallunterscheidung, ansonsten müsste man mehrere Wege per AStar durchgehen. Ich habe keine Ahnung wie ressourcenhungrig AStar ist, aber ich habe fast das Gefühl, auch das ließe sich machen.

Das Problem als Solches beschreibt Eines ganz gut, AStar ist scheinbar optimiert auf in sich geschlossene Mazes. Sobald man eine sich wiederholende Map hat, muss man tüfteln.

mfg chmee


----------



## Eclypse (16. Februar 2010)

Resourcenabhängigkeit...


Also ich hab grade eine karte(obiges Beispiel - 700x400px) in eine Maze umgewandelt. (Monochrom gemacht, pixel gecheckt ob 0 oder 255 und in eine txt datei "w" oder " " geschrieben. Diese Maze habe ich dann über die Astar funktion auf der webseite erstmal probegecheckt. 

Die Operation wird bei 30sec exceed abgebrochen ^^


Jetzt habe ich 25% der Grafik genommen und bekomme zumindest eine Maze dargestellt. Für den moment noch fehlerhaft aber da wurstel ich noch ein bisschen.

Problem: wenn 700x400px schon zuviel ist fällt die Maze geschichte aus. So wie wir das spiel planen müssen wir mindestens 1000x800 "gridpunkte" haben. Maze technisch kann ich das natürlich auf ein viertel runterbrechen. (ich muss ja nicht JEDEN gridpunkt in einer maze berechnen lassen - wie oben bereits erwähnt)

Allerdings bin ich mit der 9xWorldscale sehr schnell dann doch wieder auf einer Pixelzahl die deutlich zu hoch für die doch recht Resourcenfressende Maze berechnung ist :/



*neverendingstory*


----------



## chmee (16. Februar 2010)

Achte darauf, dass ich den erheblichen Teil ja auf nur doppelt so groß eingeschrumpft habe, sprich, an jeder Seite nur die halbe Welt dazupacken (uU 2/3) sollte ausreichen, dennoch sagst Du ja, das ist so zimelich Ende der Fahnenstange.. hmpf..

p.s.: Effizient wird AStar erst, wenn das Grid klein wird. Vielleicht siehst Du eine Chance, die Worldmap noch kleiner zu kriegen, ohne Dein Spiel in Mitleidenschaft zu ziehen. Das AStar-Grid muss ja nicht dem Spielgrid entsprechen. Ich könnte mir vorstellen, dass man die Welt in 50x25px beschreiben könnte (also 100x50 nach Verdoppelung).

mfg chmee


----------



## Parantatatam (16. Februar 2010)

Was mir dazu noch einfällt, ist, dass man mit der Zeit doch auch Strecken hat, die doppelt verwendet werden. Dementsprechend könnte man doch bereits berechnete Strecken in einer Datenbank speichern mit Anfangs- und Endpunkt (und die Karte dazu) speichern. Aber das würde erst nach einiger Zeit einen Gewinn bringen.


----------



## newwarrior (16. Februar 2010)

einfach nur crack hat gesagt.:


> Was mir dazu noch einfällt, ist, dass man mit der Zeit doch auch Strecken hat, die doppelt verwendet werden. Dementsprechend könnte man doch bereits berechnete Strecken in einer Datenbank speichern mit Anfangs- und Endpunkt (und die Karte dazu) speichern. Aber das würde erst nach einiger Zeit einen Gewinn bringen.



Das haben wir uns auch schon überlegt, doch hier ist wieder das Problem, das es zu viele Ressourcen frisst.
Den wir haben ja nich tnur diese Abfrage sondern auch noch die anderen Informationen (Battlescript, Bauscript, UserInfos usw.).
Da kommt eine ganz schöne Rechenleistung auf dem Server dazu.

Jem. hatte vorgeschlagen es mit JS zu versuchen.
Wie kann man den sowas in Js umsetzen?


----------



## DeluXe (16. Februar 2010)

newwarrior hat gesagt.:


> Jem. hatte vorgeschlagen es mit JS zu versuchen.
> Wie kann man den sowas in Js umsetzen?


Dieser jemand gehört geschlagen! 

In Zeiten von Firebug und Co. wäre es ein Leichtes, das JavaScript anzupassen.
Bei einem Browsergame sollte Javascript keinerlei wichtigen Funktionen übernehmen. Es sollte lediglich ein Hilfsmittel sein.


----------



## Eclypse (17. Februar 2010)

Also die Maze scheint tatsächlich grundsätzlich zu groß zu sein. 

Eine Datei von 350x200px größe ist schon zu groß.

Gibt es irgendwo eine angabe wie groß die datei maximal sein darf?

Grundsätzlich kann ich ja auch eine kleine Maze erstellen und die auf eine große Karte anwenden. Ich weiss nur nicht wie genau die kleine Karte dann noch ist. Wahrscheinlich ergeben sich daraus in der folge dann jede menge fehler :/


----------



## Eclypse (17. Februar 2010)

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 (17. Februar 2010)

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 (17. Februar 2010)

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 (17. Februar 2010)

*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 (17. Februar 2010)

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 (17. Februar 2010)

@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 (17. Februar 2010)

> 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 (17. Februar 2010)

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 (17. Februar 2010)

@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 (22. Februar 2010)

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


----------



## chmee (22. Februar 2010)

Tatsächlich musst Du in (fast je)dem Fall beide Fälle (Wege) über Astar berechnen, da sich ad Hoc nicht entscheiden lässt, welcher kürzer ist. 

Vielleicht wäre sinnvoll, zu sagen,

WENN Startpunkt<>Endpunkt kürzer als zB 1/3 der Mazedimension DANN nur einen Weg berechnen, ansonsten beide Wege?

mfg chmee


----------



## AperfectCircle (22. Februar 2010)

ja die idee ist mir auch vorhin durch den Kopf gegangen. 

Das würde bedeuten das ich eine zweite Maze machen muss in der die Welt um 180° gedreht ist. Dann muss auch jeder Punkt auf der Karte einmal +180° addiert werden um dann in der anderen maze berechnet werden zu können. Dann kann ich entscheiden welcher Weg kürzer ist. das bedeutet in dem fall allerdings 2xBerechnungszeit und das grundsätzlich :/

Da werd ich einen "Route" server brauchen. :/


----------



## DeluXe (23. Februar 2010)

AperfectCircle hat gesagt.:


> 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.



20.000 ist für eine Datenbank nicht viel. Wenn man die in den Ram verlagert und ein paar sinnvolle Indexe anlegt.
Ist natürlich alles vom Server, der Programmierung, den Queries, dem Caching, etc. abhängig, aber wenn das gut durchdacht ist muss man sich um die paar Zeilen keinen Kopf machen. Da kannst dann auch das 10- oder 100-fache rein packen.


----------

