1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Manhatten-Distance in eindimensionalen Representationen von zweidimensionalen Arrays

Dieses Thema im Forum "Algorithmen & Datenstrukturen mit Java" wurde erstellt von Nimmer, 26. April 2012.

  1. Nimmer

    Nimmer Grünschnabel

    Hallo zusammen,

    erst einmal; hoffentlich habe ich einen passenden Namen für den Thread gewählt. Ich war mir nicht sicher wie ich es formulieren sollte.

    Momentan programmiere ich an einem kleinen Brettspiel. Das Spielbrett hat 5x5 Felder. So weit ja sehr simpel. Allerdings habe ich ein eindimensionales Array gewählt um das Spielfeld intern darzustellen, das Einzige auf das ich bis jetzt achten musste war die Umrechnung von zweidimensionalen Indizes auf einen eindimensionalen und darauf wie ich Nachbarfelder identifiziere (beides ist ja sehr einfach und hat keine Probleme bereitet).

    Jetzt bin ich aber auf ein Problem gestossen bei dem ich nicht so richtig weiter komme.
    Ich möchte unterschiedliche Bereiche des Spielfeldes identifizieren können. Die Bereiche möchte ich anhand der Entfernung zum Zentrum des Brettes unterscheiden. Als Abstand scheint sich Manhatten-Distance anzubieten.

    Aber ich habe keine Ahnung wie ich die auf dem eindimensionalen Array berechnen soll.

    Die Struktur wieder auf zweidimensional ändern möchte ich nicht da ich mit meiner Implementierung schon relativ weit bin und die Abstände nur für ein einziges Feature brauche.

    Schonmal danke fürs Lesen
    und danke im Voraus für eure Antworten
  2. genodeftest

    genodeftest Erfahrenes Mitglied

    Hi
    1. Warum nutzt du nicht ein 2dimensionales Array? Dafür sind höhere Programmiersprachen doch da. Oder willst du nicht gleich Assembler schreiben ;)
    2. Es gibt einen Modulo-Operator, in deinem Fall könnte man aus dem Index i die Zeilen und Spalten so berechnen:
    Code (Java):
    1. int spalte = i%5;
    2. int zeile = i/5;
    Damit kannst du dann einfach genauso vorgehen wie sonst bei der Berechnung der Manhattan-Distance. Also so:
    Code (Java):
    1. int source, dest; // Indizes im Array für die Start- und Zielposition, gegebene Parameter
    2. int distanceX = Math.abs(source%5-dest%5);
    3. int distanceY = Math.abs(source/5-dest/5);
    4. int distance = distanceX + distanceY;

Diese Seite empfehlen