Labyrinth Java < Softwaretechnik+Pro < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:26 So 25.04.2010 | | Autor: | matheja |
| Aufgabe | Moin moin
Ich brauch hilfe bei folgender Aufgabe:
In dieser Aufgabe sollen sie eine rekursive Methode realisieren, die einen Weg von einem vorgegebenen Startpunkt zu einem vorgegebenen Zielpunkt in einem Labyrinth findet.
Das Labyrinth wird modelliert durch ein zweidimensionales Feld mit int Werten. Der Wert 0 repräsentiert ein leeres Feld, der Wert 9 repräsentiert eine Blockade, d.h. über dieses Feld kann kein Weg führen. In einemSchritt kann einWeg zumrechtenNachbarfeld, zumunteren
Nachbarfeld, zum linken Nachbarfeld oder zum oberen Nachbarfeld führen.
Beispiel:
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 9 0 9 0 9
2 0 0 9 0 0 0
3 9 0 9 0 9 9
4 0 0 9 0 0 0
5 0 9 0 9 0 0
EinWeg soll in dem Feld wie folgt markiert werden:
1: DerWeg geht nach rechts
2: DerWeg geht nach unten
3: DerWeg geht nach links
4: DerWeg geht nach oben
5: DerWeg endet, da das Ziel erreicht ist
EinWeg von (5,0) (Startfeld) nach (5,5) (Zielfeld) kann damit wie folgt angegeben werden:
0 1 2 3 4 5
0 1 1 1 1 2 0
1 4 9 0 9 2 9
2 4 3 9 2 3 0
3 9 4 9 2 9 9
4 1 4 9 1 1 2
5 4 9 0 9 0 5
Implementieren sie eine rekursive Methode, die einen Weg von einem gegebenen Startfeld zu einem gegebenen Zielfeld wie oben angegeben markiert, wenn es einen Weg gibt. Wenn es keinenWeg gibt, so soll die Methode dies erkennen.
Wichtig: Es ist nicht gefordert, einen kürzesten Weg zu finden. Es genügt, irgendeinen Weg
zu finden.
Testen Sie IhreMethodemit geeigneten Beispielen undmit einer passendenmain -Methode,
so dass sich eine ausführbare Klasse ergibt. |
So,
Ich hab n bissl im netz gestöbert und hab folgenden Java Code zu einem Labyrinth gefunden.Traurigerweise ist er zu kompliziert für mich.Ich hoffe euch wir bekommen das ganze einfacher hin :)
package Labyrinth;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
public class Labyrinth extends Applet implements ActionListener
{
static final int anzx=5;
static final int anzy=5;
Button initB = new Button("Initialisieren");
Button startB = new Button("Das Ziel suchen");
Graphics g;
Canvas can = new Canvas();
boolean[][]V=new boolean[anzx][anzy];
boolean[][]H=new boolean[anzx][anzy];
boolean[][]Z=new boolean[anzx][anzy];
boolean problemGeloest = false;
int startX, startY, zielX, zielY;
Panel pN= new Panel();
Panel pZ= new Panel();
public void init()
{ resize(410,410);
can.setSize(410,410);
this.setLayout(new BorderLayout(5,5));
pN.add(initB);
pN.add(startB);
pZ.add(can);
can.setBackground(Color.blue);
this.add("North",pN);
this.add("Center",pZ);
initB.addActionListener(this);
startB.addActionListener(this);
}
public void actionPerformed(ActionEvent e)
{ Object quelle = e.getSource();
if (quelle == initB)
{ initialisiere();
g = can.getGraphics();
zeichne(g);
}
else if (quelle == startB)
{ problemGeloest = false;
backtracking(new Punkt(0,0));
g.dispose();
}
} //actionPerformed
void initialisiere()
{ for(int a=0;a<anzx;a++)
{ for(int b=0;b<anzy;b++)
{ Z[a][b]=false;
double z=Math.random();
if(z>0.72)
{ V[a][b]=false;}
else
{ V[a][b]=true;}
z =Math.random();
if(z>0.72)
{ H[a][b]=false;}
else
{ H[a][b]=true;}
}
}
for (int k=0; k<anzx; k++)
{ H[k][0]=false;
H[k][anzy-1]=false;
V[k][anzy-1]=true;
}
for (int k=0; k<anzy; k++)
{ V[0][k]=false;
H[anzx-1][k]=true;
V[anzx-1][k]=false;
}
H[0][0]=false;
H[0][anzy-1]=false;
Z[0][0]=true;
zielX = anzx-2; zielY = anzy-2;
} //initialisiere
void zeichne(Graphics g)
{ g.setColor(Color.blue);
g.fillRect(0,0,410,410);
for(int x=0;x<anzx;x++)
for(int y=0;y<anzy;y++)
{
if(!V[x][y])
{
plottV(x,y,g);
}
if(!H[x][y])
{
plottH(x,y,g);
}
if(Z[x][y])
{
plottZ(x,y,g);
}
}
g.setColor(Color.green);
g.fillOval(5+16*zielX+4,5+16*zielY+4,8,8);
}
void plottH(int i,int k, Graphics g)
{ g.setColor(Color.yellow);
g.drawLine(5+16*i,5+16*k,5+16*i+16,5+16*k);
}
void plottV(int i,int k, Graphics g)
{ g.setColor(Color.yellow);
g.drawLine(5+16*i,5+16*k,5+16*i,5+16*k+16);
}
void plottZ(int i, int k, Graphics g)
{ g.setColor(Color.red);
g.fillOval(5+16*i+4,5+16*k+4,8,8);
}
void replottZ(int i, int k, Graphics g)
{ g.setColor(Color.black);
g.fillOval(5+16*i+4,5+16*k+4,8,8);
}
//-----------------------------
boolean imSuedenOffen(Punkt p)
{ return H[p.x][p.y+1];}
boolean imOstenOffen(Punkt p)
{ return V[p.x+1][p.y];}
boolean imNordenOffen(Punkt p)
{ return H[p.x][p.y];}
boolean imWestenOffen(Punkt p)
{ return V[p.x][p.y];}
boolean imZiel(Punkt p)
{ return ((zielX == p.x) && (zielY == p.y));}
boolean bereitsBesucht(Punkt p)
{ return Z[p.x][p.y];}
void merkePosition(Punkt p)
{ Z[p.x][p.y] = true;}
boolean frei(int richtung, Punkt p, Punkt neuP)
{ if ((richtung == 0) && imSuedenOffen(p)) {neuP.y = p.y+1; neuP.x = p.x; return true;}
else if ((richtung == 1) && imOstenOffen(p)) {neuP.x =p.x+1; neuP.y=p.y;return true;}
else if ((richtung == 2) && imNordenOffen(p)) {neuP.y=p.y-1; neuP.x=p.x;return true;}
else if ((richtung == 3) && imWestenOffen(p)) {neuP.x=p.x-1;neuP.y=p.y;return true;}
else return false;
}
void backtracking(Punkt p)
{ Punkt neuP = new Punkt(p.x, p.y);
merkePosition(p);
if (imZiel(p)) problemGeloest = true;
for (int richtung = 0; richtung < 4; richtung++)
{ if (!problemGeloest)
{ try
{ Thread.sleep(3);
} catch (InterruptedException e){;};
// Prüfe den nächsten freien Gang
if (frei(richtung, p, neuP) && !bereitsBesucht(neuP))
{ plottZ(neuP.x, neuP.y, g);
backtracking(neuP);
if (!problemGeloest) replottZ(neuP.x, neuP.y, g);
}//if
}//if (!problemGeloest)
}//for
}//backtracking
}//Labyrinth
class Punkt
{ int x;
int y;
Punkt(int x, int y)
{ this.x = x;
this.y = y;
}
}
Danke für alle die helfen
beste grüße vom matheja
|
|
| |
|
Hallo!
Ein interessantes Problem...
Der Code ist schon sehr aufgebläht, weil da schon extrem viel Zeugs wie ne GUI drin steckt.
Mache dir erstmal Gedanken drüber, wie so eine rekursive Funktion aussehen soll, damit du dich mit ihr durch dein Feld bewegen kannst. Im Prinzip stehst du ja auf einem beliebigen Feld, und kannst dann in vier Richtungen gehen. Für jedes der vier Felder gilt ja dann wieder das gleiche.
Wenn du das hast, mußt du noch ein wenig dran feilen: Die Funktion darf nicht am Rand aus dem Feld rausspringen, wenn da ne 9 steht, gehts auch nicht weiter. Und: Zurückspringen ist auch ne doofe Idee.
Weiter: Es gibt zwei Möglichkeiten, wie das Durchsuchen beendet wird: Einmal, wenn man auf nem Feld landet, welches das Ziel ist. Aber was passiert wohl, wenn es keinen Weg gibt? Woran wirst du das erkennen? (Es hilft, ein wenig auf nem winzigen Feld per Hand auszuprobieren)
Zu guter letzt muß es irgendwo ne Möglichkeit geben, stets den grade untersuchten Weg festzuhalten. WEnn das Ziel gefunden wird, hat man dann auch den Weg...
Aber probier es mal schritt für Schritt in der Reihenfolge, und versuche nicht, deinen Code da zu verstehen...
(Übrigens taugt dieses Problem auch dazu, in einem Minesweeper-Feld die freien Kästchen aufzudecken, ich programmiere Minesweeper in fast jeder Programmiersprache, die mir in die Finger gerät.)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:47 Di 27.04.2010 | | Autor: | matheja |
| Aufgabe | | Hi Leute ich sitz nun schon fast eine woche an dieser Aufgabe und bin trotz der tollen unterstützung von Event immer noch nicht sonderlich weit(er). |
Deswegen bitte ich euch um Nachsicht und mehr input :)
Vielleich wird das ja dann noch was
Danke und beste Grüße vom matheja
|
|
|
| |
|
Na, versuchs mal Schritt für Schritt.
Es soll erstmal ein 2D-Array geben, das möglichst global ist, sodaß jede deiner Funktionen einfach drauf zugreifen kann
int feld[MAX_X][MAX_Y]
Dieses Feld wird mit den Werten gefüllt.
Nun soll es eine rekursive Funktion geben. Sie bekommt die Koordinaten x, y eines Feldes im Array übergeben und soll das Feld untersuchen. Enthält das Feld ne 9, bricht die Funktion ab.
Andernfalls müßten die vier Felder drunter, drüber, rechts und links rekursiv untersucht werden. (rekursiv heißt, daß die Funktion sich selber aufruft!)
explore(int x, int y, int origin){
}
Beachte, daß es keinen Sinn macht, wenn man nen Schritt nach links geht, anschließend wieder nach rechts zu gehen. Dafür hab ich mal die Variable origin eingeführt. Die sei 1, 2, 3, 4 wenn man nach rechts, oben, links, unten springt. Die Funktion explore sollte also überprüfen, aus welcher Richtung man auf das akutelle Feld gekommen ist, und in diese Richtung nicht zurückspringen.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 17:07 Di 27.04.2010 | | Autor: | matheja |
| Aufgabe | Hey Event, Danke für deine Tipps
Ich hab nun deine Ratschläge beherzt.Ich und ein Kommiltione haben nun so gut wie es uns möglich war unseren bisherigen Code den wir auch tlw. aus den Netz haben mit deinen Ratschlägen aktualisiert: |
package Labyrinth;
public class Labyrinth {
final static int[] STEPX = { 0, 1, 0,-1 };
final static int[] STEPY = { -1, 0, 1, 0 };
static int schritt;
final static int RECHTS = 1, UNTEN = 2, LINKS = 3, OBEN = 4, ZIEL = 5;
static int aktX;
static int aktY;
int [mm] MAX_X [/mm] = 6;
int [mm] MAX_Y [/mm] = 6;
int [][] labyrinth = {
{0,0,0,0,0,0},
{0,9,0,9,0,9},
{0,0,9,0,0,0},
{9,0,9,0,9,9},
{0,0,9,0,0,0},
{0,9,0,9,0,0}};
static boolean findeWeg(int[][] lab, int i, int j){
int n = lab.length;
int schritt = -1;
zeige(lab);
System.out.println("----");
while (schritt != LINKS) {
schritt ++;
int neuX = i + STEPX[schritt];
int neuY = j + STEPY[schritt];
boolean ok = true;
if (neuX < 0 || neuX >= n) ok = false;
if (neuY < 0 || neuY >= n) ok = false;
if (ok && lab[neuX][neuY] !=' ') ok = false;
if(ok){
lab[neuX][neuY] = '.';
if (!ausgangGefunden(neuX, neuY)) {
// rekursiver Aufruf von FindeLoesung
if (findeWeg(lab, neuX, neuY)) {
// Lösung gefunden
return true;
} else {
lab[neuX][neuY] = ' ';
}
} else return true;
}
}//while
return false;
}
private static boolean ausgangGefunden(int neuX, int neuY) {
if(neuX==4 && neuY==4){
return true;
}
return false;
}
public static void zeige(int[][]a){
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
System.out.print(a[i][j]+ " ");
}
System.out.println();
}
}
public static void main (String[] args){
zeige(labyrinth);
boolean b = findeWeg(labyrinth, 0, 0);
if (b) System.out.println("Weg gefunden");
else System.out.println("Keinen Weg gefunden");
zeige(labyrinth);
}
}// Klassenende
MIt der folgenden Ausgabe:
0 0 0 0 0 0
0 9 0 9 0 9
0 0 9 0 0 0
9 0 9 0 9 9
0 0 9 0 0 0
0 9 0 9 0 0
0 0 0 0 0 0
0 9 0 9 0 9
0 0 9 0 0 0
9 0 9 0 9 9
0 0 9 0 0 0
0 9 0 9 0 0
----
Keinen Weg gefunden
0 0 0 0 0 0
0 9 0 9 0 9
0 0 9 0 0 0
9 0 9 0 9 9
0 0 9 0 0 0
0 9 0 9 0 0
Wieso findet er keinen Weg obwohl es einen gibt?
Wie könnt wir das so machen dass für
0 1 2 3 4 5
0 1 1 1 1 2 0
1 4 9 0 9 2 9
2 4 3 9 2 3 0
3 9 4 9 2 9 9
4 1 4 9 1 1 2
5 4 9 0 9 0 5
Danke für Hilfe
beste grüße
matheja
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Di 27.04.2010 | | Autor: | matheja |
Hi Leute, ich bins nochmal
so langsam etnwickelt sich die Aufgabe zu einen Fass ohne Boden,
wir haben unser Programm jetzt weiter modifiziert, doch leider dreh wir uns zur zeit im Kreis,
wir hoffen auf eurer feedback
Unser modifizierter Code:
| 1: |
| | 2: |
| | 3: | package Labyrinth;
| | 4: |
| | 5: | import java.util.Iterator;
| | 6: |
| | 7: | public class Labyrinth {
| | 8: |
| | 9: | int[][] lab;
| | 10: | int max_x;
| | 11: | int max_y;
| | 12: | int start_x;
| | 13: | int start_y;
| | 14: |
| | 15: |
| | 16: |
| | 17: | public Labyrinth() {
| | 18: | lab = new int [][]{
| | 19: | {0,0,0,0,0,0},
| | 20: | {0,9,0,9,0,9},
| | 21: | {0,0,9,0,0,0},
| | 22: | {9,0,9,0,9,9},
| | 23: | {0,0,9,0,0,0},
| | 24: | {0,9,0,9,0,0}};
| | 25: | max_x=6;
| | 26: | max_y=6;
| | 27: | start_x=1;
| | 28: | start_y=6;
| | 29: |
| | 30: | }
| | 31: |
| | 32: | /*
| | 33: | * set_field(int x, int y, char c)
| | 34: | *
| | 35: | * Legt für ein Feld im Labyrinth (lab[x][y]) den neuen Typ c fest
| | 36: | * c =
| | 37: | * 0 frei
| | 38: | * 9 Blockade
| | 39: |
| | 40: | */
| | 41: | public void set_field(int x, int y, char c) {
| | 42: | lab[x][y]=c;
| | 43: | }
| | 44: |
| | 45: | /*
| | 46: | * zeichne_lab()
| | 47: | *
| | 48: | * Zeichnet das aktuelle Labyrinth mit der aktuellen Position (*)
| | 49: | */
| | 50: | public void zeichne_lab(){
| | 51: | for(int j=0;j<max_y;j++)
| | 52: | for(int i=0; i<max_x;i++)
| | 53: | if(i==max_x-1)System.out.println(lab[i][j]);
| | 54: | else System.out.print(lab[i][j]);
| | 55: | }
| | 56: |
| | 57: | /*
| | 58: | * suche_ausgang(int cur_x, int cur_y);
| | 59: | *
| | 60: | * returns true - Ausgang gefunden
| | 61: | * returns false - kein Ausgang findbar
| | 62: | */
| | 63: | public boolean suche_ausgang(int cur_x, int cur_y,int origin) {
| | 64: | int x = lab[cur_x][cur_y];
| | 65: | if(x == 0) return true;
| | 66: | else if (x == 9) return false;
| | 67: | else if (x == origin) return false;
| | 68: | if (suche_ausgang(cur_x+1,cur_y,1)) return true;
| | 69: |
| | 70: | else if (suche_ausgang(cur_x,cur_y+1,4)) return true;
| | 71: | else if (suche_ausgang(cur_x-1,cur_y,3)) return true;
| | 72: | else if (suche_ausgang(cur_x,cur_y-1,2)) return true;
| | 73: | else{
| | 74: | set_field(cur_x,cur_y, 'f');
| | 75: | return false;
| | 76: | }
| | 77: | }
| | 78: |
| | 79: |
| | 80: |
| | 81: |
| | 82: |
| | 83: |
| | 84: |
| | 85: | public static void main(String[] args) {
| | 86: |
| | 87: | Labyrinth l = new Labyrinth();
| | 88: |
| | 89: | l.zeichne_lab();
| | 90: |
| | 91: |
| | 92: | if (l.suche_ausgang(1, 6, 0)) System.out.println("Ausgang gefunden");
| | 93: | else System.out.println("Kein Ausgang");
| | 94: |
| | 95: | l.zeichne_lab();
| | 96: | }
| | 97: |
| | 98: | }
|
Danke schonmal für Hilfe
beste grüße vom matheja
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:50 Di 27.04.2010 | | Autor: | matheja |
Hi Leute,
hier ist unser letzter Versuch;
Wir haben insbesondere Probleme mit der Main und der suche ausgang-methode.
Wir wissen nicht wie origin implementieren solln,
außerdem zeigt er uns das er einen weg gefunden hat aber nicht wie.
wir haben generell ein problem einen konkreten startpunkt zu finden so wie verlangt
| 1: |
| | 2: | package Labyrinth;
| | 3: |
| | 4: | //import java.util.Iterator;
| | 5: |
| | 6: | public class Labyrinth {
| | 7: |
| | 8: | int[][] lab;
| | 9: | int max_x;
| | 10: | int max_y;
| | 11: | int start_x;
| | 12: | int start_y;
| | 13: |
| | 14: | public Labyrinth(int max_x, int max_y, int start_x, int start_y) {
| | 15: | lab = new int[max_x][max_y];
| | 16: | this.max_x=max_x;
| | 17: | this.max_y=max_y;
| | 18: | this.start_x=start_x;
| | 19: | this.start_y=start_y;
| | 20: | }
| | 21: |
| | 22: | public Labyrinth() {
| | 23: | lab = new int [][]{
| | 24: | {0,0,0,0,0,0},
| | 25: | {0,9,0,9,0,9},
| | 26: | {0,0,9,0,0,0},
| | 27: | {9,0,9,0,9,9},
| | 28: | {0,0,9,0,0,0},
| | 29: | {0,9,0,9,0,0}};
| | 30: | max_x=6;
| | 31: | max_y=6;
| | 32: | start_x=1;
| | 33: | start_y=6;
| | 34: |
| | 35: | }
| | 36: |
| | 37: | /*
| | 38: | * set_field(int x, int y, char c)
| | 39: | *
| | 40: | * Legt für ein Feld im Labyrinth (lab[x][y]) den neuen Typ c fest
| | 41: | * c =
| | 42: | * 1 rechts
| | 43: | * 2 unten
| | 44: | * 3 links
| | 45: | * 4 oben
| | 46: | * 5 Ziel
| | 47: | */
| | 48: | public void set_field(int x, int y, char c) {
| | 49: | lab[x][y]=c;
| | 50: | }
| | 51: |
| | 52: | /*
| | 53: | * zeichne_lab()
| | 54: | *
| | 55: | * Zeichnet das aktuelle Labyrinth
| | 56: | */
| | 57: | public void zeichne_lab(){
| | 58: | for(int j=0;j<max_y;j++)
| | 59: | for(int i=0; i<max_x;i++)
| | 60: | if(i==max_x-1)System.out.println(lab[i][j]);
| | 61: | else System.out.print(lab[i][j]);
| | 62: | }
| | 63: |
| | 64: | /*
| | 65: | * suche_ausgang(int cur_x, int cur_y);
| | 66: | *
| | 67: | * returns true - Weg gefunden
| | 68: | * returns false - kein Weg weiter
| | 69: | */
| | 70: | public boolean suche_ausgang(int cur_x, int cur_y,int origin) {
| | 71: | int x = 0;
| | 72: | if(x == 0) return true;
| | 73: | else if (x == 9) return false;
| | 74: | else if (x == origin) return false;
| | 75: | if (suche_ausgang(cur_x+1,cur_y,1))
| | 76: | {set_field(cur_x,cur_y,'1');
| | 77: | return true;}
| | 78: | else if (suche_ausgang(cur_x,cur_y+1,4))
| | 79: | {set_field(cur_x,cur_y,'4');
| | 80: | return true;}
| | 81: | else if (suche_ausgang(cur_x-1,cur_y,3))
| | 82: | {set_field(cur_x,cur_y,'3');
| | 83: | return true;}
| | 84: | else if (suche_ausgang(cur_x,cur_y-1,2))
| | 85: | {set_field(cur_x,cur_y,'2');
| | 86: | return true;}
| | 87: | else {return false;}
| | 88: | }
| | 89: |
| | 90: |
| | 91: |
| | 92: |
| | 93: |
| | 94: |
| | 95: |
| | 96: | public static void main(String[] args) {
| | 97: |
| | 98: | Labyrinth l = new Labyrinth();
| | 99: |
| | 100: | l.zeichne_lab();
| | 101: |
| | 102: |
| | 103: | if (l.suche_ausgang(6, 6, 0)) System.out.println("Ausgang gefunden");
| | 104: | else System.out.println("Kein Ausgang");
| | 105: |
| | 106: | l.zeichne_lab();
| | 107: | }
| | 108: |
| | 109: | }
| | 110: |
|
Danke für Hilfe und gute n8
matheja
wenigstens bayern hat gewonnen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Do 29.04.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
