2d-Array - gleiche Nachbarn zählen

[Tachyon176]

Hallo,

ich suche einen Algorithmus, mit dem ich zählen kann, wie viele Felder des gleichenTyps zusammenhängend in einer 2d-Map sind.
Ich habe z.b. eine 10x10 Map, jedes Feld hat eine Farbe. Wenn nun 5 Felder mit der gleichen Farbe zusammenhängen (nebeneinander/übereinander), dann soll jedes Feld den Wert 5 haben.
Ich habe versucht dass ähnlich mittels rekursiven Floodfill Algo umzusetzen - da klappt aber nicht ganz.
Jemand eine Idee?

 

[mikdoe]

zeig mal deinen code

 

[Tachyon176]

z.Zt. sieht es so aus. Ist aber nur ein versuch gewesen.

	this.CheckConnections = function (lastField, map, x, y) {

		var mapField = map.Get(x, y);
		var nextval = 0;
		if (x < (map.width) && y < (map.height)) {
			if (lastField != null && mapField != null && lastField.gem != null && mapField.gem != null && lastField.gem.type == mapField.gem.type) {
				// letztes Feld ist gleich mit diesem: raufzählen
				mapField.count = lastField.count + 1;
			}
			else
				mapField.count = 1;
			if (x < (map.width - 1)) {
				nextVal = this.CheckConnections(mapField, map, x + 1, y);
				if (nextval > mapField.count)
					mapField.count = nextval;
			}
			if (y < (map.height - 1)) {
				nextVal = this.CheckConnections(mapField, map, x, y + 1);
				if (nextval > mapField.count)
					mapField.count = nextval;
			}
		}
		return (mapField.count);
	}

 

[mikdoe]

müsste da nicht irgendeine art von schleife sein die jede 5er kombi testet?

 

[kkapsner]

Brauchst du den Wert nur für ein Feld oder für alle?

 

[Tachyon176]

müsste da nicht irgendeine art von schleife sein die jede 5er kombi testet?

Eigentlich nicht. Es fehlen nur die Aufrufe in die "Richtungen" x-1 und y-1
Aber dann werdem trotzdem die Werte einer Gruppe in verschiedene Richtungen nicht gemeinsam addiert.

Brauchst du den Wert nur für ein Feld oder für alle?

mittlerweile reicht der Wert in einem Feld.

Edit: Quote

- - - Aktualisiert - - -

Hab's durch die Hinweise neu nachgedacht. Danke

1) komplett durch die Map durchiterieren - jede Gruppe finden.
2) Gruppe mittels floodfill markieren und parent merken (ein Feld reicht)

    this.FillGroups = function (lastField, map, x, y) {

        var currentField;
        currentField = map.Get(x, y);
        if (currentField == null || currentField.gem == null || currentField.checked == true)   // bereits gecheked
            return;
        currentField.checked = true;

        // rechts
        if (x < map.width - 1) {
            var nextField = map.Get(x + 1, y);
            if (nextField.gem != null && nextField.checked == false && currentField.gem.type == nextField.gem.type) {
                nextField.parentGroup = lastField.parentGroup;
                nextField.parentGroup.count++;
                this.FillGroups(nextField, map, x + 1, y);
            }
        }
        // links 
        if (x > 0) {
            var nextField = map.Get(x - 1, y);
            if (nextField.gem != null && nextField.checked == false && currentField.gem.type == nextField.gem.type) {
                nextField.parentGroup = lastField.parentGroup;
                nextField.parentGroup.count++;
                this.FillGroups(nextField, map, x - 1, y);
            }
        }
        if (y < map.height - 1) {
            var nextField = map.Get(x, y + 1);
            if (nextField.gem != null && nextField.checked == false && currentField.gem.type == nextField.gem.type) {
                nextField.parentGroup = lastField.parentGroup;
                nextField.parentGroup.count++;
                this.FillGroups(nextField, map, x, y + 1);
            }
        }
        if (y > 0) {
            var nextField = map.Get(x, y - 1);
            if (nextField.gem != null && nextField.checked == false && currentField.gem.type == nextField.gem.type) {
                nextField.parentGroup = lastField.parentGroup;
                nextField.parentGroup.count++;
                this.FillGroups(nextField, map, x, y - 1);
            }
        }

    }


    this.CheckGroups = function map() {
        this.ResetChecked();
        for (var y = 0; y < this.map.height; y++) {
            for (var x = 0; x < this.map.width; x++) {
                var field = this.map.Get(x, y);
                if (field != null && field.checked == false) {
                    field.parentGroup = field;
                    field.count = 1;
                    this.FillGroups(field, this.map, x, y);
                }
            }
        }

    }