You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

207 lines
6.4 KiB
Plaintext

/*class*/import java.util.ArrayList;
public class Search{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Eigenschaften / Protperties
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
private Hamster sh;
// Spielfeldgröße
private int fieldRow = Territorium.getAnzahlReihen();
private int fieldCol = Territorium.getAnzahlSpalten();
// Start- und Ziel-Feld
private Field goal;
private Field start;
// Arrays zum halten von Informationen.
private ArrayList<Field> queue = new ArrayList<Field>();
private ArrayList<Field> visited = new ArrayList<Field>();
boolean bInVisited = false;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Public Methoden und Konstruktoren
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Konstruktor -> zu bewegenden Hamster erforderlich
public Search(Hamster h){
sh = h;
}
// Initialisiern und ermitteln der Start- und Zielposition
public boolean init(){
// Startfeld kann immer gefunden werden
getStart();
// Wenn kein oder mehrere Körner gefunden wurden, sollte ein Fehler ausgegeben werden;
return getGrainField();
}
// Pfad ermitteln
public Field findPath(){
return searchPathToGrain();
}
// Pfad laufen und Korn aufnehmen
public boolean walkPathGetKorn(Field goalField){
walkByPath(getPath(goalField));
if(sh.kornDa()){
sh.nimm();
return true;
}
return false;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Ermitteln des Weges mit Breitensuche
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
private Field searchPathToGrain(){
// ersten Knoten/Hamster in queue stellen
queue.add(start);
// Solange queue nicht leer, Schleife durchlaufen
while(queue.size() > 0){
// Aktuelles Feld nehmen und aus queue entfernen
Field currField = queue.get(0);
queue.remove(0);
// Feld auf Liste der besuchten Felder setzten
visited.add(currField);
// Wenn Ziel gefunden Fled zurückgeben
if(currField.column == goal.column && currField.row == goal.row){
return currField;
}
// Freie Nachbarfelder ermitteln.
ArrayList<Field> freeNeighbours = getFreeNeighbours(currField);
for(int i = 0; i<freeNeighbours.size(); i++){
// prüfen ob Nachbarfeld nicht schon besucht wurde...
bInVisited = false;
for(Field visitedField : visited){
if(visitedField.column == freeNeighbours.get(i).column && visitedField.row == freeNeighbours.get(i).row){
bInVisited = true;
break;
}
}
// ...wenn nicht bearbeiten
if(!bInVisited){
// Nachbar an queue hinzufügen
queue.add(freeNeighbours.get(i));
freeNeighbours.get(i).parent = currField;
visited.add(freeNeighbours.get(i));
}
}
}
// Wenn Ziel nich erreicht wurde...
return null;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Bewegung des Hamsters anhand eines Pfades.
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
private void walkByPath(ArrayList<Field> path){
// Aktuelle Hamsterpositions
Field curHamsterPos = start;
// Alle Felder des Pfades durchgehen und ablaufen
for(Field nextField : path){
// Links-Rechts-Bewegung
switch(nextField.column - curHamsterPos.column){
case 1: // nach rechts gehen
moveHamster(Hamster.OST);
break;
case -1: // nach links gehen
moveHamster(Hamster.WEST);
break;
}
// Hoch-Runter-Bewegung
switch(nextField.row - curHamsterPos.row){
case 1: // nach oben gehen
moveHamster(Hamster.SUED);
break;
case -1: // nach unten gehen
moveHamster(Hamster.NORD);
break;
}
// Hamsterposition aktualisieren
curHamsterPos = nextField;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Hilfsmethoden
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Pfad anhand der Paren-Child beziehung aus einem Feld aufbauen.
private ArrayList<Field> getPath(Field f){
boolean bStartFound = false;
ArrayList<Field> path = new ArrayList<Field>();
Field cf = f;
while(!bStartFound){
path.add(0,cf);
if(cf.parent == null)
bStartFound = true;
else
cf = cf.parent;
}
return path;
}
// Feld ermittlen, auf dem der Hamster aktuell sitzt
private void getStart(){
start = new Field(sh.getSpalte(), sh.getReihe());
}
// Feld ermitteln, auf dem das Korn liegt
private boolean getGrainField(){
int grainCounter = 0;
//Ermitteln, auf welchem Feld das Korn liegt
for(int col=0; col < fieldCol; col++){ // Spalten durchgehen
for(int row=0; row < fieldRow; row++){ // Reihe durchgehen
if(Territorium.getAnzahlKoerner(row,col) > 0 ){
goal = new Field(col,row); // Zielkoordinate setzen und Schleife abbrechen
grainCounter++;
}
}
}
if(grainCounter == 1){
return true;
}
return false;
}
// Rotiert den Hamster in eine definierte Blickrichtung und bewegt ihn einen schritt vor.
private void moveHamster(int blickrichtung){
boolean moved = false;
while(!moved){
if(sh.getBlickrichtung() == blickrichtung){
sh.vor();
moved = true;
}
else {
sh.linksUm();
}
}
}
// Freie Nachbarfelder für Field cf ermitteln
private ArrayList<Field> getFreeNeighbours(Field cf){
ArrayList<Field> neigbours = new ArrayList<Field>();
// Feld oben prüfen
if(!Territorium.mauerDa(cf.row-1, cf.column)){
neigbours.add(new Field(cf.column, cf.row-1));
}
// Feld rechts prüfen)
if(!Territorium.mauerDa(cf.row, cf.column+1)){
neigbours.add(new Field(cf.column+1, cf.row));
}
// Feld unten prüfen)
if(!Territorium.mauerDa(cf.row+1, cf.column)){
neigbours.add(new Field(cf.column, cf.row+1));
}
// Feld links prüfen
if(!Territorium.mauerDa(cf.row, cf.column-1)){
neigbours.add(new Field(cf.column-1, cf.row));
}
return neigbours;
}
}