# bewegungsberechnung hexmap



## grayson (19. Jul 2004)

Hallo, ich arbeite an einem hexfeldbasierten strategiespiel und habe bei der einheiten bewegungsberechnung ein problem : 

dazu mal nen screenshot :










der mech dort soll eine bewegungsreichweite von sagen wir 4 feldern haben. die einzelnen felder befinden sich in einem array mit x und y koordinate und können darüber auch explizit angesprochen werden.

bei einer bewegungsweite von 4 feldern, würde sich ein großes sechseck mit den eckpunkten : 4 felder hoch /runter, 4 felder links/rechts, 4 felder schräg hoch/runter zu beiden seiten ergeben, wie eingezeichnet. (rot)


wie ich im array auf die 6 eckpunkte komme, das bekomm ich hin. aber von der einheit aus soll jedes feld innerhalb dieses sechseckes markiert werden mit so einem netten lila, wie es bereits um die einheit herum zu sehen ist.

dazu die erste frage : wie bekomm ich die felder innerhalb des arrays die innerhalb des sechseckes liegen ?

frage 2 - und die macht das ganze erst interessant - :

die verschiedenen geländetypen begünstigen, erschweren oder verhindern bewegung einer einheit.

so soll zb eine strasse eine bewegung begünstigen ( +2 ), normaler boden (+0), wald  (-1), berge (-2) ,wasser - verhindern.

diese sache verändert das bewegungssechseck natürlich um einiges. so müssten zb 2 felder strasse nach oben noch dazu selektiert werden , die 3 felder berge oben allerdings abgezogen. genau wie unten der wald, bei dem jeweils die äusseren felder ( die wo die roten linien durchlaufen ) abgezogen werden müssten.

zu dieser berechnung der ganzen bewegung fehlt mir grad jede idee. wenn ihr eine habt, lasst es mich wissen !


p.s. annahme : einheit steht auf feld x=90,y=90
dann sind die eckpunkte des sechseckes :

oben = x=90, y = 90 -4
unten = x=90, y= 90+4
links = x= 90-4,y=90
rechts = x=90+4,y=90
oben links = x= 90-4, y= 90-4
oben rechts = x= 90+4, y= 90-4
unten links = x= 90-4, y=90+4
unten rechts = x=90+4, y= 90+4


----------



## Beni (19. Jul 2004)

Ich würde da was rekursives machen.
Du gehst von einem Startfeld aus, und guckst, wohin kommst du überall mit _einem_ Schritt. Diese erreichbaren Felder markierst du. Gleichzeitig hast du eine Variable, wieviel Bewegungseinheiten noch verbleiben, diese Variable zählst du mit jedem Schritt runter.
Dann hast du ein neues Startfeld...

Ich zeichne das mal in Pseudocode auf:

```
public void mark( Feld position, int max ){
  // in position wird gespeichert, wieviel es Kosten würde, auf dieses Feld zu kommen.

  for( int i = 0; i < 6; i++ ){
    Feld friend = position.getFriend( i ); // Das Nachbarfeld in Richtung "i". Wie auch immer das berechnet wird...
    int delta = position.costsTo( i ); // Die Kosten, um auf das benachbarte Feld "i" zu kommen.

    int sum = position.getCosts() + delta; // Die Gesammtkosten um auf das benachbarte Feld "i" zu kommen.
    if( sum > max )
      continue; // Das Kostet eindeutig zu viel.

    int oldCosts = friend.getCosts(); // Die Gesammtkosten um auf ein Feld zu kommen, werden im Feld gespeichert. Ein Wert von -1 bedeutet, dass das Feld noch nicht betrachtet wurde.
  
    if( (oldCosts == -1) || (oldCosts > sum )){ // Dieser Nachbar wurde noch nicht besucht, oder es gibt einen billigeren Weg zu dem Nachbar.

      friend.setCosts( sum );  // Die Gesammtkosten zu diesem Feld speichern
      friend.setMarked( true );  // Das Feld markieren. Man könnte es z.b. auch in einen Vector speichern, um es später schneller zu finden...

      mark( friend, max ); // Der rekursive Aufruf. Nun ist der Nachbar das neue Startfeld
    }
  }
}
```

