Algorithmus um Flächen zu erkennen

[Comonox]

Hallo Forum,

ich möchte ein Spiel programmieren, das Cathedral heißt und habe folgende Problematik. So kann ein Spielbrett zu einem gewissen Zeitpunkt im Spiel aussehen (Design, Spielsteine setzen, Freiräume für Spielsteine erkennen, erkennen dass mein einen Spielstein nicht auf ein Feld setzen kann hab ich alles schon programmiert):

Jetzt muss erkannt werden, dass oben rechts in der Ecke die Felder von blauen Steinen eingekreist sind oder z.B. unten rechts in der Ecke die Steine von grünen da diese Felder dem blauen, bzw. dem grünen Spieler gehören.
Mein Ansatz: Ich habe erstmal folgenden Algorithmus geschrieben, um Polygonzüge zu erkennen:

public void getConnectedFields(Point p, Player player, ArrayList<Point> connected_fields, ArrayList<Point> border_fields){
		int x = (int) p.getX();
		int y = (int) p.getY();
		connected_fields.add(p);
		
		if (x == 0 || x == 9 || y == 0 || y == 9)
			border_fields.add(p);

		if (x+1 <= 9 && this.fieldMatrix[x+1][y] == player.getId() && !connected_fields.contains(new Point(x+1,y)))
			this.getConnectedFields(new Point(x+1,y),player,connected_fields, border_fields);
			
		if(y+1 <= 9 && this.fieldMatrix[x][y+1] == player.getId() && !connected_fields.contains(new Point(x,y+1)))
			this.getConnectedFields(new Point(x,y+1),player,connected_fields, border_fields);
			
		if(x-1 >= 0 && this.fieldMatrix[x-1][y] == player.getId() && !connected_fields.contains(new Point(x-1,y)))
			this.getConnectedFields(new Point(x-1,y),player,connected_fields, border_fields);
			
		if(y-1 >= 0 && this.fieldMatrix[x][y-1] == player.getId() && !connected_fields.contains(new Point(x,y-1)))
			this.getConnectedFields(new Point(x,y-1),player,connected_fields, border_fields);
		
	}

Dieser Algorithmus findet quasi rekursiv immer einen weiteren weg zum nächsten stein bis es keinen mehr gibt.

Aber jetzt weiß ich nicht mehr weiter, alles, was ich dann probiert habe funktioniert immer nur teilweise, es werden einfach nicht immer inneliegende Felder erkannt. Vielleicht sieht ja einer von Euch die Problematik und denkt "Hey, das ist kann man doch mit dem x,y-Algorithmus lösen" aber ich weiß einfach nicht mehr weiter und wäre über Hilfe dankbar!

LG

Chris

 

[SlaterB]

bevor du noch mehr solchen Code fabrizierst wäre es hier besonders gut, Luft zu holen und den vorhandenen zu korrigieren,
da ist ja schrecklich viel Wiederholung drin

deine Zeilen 9-20 könntest du durch 4 Aufrufe

check(p, 1, 0, player, connected_fields, border_fields);
check(p, 0, 1, player, connected_fields, border_fields);
check(p, -1, 0, player, connected_fields, border_fields);
check(p, 0, -1, player, connected_fields, border_fields);

ersetzen mit nur noch einer Methode check(), die das richtige vergleichen kann usw.,
die vielen übergebenen Parameter lassen selbst das noch etwas unschön aussehen, wären besser Instanzattribute,
und sei es notfalls in einer extra neuen Such-Klasse, oder Attribute in Player oder neue Klasse ZusammenhaengendeFlaeche

so selten wie du p tatsächlich brauchst, und so häufig wie du x, y extrahierst und neue Points erstellt,
wäre es dagegen eher leichter, x + y als einzelne Parameter zu übergeben statt als Point zusammengefasst

------

