[C#/Alg] Herkenning rechthoeken in 2D grid

[Sebazzz]

Voor een spelletje moet er in een 2D grid gezocht worden naar rechthoeken. De rechthoek moet minstens 3x1 (of 1x3) blokken groot zijn tot een maximum van 9x3 blokken. Omdat de blokken in het grid verschillende kleuren kunnen hebben is het ook belangrijk dat de rechthoek dus één kleur heeft. Het raster hoeft niet volledig gevuld te zijn, dus er kunnen ook coordinaten zijn waarbij de blokken op null staan. Een visuele representatie van het probleem:

In het linkergrid zie je een beginsituatie. In het rechtergrid zie je hoe het zou moeten. Merk op dat de het paarse blok rechts in twee blokken is verdeeld. Het moet ook mogelijk zijn om blokken te 'mergen'. Zeg dat je eerste een 3x1 blok heb met daarop een 2x1 blok. Het 2x1 wordt niet één rechthoek, want het is te klein. Het 3x1 rechthoek wel. Hierna valt er naast het 2x1 blok een blok. Hierdoor kan het een 3x1 rechthoek worden, maar het moet eigenlijk een zo groot mogelijk rechthoek worden. Een 3x2 rechthoek dus:


De vraag is, hoe kan ik efficient de blokken herkennen? Ik zou het niet weten hoe ik het moet oplossen.

Nu kan ik zelf wel wat proberen, maar ik weet bijna zeker dat als ik het schrijf het zo ongelooflijk traag wordt, of het gaat zowieso niet goed werken. Nu weet ik bijna wel zeker dat er een algorithme voor bestaat (pattern recognition?), maar de naam zou ik niet weten. Wie helpt mij op weg?

[Creepy]

Aangezien we hier toch echt zelf ontwikkelen: probeer toch echt zelf eens wat, of post eens (uitleg of in pseudo taal) wat je zelf voor idee hebt om dit op te lossen. Nu is het niet meer dan een "ik wil dit, wie bedenkt het voor me" en dat is natuurlijk ook weer niet de bedoeling.

[Arise]

Met een 2 dimensionele array, paar for lusjes, bools en tellertjes moet dat wel lukken.

[roy-t]

Je kunt vanaf onderaf het meest linker blokje pakken. Dan in een loopje proberen om telkens 1 stap omhoog en 1 stap naar rechts te doen je stopt pas als beide niet meer kan. Nu heb je een soort rechthoek gegroeid.

Daarna ga je verder naar het eerste blokje rechts van je dat niet meer voldoet, en daarna naar boven en zo verder .

Dit is even kort door de bocht, vind ook vierkanten, maar vind volgens mij ook redelijk snel zo groot mogelijke rechthoeken door 1 van de 2 checks eerst te doen heb je affiniteit voor liggende of staande rechthoeken. Je vind ook vierkanten maar dan moet je maar even kijken of je die ook wilt. Als er een grote en een kleine rechthoek op elkaar liggen en overlappen krijg je mogelijk rare problemen, moet je even kijken hoe je dat wilt oplossen .

[Sebazzz]

Creepy schreef op zaterdag 05 december 2009 @ 14:14:
probeer toch echt zelf eens wat, of post eens (uitleg of in pseudo taal) wat je zelf voor idee hebt om dit op te lossen.

Zelf zat ik aan het volgende te denken:

Met (0,0) als de hoek linksonder ieder vakje afgaan (1,0), (2,0) ... (0,1), (1,1) en per vakje kijken of het volgende vakje of vakje erboven van dezelfde kleur is, en daar weer dezelfde procedure uitvoeren.

Nu is het niet meer dan een "ik wil dit, wie bedenkt het voor me" en dat is natuurlijk ook weer niet de bedoeling.

Dat is niet de intentie waarmee ik dit topic heb geopend, dat snap je hopelijk wel

[Mithrandir]

Maakt het uit welk antwoord gekozen wordt als je meerdere mogelijkheden hebt? Bijvoorbeeld:

code:

XXXX
XXXX
XXX

Kan als 4x2 + 1x3 blok of als 3x3 + 1x2 blok gezien worden. Wil je alle oplossingen vinden? De grootste? Of maakt het niet uit?

[Sebazzz]

Het liefst de grootste, ik denk dat implementatie een stuk eenvoudiger is zo. Ik heb nog zitten denken:
Ik kan het raster ook rij voor rij behandelen en daarbij een flag ofzo op de blokjes te zetten die aaneensluiten. Daarna ga ik kolom voor kolom kijken en kijken wat het grootste rechthoek is die ik eruit kan krijgen.

code:

ABBDDEEF
ABBBDEEE
BBBDDDEE

code:

AbbddeeF
AbbbDee
bbbdddee

code:

AbbDDeeF
AbbBDeeE
BbbdddEE

[Mithrandir]

Als een blok maximaal 9x3 groot is, zijn er minder dan 27 mogelijke blokgroottes. Als een bepaalde kleine blokgrootte niet te vinden is, bestaat een groter blok ook niet, dus meestal zul je een groot deel van je zoekruimte zowiezo niet hoeven te verkennen.

Je blokken kunnen op een paar honderd manieren in je ruimte zitten, dus dat is bruteforce prima te doen.

Het is ongetwijfeld mogelijk om het 'slimmer' te doen, maar als je daar niet heel goed over nadenkt zal het waarschijnlijk alleen maar langer duren. Bruteforce is in dit geval een prima oplossing, ik zou er pas weer over nadenken als het daadwerkelijk te lang duurt.

[ Voor 10% gewijzigd door Mithrandir op 06-12-2009 18:28 ]

[Sebazzz]

Ik weet zeker dat het te lang gaat duren. Het is wel Silverlight, dus supersnel zoals .NET PE zelf wel is. Daarnaast moet het niet te lang duren, het is voor een internet puzzelspel. Je hebt gelijk dat als een klein blok niet te vinden is, dan is een groot blok ook niet te vinden, dus daarmee zou ik tijdwinst maken, maar met die methode van jou moet ik wel 27 blokken handmatig programmeren.

Ik ga eerste wel wat experimenteren met de methode van roy-t.

[kaesve]

ik ben toch wel geinteresseerd in een slimmere manier.. ik ben een beginnend programmeurtje die deze zomer maar eens begonnen is met c# en het xna-framework. ik gebruik iets dat hier sterk op lijkt voor het minimaliseren/optimaliseren van collisions in mijn game (veel sprites bestaan uit grote rechthoeken en is dus goed te optimaliseren)..
maar ik heb nog geen algoritme kunnen vinden of bedenken dat steeds alles kan opdelen in zo min mogelijk rechthoeken.

ik zou het dus jammer vinden als we nu maar gewoon kiezen voor de brute-force manier..

omdat GoT altijd graag hoort wat we zelf allemaal al hebben geprobeert:

het beste waar een vriend van mij (die ook in mijn projectje mee doet) mee kon komen was iets dat erg op het idee van roy-t lijkt:

je begint in een hoek. lets say links onder. dan ga je zo ver mogelijk naar rechts, totdat je een andere kleur tegen komt. dan ga je voor elk blokje dat je naar rechts bent gegaan steeds 1 naar boven, totdat je ook daar ergens een andere kleur tegen komt..
dit levert echter niet altijd 'het beste' resultaat op.

@roy-t: begrijp ik je verhaaltje verkeerd, of klopt het niet? even laten zien hoe ik het interpreteer met een plaatje:



daar komen geen mooie rechthoeken uit :[

[Sebazzz]

kaesve schreef op zondag 06 december 2009 @ 19:01:
@roy-t: begrijp ik je verhaaltje verkeerd, of klopt het niet? even laten zien hoe ik het interpreteer met een plaatje:

[afbeelding]

daar komen geen mooie rechthoeken uit :[

Vergeet niet het regeltje: "Daarna ga je verder naar het eerste blokje rechts van je dat niet meer voldoet, en daarna naar boven en zo verder ". Dan krijg je dit:
.
Of als je met horizontaal schuiven begint dit:

In het onderste geval zijn de coordinaten (top-links en bottom-rechts) van de rechthoek (a_x-begin, b_y-eind) (b_x-begin, b_y-eind).

[Mithrandir]

Het systeem van roy klinkt leuk, maar het geeft niet altijd de juiste oplossing. Vooral met vreemd gevormde blokjes en lange 'gangen' kun je zien dat ook die oplossing snel degradeerd tot bruteforce.

[Sebazzz]

Wat een lekkere douche op een zondagavond niet kan doen

Ik heb het volgende idee gekregen:
3x1, 1x3, 1x2, 1x**** blokken zijn allemaal makkelijk te herkennen. Dit kan je dus doen in horizontale richting (1) en verticale richting (2). Afhankelijk of je liever een liggend of staand blok wil kan je als breedte van het blok gebruiken de kortste horizontale strook die de verticale stroken aanraken of de breedte van het totaal aantal verticale stroken. De hoogte krijg je door de hoogste van het totaal aantal horizontale stroken te nemen of de kortste verticale strook te nemen, weer afhankelijk of je liever een staande of liggende rechthoek wilt. En zo krijg je 3. Is dit slimmer?

[Sebazzz]

Ik ga toch maar voor de domme manier. Ik krijg het niet lekker geïmplementeerd. Ik hoef toch maar blokken van 1x1 tot 5x5 en van 1x3 tot 9x3 te herkennen dus.

[kaesve]

jammer, want nu zit ik zelf nog steeds met het zelfde probleem (maar dan zonder een 'domme' oplossing, omdat er bij ons geen limiet aan mogelijkheden is..)

[pedorus]

Zonder duidelijke regels is het nogal onduidelijk wat een 'slimme' oplossing zou moeten doen. Verder lijkt dit probleem erg op dat in Programming Contest Nieuwe Stijl: Contest 4. Tal van floodfill-varianten zijn daar al besproken.

[.oisyn]

Niet helemaal gerelateerd, maar vond 'm wel grappig: http://www.collegehumor.com/video:1924722

Ontopic: brute force lijkt me niet zo'n probleem eerlijk gezegd. Ik bedoel, zo groot is je grid nou ook weer niet.

[PrisonerOfPain]

.oisyn schreef op donderdag 10 december 2009 @ 17:25:
Ontopic: brute force lijkt me niet zo'n probleem eerlijk gezegd. Ik bedoel, zo groot is je grid nou ook weer niet.

Inderdaad een simpel floodfill algoritme zou dit probleem zo op moeten kunnen lossen.

[Sebazzz]

Dat zeggen jullie wel, maar het is een online game, en het moet mogelijk eens per seconde worden uitgevoerd. Ik heb te weinig, zeg maar niet, in Silverlight geprogrammeerd om te begrijpen hoe langzaam Silverlight is, maar het moet wel soepel blijven. Sowieso snap ik niet hoe een floodfill algorithme mij kan helpen Want als ik op de wiki kijkt, kan je inderdaad een vlak herkennen en verwijderen. Dit is wat ik al in mijn spel doet (als er een speciaal roze blokje op een roze blokje valt, dan worden alle roze blokjes in connectie daarmee verwijderd), maar de vierkanten hebben een specifieke betekenis.

Ik had weer even een brainfart onder de douche, en daar kwam dit uit:

Het algorithme begint bij het blok rechtsonderin, zeg punt A:
• Ga omhoog tot je niet verder kan, noem dit punt B
• Ga bij beginpunt links verder tot je niet verder kan, noem punt C
• Probeer bij punt B tot de x-coordinaat van punt C te komen, indien dat niet lukt, teruggaan naar B, ééntje lager gaan (noem dit punt D) en opnieuw proberen. Noem dit punt E.
• Probeer bij punt C omhoog te gaan om punt E te raken, indien dit niet lukt, terug gaan en opnieuw proberen.
• Rechthoek is nu A,B,D,E.

[ Voor 33% gewijzigd door Sebazzz op 10-12-2009 22:43 ]

[.oisyn]

Sebazzz schreef op donderdag 10 december 2009 @ 22:30:
Dat zeggen jullie wel, maar het is een online game, en het moet mogelijk eens per seconde worden uitgevoerd. Ik heb te weinig, zeg maar niet, in Silverlight geprogrammeerd om te begrijpen hoe langzaam Silverlight is, maar het moet wel soepel blijven.

Kom op zeg, binnen een seconde. Dat kan in Javascript zelfs gemakkelijk

[Sebazzz]

.oisyn schreef op donderdag 10 december 2009 @ 23:03:
[...]

Kom op zeg, binnen een seconde. Dat kan in Javascript zelfs gemakkelijk

Ik hoop het.

Ik ben wel wat vaker bang voor performance, maar dat blijkt altijd wel mee te vallen.

[pedorus]

Sebazzz schreef op donderdag 10 december 2009 @ 23:08:
[...]

Ik hoop het.

Ik ben wel wat vaker bang voor performance, maar dat blijkt altijd wel mee te vallen.

Dit lukt ook met javascript en een brakke browser nog makkelijk, is ook mijn inschatting. Waarom test je het niet gewoon bruteforce uit?

Sebazzz schreef op donderdag 10 december 2009 @ 22:30:
Sowieso snap ik niet hoe een floodfill algorithme mij kan helpen Want als ik op de wiki kijkt, kan je inderdaad een vlak herkennen en verwijderen.

Hoezo zou floodfill juist moeten verwijderen? Het is alleen maar een methode om iets te selecteren en daar iets mee te doen...

• Rechthoek is nu A,B,D,E.

Waarom zou 2*3 beter zijn dan 3*2, of 1*3+1*4+1*3? De gedachte daarachter maakt nogal uit hoe je algoritme eruit moet zien. En hoe kom je ertoe dat je begint bij 1?

[Sebazzz]

pedorus schreef op donderdag 10 december 2009 @ 23:12:
[...]

Dit lukt ook met javascript en een brakke browser nog makkelijk, is ook mijn inschatting. Waarom test je het niet gewoon bruteforce uit?

Omdat ik niet te lang erop wil zitten, ik ben al genoeg tijd kwijt aan het spel. Bovendien ben ik de enige programmeur in mijn groepje.

Hoezo zou floodfill juist moeten verwijderen? Het is alleen maar een methode om iets te selecteren en daar iets mee te doen...

Nee maar daar gebruik ik het voor

[...]
Waarom zou 2*3 beter zijn dan 3*2, of 1*3+1*4+1*3? De gedachte daarachter maakt nogal uit hoe je algoritme eruit moet zien. En hoe kom je ertoe dat je begint bij 1?

Hoe groter hoe beter. Tot een maximum van 9x3.

[Anoniem: 267113]

Ik kan je een leuke tip geven (aangezien ik zelf meer dan eens zulke constructies heb moeten proggen/ontwikkelen). Benader het probleem eens van de object geörienteerde kant

Doe eens geen loop op het hele raster, maar laat elk blok zijn eigen buren bijhouden. Hiermee doorloop je niet steeds het hele raster maar controleer je of naaste buren nog andere matchende buren hebben (een iteratieve functie die zichzelf binnen zijn eigen functie nogmaals aanroept "recursieve itteratie (dacht ik)").

Ook wordt het op deze manier makkelijk om te "mergen" aan de kant waar een buur zit hoeft je namelijk geen lijn te tekenen en andersom.

Hieronder een "voorbeeld" van een classe veld

psuedo code:

C#:

public class veld {
  private Point currentIndex;
  private string color;
  public bool hasMatch {
      // controleer buren currentIndex.X-1 of +1 en currentIndex.Y-1 of +1 && buren.color == this.color
  }

  public List<string> getMatchingSides {
      //geef een list terug met matchende buren ("left", "right", "top", "bottom") (maak hier een kleine enum van)
      //je kan zelfs nog referenties van de matchende buren zelf terug geven, 
      //dan wordt het ERG makkelijk om bepaalde patronen te doorgronden
  }
}

Met een bovenstaande klasse is het appeltje-eitje een algorithme te bedenken wat een bepaalde constructie aan buren zal herkennen (en hoeveel)

[ Voor 19% gewijzigd door Anoniem: 267113 op 18-12-2009 22:28 ]

[Sebazzz]

Anoniem: 267113 schreef op vrijdag 18 december 2009 @ 22:15:
Met een bovenstaande klasse is het appeltje-eitje een algorithme te bedenken wat een bepaalde constructie aan buren zal herkennen (en hoeveel)

Niet echt, want je startpunt is nog steeds een blokje, of het nou in dit algoritme is of ieder ander algoritme. Of zie ik dit verkeerd?

[pedorus]

Volgens mij gaat dat je ook niet echt helpen. Behalve met veel overhead aan classes zit je in weze nog steeds met hetzelfde probleem.

Weet je inmiddels al eens of een 3*2 beter is dan een 2*3? Het je het nu al eens brute-force uitgeprobeerd? (Dus gewoon op ieder mogelijk startpunt proberen met dat punt als linkerbovenhoek een zo groot mogelijk gebiedje te maken. Op het einde het grootst gevonden rechthoek weghalen, en opnieuw beginnen. Stoppen als er geen rechthoek meer gevonden is.)

[Anoniem: 267113]

Tsja kan niet slapen en dan ga je nadenken over de raarste dingen

EDIT: zie nou dat onderstaande niet gaat werken... nvm (was ook wel erg laat)

Als je de eigenschappen bekijkt van een blokje dat deel uitmaakt van een raster met een lengte 2 of meer en een hoogte van 2 of meer, zie dat deze altijd 2(of meer) matchende buren heeft welke zelf ook weer 2(of meer) matchende buren heeft Let wel op dat als een blokje een match heeft met een veld (die zelf maar 2 matches heeft dat de matches van dat veld geen tegenpolen zijn boven-onder of rechts-links anders kunnen non-rechthoekige matches intstaan.

Dus je loopt eenmaal door alle velden heen en bekijkt de overeenkomende kleur, 2(of meer) matchende velden en of deze matchende velden zelf ook weer 2(of meer) matchende buren heeft (waarvan de matches , als het er maar 2 zijn geen tegenpolen zijn). Gooi alle velden die hieraan voldoen in een list (of andere verzameling) en kijk vervolgens of deze groter/kleiner is dan de 1x1(of groter) rasters (daar is bovengenoemde eigenschap namelijk niet van op toepassing)

Maak dus in die eerder gegeven psuedo klasse een functie wat het aantal matchende buren terug geeft

[ Voor 43% gewijzigd door Anoniem: 267113 op 19-12-2009 09:31 ]

[djluc]

Ik heb een ideetje uitgewerkt uit dit topic, wellicht interessant. Het idee is gebaseerd op de objecten methode zoals gesuggereerd. Dus elk blokje is een object een heeft buren.

http://onetofollow.nl/test.php

Het resultaat klopt, het geeft aan dat er een 3x3 result gevonden is. De code is als test gemaakt in PHP:

http://onetofollow.nl/test.phps

Ook met meerdere kleuren werkt het. Het idee is als volgt:

Start met 1 blokje. Kijk welke kleur hij heeft (dit is dus een actie die je bijvoorbeeld doet als je een tetris blokje laat vallen). Het blokje kent zijn buren al dus hij kijkt welke buur de juiste kleur heeft. Vervolgens kijkt die buur weer welke buren de juiste kleur heeft enz. Die beperkte groep goede blokjes wordt vervolgens geteld zodat we weten hoe groot het blok bij elkaar is.

De vraag is: Zal dit ooit efficient worden? Ik denk het niet, gezien de flinke hoeveelheid overhead die je hebt. Het leuke hieraan is wel dat je het triggert op het moment dat bijvoorbeeld een blokje toegevoegd wordt. Dus je checkt nooit een grote matrix, je checkt altijd maar een gedeelte daarvan.

[edit]Nog even verder gedacht is dit gewoon bijna niet te doen op een efficiente manier en zal het dus waarschijnlijk gewoon brute force het meest snel zijn. Afhankelijk van je opzet natuurlijk want op zich is de object georiënteerde methode wel handig en goed beheersbaar.

[ Voor 35% gewijzigd door djluc op 19-12-2009 21:25 ]

[Sebazzz]

Okey ik wist dus blijkbaar niet wat ik wilde Ik ben toch maar voor een min of meer slimme manier gegaan. Het is geen bruteforce in ieder geval.


Dit algoritme heb ik prima werkend gekregen en is voldoende snel. Ik heb het niet geprofiled maar in een 20x9 grid doet ie het prima binnen een seconde. Het algoritme werkt als volgt:

• Kies een willekeurig punt 1
• Tel hoeveel je vanaf daar naar beneden en rechts kan. Houd dit bij.
• Ga één omlaag, één naar rechts. Noem dit punt twee.
• Tel weer hoeveel je naar rechts kan en naar beneden, houd hierbij rekening met het feit dat je naar beneden en rechts ben gegaan, en corrigeer je telling daarmee. Houd deze telling bij.
• Opnieuw één omlaag, één naar rechts en weer tellen totdat je niet verder meer kan.
• Het minimale wat je geteld hebt in verticale en horizontale richting is je rechthoek.

In de afbeelding staat drie mogelijke checks op rechthoeken weergegeven. A voor een pass, deze gebruikt de zwarte pijlen. B voor een pass, deze gebruikt blauwe pijlen. En als laatste C, die groene pijlen voor de duidelijkheid gebruikt. Zoals je ziet vind je met C een rechthoek van 2x3 en met B een rechthoek van 3x2. Met A vind je een rechthoek van 4x1.
Voor mijn doeleinden werkt het algoritme prima, aangezien ik rechthoeken nodig hebt van minimaal een bepaalde grootte. Dus ik weet niet of het algoritme correct werkt met kleinere rechthoeken.

Een nadeel met deze implementatie is dat je meerdere overlappende rechthoeken krijgt. Hiervoor kan je dit gebruiken:
• Sorteer de rechthoeken op oppervlakte van groot naar klein
• Kopieer het raster waarin je werkt (indien je alleen wilt detecteren, niet gelijk wilt aanpassen)
• Kijk of de rechthoek met een bestaand rechthoek interfereert
• Maak de langste zijde één kleiner, en controleer of de rechthoek nog aan je wensen qua grootte voldoet en het nog interfereert met een rechthoek
• In je raster, plaats de rechthoek.
• Hetzelfde verhaaltje voor het volgende rechthoek