Man könnte das natürlich optimieren, aber bei den ~20 Feldern macht das wohl keinen grossen Sinn.


----------



## grayson (19. Jul 2004)

danke, probier ich morgen mal aus und sag dir obs geklapt hat


----------



## Grizzly (19. Jul 2004)

grayson hat gesagt.:
			
		

> danke, probier ich morgen mal aus und sag dir obs geklapt hat


Gibt es auch irgendwann das komplette Spiel zum Anschauen (und spielen)?  
Erinnert mich stark an Battle Isle...


----------



## grayson (21. Jul 2004)

ja klar, das gibt es irgendwann natürlich. es ist so geplant, das man sich als pilot eines der 5 großen battletech häuser anmelden kann, dann gibt es eine sternenkarte mit planeten um die man kämpfen kann, und so soll das ziel für jedes haus natürlich darin bestehen die gesammte sternenmap zu erobern hehe.
momentan fertig ist der mapeditor ( naja er läuft halt, aber wenn ich noch fabriken usw ins spiel einbaue muss ich da auch noch was machen ) vom spiel geht momentan nur das laden der karte, scrollen und bewegen des hexfeldcursors, sowie das deployen der einheiten zum spielstart und ich sitze grad an dem bewegunssachen für die einheiten.

zu machen ist noch : das sternenkarteninterface, die komplette datenbank mit usern, einheiten, waffen ect ( momentan füttere ich das spiel nur mit statischen testdaten, später soll das ganze über nen rmi server funzen, der natürlich auch noch zu schreiben ist ) 

tja und last but not least, sollte die ebtl ( ebtl.de ) kein interesse daran zeigen den rmi server zu hosten, muss ich auch irgendwo noch kostenlosen oder sehr billigen space auftreiben, auf dam man so nen rmi server laufen lassen kann und eine ebenfalls noch nicht erstellte projektseite wo man sich den client ( das spiel an sich ) runterladen kann ect ect ect..... da ich leider gottes ganz allein an dem projekt sitze wird das aber wohl noch ne ganze weile dauern , auch wenn ich selbst lieber heute als morgen mit dem zocken anfangen würde 

und ja, es soll sehr stark an battle isle angelehnt sein. wer megamek kennt weis wie kompliziert und fad der spielablauf dort ist ( ist halt ne brettspielumsetzung ) ich will eine ähnliche spieltiefe wie bei BI erreichen, ohne so in die details zu gehen wie megamek.


wenn natürlich jemand mitmachen möchte..... registriert hab ich das projekt auf souceforge, nutze den space dort allerdings noch nicht da ich ja allein arbeite bis jetzt.


----------



## Grizzly (21. Jul 2004)

grayson hat gesagt.:
			
		

> [...]wenn natürlich jemand mitmachen möchte..... registriert hab ich das projekt auf souceforge, nutze den space dort allerdings noch nicht da ich ja allein arbeite bis jetzt.


Unter welchem Projektnamen läuft das Spiel?

Du könntest doch Leute hier im Forum suchen. Dazu solltest Du vielleicht einen Thread unter *Aufgaben und Gesuche* oder unter *Codeschnipsel u. Projekte* aufmachen.


----------



## grayson (22. Jul 2004)

läuft da unter mechstrategic das dingen.


----------



## grayson (23. Jul 2004)

grummel, so richtig funzt das noch nicht.... hier mal der code :


