Weg Berechnung / Karte / Meer / Browsergame

[newwarrior]

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]

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]

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]

moin,

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

Danke

 

[chmee]

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

mfg chmee

 

[newwarrior]

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

 

[holzmensch]

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]

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]

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

 

[Marius Heil]

@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 ;-)