comments added

[schiebespiel.git] / Knoten.java

/* Schiebespiel - effectively computes solution for a one player board game
 * Copyright (C) 2007  Dirk Ribbroch / Martin Drohmann
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *  
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
import java.util.*;

/**
 * Knoten repräsentiert einen Zustand des Spielfeldes.
 */
public class Knoten implements Comparable<Knoten> {
    public static final int leer=0;
    public static final int einer=1;
    public static final int zweier_rechts=2;
    public static final int zweier_links=3;
    public static final int zweier_oben=4;
    public static final int zweier_unten=5;
    public static final int vierer_ro=6;
    public static final int vierer_ru=7;
    public static final int vierer_lo=8;
    public static final int vierer_lu=9;
    public static final int nicht_leer=21;
    public static final int HEURISTIK_SIMPEL=0;
    private static int HeuristikTyp = 0;
    private static Knoten ziel;
    private static Knoten start;

    /**
     * Setzt den Typ der Heuristik, nach der Knoten bewertet werden sollen. Die
     * Standardheuristik ist 0 (=HEURISTIK_SIMPEL)
     */
    public static void SetHeuristikTyp(int typ) {
        HeuristikTyp = typ;
    }

    /** 
     * Gibt eine Kopie des aktuellen Spielfeldzustands zurück.
     * @return Spielfeldkopie
     */
    private int[][] getSpielfeldKopie() {
        int[][] neu = new int[5][4];
        for (int i=0; i<5; ++i) {
            System.arraycopy( spielfeld[i], 0, neu[i], 0, 4 );
        }
        return neu;
    }