```
/**
   * selektiert alle erreichbaren felder vom startfeld einer einheit aus
   * wird erstmalig vom startfeld aufgerufen und ruft sich dann für jeden nachbarn selbst auf
   * @param selection Coord
   */
  public void getFriends(Coord selection) {
    HexMapModel.Field thisField = mMap.getModel().getField(selection.x,
          selection.y);
      // feld das es zu prüfen gilt
 HexMapModel.Field check = null;
// nachbarnliste, die abgearbeitet wird
ArrayList friends=new ArrayList();

    try {
     
      check = mMap.getModel().getField(selection.x - 1, selection.y);
 friends.add(check);
   }catch (Exception e) {} // ArrayOutOfBoundsException wenn kartenrand erreicht
    try {
    
      check = mMap.getModel().getField(selection.x + 1, selection.y);
 friends.add(check);
        }catch (Exception e) {}
         try {
      check = null;
      check = mMap.getModel().getField(selection.x, selection.y + 1);
  friends.add(check);
       }catch (Exception e) {}
 try {
      check = null;
      check = mMap.getModel().getField(selection.x, selection.y - 1);
  friends.add(check);
        }catch (Exception e) {}
        
     // bei geraden feldindexen verteilen sich die diagonal liegenen nachbarn unten, bei ungeraden oben
        if (mMap.getModel().index(thisField.getCoord().x, thisField.getCoord().y) %
        2 == 0) {
 try {
        check = null;
        check = mMap.getModel().getField(selection.x - 1, selection.y - 1);
  friends.add(check);
          }catch (Exception e) {}
      }

      else {
 try {
        check = null;
        check = mMap.getModel().getField(selection.x + 1, selection.y + 1);
     friends.add(check);
          }catch (Exception e) {}
 try {
        check = null;
        check = mMap.getModel().getField(selection.x - 1, selection.y + 1);
 friends.add(check);
          }catch (Exception e) {}

      }
 for(int i=0;i<friends.size();i++){
  
   HexMapModel.Field goTo =(HexMapModel.Field)friends.get(i);
   if (maxMove == 0) {
         maxMove=thisField.getProperties().getUnit().
                                                getMoveRange();
         thisField.getProperties().setRangeLeft(thisField.getProperties().getUnit().
                                                getMoveRange());
       }
       // bewegungskosten berechnen
       int movecost = calculatecosts(goTo.getProperties().getgroundType());
       // wenn groundtype = unpassierbar wird 500 zurück gegeben    
       if (movecost == 500) {
             goTo.getProperties().setRangeLeft(thisField.getProperties().
                                                getRangeLeft());
           }
           else {
            // bewegungskosten von den bewegungspunkten der einheit (bzw den gespeicherten in thisField)
 //abziehen und in feld speichern
             goTo.getProperties().setRangeLeft(thisField.getProperties().
                                                getRangeLeft() - movecost);
             //selectionsbild auf feld adden
              goTo.getProperties().setPlainForegroundImage(mMap.load("actionselect"));
           }
          // wenn noch bewegungspunkte übrig sind in diesem feld rekursiver aufruf
           if (goTo.getProperties().getRangeLeft() > 0) {
            
            //überprüftes feld ist jetzt neues startfeld
             getFriends(goTo.getCoord());
           }

 }

  }
```
und hier der screenshot für diese methode in der form : 







hat jemand ne idee? ich hab irgendwie grad tomaten uf dem augen...


----------



## Beni (23. Jul 2004)

Also was ich nicht verstehe ist, dass du 7 mal "friends.add" aufrufst, aber ein Feld ja höchstens 6 Nachbarn haben kann?
Wie funktioniert dein Koordinatensystem?  ???:L


----------



## grayson (23. Jul 2004)

ups, stimmt für gerade felder hat das feld diagonal oben rechts gefehlt.


also alle felder befinden sich in einem array, jedes feld hat eine x und y koordinate


bei einem feld ist der linke nachbar = x-1,y der rechte x+1,y oben x,y-1 unten x,y+1

und je nach dem ob es ein gerades oder ungerades feld ist ( index im array) liegen die 2 restlichen diagonalen nachbarn entweder leicht oberhalb oder unterhalb daher 8 aufrufe von add, von denen für ein feld aber nur 6 ausgeführt werden. hier der aktualisierte code, viel hat sich net geändert aber ich denk jetzt sieht man es besser :


