Transitions.java

   1 /* Schiebespiel - effectively computes solution for a one player board game
   2  * Copyright (C) 2007  Dirk Ribbroch / Martin Drohmann
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18
  19 import java.util.*;
  20 import java.lang.*;
  21
  22 /**
  23  * Diese statische Klasse verwaltet alle möglichen Zugmöglichkeiten, die von
  24  * uns "Transition"en genannt werden. Sie stellt über die Methode expand_knoten
  25  * ein Interface her, um alle möglichen Folgeknoten eines Knotens zu berechnen.
  26  */
  27 public class Transitions {
  28
  29     /**
  30      * Transition = Zugmöglichkeit
  31      */
  32     class Transition {
  33         private int[][] a,b, leer;
  34         private int x,y;
  35         private int n_leer;
  36         /**
  37          * Dieser Konstruktor initialisert eine Transition von Zustand a in
  38          * Zustand b, der Breite x und Höhe y. Die Zustandsarrays werden
  39          * zeilenweise eingelesen.
  40          * @param a Startzustand
  41          * @param b Endzustand
  42          * @param x Breite der Transition
  43          * @param y Höhe der Transition
  44          */
  45         public Transition(int[] a, int[] b, int x, int y) {
  46             this.a=new int[x][y];
  47             this.b=new int[x][y];
  48             this.x=x;
  49             this.y=y;
  50             for (int i = 0; i < x; ++i) {
  51                 for(int j = 0; j < y; ++j) {
  52                     this.a[i][j] = a[i + j*x];
  53                     this.b[i][j] = b[i + j*x];
  54                 }
  55             }
  56             int count = 0;
  57             this.n_leer = (x < y ? x : y);
  58             this.leer = new int[this.n_leer][2];
  59             for(int i = 0; i < a.length; ++i) {
  60                 if(a[i] == Knoten.leer) {
  61                     this.leer[count][0] = i % x;
  62                     this.leer[count][1] = i / x;
  63                     ++count;
  64                 }
  65             }
  66         }
  67
  68         /**
  69          * Gibt einen Punkt des Startzustands aus.
  70          * @param x,y Koordinaten des Punktes
  71          * @return Wert des Startzustands. (Stein-ID)
  72          */
  73         public int get_afield(int x, int y) {
  74             return a[x][y];
  75         }
  76
  77         /**
  78          * Gibt den Endzustand zurück.
  79          * @return Endzustand
  80          */
  81         public int[][] get_bfield() {
  82             return b;
  83         }
  84
  85         /**
  86          * Gibt die x-Koordinate des leeren Feldes mit Index index zurück.
  87          * Leere Felder sind (willkürlich) durchnummeriert.
  88          * @param index Index des leeren Feldes (0-1)
  89          * @return x-Koordinate des Feldes
  90          */
  91         public int get_leer_x(int index) {
  92             return leer[index][0];
  93         }
  94         /**
  95          * Gibt die y-Koordinate des leeren Feldes mit Index index zurück.
  96          * Leere Felder sind (willkürlich) durchnummeriert.
  97          * @param index Index des leeren Feldes (0-1)
  98          * @return y-Koordinate des Feldes
  99          */
 100         public int get_leer_y(int index) {
 101             return leer[index][1];
 102         }
 103         /**
 104          * Gibt die Breite der Transition zurück
 105          * @return Breite
 106          */
 107         public int get_width() {
 108             return x;
 109         }
 110         /**
 111          * Gibt die Höhe der Transition zurück
 112          * @return Höhe
 113          */
 114         public int get_height() {
 115             return y;
 116         }
 117         /**
 118          * Gibt die Anzahl der leeren Elemente in der Transition zurück.
 119          * @return Anzahl (1-2)
 120          */
 121         public int get_n_leer() {
 122             return n_leer;
 123         }
 124     }
 125     /* Initialisiere Liste mit Transitionen */
 126     static Transition[] transitions = new Transition[16];
 127
 128     /**
 129      * Berechnet die möglichen Folgezustände eines Knoten, und gibt diese in
 130      * einem LinkedList Container zurück.
 131      * @param k Knoten, dessen Folgezustände berechnet werden.
 132      * @return LinkedList der Folgezustände.
 133      */
 134     public static LinkedList<Knoten> expandKnoten(Knoten k) {
 135
 136         LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
 137
 138 transition:
 139         for(Transition tr: transitions) {
 140             for(int i = 0; i < 4; ++i) {
 141                 int[] off1 = k.get_leere(i);
 142                 /*                System.out.println("leere: " + i + " " + off1[0] + " "
 143                                   + off1[1]); */
 144                 if(off1[0] == -1) {
 145                     continue transition;
 146                 }
 147
 148 position:
 149                 for(int ii = 0; ii < tr.get_n_leer(); ++ii) {
 150                     int[] offset = new int[2];
 151                     offset[0] = off1[0] - tr.get_leer_x(ii);
 152                     offset[1] = off1[1] - tr.get_leer_y(ii);
 153                     if(offset[0] < 0 || offset[1] < 0
 154                             || offset[0] + tr.get_width() > 5
 155                             || offset[1] + tr.get_height() > 4) {
 156                                                 continue;
 157                                         }
 158                                         for(int x = 0; x < tr.get_width(); ++x) {
 159                         for(int y = 0; y < tr.get_height(); ++y) {
 160                                                         if( k.get_field(offset[0] + x, offset[1] + y)
 161                                                                         != tr.get_afield(x,y) ) {
 162                                                                 continue position;
 163                                                         }
 164                         }
 165                     }
 166                     /* Wenn wir hier sind, dann haben wir was gefunden.*/
 167                     Knoten neuerKnoten = new Knoten(k, offset,
 168                             tr.get_bfield());
 169                                         /*System.out.println(neuerKnoten); */
 170                                         /*    try {
 171                                                   Thread.sleep(500);
 172                                                   }     catch(Exception e) {} */
 173                                         neuerKnoten.add_dublikatfrei(knotenListe);
 174
 175                                 }
 176                         }
 177                 }
 178
 179                 /* Speziellste Transition von Welt! */
 180                 if( k.get_field(0,1) == Knoten.vierer_ru && k.get_field(0,2)
 181                                 == Knoten.vierer_ro && k.get_field(1,1) == Knoten.leer
 182                                 && k.get_field(1,2) == Knoten.leer )
 183                 {
 184
 185                         int[][] a = { { Knoten.vierer_lo, Knoten.vierer_ro },
 186                                 { Knoten.vierer_lu, Knoten.vierer_ru } };
 187                         int[] offset = { 0,1 };
 188                         Knoten neuerKnoten = new Knoten(k, offset, a);
 189                         neuerKnoten.add_dublikatfrei(knotenListe);
 190                 }
 191                 if( k.get_field(0,1) == Knoten.vierer_lu
 192                                 && k.get_field(0,2) == Knoten.vierer_lo
 193                                 && k.get_field(1,1) == Knoten.vierer_ru
 194                                 && k.get_field(1,2) == Knoten.vierer_ro )
 195                 {
 196
 197                         int[][] a = { { Knoten.vierer_ru, Knoten.vierer_ro },
 198                                 { Knoten.leer, Knoten.leer } };
 199                         int[] offset = { 0,1 };
 200                         Knoten neuerKnoten = new Knoten(k, offset, a);
 201                         //      System.out.println(neuerKnoten.toString());
 202                         neuerKnoten.add_dublikatfrei(knotenListe);
 203                 }
 204
 205
 206         Collections.sort(knotenListe);
 207         return knotenListe;
 208     }
 209
 210     public Transitions() {
 211         int[] a = {Knoten.einer, Knoten.leer};
 212         int[] b = {Knoten.leer, Knoten.einer};
 213         transitions[0] = new Transition(a, b, 2,1);
 214         transitions[1] = new Transition(b, a, 2,1);
 215         transitions[2] = new Transition(a, b, 1,2);
 216         transitions[3] = new Transition(b, a, 1,2);
 217         int[] c = { Knoten.zweier_unten, Knoten.leer,
 218             Knoten.zweier_oben, Knoten.leer };
 219         int[] d = { Knoten.leer, Knoten.zweier_unten,
 220             Knoten.leer, Knoten.zweier_oben };
 221         transitions[4] = new Transition(c, d, 2,2);
 222         transitions[5] = new Transition(d, c, 2,2);
 223         int[] e = { Knoten.zweier_links, Knoten.zweier_rechts,
 224             Knoten.leer };
 225         int[] f = { Knoten.leer, Knoten.zweier_links,
 226             Knoten.zweier_rechts };
 227         transitions[6] = new Transition(e, f, 3,1);
 228         transitions[7] = new Transition(f, e, 3,1);
 229         int[] g = { Knoten.vierer_lo, Knoten.vierer_ro,
 230             Knoten.vierer_lu, Knoten.vierer_ru,
 231             Knoten.leer, Knoten.leer };
 232         int[] h = { Knoten.leer, Knoten.leer,
 233             Knoten.vierer_lo, Knoten.vierer_ro,
 234             Knoten.vierer_lu, Knoten.vierer_ru };
 235         transitions[8] = new Transition(g, h, 2,3);
 236         transitions[9] = new Transition(h, g, 2,3);
 237         int[] i = { Knoten.vierer_lu, Knoten.vierer_ru, Knoten.leer,
 238             Knoten.vierer_lo, Knoten.vierer_ro, Knoten.leer };
 239         int[] j = { Knoten.leer, Knoten.vierer_lu, Knoten.vierer_ru,
 240             Knoten.leer, Knoten.vierer_lo, Knoten.vierer_ro };
 241         transitions[10] = new Transition(i, j, 3,2);
 242         transitions[11] = new Transition(j, i, 3,2);
 243         int[] k = { Knoten.zweier_unten, Knoten.zweier_oben,
 244             Knoten.leer };
 245         int[] l = { Knoten.leer, Knoten.zweier_unten,
 246             Knoten.zweier_oben };
 247         transitions[12] = new Transition(k, l, 1,3);
 248         transitions[13] = new Transition(l, k, 1,3);
 249         int[] m = { Knoten.zweier_links, Knoten.zweier_rechts,
 250             Knoten.leer, Knoten.leer };
 251         int[] n = { Knoten.leer, Knoten.leer,
 252             Knoten.zweier_links, Knoten.zweier_rechts};
 253         transitions[14] = new Transition(m, n, 2,2);
 254         transitions[15] = new Transition(n, m, 2,2);
 255     }
 256 }