Neighbor search algorithm?

Hey guys,

Here is what I am working with right now:



It is an array which consists of block objects. What I am trying to do is to seperate this into color coded regions, where each region consists of 3 more more touching blocks (but not diagonally).

For example, the red regions will be split up as such:

region 1:

[0, 0] [0, 1] [1, 0] [1, 1] [1, 2] [2, 1] [2, 2]

region 2:

[3, 0] [4, 0] [4, 2] [5, 0] [5, 1] [5, 2] [6, 1]

region 3:

[5, 5] [6, 5] [6, 6]

region 4:

[8, 9] [8, 10], [9, 7] [9, 8] [9, 9] [10, 9] [10, 10] [11, 9]

region 5:

[2, 12] [3, 12] [3, 13] [4, 13] [5, 13]

etc... for all of the other colors.

Anyone have any idea on how to do this?

How "intelligent" would you like this to be? I can only imagine it's going to be an order of magnitude more difficult to come up with the most efficient/most intelligent algorithm compared to a more 'hack' algorithm that gets the job done but is slower and 'stupider'.

Also, are there any rules besides moving each color so that it makes a grouping of 3? Is it desirable to try and make the largest groupings possible, given that doing so takes no more moves than not doing so. Please elaborate on any further rules or desirable/undesirable behavior.

Lastly, how often is this going to need to be calculated, and how fast do you need the calculation to be? I know I'd be able to offer more help if I knew what kind of guidelines I needed to work with.

Thanks :)

Look for HOSHEN - Koppelman (think was written like this) algorithm

should provide you with a very performatn solution for finding regions of same neighbors

Aww, trying to come up with your own algorithm is where the fun's at! :)

Actually, I usually try and come up with an algorithm for any problem, and only *then* see what's out there. Not only does this get you thinking, but this also lets you see how you approach the problem and then later reflect on how you can improve your approach to problems in general.

i did this in purebasic some time ago, it is simply a recursive routine:

(srry for german variables)

VerarbeiteSpielfeld = Functionname
farbe = index of color
score = to count the amount of stones
entfernen = flag if selectet stones should be removed
hidden = flag if should be shown

i used 2 arrays - one for playing (Spielfeld[x,y] and a seconde one for showing Tips to Player (TipSpielfeld[x,y])

Procedure VerarbeiteSpielfeld(x.l, y.l, farbe.b, score.l, entfernen.b, versteckt.b)

  If x<0 Or x>#dim_x Or y<0 Or y>#dim_y Or TipSpielfeld(x,y) = -1 Or Spielfeld(x,y) = -1 
      
      ProcedureReturn score.l
  
  Else

    If versteckt.b = 0
      DisplayTransparentSprite(#gfx_tip,x*16+#offset_X,y*16+#offset_y)
    EndIf
    
    TipSpielfeld(x,y) = -1
    
    If entfernen.b = 1
      Spielfeld(x,y) = -1
      ;Debug "Lösche: "+Str(x)+"/"+Str(y)
    EndIf
    
    If y>0 And Spielfeld(x, y-1) = farbe And TipSpielfeld(x, y-1) <> -1 And Spielfeld(x,y-1) <> -1
      score = VerarbeiteSpielfeld(x, y-1, farbe, score+1, entfernen, versteckt.b)
    EndIf
    If x>0 And Spielfeld(x-1, y) = farbe And TipSpielfeld(x-1, y) <> -1 And Spielfeld(x-1,y) <> -1
      score = VerarbeiteSpielfeld(x-1, y, farbe, score+1, entfernen, versteckt.b)
    EndIf
     If y<#dim_y And Spielfeld(x, y+1) = farbe And TipSpielfeld(x, y+1) <> -1 And Spielfeld(x,y+1) <> -1
      score = VerarbeiteSpielfeld(x, y+1, farbe, score+1, entfernen, versteckt.b)
    EndIf   
    If x<#dim_x And Spielfeld(x+1, y) = farbe And TipSpielfeld(x+1, y) <> -1 And Spielfeld(x+1,y) <> -1
      score = VerarbeiteSpielfeld(x+1, y, farbe, score+1, entfernen, versteckt.b)
    EndIf
    
    ProcedureReturn score.l

  EndIf

EndProcedure

^ Looks like a default FloodFill. Works well unless you're checking big areas. Then you could run into stack-issues. Search Wikipedia for floodfill, there are links to non recursive versions.

For my puzzle game I use this recursive FF-Algo, too. Too lazy to write a listbased FF, but if anyone has one in store... ;)

yes, recursion is nothing for big arrays :)

The naive approach on that problem, if not interested in see a potential way would be:

Check all fields for their neighbors and their own "nationality" and see if they are equal.
If yes: See if that neighbor field is part of a region. If so, join the region. If not, declare a new region for this and that neightbor

At least from the given problem that would how I would be doing it, especially as it looks nice and "doable" with more than only 2 dimensions :-)

.

Thanks all for the info! I'll give your suggestions a try.

Hey again.

I tried implementing the 'Flood Fill' algorithm from the Wikipedia article, and it was a lot easier than I had anticipated. Thanks for the suggestion! :)

There is one problem though....The program tends to crash when I search to the north and to the left O_o

Here is the code:

Method tesRegion(a_color$, x_coord%, y_coord%, region_num%)
		If Container[x_coord, y_coord].getBlockColor$() <> a_color Then Return 
		
		Container[x_coord, y_coord].setRegion(region_num)
		
		If x_coord > 0 Then tesRegion(a_color$, x_coord - 1, y_coord, region_num)
		If x_coord < 13 Then tesRegion(a_color$, x_coord + 1, y_coord, region_num)
		If y_coord > 0 Then tesRegion(a_color$, x_coord, y_coord - 1, region_num)
		If y_coord < 11 Then tesRegion(a_color$, x_coord, y_coord + 1, region_num)

		Return 
		
	End Method 

Here are the calls that I made to test the code:

Global blockContainer:BContainer = New BContainer

blockContainer.tesRegion(blockContainer.getContBlockColor(6,9), 6, 9, 1)

The program doesnt run until I comment out the following lines:

If x_coord > 0 Then tesRegion(a_color$, x_coord - 1, y_coord, region_num)

If y_coord > 0 Then tesRegion(a_color$, x_coord, y_coord - 1, region_num)

Anyone have any idea regarding what may be going wrong?