```
public void getFriends(Coord selection) {
    HexMapModel.Field thisField = mMap.getModel().getField(selection.x,
        selection.y);
    // feld das es zu prüfen gilt
    HexMapModel.Field check = null;
// nachbarnliste, die abgearbeitet wird
    ArrayList friends = new ArrayList();

    try {

      check = mMap.getModel().getField(selection.x - 1, selection.y);
      friends.add(check);
    }
    catch (Exception e) {} // ArrayOutOfBoundsException wenn kartenrand erreicht
    try {

      check = mMap.getModel().getField(selection.x + 1, selection.y);
      friends.add(check);
    }
    catch (Exception e) {}
    try {
      check = null;
      check = mMap.getModel().getField(selection.x, selection.y + 1);
      friends.add(check);
    }
    catch (Exception e) {}
    try {
      check = null;
      check = mMap.getModel().getField(selection.x, selection.y - 1);
      friends.add(check);
    }
    catch (Exception e) {}
    System.err.println(mMap.getModel().index(thisField.getCoord().x,
                                             thisField.getCoord().y));
    // bei geraden feldindexen verteilen sich die diagonal liegenen nachbarn unten, bei ungeraden oben
    if (mMap.getModel().index(thisField.getCoord().x, thisField.getCoord().y) %
        2 == 0) {
      try {
        check = null;
        check = mMap.getModel().getField(selection.x - 1, selection.y - 1);
        friends.add(check);
      }
      catch (Exception e) {}

      try {
        check = null;
        check = mMap.getModel().getField(selection.x + 1, selection.y - 1);
        friends.add(check);
      }
      catch (Exception e) {}
    }

    else {
      try {
        check = null;
        check = mMap.getModel().getField(selection.x + 1, selection.y + 1);
        friends.add(check);
      }
      catch (Exception e) {}
      try {
        check = null;
        check = mMap.getModel().getField(selection.x - 1, selection.y + 1);
        friends.add(check);
      }
      catch (Exception e) {}

    }
    for (int i = 0; i < friends.size(); i++) {

      HexMapModel.Field goTo = (HexMapModel.Field) friends.get(i);
      if (maxMove == 0) {
        maxMove = thisField.getProperties().getUnit().
            getMoveRange();
        thisField.getProperties().setRangeLeft(thisField.getProperties().
                                               getUnit().
                                               getMoveRange());
      }
      // bewegungskosten berechnen
      int movecost = calculatecosts(goTo.getProperties().getgroundType());
      // wenn groundtype = unpassierbar wird 500 zurück gegeben
      if (movecost == 500) {
        goTo.getProperties().setRangeLeft(thisField.getProperties().
                                          getRangeLeft());
      }
      else {
        // bewegungskosten von den bewegungspunkten der einheit (maxMove) abziehen und in feld speichern
        goTo.getProperties().setRangeLeft(thisField.getProperties().
                                          getRangeLeft() - movecost);
        //selectionsbild auf feld adden
        goTo.getProperties().setPlainForegroundImage(mMap.load("actionselect"));
      }
      // wenn noch bewegungspunkte übrig sind in diesem feld rekursiver aufruf
      if (goTo.getProperties().getRangeLeft() > 0) {

        //überprüftes feld ist jetzt neues startfeld
        getFriends(goTo.getCoord());
      }

    }

  }
```


----------



## grayson (26. Jul 2004)

so, das hab ich geschafft juhuu !

nun mal nen neuer screenshot, und die frage dazu. wie bekomm ich nur die felder zurück, die unter der lila linie liegen ? 

oben die zahlen 1- dings sind die indexe im felderarray. diex,y koordinaten sind die koordinaten der felder in der map, beide varianten lassen sich direkt ansteuern.
jemand ne idee???


----------



## grayson (28. Jul 2004)

