Lage labyrint med rekrusjon

[Jokke85]

Jeg vil lage en tekstbassert labyrint med rekrusjon:

Jeg har gjort dette til nå:

 

public class Labyrint {
private final char BRUKT = 'B';
private final char VEI = 'O';

private char[][] grid =
	{   { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
		{ '.', '.', '.', '.', '#', '.', '.', '#', '#', '#', '.', '.', '.', '.', '#' },
		{ '#', '.', '#', '.', '.', '.', '#', '.', '.', '.', '.', '#', '#', '.', '#' },
		{ '#', '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '#', '#' },
		{ '#', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#' },
		{ '#', '.', '#', '.', '#', '#', '#', '#', '.', '.', '.', '#', '#', '.', '#' },
		{ '#', '.', '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '#' },
		{ '#', '.', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
		{ '#', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
		{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }
	};

//-----------------------------------------------------------------
//  Prøver å gå igjennom labyrinten rekursivt. Setter inn spesielle 
//  karakterer (tegn) for å markere steder som har vært besøkt 
//  (BRUKT) og steder som bli del av løsningen (VEI).
//-----------------------------------------------------------------
public boolean traverse(int row, int column) {
	boolean ferdig = false;
	if(valid(row, column)){
		grid[row][column] = VEI;
		if(row == grid.length-1 && column==grid[0].length-1){
			ferdig = true;
		}
		else{
			ferdig = traverse(row+1, column);
			if(!ferdig)
				ferdig = traverse(row, column+1);
			if(!ferdig)
				ferdig = traverse(row-1, column);
			if(!ferdig)
				ferdig = traverse(row, column-1);
	   }

	   if(ferdig)
			grid[row][column] = BRUKT;
   }
   return ferdig;
}

//-----------------------------------------------------------------
//  Avgjør om en bestemt lokasjon er gyldig (dvs innenfor
//  labyrinten eller ikke 'besøkt'
//-----------------------------------------------------------------
private boolean valid(int row, int column) {
	boolean result = false;

	if(row >= 0 && row < grid.length && column >= 0 && column < grid[row].length){
		if(grid[row][column] == 1){
			result = true;
		}
	}
	return result;
}

//-----------------------------------------------------------------
//  Returnerer labyrinten som en String, setter tilbake opprinnelig
//  tegn på en plass som er besøkt, men ikke en del av løsningen.
//-----------------------------------------------------------------
public String toString() {
	String result = "\n";

	for (int row = 0; row < grid.length; row++) {
		for (int column = 0; column < grid[row].length; column++) {
			char tegn = grid[row][column];
			if (tegn == BRUKT) result += ".";
			else result += tegn + "";
		}
		result += "\n";
	}

	return result;
}
}





public class LabyrintGjennomgang {
// -----------------------------------------------------------------
// Lager en labyrint, skriver den ut på skjermen, prøver å løse den
// og skriver ut labyriten med eventuell løsning (riktig vei).
// -----------------------------------------------------------------
public static void main(String[] args) {
	Labyrint labyrint = new Labyrint();

	System.out.println(labyrint);

	if (labyrint.traverse(1, 0))
		System.out.println("Det ble funnet en vei!");
	else
		System.out.println("Det finnes ingen vei!");

	System.out.println(labyrint);
}
}

 

hva har jeg gjort feil her?

haster litt...

[Gjest Slettet+1374861]

Synes det finnes en hel del vesentlige feil ved denne fremgangsmåten....

Første og største feilen er at løsningen er overhode ikke generell. Du oppgir ett startpunkt, men leter etter ett spesifikt sluttpunkt. I utgangspunktet burde man gå i blinde fra startpunktet og prøve å nå en kant (som ikke er den du startet på).

 

Forøvrig så er det bare ett par småfeil på at DENNE spesifikke labyrinten skal løses.

		if(row >= 0 && row < grid.length && column >= 0 && column < grid[row].length){
		if(grid[row][column] == 1){
			result = true;
		}
	}

grid[row][column] == 1 kommer vel neppe til å skje. Det du leter etter er jo om det er en vei eller ikke, altså grid[row][column] == '.'

 

Det andre problemet er da som nevnt tidligere at du leter etter ett spesifikt sluttpunkt, som du har spesifisert som..

if(row == grid.length-1 && column==grid[0].length-1){
			ferdig = true;
		}

Dette tilsvarer jo HELT nede i høyre hjørne, som ikke stemmer overens med labyrinten din. Hvis det er det punktet du leter etter, vel, da er det ingen vei... Forøvrig finnes det en generell utgang, men denne er grid.length-2.

 

 

--- Så må jeg jo også spørre hvilket fag dette er til, og ved hvilken skole? Høres jo ut som ett koslig fag!

Endret 24. januar 2008 av Slettet+1374861

[Jokke85]

Takk skal du ha, fant det ut.

Jeg går på NITH i Oslo, webprogrammering, faget er java(PG411)

 

Jeg gjorde om koden litt, og det resultatet av koden ble:

bare klassen Labyrint som er gjort om så legger bare til den:

 

//PG411 INNLEVERING JOACHIM BJERKE

public class Labyrint {
private final char BRUKT = 'B';
private final char VEI = 'O';

private char[][] grid = {
		{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
		{ '.', '.', '.', '.', '#', '.', '.', '#', '#', '#', '.', '.', '.', '.', '#' },
		{ '#', '.', '#', '.', '.', '.', '#', '.', '.', '.', '.', '#', '#', '.', '#' },
		{ '#', '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '#', '#' },
		{ '#', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#' },
		{ '#', '.', '#', '.', '#', '#', '#', '#', '.', '.', '.', '#', '#', '.', '#' },
		{ '#', '.', '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '#' },
		{ '#', '.', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
		{ '#', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
		{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };

// -----------------------------------------------------------------
// Prøver å gå igjennom labyrinten rekursivt. Setter inn spesielle
// karakterer (tegn) for å markere steder som har vært besøkt
// (BRUKT) og steder som bli del av løsningen (VEI).
// -----------------------------------------------------------------
public boolean traverse(int row, int column) {
	boolean ferdig = false; // labyrintveien er ikke ferdig funnet

	if (valid(row, column)) {
		grid[row][column] = BRUKT; // this cell is tried
		if (row == grid.length - 2 && column == grid[0].length - 1)
			ferdig = true; // veien ble funnet
		else {
			ferdig = traverse(row + 1, column); // flytter ned
			if (!ferdig)
				ferdig = traverse(row, column + 1); // flytter høyre
			if (!ferdig)
				ferdig = traverse(row - 1, column); // flytter opp
			if (!ferdig)
				ferdig = traverse(row, column - 1); // flytter venstre
		}
		if (ferdig)
			grid[row][column] = VEI;
	}
	return ferdig;
}

// -----------------------------------------------------------------
// Avgjør om en bestemt lokasjon er gyldig (dvs innenfor
// labyrinten eller ikke 'besøkt'
// -----------------------------------------------------------------
private boolean valid(int row, int column) {
	boolean result = false;

	if (row >= 0 && row < grid.length && column >= 0
			&& column < grid[row].length) {
		if (grid[row][column] == '.') {// sjekker om det finnes en vei.

			result = true;
		}
	}
	return result;
}

// -----------------------------------------------------------------
// Returnerer labyrinten som en String, setter tilbake opprinnelig
// tegn på en plass som er besøkt, men ikke en del av løsningen.
// -----------------------------------------------------------------
public String toString() {
	String result = "\n";

	for (int row = 0; row < grid.length; row++) {
		for (int column = 0; column < grid[row].length; column++) {
			char tegn = grid[row][column];
			if (tegn == BRUKT)
				result += ".";
			else
				result += tegn + "";
		}
		result += "\n";
	}

	return result;
}
}