Array Muster erkennung ?

Zespire · 13. Mai 2018

Ahoi !

Mir stellt sich folgendes Problem ich habe ein 2d Array und will wissen welche anliegenden Felder welchen Wert haben und welches Muster jene bilden.
Jetzt habe ich mir folgende Lösung überlegt ich gebe jedem Feld einen wert der so gewählt ist das alle möglichen Kombinationen eine einzigartige Summe bilden.

Hier zur Veranschaulichung wie ich mir das vorstelle.

Somit hätte ich für den Fall das es die 3 oben anliegenden Felder sind den Wert 111 und falls es die Felder oben links und unten rechts sind den Wert 10001 und so weiter für alle 64 möglichen Fälle.

Jetzt würde ich gerne wissen ob es dafür eine elegantere Lösung gibt oder wonach man da googeln könnte.

NeoExacun · 13. Mai 2018

Das kommt auf die Sprache und das Problem an.

kuddlmuddl · 13. Mai 2018

Deine Frage ist kaum zu verstehen.. wie genau ist das Interface deiner Anfrage und was für eine Antwort erwartest du?

will wissen welche anliegenden Felder welchen Wert haben

int left = feld[y][x-1] und right = feld[y][x+1]? Das wirst du kaum meinen?

und welches Muster jene bilden

Wie bilden Nachbarn denn ein Muster? Wenn du nur links und rechts wählst isses doch immer ne Linie aus 3 Quadraten? Wenn oben und unten dazu kommen hast du entweder nur ein Plus (5 Quadrate) oder noch die Ecken dazu und ein 3x3 Quadrat aus 9 Einzelquadraten.

Somit hätte ich für den Fall das es die 3 oben anliegenden Felder sind den Wert 111 und falls es die Felder oben links und unten rechts sind den Wert 10001 und so weiter für alle 64 möglichen Fälle.

Ich glaube jetzt erahne ich langsam, was dein Problem ist:
Du hast 64 Werte hintereinander - quasi linear angeordnet. Aber eigentlich sollen es 8x8 also 64 Felder in einem Quadrat sein?

Es gibt verschiedene Möglichkeiten aber was spricht denn dagegen, nochmal eine 8x8 Datenstruktur aufzubauen? Entweder kopierst du die Felder hierfür oder zumindest Referenzen/Pointer auf die original-Felder, falls du den doppelten Speicher nicht willst.
Die andere Möglichkeit sind Access-Funktionen.
Also

Code:

Zelle getZelle(int x, int y)
{
  assert(x >= 0); assert(x < 8);
  assert(y >= 0); assert(y < 8);
  return meinFeld[x+y*8];
}

Durch x+y*8 bekommst du den korrekten Index in deiner linearen 64er-Array-Anordnung.

Zespire · 13. Mai 2018

Sprache wäre in dem Fall C# sollte aber ein allgemeines Problem sein hier noch etwas pseudo Code.

Code:

	int[,] array;
		int foo;
		int sum;

		if(array[0,1] == foo)
			sum += 1;
		if(array[1,1] == foo)
			sum += 10;
		if(array[1,0] == foo)
			sum += 100;
		if(array[1,-1] == foo)
			sum += 1000;
		if(array[0,-1] == foo)
			sum += 10000;
		if(array[-1,-1] == foo)
			sum += 100000;
		if(array[-1,0] == foo)
			sum += 100000;
		if(array[-1,1] == foo)
			sum += 1000000;

		//Jetzt weiß ich anhand der summe welches Muster die Nachbarn mit dem wert foo bilden.

kuddlmuddl schrieb:
Deine Frage ist kaum zu verstehen...

Wen dem nicht so wäre hätte ich es gegoogelt

coolmodi · 13. Mai 2018

Wie genau weißt du das dann? Du hast es doch dann nur von einem array in eine Zahl "konvertiert", aber das Programm weiß genau so wenig wie vorher, und wenn du es ausgibst ist es schwerer zu lesen als wenn du einfach das array in einer 3x3 Matrix ausgibst. Ich verstehe das Ziel einfach nicht.

Edit: Und wenn du es in eine Zahl konvertieren willst, dann nimm ne Bitmaske, sprich [1,2,4,8,16,32,...], also nur 2^x, denn dann kannst du mit z.B.

Code:

if ((sum&16) != 0) {
    // sum enthält 16
}

testen, ob ein bit enthalten ist.

Nilson · 13. Mai 2018

Heißt du willst dein Muster aus 3x3 Zellen in eine Zahl konvertieren? Und anhand der Zahl das Muster identifizieren?
Dann nimm die Lösung von coolmodi mit der Bitmaske.
Pseudocode:

Code:

word muster = 0; 
int counter = 0;
for(i=-1;i<2;i++){
 for(j=-1;j<2;j++){
  if(array[i,j]) == foo) {
   muster.set_bit(counter); //Setzt Bit in Muster an stelle counter
  }
  counter++;
 }
}

Zespire · 13. Mai 2018

Habe eine Shader geschrieben der wie eine Art splat map funktioniert nur ohne Beschränkung auf 4 Texturen oder allgemein die rgba Kanäle einer splat map zu nutzen.

Damit der Shader funktioniert muss ich jedoch bei der Generierung des Terrains 3 UV Sets erstellen bei einem davon ist es wichtig zu wissen welches Muster anliegende Felder mit dem selben wert bilden damit die blend Funktion den richtigen Teil der Textur projiziert...

Jetzt würde ich gerne darauf verzichten in 3 Wochen fest zu stellen das dass man das ganze einfacher prüfen kann nur leider finde ich bei google nichts brauchbares/vergleichbares....

[Edit]:
Und die Größe des Arrays sollte egal sein da ein Feld nicht mehr als 8 Nachbarn haben kann.

coolmodi · 13. Mai 2018

Elementarer als iterieren und dabei die Daten in eine andere Form brigen geht kaum, aber welche Form das ist können wir dir nicht sagen. "Muster" ist eben kein Datentyp

In welcher Form erwartet die "blend" Funktion, oder was auch immer anhand des Musters etwas machen soll, denn die Daten? Das ist doch die wichtigste Information.

Zespire · 13. Mai 2018

Nilson schrieb:
Heißt du willst dein Muster aus 3x3 Zellen in eine Zahl konvertieren? Und anhand der Zahl das Muster identifizieren?
Dann nimm die Lösung von coolmodi mit der Bitmaske.
Pseudocode:

Code:

word muster = 0; int counter = 0; for(i=-1;i<2;i++){ for(j=-1;j<2;j++){ if(array[i,j]) == foo) { muster.set_bit(counter); //Setzt Bit in Muster an stelle counter } counter++; } }

Set_bin wäre

Code:

muster = 1 << counter;

und dann wäre

Code:

if(muster == 1)

nur das Feld unten links blockiert oder wie würde das genau funktionieren ?

Hatte auch schon den Gedanken an eine Bitmaske nur leider habe ich da so ziemlich keine Erfahrung mit und es kam mir ziemlich ähnlich mit meinem Versuch vor.

Ergänzung (14. Mai 2018)

coolmodi schrieb:
Elementarer als iterieren und dabei die Daten in eine andere Form brigen geht kaum, aber welche Form das ist können wir dir nicht sagen. "Muster" ist eben kein Datentyp

In welcher Form erwartet die "blend" Funktion, oder was auch immer anhand des Musters etwas machen soll, denn die Daten? Das ist doch die wichtigste Information.

BlendIndex ist eine zahl zwischen 0 und 64 abhängig vom Muster der anliegenden Felder.

Code:

	private void AddBlendUvCoordinates(TerrainMap map,float currentAlbedoIndex, float blendIndex)
	{
		float widthOffsetx = 1.0f / (map.Biome.BiomeTiles.Length);
		float tileTextureInde = blendIndex;
		float vTopLeftX = widthOffset * currentAlbedoIndex;
		float vTopLeftY = 1.0f - tileTextureInde * scale;
		float vTopRightX = vTopLeftX + widthOffset;
		float vTopRightY = vTopLeftY;
		float vButtomRightX = vTopRightX;
		float vButtomRightY = 1.0f - tileTextureInde * scale - scale;
		float vButtomLeftX = vTopLeftX;
		float vButtomLeftY = vButtomRightY;
		uvC.AddRange(new Vector2[]{new Vector2(vButtomLeftX,vButtomLeftY),new Vector2(vButtomRightX,vButtomRightY),new Vector2(vTopLeftX,vTopLeftY), new Vector2(vTopRightX,vTopRightY)});
	}

coolmodi · 13. Mai 2018

Zespire schrieb:
Hatte auch schon den Gedanken an eine Bitmaske nur leider habe ich da so ziemlich keine Erfahrung mit und es kam mir ziemlich ähnlich mit meinem Versuch vor.

Bitmasken sind eigentlich extrem einfach. Du musst dir die Zahl einfach als Binärwert vorstellen. Mit dem bitwise-and operator (&) kannst du dann testen, ob beide Seiten das gleiche bit enthalten:

Code:

int x = 0; 	// 0000 0000  vereinfacht, eigentlich 32 bits
x = 1;     	// 0000 0001  1. bit ist gesetzt
x = x << 1	// 0000 0010  shift operator VERSHIEBT nur, er fügt nichts hinzu!!!
x |= 1 << 2	// 0000 0110  das aber setzt ein bit
x &= ~(1 << 1) // 0000 0100  und das entfernt ein bit (glaube ist so richtig)
// x = 4
x = x + 64	// 0100 0100  3. und 7. bit gesetzt, da 64 0100 0000 ist
// x = 68
y = x & 32 	// y = 0, da 32 (0010 0000) nicht in 68 (0100 0100) ist
z = x & 96 	// z = 64, da das 7. bit aus 68 (0100 0100) auch in in 96 (0110 0000) ist
w = x & 68 	// w = 68 da bits auf beiden seiten gleich

Du mappst praktisch booleans auf bits, und kannst so 32 verschiedene (bei uint) in einer Zahl speichern. Wichtig ist nur, dass es die dichteste Speichermöglichkeit in der Form ist, da eben 1bit=1Information, bei deinen Zehnerpotenzen brauchst du mehr Speicher für das Gleiche

Zespire schrieb:
BlendIndex ist eine zahl zwischen 0 und 64 abhängig vom Muster der anliegenden Felder.

Ich denke mal blendIndex funktioniert dann so, dass jede Kombination eben eine Zahle ist, z.B.
Rechts oben + Links unten + Rechts mitte = 28
Nehmen wir weiterhin mal folgende Binärwerte für deine array an:

Code:

1      2      4

128           8

64     32     16

Dann entspricht RO+LU+RM = 4+64+8 = 76, dementsprechend kannst du eindeutig dieses "Muster" auf den entsprechenden blendIndex Wert abbilden, z.B.:

Code:

if (maske & 76) {
   blendIndex = 28
}

Aber da die Werte immer gleich sind, und du auch immer nur "übersetzen" willst, kannst du einfach noch einen LUT erstellen, welcher alle möglichen Maskenwerte auf die jeweiligen blendIndex Werte abbildet. Oder noch mal zusammengefasst:

Nachbarfelder mit loops iterieren (oder 8x ifs, sollte schneller sein

), dabei Maske bilden, und dann mit Hilfe eines LUT den blendIndex bekommen.
Da du nur 8 bits (1000 0000=128) brauchst kannst du für die Maske auch ein byte statt (u)int nutzen.

Edit: Eine andere möglichkeit ein bit an einer bestimmten stelle zu setzen ist das

Code:

maske |= 1 << position
// z.B.
maske |= 1 << 3
// entspricht (sofern maske vorher 0 war!!)
maske += 8

Hab das oben mal ergänzt

Zespire · 14. Mai 2018

Danke für die ausführliche Antwort hatte mir auch schon etwas zusammen geschustert wobei es scheinbar daran scheitert meine Maske als Enum richtig zu definieren.

Code:

	public enum PossibleCombinations {topRow  = 5 | 6 | 4, right = 3}

	void Test () 
	{
		int[,]array = new int[5,5];
		int foo = 0;
		int sum = 0;

		if(array[0,1] == foo)
			sum = 1 | (1 << 0);
		if(array[1,1] == foo)
			sum = 1 | (1 << 1);
		if(array[1,0] == foo)
			sum = 1 | (1 << 2);
		if(array[1,1] == foo)
			sum = 1 | (1 << 3);
		if(array[0,1] == foo)
			sum = 0 | (1 << 4);
		if(array[1,1] == foo)
			sum = 0 | (1 << 5);
		if(array[1,0] == foo)
			sum = 0 | (1 << 6);
		if(array[1,1] == foo)
			sum = 1 | (1 << 7);

		if((sum & (int)PossIbleCombinations.topRow) == 0)
			Console.WriteLine("läuft");
	}

coolmodi · 14. Mai 2018

Zespire schrieb:
wobei es scheinbar daran scheitert meine Maske als Enum richtig zu definieren.

Code:

// Hashtable = sehr schnell ;)
var blendLut = new Dictionary<byte, float>();
//
// 1      2      4
//
// 128           8
//
// 64     32     16
//
// RO+LU+RM = 4+64+8 = 76
// RO+LU+RM als blendIndex soll 28 sein
blendLut[76] = 28.0F;
// Analog für alle anderen kombinationen füllen

byte maske = 0;
int foo = 1;

// Ohne array da kein Bock zu initialisieren :D
if(0 == foo)
	maske = 1;
if(0 == foo)
	maske |= 1 << 1;
if(1 == foo) // == Rechts oben
	maske |= 1 << 2;
if(1 == foo) // == Rechts mitte
	maske |= 1 << 3;
if(0 == foo)
	maske |= 1 << 4;
if(0 == foo)
	maske |= 1 << 5;
if(1 == foo) // == Links unten
	maske |= 1 << 6;
if(0 == foo)
	maske |= 1 << 7;

Console.WriteLine(maske); // 76

float blendIndex = blendLut[maske];

Console.WriteLine(blendIndex);  // 28

siehe https://dotnetfiddle.net/zkRgY0

Zespire · 14. Mai 2018

Vielen vielen dank für die ausführlichen Antworten hatte mich bei deinem ersten post gewundert wie bei dir die werte 1 / 2 / 16 / 128 zustanden kommen aber die setzen wir ja selber.

Und du kannst dir nicht vorstellen wie begeistert ich war als ich beim ersten lesen

Code:

// Analog für alle anderen kombinationen füllen

überlesen habe

Ergänzung (14. Mai 2018)

Im Nachhinein stellt sich mir doch die Frage ob ich mit dem Wissen über die Ergebnisse der Bit Operationen nicht einfach

Code:

If(foo == 0)
    Sum += 1;
If(foo == 1)
    Sum += 2;
... 
 If(foo == 0)
    Sum += 128;

schreiben könnte oder würde das etwas am rechen Aufwand ändern.

coolmodi · 14. Mai 2018

Zespire schrieb:
schreiben könnte oder würde das etwas am rechen Aufwand ändern.

Keine Ahnung was der compiler da am Ende draus macht, aber im Zweifel bencht man es halt kurz, und bei 99999999 Durchläufen habe ich 2307ms vs. 2323ms auf dotnetfiddle.net. Also scheint völlig wurst zu sein.

rob- · 14. Mai 2018

Ich verstehe dein Problem nicht genau. Dein 2D Array ist doch nichts anderes als eine Tabelle mit Zeilen- und Spaltennummer. Du kannst doch einfach beliebig darüber iterieren, musst nur die Anzahl der Spalten und Zeilen kennen - das erfährst du über size(), da sich das Array bei seiner Erstellung diese Daten merkt.

Array[0][0] ist links oben. Du weist dass du 3 Spalten hast. Dann fragst du einfach Array[0][0], Array[0][1], Array[0][2] in einer Schleife ab und fertig.

Wenn du in der Mitte bei [1][1] startest, schaust einfach was links und Rechts ist, geht ja immer alles im Beispiel oben von 0-2. Dafür schreibst dir einen eigenen Iterator der auf einem Array arbeitet und dir die Daten entsprechend ausspuckt. Als Eingabe dient dann ein Array und die Zeilen- und Spaltennummer eines Kästchen, sowie die Angabe ob vertikal oder horizontal geschaut werden soll. Das wäre die sauberste Lösung, da du beliebige Array durchsuchen kannst, unabhängig ihrer Größe. Die Benutzung ist einfach, da du nur ein Array und Spalte / Zeile angeben musst.

Du kannst natürlich auch statt eines Iterators auch wie eine Datenbank einen Hash aufbauen. Dein Key wäre dann das Tupel aus (Zeile, Spalte) - der Einfachheit halber als String da die Kombo einzigartig ist, der Wert die Zahl die im Kästchen steht. Abruf dann per Hash["0,0"], Hash["0,1"], Hash["0,2"]. Aber auch hier wirst du eine Form von Schleife / Iterator brauchen, nur nicht so komplex.

Du könntest aber auch Zeilenweise / Spaltenweise hashen, so dass Zeile / Spalte (Hash["1"]) ein Array mit den Werten in Reihe enthält.

Zespire · 14. Mai 2018

Weil 8 if Abfragen und eine LUT mit 68 Werten wesentlich besser ist als 68 if Abfragen.

Die Frage war einfach nur ob es noch besser geht zum Schluss habe ich die 10er Potenzen durch 2er ersetzt.

Suche

Array Muster erkennung ?

Zespire

Lieutenant

NeoExacun

Lieutenant

kuddlmuddl

Commander

Zespire

Lieutenant

coolmodi

Lt. Commander

Nilson

Grand Admiral

Zespire

Lieutenant

coolmodi

Lt. Commander

Zespire

Lieutenant

coolmodi

Lt. Commander

Zespire

Lieutenant

coolmodi

Lt. Commander

Zespire

Lieutenant

coolmodi

Lt. Commander

rob-

Gast

Zespire

Lieutenant

Ähnliche Themen