Zufällige Karte generieren haut nicht ganz hin

[Der-Gizmo]

Hallo Freunde des Java-Codes,

ich weiß nicht ob ich gerade auf dem Schlauch sitze, aber ich finde keine Lösung für folgendes Problem:

Ich habe eine Methode geschrieben, diese befüllt in einer quatratisch unterteilten Fläche eine übergebene Anzahl an Teilquatraten mit Farbe.

Die quatratische Fläche hat z.B. 9x9 Felder, in dieser soll zufällig ein erstes Feld ausgewählt werden und mit einer Farbe ausgefüllt werden. Soweit so gut und kein Problem.

Jetzt soll ausgehend von diesem Quadrat ein benachbartes Quadrat ausgewählt und befüllt werden und von diesem wieder und wieder....

Das Kriterium dabei ist, dass ein bereits ausgefülltes Quadrat nicht nochmals befüllt werden darf.

Das Problem, was ich dabei festgestellt habe ist, dass der Algorithmus bei einer kleinen Anzahl an Quadraten noch gut funktioniert, aber sobald es etwas mehr werden hängt die Schleife irgendwann fest, weil die sich sozusagen eingeschlossen hat, wenn keine unmittelbaren freien Nachbarn mehr da sind zum auswählen.

Ziel soll sein, dass bei einer Fläche von 9x9 = 81 Quadraten maximal 81 durch diesen Algorithmus zufällig befüllt werden sollen.

Ich weiß gar nicht ob das überhaupt mit diesem Ansatz möglich ist, weil ich das Gefühl habe der hängt immer irgendwann fest, aber vielleicht hat einer eine Idee wie ich das Problem besser lösen kann?

Grüße!

Der-Gizmo

 

[zerix]

Zufällige Karte generieren haut nic ...

Hallo,

Wenn du etwas Code zeigen würdest könnte man dir eher helfen.

Gruß

Sascha

 

[Der-Gizmo]

Hallo Sascha,

