- schiebe4 hinzugefügt

[schiebespiel.git] / Knoten.java

/* Schiebespiel - effectively computes solution for a one player board game
 * Copyright (C) 2007  Dirk Ribbrock / 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;
    public static final int HEURISTIK_DIFFERENZ=1;
    public static final int HEURISTIK_LUFT=2;
    private static int HeuristikTyp = 0;
    private static Knoten ziel;
    private static Knoten start;
    private static MinSchritte ms;

    /**
     * Setzt den Typ der Heuristik, nach der Knoten bewertet werden sollen. Die
     * Standardheuristik ist 0 (=HEURISTIK_SIMPEL), 1(HEURISTIK_DIFFERENZ), 2(HEURISTIK_LUFT)
     */
    public static void setHeuristikTyp(int typ) {
            if(typ == HEURISTIK_LUFT) {
                    ms = new MinSchritte(ziel);
            }
        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
     */
    public void computeHeuristik() {
        switch(HeuristikTyp) {
            case HEURISTIK_SIMPEL:
                this.heuristik = heuristik_simpel();
                                break;
                case HEURISTIK_DIFFERENZ:
                                this.heuristik = heuristik_differenz();
                                break;
                        case HEURISTIK_LUFT:
                                this.heuristik = heuristik_luft();
                                break;
                        default:
                /* Default: */
                                this.heuristik = heuristik_simpel();
                                break;
                }
    }
    /**
     *Prüft ob der Knoten gleich dem Knoten k ist
     */
    public boolean is(Knoten k)
    {
        for(int x = 0; x < spielfeld.length; ++x) {
            for(int y = 0; y < spielfeld[0].length; ++y) {
                if(spielfeld[x][y] != k.get_field(x,y)) {
                    return false;
                }
            }
        }
        return true;
        
    }
    
    /**
     * 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;
    }

    /**
     * Eine einfache Heuristik, die einen Knoten mit der Anzahl der abweichenden Zellen                 bewertet, und           andernfalls mit 0 bewertet. A* ist also hiermit sehr zielgerichtet 
     */
    private int heuristik_differenz() {
        int differenzen=0;
        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)) {
                    differenzen++;
                }
            }
        }
                if (differenzen==0) return 0; // knoten sind identisch
        if (this.get_tiefe()>18) return 100; // wir sind zu tief
                //mit der tiefe des knotens verrechnen
                //differenzen = (int)(differenzen + (float)(10/this.get_tiefe()));
                
                return differenzen;
    }

    /**
     * Eine einfache Heuristik, die einen Knoten mit der Anzahl notwendigen Schritte in Luftlinie bewertet
     */
    private int heuristik_luft() {
                return get_tiefe() + ms.computeLuftlinie(this);
    }

    public int[][] get_spielfeld() {
            return spielfeld;
    }
    
    public static Knoten getZiel()
    {
        return Knoten.ziel;
    }
    
    public static Knoten getStart()
    {
        return Knoten.start;
    }

    /**
     * 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);
            }
        }
        computeHeuristik();
    }

    /** 
     * 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 Heuristikwert des Knotens zurück.
        */
    int get_heuristik() {
                return heuristik;
    }

    /**
     * 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;
    }
}