Wegfindung

[readme.txt]

Hi Leue ...

Ich steh bei einer Geschichte gerade ein bisschen auf dem Schlauch und hoffe einer von euch kann mir einen Tritt in die Richtige Richtung geben.

Folgendes:

Ein Tile-Basierendes Spiel, jede Tile hat einen Wert der die "Bewegungskosten" angibt die sie verbraucht.

Bsp: ein Tile des Typs "Wiese" verbraucht 2 Bewegungspunkte, ein Tile des Typs "Wald" verbraucht 3 Punkte.

Auf der Map steht nun eine Spielfigur. Die Figur hat einen Wert der angibt wie Viele Bewegungspunkte ihr zur Verfügung stehen.

Problem:
Bei Klick auf die Figur soll jedes Tile makiert werden das die Figur mit ihren Bewegungspunkten erreichen kann.

Bei dem Algorithmus hacks bei mir im Moment. Hat einer eine Idee wie man sowas am Performantesten angeht?

[X-Tender]

Vielleicht findest du im TonyPa TUT ja ein paar Anregungen.

http://www.tonypa.pri.ee/tbw/tut22.html

[wayfinder]

kann leider trotz meines namens nicht weiter helfen






(preis für den nutzlosesten post des monats.)

[readme.txt]

Zitat von X-Tender

Vielleicht findest du im TonyPa TUT ja ein paar Anregungen.

http://www.tonypa.pri.ee/tbw/tut22.html

Das Tut kenn ich ... ich fürchte mein Threadtitel war etwas verwirrend. Ich muss nicht den kürzesten Weg für die Figur von Tile A nach Tile B finden sondern ich brauche alle Felder die die Figur theoretisch erreichen kann.

[elysian]

xervus readme!

dein stichworte sind graphentheorie und kantengewichteter graph.
hab leider grade nicht die zeit, aber there you go...

cheers, thomas.

[Janoscharlipp]

Rekursiv würde ich sagen.

Fängst am Startpunkt an, und machst für jeden Nachbarpunkt folgende Überlegungen:

1) kann der Punkt mit den Reserven erreicht werden?
2) wieviel Reserven bleiben?
3) wurde der Punkt schon mit mehr verbleibenden Reserven erreicht?
4) wenn ja, vergiss es
5) wenn nein, speichere den Punkt mit den verbleibenden Reserven in ein Array

mit allen Punkten im Array gehts wieder bei 1) los.

Sicher nicht optimal von der Performance, aber sollte bei mittleren Reichweiten ausreichen

[readme.txt]

@elysian: Uff ... harter Tobak ... ich werd mal versuchen mich da reinzulesen.

@Janoscharlipp: So ähnlich hab ichs schon versucht ... aber irgendwo hatte ich da noch einen Fehler.

Ich bring das Beispiel morgen mal mit vieleicht hilft das ja.

[readme.txt]

Ich bins nochmal.

Ich habs gestern nicht mehr auf die Reihe bekommen. Ich hab hier:

http://www.surge-oe.de/develop/tile/

mal das Beispiel hochgeladen. Die Voraussetzungen sind das ein Feld des Typs "Ebene" 1 Bewegungspunkt verbraucht und ein Feld des Typs "Wald" 2 Punkte.

Die Spielfigur hat 5 Bewegungspunkte zur Verfügung.

Das ist der Code der die Felder auswählt:

PHP-Code:

// -> move_tank() -> Berechnet die Reichweite einer Spielfigur 
function move_tank(tile,tank) {
  var map    = tile._parent;
  var felder = new Array([tile.col,(tile.row-1)],[tile.col,(tile.row+1)],[(tile.col-1),tile.row],[(tile.col-1),(tile.row-1)],[(tile.col+1),tile.row],[(tile.col+1),(tile.row-1)]);
  
  for(var i=0; i<felder.length; i++) {
    var akt_tile = map["tile_"+felder[i][0]+"_"+felder[i][1]];
    
    if(akt_tile && akt_tile != tank.tile && (tile.move_points-akt_tile.move_cost) >= 0 && !isNaN((tile.move_points-akt_tile.move_cost))) {
      var hex = map.createEmptyMovieClip("hex_"+felder[i][0]+"_"+felder[i][1],map.getNextHighestDepth());
          hex.draw_hex(akt_tile);
          
      akt_tile.move_points = (tile.move_points-akt_tile.move_cost);
      
      move_tank(akt_tile,tank);
    }
  }
  
  tank.swapDepths(tank._parent.getNextHighestDepth());
}
// <- move_tank() 


Im groben übergebe ich an die Funktion die Tile die sie BErechnen soll. Dann stelle ich ein Array zusammen das alle Tiles um diese Tile enthält (jeweils 6 Stück)

Für jede der Tiles überprüfe ich dann ob sie existiert, ob sie nicht die tle ist auf der die spielfigur steht und ob die aktuelle der aktuelle Bewegungspunktvorrat - die Kosten für diese tile >= 0 ist. Ist das der Fall zeichne ich ein hexfeld als Markierung ein, übergebe den Bewegungspunktvorrat - die Kosten für diese Tile an die Tile und starte die Funktion mit dieser Tile neu.

Mehr ist das eigendlich nicht, aber funktionieren tut es trotzdem nicht ^^ ... Ich muss vieleicht noch dazu sagen das ich nicht der begnadetste Programmierer unter der Sonne bin. Ich krieg eigendlich immer alles hin was ich will aber nicht zwangsläufig besonders Elegant.

Wenn jemand Ideen/Tips hat oder einen Denkfehler bei mir bemerkt würd ich mich freuen.

[madflanderz]

ich glaube dein problem kannst du auch mit dem a*-algorithmus lösen.
hier is der mal schön erklärt und unten gibts auch gleich das beispiel skript.

http://www.policyalmanac.org/games/aStarTutorial.htm

gruß mad

[Janoscharlipp]

Ich denke, das Problem ist, dass du im Kreis laufen kannst, mit deiner Rekursion, und damit die move_points von Feldern verringerst, die eigentlich später erst in der Rekursion abgearbeitet werden.
(s. Punkt 3 in meinem Gedankengang)

[readme.txt]

Danke nochmal für eure Hilfe ... Ich habs gestern Abend dann doch noch hinbekommen.

Der Knackpunkt war dan am Ende tatsächlich zu überprüfen ob jedes gegebene Feld aus einer anderen Richtung mit mehr verbleibenden "Bewegungspunkten" erreicht werden kann.

Danke nochmal

[X-Tender]

Du meinst es wurde dir auf flashkit gezeigt

[readme.txt]

Hehe ... es war eine Kombination aus Tips von Flashkit und vom Flashforum