das Internet ist aber klein ;-) Habe dir das Problem heute ja schon persönlich erklärt, aber der eine Link hat mir nicht wirklich geholfen :-(

Aber hier mal etwas Code:

Methode karteGenerieren:

public void karteGenerieren(int sektoren){

		int naechsteZahl = (int) (Math.random() * (80 - 0) + 0);	
		
		boolean generierung = false;
				
		while(generierung==false)
		{
			
			if(counter==sektoren)
			{
				generierung = true;
				
				System.out.println(sektoren+" Sektoren erfolgreich generiert");
			}
			
			else
			{
				
				if(vergebenerBereich.contains(naechsteZahl)){
									
					
					naechsteZahl=waehleNaechsteZahl(naechsteZahl,letzerBereich);
				
					
				}
				
				else
				
				{
					
					counter++;
					
					
					if(pruefeZahlenbereich(naechsteZahl)==true){				
								
						int bereich[] = {naechsteZahl-10, 
								naechsteZahl-9, 
								naechsteZahl-8, 
								naechsteZahl-1,
								naechsteZahl+1,
								naechsteZahl+8,
								naechsteZahl+9,
								naechsteZahl+10};
						
						
						naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
						
						
														
						
					}
					
					
					else
					
					{
								
				
						if(naechsteZahl==0){
							
							int [] bereich = {1,9,10};	
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
	
							
						}
						
						if(naechsteZahl==8){
							
							int bereich[] = {7,16,17};	
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
							
							
							
						}
						
						if(naechsteZahl==72){
							
							int bereich[] = {63,64,73};	
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
							
						}
						
						if(naechsteZahl==80){
							
							int bereich[] = {70,71,79};	
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
							
						}
							
						if(naechsteZahl>0 && naechsteZahl <8){
							
							int bereich[] = {naechsteZahl-1,naechsteZahl+1,naechsteZahl+8,
									naechsteZahl+9,naechsteZahl+10};	
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
							
						}
						
						if(naechsteZahl>72 && naechsteZahl <80){
							
							int bereich[] = {naechsteZahl-1,naechsteZahl+1,naechsteZahl-8,
									naechsteZahl-9,naechsteZahl-10};
							
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
							
						}
					
						if(naechsteZahl==9 || naechsteZahl==18 || naechsteZahl==27 || naechsteZahl==36
								|| naechsteZahl==45 || naechsteZahl==54 || naechsteZahl==63){
							
							int bereich[] = {naechsteZahl-9,naechsteZahl-8,naechsteZahl+1,
									naechsteZahl+9,naechsteZahl+10};	
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
											
						}
						
						if(naechsteZahl==17 || naechsteZahl==26 || naechsteZahl==35 || naechsteZahl==44
								|| naechsteZahl==53 || naechsteZahl==62 || naechsteZahl==71){
							
							int bereich[] = {naechsteZahl-9,naechsteZahl-10,naechsteZahl-1,
									naechsteZahl+8,naechsteZahl+9};	
							
							naechsteZahl=waehleNaechsteZahl(naechsteZahl, bereich);
							
							
							
						}
					
					}
					

						
					
						
						
				}	
			
			}
				
			
			
			}	
		}

Methode waehleNaechsteZahl

	public int waehleNaechsteZahl(int naechsteZahl, int [] bereich){
		
		
		letzerBereich=bereich;
		
		int[] bereichGroesse = new int[bereich.length];
		
		int bereichsZaehler = 0;
		
		buttons[naechsteZahl].setBackground(Color.LIGHT_GRAY);
		
		vergebenerBereich.add(naechsteZahl);
			
		int zufallbereichszahl = (int) (Math.random() * (bereich.length - 1) + 0);
		
		if (vergebenerBereich.contains(zufallbereichszahl)){
			
			
			while(vergebenerBereich.contains(zufallbereichszahl)){
				
				
				if(bereichsZaehler != bereichGroesse.length){
					
					zufallbereichszahl = (int) (Math.random() * (bereich.length - 0) + 0);
							
					
					bereichsZaehler++;
					
				}
				
				else{
					
					System.out.println("Bereich wurde komplett ausgeschöpft");
					
					System.exit(0);
					
				}
				
				
			}	
			
		}
				
		naechsteZahl = bereich[zufallbereichszahl];
			
		return naechsteZahl;
		
	}

Alternativ hatte ich noch einen anderen Ansatz gewählt, aber dort laufe ich in einen StackOverflow bei zu vielen Sektoren:

public void karteGenerieren2(int sektoren){
			
		int zufallszahl = (int) (Math.random() * (81));
		
			
			if((zufallszahl-letzteZahl==-10  
					||	zufallszahl-letzteZahl==-9 
					||	zufallszahl-letzteZahl==-8
					||	zufallszahl-letzteZahl==-1
					||	zufallszahl-letzteZahl==1
					||	zufallszahl-letzteZahl==8
					||	zufallszahl-letzteZahl==9
					||	zufallszahl-letzteZahl==10)&&!vergebenerBereich.contains(zufallszahl))
			
			{						
				
				buttons[zufallszahl].setBackground(Color.LIGHT_GRAY);
				
				vergebenerBereich.add(zufallszahl);
				
				
				
				letzteZahl=zufallszahl;
				
				if(sektoren>1){
							
					karteGenerieren2(sektoren-1);
					
					
				}
				
			}
			
			else
			
			{
				
				karteGenerieren2(sektoren);		
				
			}

 

[genodeftest]

Warum machst du es nicht so, dass du durch ein 2dimensionales Array iterierst und bei jedem einzelnen Feld (zufällig) entscheidest, ob es gefüllt wird?

Dein Problem beim 2. Versuch lautet Rekursion: die Methode karteGenerieren2 ruft sich selbst auf. Bei ausreichend großem

int sektoren

musst du einen Stackoverflow bekommen.

 

[Der-Gizmo]

Warum machst du es nicht so, dass du durch ein 2dimensionales Array iterierst und bei jedem einzelnen Feld (zufällig) entscheidest, ob es gefüllt wird?

Wenn ich ein zweidimensionales Array verwende habe ich aber immer noch das Problem, dass ich die Nachbarn prüfen muss und das nächste Feld auswähle etc., ich sehe da jetzt kein großen Unterschied oder ich steig grad nicht dahinter!?

 

[zerix]

Hey,

eine Idee von mir wäre folgende:

Du hast dein 2D-Array, eine Liste in der die freien Felder des Array stehen und eine weitere Liste.
Beim Start nimmst du ein beliebiges freies Feld und markierst es und entfernst es aus der Liste mit den freien Feldern. Dann nimmst du dir wieder ein zufälliges Feld aus der Liste mit den freien Feldern und prüfst um es als Nachbar ein markiertes Feld hat. Falls nicht entfernst du es aus dieser Liste und speicherst es in der anderen Liste. Dies machst du solange, bis du eins Feld gefunden hast, welches als Nachbar ein markiertes Feld hat und markierst dieses ebenfalls. Dann entfernst du das auch aus der Liste mit dem freien Feldern. Die zweite Liste, in der du die anderen Felder gespeichert hattest, die keinen markierten Nachbar hatten, packst du jetzt wieder in die Liste mit den freien Feldern.
Das ganze machst du solange, bis du die gewünschte Menge erreicht hast.

Gruß

Sascha