hmm keine antwort? so kompliziert das? wargh......


----------



## Beni (28. Jul 2004)

Frage: wie hast du die lila Linie gezeichnet, ich meine, da musst du ja schon wissen, welche Felder du hast ???:L 

Ansonsten kommt das ganz auf deine Datenstruktur draufan, was die alles kann, wie sie aufgebaut ist, und die Umrechnung der Koordinaten in Indices kennst wohl auch nur Du selbst  :cry:  :wink: 

Vielleicht missversteht dich hier auch jeder, und Du musst die Frage nochmals stellen  8)


----------



## Scoobie (28. Jul 2004)

Du könntest es mal mit einem Graphen probieren!

Graphen sind so ähnlich wie Bäume. Also eine spezielle Datenstruktur in der Knoten existieren, die zu verschiedenen anderen Knoten verbindungen haben.

Ungefähr wie eine Liste nur können die Knoten mehr als nur eine Verknüpfung zu anderen Knoten haben.

Du kannst dann in deinem Graphen in den jeweiligen Knoten das Gewicht also (-2 für Wasser, -1 für Berge usw.) abspeichern und somit die Wegspanne in die verschiedenen Richtungen berechnen

Such vielleicht einfach mal unter dem Begriff Datenstrukturen: Graphen wenn du damit nicht vertraut bist.

Ist auch nur eine Idee wenn dir das Konzept nicht zusagt


----------



## grayson (29. Jul 2004)

nunja, die berechnun der reichweiten funktioniert mittlerweile gut, auch so das strassen ect berücksichtigt werden.

mir eht es momentan nur darum, wie ich innerhalb der markierten felder einen weg finde. dazu mal die bilder : (die lila linie im forherigen bild hab ich per hand eingezeichnet, das ist die berechnun die das programm selber machen soll wo ich aber net weis wie.)

phase 1: einheit wird markiert und zugweiten berechnet (die markierte liegt unter dem grünen pfeilsymboldingens, das andere da ist eine 2weite testeinheit und steht da nur so rum):







phase 2 : der weg innerhalb der möglichen felder zum selektierten zielpunkt wird angezeigt, der rest der möglichen zugfelder ausgebelendet (mögliche wege die das programm hier berechnen sollte, sind lila linien, zielpunkt ist lila kreis. bei der berechnung müssten auch hindernisse wie zb andere einheiten berücksichtigt werden)







so, und bei diesem kram weis ich nicht wie ich es machen soll. annahme zu dieser situation : das startfeld hat die koordinaten x = 13, y= 7 und das zielfeld x=15, y= 16.

ich hoffe jetzt wird es deutlicher.

die einheiten einfach zum zielfeld "warpen" zu lassen kann ich ohne progleme, aber sie sollen ja eigendlich den dann selektierten pfad "abfahren " das sieht netter aus. und da kommen wir auch gleich zum nächsten problem : wie kann ich das einheitenbild drehen in schritten von 45 grad?


----------



## Beni (29. Jul 2004)

Du könntest bei jedem Feld speichern, woher der Rekursionalgorithmus (getFriend) zuletzt gekommen ist. Dann kannst du den Weg rückwärts berechnen.


----------



## grayson (29. Jul 2004)

gute idee, probier ich gleich mal aus


----------



## grayson (29. Jul 2004)

mist, funzt so leider nicht. zuer erläuterung hier mal nen bild, wie ich die bewegungen erreche.







die lila linien sind die aststruktur, nach der ich durch die felder wandere und so lane movementpoints abziehe, bis keine mehr da sind. danach gehe ich mit der grünen linie nocheinmal drumrum und check die randfelder nochmal durch ( wenn es um berge herum geht oder andere einheiten ect, lässt die aststruktur schonmal ein oder 2 movepoints über, die sie eigendlich mit berechnen müsste - sie läuft schlicht ins leere manchmal und das ganze komplett rekursiv zu machen wird zu langsam, daher eine nochmalige prüfung der äusseren felder.)

