I'm working out one of the core algorithyms for Big Dig. This is the algorithym which groups same-coloured blocks together so that they can fall together as a chunk or be eliminated together as a group.
This is, essentially a travelling salesman type problem however recursion is really not an option as there's no way I have enough RAM for the potential stack overhead.
I have two algorityms. Algorithym 1 was used in the original Big Dig. It works fine, however it is very, very slow. So slow that I could only group together 1 set of blocks per frame. So only one set of blocks could be falling/disappearing at a time. Not an ideal situation.
Algorithym 2 should be much faster but it's more complex. It's the algorithym I was going to rplace the original with in Big Dig. Now that I'm doing a rewrite I'll go right to this one unless somebody else has a good idea.
Which of course is the point of this post.
In the abstract, Algorithym 1 sequentially searches the entire data structure of blocks. When it finds a block of the same colour as the "first block" it checks all neighbouring blocks to see if any have been flagged as part of the group. If there is a member of the group beside this block, then this block is flagged as part of the group. This Algorityhm continues searching the entire data structure again and again until it makes it through the structure without flagging any new blocks.
Algorithym 2 narrows the search to the immediate area of the first block. As new blocks are flagged, the area of the search is widened to encompass these new blocks. So if the group is small, Algorithym 2 will be much faster. For very large groups Algo 2 will become almost as slow as Algo 1 but will still be better in almost all real cases.
So I'm looking for any thoughts on improving this - Of which I may have just had one. Suppose the search area in Algo 2 is handled smarter. Instead of just constantly widening, what if the search area was instead set to where new blocks were last flagged? That is, if an area didn't show any new blocks the last time through, there's no need to search there any more. So the search are can be made smaller in one direction while growing in another.
I'll give that idea a working over, but in the meantime if anyone has thoughts, I'd welcome them!!
Algorithym 1:
Flag first block and note colour
LOOP2:
x=0
LOOP1:
y=0
Is block at (x,y) of same colour?
YES -> Is there a neighbouring block which has been flagged?
YES -> Flag block at (x,y)
y=y+1
Is Y past the end of a row?
YES -> X=X+1
is X past the end of a column?
NO -> Go to LOOP1
Did any blocks get flagged this time through?
YES -> Go to LOOP2
Algorithym 2:
Flag first block and note colour
startx=column of first block
endx=column of first block
starty=row of first block
endy=row of first block
LOOP3:
x=startx
LOOP2:
y=starty
LOOP1:
Has block at (x,y) been flagged?
YES -> Is block to left same colour
YES -> Flag block to the left, startx=startx-1
Is block to right same colour
YES -> Flag block to the right, endx=endx+1
Is block above same colour
YES -> Flag block above, starty=starty-1
Is block below same colour
YES -> Flag block below, endy=endy-1
y=y+1
Is y>endy
NO -> Got to LOOP1
x=x+1
is x>endx
NO -> Go to LOOP2
Where any blocks flagged this time through?
YES -> Go to LOOP3
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
