Hallo,
also ich habe eine 340 * 340 felder grosse karte der 0/0 punkt ist in der mitte.
wenn jetzt jemand einen anderen angreiffen will, kann ich die anzahl felder zwischen den beiden städten per wurzelziehen herausfinden. nun dachte ich, ich baue noch Wasser ein, nun komme ich aber zum problem: wenn zwischen zwei städten wasser liegt, sollten die einheiten drum herum gehen.
nur habe ich keine ahnung wie ich herausfinden soll, ob zwischen den beiden städten wasser liegt, und wie viele felder sie ungefähr drum herum laufen müssen. google brachte nichts.
ich dachte das ich irgendwie die betrofenen felder aus der mysql datenbank lese..... und dan ausrechne wie gross der see ist oder so.
bin für ideen dankbar
mfg Roland
X/y karte, wasser und einheiten
gepostet vor 18 Jahre, 6 Monate von planetenkiller
gepostet vor 18 Jahre, 6 Monate von Kapsonfire
also ich hab alles in einer db und wenn wasser ist mach ich begehbar="0"
nun durch ein aufwendiges script erstellt der computer eine route und berechnet die zeit xD
nun durch ein aufwendiges script erstellt der computer eine route und berechnet die zeit xD
gepostet vor 18 Jahre, 6 Monate von planetenkiller
das mit dem berechnen der route hört sich cool an, nur ich habe immer noch keine ideen wie ich die route berechnen könnte.
gepostet vor 18 Jahre, 6 Monate von TheUndeadable
Suche mal nach dein A* (A-Star)-Algorithmus. Eigentlich der Standard-Algorithmus für Wegsuche in Spielen.
gepostet vor 18 Jahre, 6 Monate von woodworker
ne php implementation von A* gibts im snippets bereich
gepostet vor 18 Jahre, 6 Monate von BLUESCREEN
AFAIK gibt es zu dem Thema hier im Forum mindestens einen umfangreichen Thread - also auch danach einfach mal suchen.
gepostet vor 18 Jahre, 6 Monate von Itchy
Wenn Dir der A* Algorithmus zu komplex ist (bei großen Maps kann der schon ordentlich rechnen) gibt es auch eine ganz einfache Algorithmen, die allerdings nicht immer (d.h. nur mit Glück) den kürzesten Weg finden oder überhaupt einen Weg finden.
Dazu gehst Du einfach vom Startpunkt in die Richtung des Zielpunktes. Stößt auf ein Hindernis, dann versuchst Du diesem auf eine fest vorgegebene Art auszuweichen, realisiert über eine kleine Tabelle (bzw. ein Array).
z.B. (es gibt natürlich mehrere Kombinationsmöglichkeiten)
$ausweich['W'] = 'S';
$ausweich['O'] = 'N';
$ausweich['S']='O';
$ausweich['N'] = 'W';
Das bedeutet, wenn man nach Osten gehen will aber der Weg dorthin blockiert ist, wird versucht nach Norden auszuweichen( $ausweich['O'] = 'N' ). Ist der Weg nach Norden auch blockiert, so wird versucht Westen auszuweichen, ist auch dieser Weg blockiert, so wird nach Süden ausgewichen. Wenns da auch nicht weitergeht, gut, dann gibt es entweder keinen Weg, oder dieser billige Algorithmus reicht für diese Zwecke eben nicht aus. Findet man eine Ausweichmöglichkeit, so merkt man sich das Urspungsfeld. Zu beachten ist auch, daß der Algorithmus ebenfalls abgebrochen wird, wenn als Ausweichsmöglichkeit ein bereits besuchtes Feld ausgewählt wird.
Das kann man nun für die anderen Ausweichtabellen wiederholen und z.B. den kürzesten gefundenen Pfad dann zurückgeben.
Zu beachten bei den Ausweichtabellen ist auch, daß eine Ausweichmöglichkeit $ausweich['N'] = 'S' wenig Sinn macht - so findet man garantiert keinen Weg.
Wie gesagt, der Algorithmus ist nicht besonders elegant und hat keine Garantie auf Erfolg oder gar die kürzeste Strecke, ist jedoch sehr einfach zu implementieren, man kommt ohne irgendwelche Datenstrukturen wie Listen aus und hat eine recht geringe Komplexität.
Dazu gehst Du einfach vom Startpunkt in die Richtung des Zielpunktes. Stößt auf ein Hindernis, dann versuchst Du diesem auf eine fest vorgegebene Art auszuweichen, realisiert über eine kleine Tabelle (bzw. ein Array).
z.B. (es gibt natürlich mehrere Kombinationsmöglichkeiten)
$ausweich['W'] = 'S';
$ausweich['O'] = 'N';
$ausweich['S']='O';
$ausweich['N'] = 'W';
Das bedeutet, wenn man nach Osten gehen will aber der Weg dorthin blockiert ist, wird versucht nach Norden auszuweichen( $ausweich['O'] = 'N' ). Ist der Weg nach Norden auch blockiert, so wird versucht Westen auszuweichen, ist auch dieser Weg blockiert, so wird nach Süden ausgewichen. Wenns da auch nicht weitergeht, gut, dann gibt es entweder keinen Weg, oder dieser billige Algorithmus reicht für diese Zwecke eben nicht aus. Findet man eine Ausweichmöglichkeit, so merkt man sich das Urspungsfeld. Zu beachten ist auch, daß der Algorithmus ebenfalls abgebrochen wird, wenn als Ausweichsmöglichkeit ein bereits besuchtes Feld ausgewählt wird.
Das kann man nun für die anderen Ausweichtabellen wiederholen und z.B. den kürzesten gefundenen Pfad dann zurückgeben.
Zu beachten bei den Ausweichtabellen ist auch, daß eine Ausweichmöglichkeit $ausweich['N'] = 'S' wenig Sinn macht - so findet man garantiert keinen Weg.
Wie gesagt, der Algorithmus ist nicht besonders elegant und hat keine Garantie auf Erfolg oder gar die kürzeste Strecke, ist jedoch sehr einfach zu implementieren, man kommt ohne irgendwelche Datenstrukturen wie Listen aus und hat eine recht geringe Komplexität.
gepostet vor 18 Jahre, 6 Monate von Skyrunner
1. Die Distanz (Luftlinie) zwischen den beiden Punkten (User und Opfer) mit Pythagoras ausrechnen und begrenzen: z.B. 50 Felder.
2. Alle Felder zwischen Startfeld A und Zielfeld B laden (Bild)
Du lädst einfach alle Felder im gelben Bereich (1 SQL Abfrage).
2. Dann benutzt du den A* Algorithmus. Alles andere ist Müll! Ausserdem beschränkst Du den Weg zwischen A undB ja eh schon (siehe Punkt 1.), von daher ist A* auch nicht soo extrem langsam.
3. Jetzt passt Du den A* Algorithmus einfach dahingehend an, dass Du die Felder mit Hindernissen entsprechend ausschließt.
Wichtig: Sollte der A* einmal über ein Feld gehen wollen, das Du noch nicht geladen hast, so lädst Du einfach alle Felder im Umkreis des Feldes wo der A* grad steht. Den Radius musst Du halt so setzen, dass Du möglichst wenig Felder lädst, damit die Performance gewahrt bleibt. Wenn nun der Algorithmus wieder an ein Feld stößt dass er noch nicht geladen hat dann lädst du wieder alle felder im umkreis... und so weiter... bis er das Ziel gefunden hat
Fertig
2. Alle Felder zwischen Startfeld A und Zielfeld B laden (Bild)
Du lädst einfach alle Felder im gelben Bereich (1 SQL Abfrage).
2. Dann benutzt du den A* Algorithmus. Alles andere ist Müll! Ausserdem beschränkst Du den Weg zwischen A undB ja eh schon (siehe Punkt 1.), von daher ist A* auch nicht soo extrem langsam.
3. Jetzt passt Du den A* Algorithmus einfach dahingehend an, dass Du die Felder mit Hindernissen entsprechend ausschließt.
Wichtig: Sollte der A* einmal über ein Feld gehen wollen, das Du noch nicht geladen hast, so lädst Du einfach alle Felder im Umkreis des Feldes wo der A* grad steht. Den Radius musst Du halt so setzen, dass Du möglichst wenig Felder lädst, damit die Performance gewahrt bleibt. Wenn nun der Algorithmus wieder an ein Feld stößt dass er noch nicht geladen hat dann lädst du wieder alle felder im umkreis... und so weiter... bis er das Ziel gefunden hat
Fertig
gepostet vor 18 Jahre, 6 Monate von friedenspanzer
> Du lädst einfach alle Felder im gelben Bereich (1 SQL Abfrage).
Naja, könnte ein Problem werden wenn grad der gelbe Bereich nicht betretbar ist. Der Weg wäre dann problemlos für jeden Menschen ersichtlich, das drumherum manövrieren wäre also ein sinnloser Mehraufwand der schnell für Frust sorgt (besonders wenn das ganze zeitabhängig ist).
Ich würde sagen erweiter den gelben Bereich um, sagen wir mal 50% - 75% in alle Richtungen. Das sollte auch net so arg in die Performance gehen und lässt den Algorithmus intelligenter arbeiten.
Naja, könnte ein Problem werden wenn grad der gelbe Bereich nicht betretbar ist. Der Weg wäre dann problemlos für jeden Menschen ersichtlich, das drumherum manövrieren wäre also ein sinnloser Mehraufwand der schnell für Frust sorgt (besonders wenn das ganze zeitabhängig ist).
Ich würde sagen erweiter den gelben Bereich um, sagen wir mal 50% - 75% in alle Richtungen. Das sollte auch net so arg in die Performance gehen und lässt den Algorithmus intelligenter arbeiten.
gepostet vor 18 Jahre, 6 Monate von planetenkiller
vielen dank euch allen.
ich muss zuerst mal den algorithmus progen, dann werde ich das ganze script optimieren, das mit dem nachladen werde ich machen.
auserdem habe ich vor evtl. eine tabelle zu erstellen wo ich die die auswertung von a-star algo reinsetze und wenn der angreiffer(start) oder der verteidiger(ziel) mal wider einheiten schickt, das ich dann nicht nochmal den algo ausführen muss, den das wasser, wald... werden sich ja nicht ändern.
mfg Roland
ich muss zuerst mal den algorithmus progen, dann werde ich das ganze script optimieren, das mit dem nachladen werde ich machen.
auserdem habe ich vor evtl. eine tabelle zu erstellen wo ich die die auswertung von a-star algo reinsetze und wenn der angreiffer(start) oder der verteidiger(ziel) mal wider einheiten schickt, das ich dann nicht nochmal den algo ausführen muss, den das wasser, wald... werden sich ja nicht ändern.
mfg Roland
gepostet vor 18 Jahre, 6 Monate von planetenkiller
*edit* das hier bitte löschen, fehler von mir
mfg Roland
mfg Roland
gepostet vor 18 Jahre, 6 Monate von planetenkiller
ok, ich habe mich beim a-star algorithmus überschätzt konnte es bis jetzt noch nicht inpletieren. er findet den pfad einfach nie, obwohl das ziel 2 diagonale felder entfehrt wäre.
hier mal der code:
achtung: momentan wir nichts mit der Karte aus der db abgeglichen, nur die 8 umliegenden fleder berechnent und zurückgegeben.
als anhang der code
mfg Roland
*edit*
juhu juhu es geht jetzt. aber ich muss schauen ob ich es noch optimieren kann, denn von der koordinate (x/y) 1/1 zu 169/100 brauchte er 290 sec.
hier mal der code:
achtung: momentan wir nichts mit der Karte aus der db abgeglichen, nur die 8 umliegenden fleder berechnent und zurückgegeben.
als anhang der code
mfg Roland
*edit*
juhu juhu es geht jetzt. aber ich muss schauen ob ich es noch optimieren kann, denn von der koordinate (x/y) 1/1 zu 169/100 brauchte er 290 sec.
gepostet vor 18 Jahre, 6 Monate von planetenkiller
ok, der algo gefällt mir richtig gut.
nun zum optimieren:
streke: x/y 1/1 nach 129/80
vorher: 52 sec.
nachher: 12 sec. !!
was ich optimiert habe:
ich habe für die open-list und die closed-list jeweils eine neue liste erstellt, darin wird der x/y wert und G gespeichert ( $openList_xy[$x][$y] = $node->g; ).
beim prüfen ob der aktuelle node in der open oder closed liste ist, ist jetzt nur noch eine if abfrage ob die koordinate im xxListe_xy ist.
Beim verschieben eines nodes von der open zur closed liste muss man die zwei anderen listen auch updaten, auch beim eintragen in die open liste in die zweite liste einen eintrag machen.
leider braucht die function, die den eintrag mit dem kleinsten F wert sucht, 6 von den 12 sec. ich muss eben die openliste durchgehen und dan den key des eintrages mit dem kleinsten f wert zurückgeben.
der code:
// die knoten position mit dem kleinsten F holen
function getBestKnoten(&$openList)
{
reset($openList);
$id = key($openList);
$klein = $openList[$id];
$found = $id;
foreach ($openList AS $key => $val)
{
if(bccomp($val->f, $klein->f, 10) == -1 ) // bccomp ist zum vergleichen der f werte, die ja leider auch nachkomastellen haben
{
$klein = $val;
$found = $key;
}
}
return $found;
}
mfg Roland
nun zum optimieren:
streke: x/y 1/1 nach 129/80
vorher: 52 sec.
nachher: 12 sec. !!
was ich optimiert habe:
ich habe für die open-list und die closed-list jeweils eine neue liste erstellt, darin wird der x/y wert und G gespeichert ( $openList_xy[$x][$y] = $node->g; ).
beim prüfen ob der aktuelle node in der open oder closed liste ist, ist jetzt nur noch eine if abfrage ob die koordinate im xxListe_xy ist.
Beim verschieben eines nodes von der open zur closed liste muss man die zwei anderen listen auch updaten, auch beim eintragen in die open liste in die zweite liste einen eintrag machen.
leider braucht die function, die den eintrag mit dem kleinsten F wert sucht, 6 von den 12 sec. ich muss eben die openliste durchgehen und dan den key des eintrages mit dem kleinsten f wert zurückgeben.
der code:
// die knoten position mit dem kleinsten F holen
function getBestKnoten(&$openList)
{
reset($openList);
$id = key($openList);
$klein = $openList[$id];
$found = $id;
foreach ($openList AS $key => $val)
{
if(bccomp($val->f, $klein->f, 10) == -1 ) // bccomp ist zum vergleichen der f werte, die ja leider auch nachkomastellen haben
{
$klein = $val;
$found = $key;
}
}
return $found;
}
mfg Roland