zählen von zusammenhängenden Spielfeldern

[HenrivanAalen]

Ich Grüße Euch

Folgendes Problem!

Ich möchte auf einer landkarten-ähnlichen Spielfläche die größte Anzahl zusammenhängender besetzter Spielfelder ermitteln.

Das zusammenzählen aller besetzten Spielfelder ist kein Problem. Mit welcher Methode kann ich eine Vorgehensweise berechnen die mir die größte Anzahl an zusammenhängenden Felder ausgibt. (Sprich die Felder die aneinander grenzen ohne Spielfelder dazwischen die von anderen Spielern besetzt sind)

Vorgehensweisen und Lösungsansätze würden mir hierbei erstmal weiterhelfen.

Mir fällt absolut nicht ein mit welcher Methode ich das lösen soll ...

Vielen Dank schonmal vorab.

P.S.: Der Lösungsansatz solllte alle kombinationen von variierenden Länderkonstellationen einer Karte und besetzte Felder beinhalten.

[X-Tender]

Grundsätzlich müsstest du einmal wissen welche Länder aneinandergrenzen.
Dann kannst du von einem land aus rekursiv durchgehen indem du alle Länder die an ihm angrenzen dir merkst.
Dann machst du das selbe halt für die Länder die angegrenzt sind. Markierst dir irgendwie dann ob das land bereits geprüft wurde.
Und am ende hast du dann eine liste mit ländenr die miteinadner verbudnen sind ,durch eine abfrage kansnt du dann besetzte und nicht besetzt länder ausfiltern ..

[hazy fantazy]

Sagen wir mal, du hast ein Spielfeld 8 x 8. Dann würde ich mit dem ersten Feld 0:0 beginnen und von dort ausgehend zusammenhängende Felder suchen, also prüfen, ob 0:1, 1:1 und 1:0 zusammenhängen und dann deren Nachbarn usw. Jedes Feld, dass du schon besucht hast, kannst du markieren. Markierte Felder werden nicht mehr beachtet. Irgendwann kommst du dann zu dem Punkt, dass die zusammenhängende Fläche zuende ist. Dann gehst du einfach der Reihe nach zum nächsten Feld, das noch nicht markiert ist, also der mögliche Anfang einer neuen zusammenhängenden Fläche ist und beginnst von vorne.

[hgseib]

http://de.wikipedia.org/wiki/Floodfill

[HenrivanAalen]

wunderbar
Danke euch ersteinmal.

Diese Ansätze hatte ich teilweise auch schon angeschnitten. Hab aber gedacht, daß sich dieses nicht umsetzen läßt ... allerdings komme ich wahrscheinlich mit dem Begriff "Stapelspeicher" weiter.
Dies ist dann wohl der Lösungsweg ... muss ich dann nur in einem code umsetzen und so flexibel gestalten, dass sich neue karten unter diesem prinzip durchlaufen lassen.

Danke Euch für die Denkansätze.
Ich wußte, dass ich hier in diesem Forum weiter kommen werden ... ist halt die beste Ideenschmiede im Netz

Gruß Henri

[hgseib]

die literatur erscheint mir etwas dürftig zu sein? ausser polygone füllen finde ich da wenig. obwohl sich dieser floodfill sehr einfach und sehr effizient beschleunigen lässt:
(ermittlung eines gültigen startpunktes ist nicht mit dabei.
und der geschwindigkeitsvorteil hängt natürlich sehr stark von der verwendeten programmiersprache ab.)

function fMakeA() {
	_a = [];
	_a.push("---xxx--xxx----");
	_a.push("---xxx----x----");
	_a.push("x--xxxxx--xxxx-");
	_a.push("x--xxxxx--xx---");
	_a.push("x-xxxxxxxxxx---");
	_a.push("xxxxxxxx--x----");
	_a.push("xx---xxx--x----");
	_a.push("xxx--xxx--xx---");
	_a.push("--xxxxxxx-----x");
	_a.push("-------------xx");
	_a.push("-----------xxxx");
	for (var i in _a) _a[i] = _a[i].split('');
	_anzX = 0;
	_startX = 3;
	_startY = 0;
}
_n = 100;
_time = getTimer();
for (var i = 0; i<_n; i++) fMakeA();
_makeT = getTimer()-_time;
// 
// 
// klassiker
function fill4(x, y) {
	if (_a[x][y] == 'x') {
		_a[x][y] = "o";
		_anzX++;
		fill4(x+1, y);
		fill4(x, y+1);
		fill4(x-1, y);
		fill4(x, y-1);
	}
}
_time = getTimer();
for (var i = 0; i<_n; i++) {
	fMakeA();
	fill4(_startX, _startY);
}
_t1 = getTimer()-_time-_makeT;
trace(_t1+" / "+_anzX);
trace(_a.join("\r").split(",").join(""));
trace("");
// 
// nur dann rekursion, wenn punkt
function fillHGS(x, y) {
	_a[x][y] = "o";
	_anzX++;
	if (_a[x+1][y] == 'x') fillHGS(x+1, y);
	if (_a[x][y+1] == 'x') fillHGS(x, y+1);
	if (_a[x-1][y] == 'x') fillHGS(x-1, y);
	if (_a[x][y-1] == 'x') fillHGS(x, y-1);
}
_time = getTimer();
for (var i = 0; i<_n; i++) {
	fMakeA();
	fillHGS(_startX, _startY);
}
_t2 = getTimer()-_time-_makeT;
trace(_t2+" / "+_anzX);
trace(_a.join("\r").split(",").join(""));
trace(int((1-_t2/_t1)*100)+"% schneller");

[HenrivanAalen]

Es war ein bischen Denkarbeit aber ich habe es umsetzen können.
Vielen Dank für die Denkanstöße.

Hab ein Mehrdimensionales-Array erstellt wo angegeben ist welche Nachbarländer ein Land hat.

Ein Array das die Spielfarbe eines jeden Landes festhält

Eine Zusätzliche Funktion mit einem Hilfsarray wo sämtliche Ländergruppen in einem neuen Array aufgelistet werden. (es kommt ja vor, dass es mehrere Grüppchen von zusammenhängenden Ländern sind)

Array sortiert und ich hatte das Ergebnis.

Der richtige Denkanstoß alles zusammenbringen und Aufgabe gelöst.

Vielen Dank.

Gruß Henri