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
  21 /**
  22  * Diese statische Klasse verwaltet alle möglichen Zugmöglichkeiten, die von
  23  * uns "Transition"en genannt werden. Sie stellt über die Methode expand_knoten
  24  * ein Interface her, um alle möglichen Folgeknoten eines Knotens zu berechnen.
  25  */
  26 public class Transitions {
  27
  28     /**
  29      * Transition = Zugmöglichkeit
  30      */
  31     class Transition {
  32         private int[][] a,b, leer;
  33         private int x,y;
  34         private int n_leer;
  35         /**
  36          * Dieser Konstruktor initialisert eine Transition von Zustand a in
  37          * Zustand b, der Breite x und Höhe y. Die Zustandsarrays werden
  38          * zeilenweise eingelesen.
  39          * @param a Startzustand
  40          * @param b Endzustand
  41          * @param x Breite der Transition
  42          * @param y Höhe der Transition
  43          */
  44         public Transition(int[] a, int[] b, int x, int y) {
  45             this.a=new int[x][y];
  46             this.b=new int[x][y];
  47             this.x=x;
  48             this.y=y;
  49             for (int i = 0; i < x; ++i) {
  50                 for(int j = 0; j < y; ++j) {
  51                     this.a[i][j] = a[i + j*x];
  52                     this.b[i][j] = b[i + j*x];
  53                 }
  54             }
  55             int count = 0;
  56             this.n_leer = (x < y ? x : y);
  57             this.leer = new int[this.n_leer][2];
  58             for(int i = 0; i < a.length; ++i) {
  59                 if(a[i] == Knoten.leer) {
  60                     this.leer[count][0] = i % x;
  61                     this.leer[count][1] = i / x;
  62                     ++count;
  63                 }
  64             }
  65         }
  66
  67         /**
  68          * Gibt einen Punkt des Startzustands aus.
  69          * @param x,y Koordinaten des Punktes
  70          * @return Wert des Startzustands. (Stein-ID)
  71          */
  72         public int get_afield(int x, int y) {
  73             return a[x][y];
  74         }
  75
  76         /**
  77          * Gibt den Endzustand zurück.
  78          * @return Endzustand
  79          */
  80         public int[][] get_bfield() {
  81             return b;
  82         }
  83
  84         /**
  85          * Gibt die x-Koordinate des leeren Feldes mit Index index zurück.
  86          * Leere Felder sind (willkürlich) durchnummeriert.
  87          * @param index Index des leeren Feldes (0-1)
  88          * @return x-Koordinate des Feldes
  89          */
  90         public int get_leer_x(int index) {
  91             return leer[index][0];
  92         }
  93         /**
  94          * Gibt die y-Koordinate des leeren Feldes mit Index index zurück.
  95          * Leere Felder sind (willkürlich) durchnummeriert.
  96          * @param index Index des leeren Feldes (0-1)
  97          * @return y-Koordinate des Feldes
  98          */
  99         public int get_leer_y(int index) {
 100             return leer[index][1];
 101         }
 102         /**
 103          * Gibt die Breite der Transition zurück
 104          * @return Breite
 105          */
 106         public int get_width() {
 107             return x;
 108         }
 109         /**
 110          * Gibt die Höhe der Transition zurück
 111          * @return Höhe
 112          */
 113         public int get_height() {
 114             return y;
 115         }
 116         /**
 117          * Gibt die Anzahl der leeren Elemente in der Transition zurück.
 118          * @return Anzahl (1-2)
 119          */
 120         public int get_n_leer() {
 121             return n_leer;
 122         }
 123     }
 124     /* Initialisiere Liste mit Transitionen */
 125     static Transition[] transitions = new Transition[12];
 126
 127     /**
 128      * Berechnet die möglichen Folgezustände eines Knoten, und gibt diese in
 129      * einem LinkedList Container zurück.
 130      * @param k Knoten, dessen Folgezustände berechnet werden.
 131      * @return LinkedList der Folgezustände.
 132      */
 133     public static LinkedList<Knoten> expandKnoten(Knoten k) {
 134
 135         LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
 136
 137 transition:
 138         for(Transition tr: transitions) {
 139             for(int i = 0; i < 4; ++i) {
 140                 int[] off1 = k.get_leere(i);
 141                 /*                System.out.println("leere: " + i + " " + off1[0] + " "
 142                                   + off1[1]); */
 143                 if(off1[0] == -1) {
 144                     continue transition;
 145                 }
 146 position:
 147                 for(int ii = 0; ii < tr.get_n_leer(); ++ii) {
 148                     int[] offset = new int[2];
 149                     offset[0] = off1[0] - tr.get_leer_x(ii);
 150                     offset[1] = off1[1] - tr.get_leer_y(ii);
 151                     if(offset[0] < 0 || offset[1] < 0
 152                             || offset[0] + tr.get_width() > 5
 153                             || offset[1] + tr.get_height() > 4) {
 154                         continue;
 155                             }
 156                     for(int x = 0; x < tr.get_width(); ++x) {
 157                         for(int y = 0; y < tr.get_height(); ++y) {
 158                             if( k.get_field(offset[0] + x, offset[1] + y)
 159                                     != tr.get_afield(x,y) ) {
 160                                 continue position;
 161                                     }
 162                         }
 163                     }
 164                     /* Wenn wir hier sind, dann haben wir was gefunden.*/
 165                     Knoten neuerKnoten = new Knoten(k, offset,
 166                             tr.get_bfield());
 167                     /*        System.out.println(neuerKnoten);*/
 168                     neuerKnoten.add_dublikatfrei(knotenListe);
 169
 170                 }
 171             }
 172
 173             /* Speziellste Transition von Welt! */
 174             if( k.get_field(0,1) == Knoten.vierer_ru && k.get_field(0,2)
 175                     == Knoten.vierer_ro && k.get_field(1,1) == Knoten.leer
 176                     && k.get_field(1,2) == Knoten.leer ) {
 177                 int[][] a = { { Knoten.vierer_lo, Knoten.vierer_ro },
 178                     { Knoten.vierer_lu, Knoten.vierer_ru } };
 179                 int[] offset = { 0,1 };
 180                 Knoten neuerKnoten = new Knoten(k, offset, a);
 181                 neuerKnoten.add_dublikatfrei(knotenListe);
 182             }
 183             if( k.get_field(0,1) == Knoten.vierer_lu && k.get_field(0,2) ==
 184                     Knoten.vierer_lo && k.get_field(1,1) == Knoten.vierer_ru &&
 185                     k.get_field(1,2) == Knoten.vierer_ro ) {
 186                 int[][] a = { { Knoten.vierer_ru, Knoten.vierer_ro },
 187                     { Knoten.leer, Knoten.leer } };
 188                 int[] offset = { 0,1 };
 189                 Knoten neuerKnoten = new Knoten(k, offset, a);
 190                 neuerKnoten.add_dublikatfrei(knotenListe);
 191             }
 192         }
 193
 194         Collections.sort(knotenListe);
 195         return knotenListe;
 196     }
 197
 198     public Transitions() {
 199         int[] a = {Knoten.einer, Knoten.leer};
 200         int[] b = {Knoten.leer, Knoten.einer};
 201         transitions[0] = new Transition(a, b, 2,1);
 202         transitions[1] = new Transition(b, a, 2,1);
 203         transitions[2] = new Transition(a, b, 1,2);
 204         transitions[3] = new Transition(b, a, 1,2);
 205         int[] c = { Knoten.zweier_oben, Knoten.leer,
 206             Knoten.zweier_unten, Knoten.leer };
 207         int[] d = { Knoten.leer, Knoten.zweier_oben,
 208             Knoten.leer, Knoten.zweier_unten };
 209         transitions[4] = new Transition(c, d, 2,2);
 210         transitions[5] = new Transition(d, c, 2,2);
 211         int[] e = { Knoten.zweier_links, Knoten.zweier_rechts,
 212             Knoten.leer };
 213         int[] f = { Knoten.leer, Knoten.zweier_links,
 214             Knoten.zweier_rechts };
 215         transitions[6] = new Transition(e, f, 3,1);
 216         transitions[7] = new Transition(f, e, 3,1);
 217         int[] g = { Knoten.vierer_lo, Knoten.vierer_ro,
 218             Knoten.vierer_lu, Knoten.vierer_ru,
 219             Knoten.leer, Knoten.leer };
 220         int[] h = { Knoten.leer, Knoten.leer,
 221             Knoten.vierer_lo, Knoten.vierer_ro,
 222             Knoten.vierer_lu, Knoten.vierer_ru };
 223         transitions[8] = new Transition(g, h, 2,3);
 224         transitions[9] = new Transition(h, g, 2,3);
 225         int[] i = { Knoten.vierer_lo, Knoten.vierer_ro, Knoten.leer,
 226             Knoten.vierer_lu, Knoten.vierer_ru, Knoten.leer };
 227         int[] j = { Knoten.leer, Knoten.vierer_lo, Knoten.vierer_ro,
 228             Knoten.leer, Knoten.vierer_lu, Knoten.vierer_ru };
 229         transitions[10] = new Transition(i, j, 3,2);
 230         transitions[11] = new Transition(j, i, 3,2);
 231     }
 232 }