daher ist das speichern in form einer came from variable unbefriedigend, aber wenn ich mal nen rekursiven we, der schnell genug ist finde uf jeden fall ne idee, danke dafür schonmal !

sonst ideen????


----------



## grayson (29. Jul 2004)

p.s. ich hasse meine tastatur.. kauft euch nur nie son billiges laptoptastatur imitat.... nach einer weile klemmen die tasten, oder funzen nur noch wenn ihr übelst drauf haut...... oder lösen aus wenn nur nen staubkorn drauf landet...


----------



## grayson (29. Jul 2004)

streiche alles ab uten morgen, das came from funzt doch ! hehe, hatte einen aufruf vergessen. exzelent ! danke !


----------



## Isaac (29. Jul 2004)

Ich.hab.mich.mal.in.einem.Forum.krank.gelacht.weil.da.einer.so.geschrieben.hat.wie.ich.im.Moment..Als.man.ihn.fragte.wieso.sagte.er.das.seine.Leertaste.kaputt.ist


----------



## grayson (30. Jul 2004)

ok, back to java.

nachdem ich nun die berechnungen alle in sack und tüten hab, möchte ich die einheit auch fahren lassen. dazu hab ich eine arraylist mit abzufahrenden feldern. ich möchte nun das die einheit ins erste feld gezeichnet wird, dann ins 2te, dann im 1ten wieder löschen ect ect ect bis sie im zielfeld ankommt. leider geht das viel zu schnell und sieht eher nach warpen aus. wie bekomm ich eine verzögerung rein, die das ganze mehr nach animation aussehen lässt, ohne mir nen thread zu schreiben?


----------



## Roar (30. Jul 2004)

einfach.ein.Thread.sleep(200).einbauen


----------



## grayson (30. Jul 2004)

nö, net so richtig. er wartet dann die 200 und danah rauscht er durch....... ka wieso, eigendlich sollte er das ja bei jedem durchlauf der schleife einmal machen


----------



## Isaac (30. Jul 2004)

Code please, 

Wenn der sleep *im* Thread steht und *in* der Schleife ist wird er auch jedesmal dort warten. Zeich ma


----------



## grayson (30. Jul 2004)

hmm habs jetzt erstmal raus geschmissen, damit ich weiter komme, hab aber noch nen 2tes interessantes problem: wie kann ich ein bild drehen um sagen wir 45, oder 90 grad?

hier ist meine perform move methode, da sollte eigendlich das "fahren" rein


```
public void performMove(HexMapModel.Field dest) {

    dest.getProperties().setUnit(mUnitToDoAction);
   
// hier soll mal das einheitenbild einfach gedreht werden ( ka wie die methode aussehen könnte)
 turnImage(dest);
    mMap.getModel().getField(mSelected.x, mSelected.y).getProperties().setUnit(null);
// resette alle felder der karte
    for (int i = 0; i < mMap.getModel().fields.length; i++) {
      mMap.getModel().fields[i].getProperties().setPlainForegroundImage(null);
      mMap.repaint();
    }
// hier wären die felder drinn für das schrittweise fahren der einheit. resette ich an dieser stelle nur, da ich es ja nicht eingebaut hab    
mFieldstoMove = new ArrayList();
  }
```


----------



## Illuvatar (30. Jul 2004)

grayson hat gesagt.:
			
		

> hmm habs jetzt erstmal raus geschmissen, damit ich weiter komme, hab aber noch nen 2tes interessantes problem: wie kann ich ein bild drehen um sagen wir 45, oder 90 grad?



Über das AffineTransform-Objekt von einem Graphics2D.


----------



## grayson (31. Jul 2004)

fein, ich benötige eine methode, bei der ich wie bei "getScaledInstance(h,w)" ein neues Image zurück bekomme um es der einheit als bild zu geben.

wie bekomm ich das mit dem graphics2d dingen hin? hab das leider noch nie gemacht


----------