    /** 
     * Überprüft, ob der this Knoten mit dem Knoten k übereinstimmt.
     * @param k Knoten mit dem der this Knoten verglichen wird.
     */
    public boolean is_clone(Knoten k) {
        for (int x = 0; x < spielfeld.length; ++x) {
            for (int y = 0; y < spielfeld[0].length; ++y) {
                if(this.get_field(x,y) != k.get_field(x,y)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Fügt den Knoten einer Liste von Knoten liste hinzu. Falls ein Klon
     * dieses Knotens bereits in der Liste existiert, wird der Knoten mit der
     * geringeren Tiefe gelöscht.
     * @param liste Eine LinkedList von Knoten, der der this Knoten hinzugefügt
     * wird.
     */
    public void add_dublikatfrei(LinkedList<Knoten> liste) {
        for (Knoten k: liste) {
            if (is_clone(k)) {
                if (k.get_tiefe() <= get_tiefe()) {
                    return;
                } else {
                    liste.remove(k);
                    liste.add(this);
                    return;
                }
            }
        }
        liste.add(this);
    }

    /**
     * Überprüft, ob wir ein Klon eines unserer Elterknotens sind.
     * @return Wahrheitswert
     */
    public boolean is_reinkarnation() {
        Knoten k = this;
        while (k.get_parent() != null) {
            k = k.get_parent();
            boolean equal=true;
            for (int x = 0; x < spielfeld.length; ++x) {
                for (int y = 0; y < spielfeld[0].length; ++y) {
                    if(this.get_field(x,y) != k.get_field(x,y)) {
                        equal = false;
                    }
                }
            }
            if(equal) {
                return true;
            }
        }
        return false;
    }
    
    /**
     * Berechnet eine Heuristik zu dem Knoten, abhängig davon, wie der
     * derzeitige Heuristik Typ gesetzt wurde.  
     * @return die Bewertung
     */
    private int compute_heuristik() {
        switch(HeuristikTyp) {
            case HEURISTIK_SIMPEL:
                return heuristik_simpel();
        }
        /* Default: */
        return heuristik_simpel();
    }

    /**
     * Eine sehr einfache Heuristik, die einen Knoten mit 1 bewertet, falls er
     * vom Zielknoten abweicht, und andernfalls mit 0 bewertet. Ein A*
     * Algorithmus würde somit zu einer Breitensuche degenerieren.
     */
    private int heuristik_simpel() {
        for(int x = 0; x < spielfeld.length; ++x) {
            for(int y = 0; y < spielfeld[0].length; ++y) {
                if(spielfeld[x][y] != ziel.get_field(x,y)) {
                    return 1;
                }
            }
        }
        return 0;
    }

    /**
     * Setzt den Zielzustand.
     */
    public static void set_ziel(Knoten ziel) {
        Knoten.ziel = ziel;
    }

    /**
     * Setzt den Startzustand.
     */
    public static void set_start(Knoten start) {
        Knoten.start = start;
    }


    /**
     * Erstellt einen leeren Knoten. Dies ist nur für Start- und Endknoten von
     * Interesse. 
     */
    public Knoten() {
        this.parent    = null;
        this.heuristik = 0;
        this.tiefe     = 0;
    }

    /** Erstellt einen Knoten aus einem Elterknoten nach folgendem Verfahren.
     * Das Array bfield wird über das Spielfeld um die in offset gegebenen
     * Koordinaten verschoben, und die "darunterliegenden" Werte des
     * Elterknotens mit denen aus bfield überschrieben. 
     * @param parent Der Elterknoten
     * @param offset Offsetkoordinaten für bfield (s.Beschreibung)
     * @param bfield Die zu ersetzenden Koordinaten
     */
    public Knoten(Knoten parent, int[] offset, int[][] bfield) {
        this.parent    = parent;
        this.tiefe     = parent.get_tiefe() + 1;
        this.spielfeld = parent.getSpielfeldKopie();
        for(int x = 0; x < bfield.length; ++x) {
            for(int y = 0; y < bfield[0].length; ++y) {
                this.spielfeld[offset[0] + x][offset[1] + y] = 
                    bfield[x][y];
            }
        }
        int count=0;
        for(int x = 0; x < spielfeld.length; ++x) {
            for(int y = 0; y < spielfeld[0].length; ++y) {
                if(spielfeld[x][y] == leer) {
                    set_leere(count, x, y);
                    count++;
                }
            }
            if(count == 2) {
                set_leere(2,-1,-1);
                set_leere(3,-1,-1);
            }
        }
        this.heuristik = compute_heuristik();
    }

    /** 
     * Vergleicht die Heuristik mit der Heuristik des Knotens k
     */
    public int compareTo(Knoten k) {
        return new Integer(this.heuristik).compareTo(new 
                Integer(k.heuristik));
    }

    Knoten parent;
    int[][] spielfeld = new int[5][4];
    int heuristik;
    int tiefe;
    int[][] leere = new int[4][2];

    /**
     * Gibt die Tiefe des Knotens im Baum zurück.
     */
    int get_tiefe() {
        return tiefe;
    }

    /**
     * Gibt den Elterknoten zurück.
     */
    Knoten get_parent() {
        return parent;
    }

    /**
     * Gibt die Stein-ID des Spielfelds an der Stelle (x,y) zurück.
     */
    int get_field(int x, int y) {
        return spielfeld[x][y];
    }

    /**
     * Gibt die Koordinaten des leeren Feldes mit dem Index index zurück. (Die
     * leeren Felder sind willkürlich durchnummeriert.) 
     * @param index Index des leeren Feldes, welches zurückgegeben werden soll.
     * (0-3)
     */
    int[] get_leere(int index) {
        return leere[index];
    }

    void set_field(int x, int y, int value) {
        spielfeld[x][y] = value;
    }

    void set_leere(int index, int x, int y) {
        leere[index][0] = x;
        leere[index][1] = y;
    }

    /**
     * Gibt das Spielfeld in einer menschen-lesbaren Form aus.
     */
    public String toString() {
        String ret = new String();
        for (int y = spielfeld[0].length - 1; y >= 0; --y) {
            for (int x = 0; x < spielfeld.length; ++x) {
                ret += "" + get_field(x, y) + " ";
            }
            ret+="\n";
        }
        return ret;
    }
}

class Koordinate
{
    private Transitions trs = new Transitions();
    private Knoten start;
    private Knoten knoten;
    private LinkedList<Knoten> elter= new LinkedList<Knoten>();
    private LinkedList<Integer> koordinaten = new 
        LinkedList<Integer>();
    private LinkedList<Knoten> tempList = new LinkedList<Knoten>();
    public Koordinate(Knoten start)
    {
        this.start = start;
        this.knoten = start;
        this.elter.add(start);
        koordinaten.clear();
    }

    public void succ()
    {
        int temp=0;
        int tiefe=0;
        if (koordinaten.size()==0)
            // Koordiante neu erstellt, wir befinden uns an der Wurzel
            {
                koordinaten.add(0);
                tempList = trs.expandKnoten(elter.getLast());
                knoten = tempList.get(0);
                return;
            }
        if (koordinaten.getLast() < tempList.size()-1)
            //Es gibt auf dieser Ebene noch weitere Knoten zu denen verzweigt werden kann
            {
                temp=koordinaten.removeLast();
                koordinaten.addLast(temp+1);
                knoten=tempList.get(koordinaten.getLast());
            }
        else
            //Ebene zu Ende, eins zurück, erhöhen und wieder vor
        {
            tiefe=koordinaten.size();
            //solang zurückgehen wie es keine weiteren kannten am elterknoten gibt
                while(koordinaten.getLast() >= tempList.size()-1)
                {
                    koordinaten.removeLast();
                    knoten=elter.removeLast();
                    tempList=trs.expandKnoten(knoten);
                }
            // hier fehlt noch, wenn man wieder an der wurzel ist muss die koordinatenlänge(tiefe) um eins erhöht werden und dann halt koord= 0,0,0,0...
                if (koordinaten.size()==0)
                {

                }
                else
                {
                    //dieser elter hat noch unerreichte kinder, koordinate um eins erhöhen
                        temp=koordinaten.removeLast();
                    koordinaten.addLast(temp+1);
                    //wieder runtergehen jeweils den linkesten ast nehmend
                    while (koordinaten.size()<tiefe)
                    {
                        koordinaten.add(0);
                        elter.add(knoten);
                        knoten=tempList.get(koordinaten.getLast());
                    }
                }

        }



    }
    public Knoten getKnoten()
    {
        return knoten;
    }

}