deine Methode erkennt anscheinend zusammenhängige Flächen, das ist schon gut,
aber nicht unbedingt mit deiner Frage nach eingeschlossenen Flächen verbunden,
dies gleichzeitig zu testen kann wohl als Komplexität vermieden werden, falls es nicht um Millionen Felder und Performance geht,

also eine eigene Methode dafür, da kannst du beliebig vorgehen, etwa alle Felder durchlaufen und die Nachbarn in ein Set einfügen,
wenn am Ende nur ein Nachbar, dann wohl eingeschlossen

 

[Comonox]

Vielen Dank für die schnelle Hilfe! Das sind schonmal eine Menge Tipps mit denen ich was anfangen kann!

 

[Comonox]

Gut, habe deinen Rat befolgt und meine Methoden entschlackt, ich kann jetzt auch Areas erkennen, läuft also.

Eine Frage habe ich noch, ich habe jeden der Spielsteine als JPanel definiert, über PaintComponent die Form festgelegt und diese JFrame hinzugefügt.

	// ============================================================= method main
	public static void main(String[] args) throws InterruptedException {
		new Cathedral();

	}// end main
		// ====================================================== applet
		// constructor

	public Cathedral() throws InterruptedException {


		/*
		 * Load GUI
		 * */
		setBackground(new Color(224,238,224));
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		playboard.freeFields(); //all fields to -1

		Container container = getContentPane();
		container.add(playboard); //playboard extends jpanel
		container.add(player_one); //player_one extends jpanel
		container.add(player_two); //player_two extends jpanel
		//create stones
		for (int i = 0; i < this.stones.length; i++) {
			container.add(this.stones[i]); //one of those stones extends jpanel
		}
		pack();
		setSize(new Dimension(Cathedral.resolution_x,Cathedral.resolution_y));
		setVisible(true);
	}

Damit überhaupt etwas angezeigt wird habe ich sowohl bei den Steinen als auch bei dem Frame dieselbe Size angegeben. Jetzt nimmt ja aber ein JPanel quasi den kompletten Bildschirm ein, ich möchte aber, dass sich die Größe dem anpasst, was ich in PaintComponent "gemalt" habe, sonst kann ich beispielweise ja mit mouseclick events nichts anfangen, denn immer wenn ich auf einen Stein klicke, wird das letzte Jpanel angeklickt, das ich hinzugefügt habe. Ich möchte also quasi ein Canvas hinzufügen damit ich pixelgenau die komponente auswählen kann.

Ich hoffe mein Problem war verständlich und jemand kann mir kurz erklären, wo mein denkfehler liegt.

 

[SlaterB]

mit Standard-BorderLayout für ContentPane kannst du eigentlich überhaupt nur eine Komponente simpel add()en,
das sollte schon bei playboard, player_one, player_two scheitern,

ideal ist sicher die Einstellung, nichts übereinander zu legen, von Panel die andere Komponenten enthalten mal abgesehen,
mit beliebigen Layouts kannst du alle Komponenten so verteilen wie es richtig ist, setPreferredSize() nötig bei paint-Komponenten

um Komponenten übereinander darzustellen und diese dennoch nicht die komplette Fläche einnehmen zu lassen (falls das überhaupt geht, mit Panel vielleicht)
denke ich an das null-Layout mit absoluter Positionierung +setSize(), oder eine eine Mischung der Layouts:
mit normalen Layout aufteilen, in einzelnen Abschnitten dann irgendwie übereinander legen

wenn nur zigfach Dinge zu zeichnen sind, dann ist aber auch empfehlenswert gar nicht so sehr Komponenten zu verwenden,
nur eine oder wenige mit aufwendigen paint-Methoden die diverse Dinge, ob Gitternetze und Figuren, zeichnen,

mit einem Hintetgrund-Modell an Koordinaten zu Pixel kann man von einem einzigen großen MouseListener herausfinden, was gerade angeklickt wurde,
ist natürlich bisschen aufwendiger

 

[Comonox]

Hey vielen dank, ich habe jetzt auf ein JPanel reduziert, in der alle Berechnungen durchgeführt werden und es wird jetzt nur noch in diesem JPanel "gemalt", das funktioniert super.

Habe einfach Umrechnungsmethoden geschrieben, die mir umrechnen, wenn z.B. 604/321 geklickt wird, dass ich dann die Mouse gerade auf dem Stein "Castle" befindet z.B. so kann ich dann ja auch einen einzigen Mousehandler für alle Aktionen nutzen.

Also vielen Dank für die Hilfe!!

 

[Comonox]

So, wenn ich eine Frage stelle, dann möchte ich zumindest auch meine Lösung präsentieren, falls jemand mal ein ähnliches Problem hat, obwohl ich als Anfänger kein Gewähr dafür geben möchte, dass das auch die eleganteste Lösung ist. Manche Methoden, die man in meiner Lösung sieht, sind spezifisch für mein Spiel, der generelle Algorithmus sollte aber dennoch ersichtlich sein.

/**
	 * detect Areas of a player (area with stones of the player and the border or with only stones of the player)
	 */
	public static void detectAreas(PlayboardJPanel playboard){
		//get player_one and player_two
		Player[] players = {playboard.getPlayer_one(),playboard.getPlayer_two()};
		//get current field_matrix
		int [][] field_matrix = playboard.getFieldMatrix();
		//init ArrayLists
		ArrayList<Stone> conflicting_stones = new ArrayList<Stone>();
		ArrayList<Point> area = new ArrayList<Point>();
		 //don't check a field, that is part of another area twice
		for (Player player : players) {
			ArrayList<Point> used_fields = new ArrayList<Point>();
			for (int y = 0; y < 10; y++){
				for (int x = 0; x < 10; x++){
					if (!used_fields.contains(new Point(x,y)) && //not part of another area (reduce overhead)
						field_matrix[x][y] != player.getId() //don't check fields, that are filled with players stones
						 &&!AreaDetection.do_not_check_again.contains(new Point(x,y))
						){ 
						getArea(x,y, area,used_fields, player, playboard);
						//do something with area, mark for example as area
						area.clear();
					} 
				} //end for-loop x
			} //end for-loop y
		} //end for-loop player
		System.out.println();
	}
/**
	 * checks the connection in 8 directions, if there is a connection, the neighbors are checked also recursively
	 * @param x
	 * @param y
	 * @param area
	 * @param player
	 */
	public static void getArea(int x, int y, ArrayList<Point> area,ArrayList<Point> used_fields, Player player, PlayboardJPanel playboard){
		area.add(new Point(x,y));
		used_fields.add(new Point(x,y));
		checkConnection(x+1, y, area, used_fields, player, playboard);//right
		checkConnection(x, y+1, area, used_fields, player, playboard);//bottom
		checkConnection(x-1, y, area, used_fields, player, playboard);//left
		checkConnection(x, y-1, area, used_fields, player, playboard);//top
		
		checkConnection(x+1, y+1, area, used_fields, player, playboard);//righttop corner
		checkConnection(x-1, y-1, area, used_fields, player, playboard);//bottomleft corner
		checkConnection(x+1, y-1, area, used_fields, player, playboard);//bottomright corner
		checkConnection(x-1, y+1, area, used_fields, player, playboard);//topleft corner
	}

	/**
	 * helper method to hold the getConnectedFields() method clearly (8-times the same check)
	 * @param x
	 * @param y
	 * @param area
	 * @param player
	 * @param playboard 
	 */
	public static void checkConnection(int x, int y, ArrayList<Point> area,ArrayList<Point> used_fields, Player player, PlayboardJPanel playboard){
		if (x >= 0 && x <=9 && y >= 0 && y <= 9){ //make sure x and y are not out of bounds and players id
			if ((playboard.getFieldMatrix()[x][y] == -1 || playboard.getFieldMatrix()[x][y] != player.getId()) && !area.contains(new Point(x,y))){
				getArea(x, y, area, used_fields, player, playboard); //extend current area with checked_field
			}
		}
	}