Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
(Note: This is the TI-Basic remake of the game. If you're looking for the C version, check out Unicorn's Thread)
FloodIt
Inspired by Unicorn's C remake of the Flood-It game, I am now creating a version of it in pure Basic as well.

I pretty much have the core game down so far:
-randomly generated, hardcoded 14x14 table with 8 colors (it won't be hardcoded in the end obviously. also 14x14 will be max size)
-blinking cursor
-custom flood fill algorithm for recoloring

Just like the original game, you must move your cursor around and click on whatever color you want.
<<Download 2/27>>

<<Official Download>>



You are able to play all the way through, however the algorithm execution time + recolor rendering time makes it extremely unenjoyable. I am hoping someone can find a way to speed my algorithm up, or find a different algorithm to use that is faster.

My algorithm is custom made; it uses [F] as the matrix to hold the color of each square, and a same sized matrix [G] to hold values of 0 or 1 as to tell the program what squares to redraw in the end.

Pseudocode:

Code:

If clicked_color is the same as top_left_color
    return

Else
Scan each element of [F]
    If that element is the same as the top_left_color and is adjacent to a 1 in matrix [G]
    Store a 1 in the 2nd matrix at the same spot the current element being scanned is at
Repeat this scan once (to make sure to get spots that hadnt had a 1 adjacent to them yet)
Replace all elements of [F] where a 1 is in [G] with clicked_color, and redraw table at same time

I am 99% sure this works, however I may have missed something when checking it. As I have said, this is very slow and either needs to be sped up somehow or replaced with a different algorithm.

Full Code:

Code:

DelVar [F]{14,14->dim([F]   //hardcoded 14x14; will change
StoreGDB 0
CoordOff:GridOff:AxesOff
BackgroundOff
0->Xmin:264->Xmax
0->Ymax:~164->Ymin
ClrDraw
Line(60,~10,60,~152,Black   //hardcoded box for 14x14 table; will change
Line(60,~10,264-62,~10,Black
Line(60,~152,264-62,~152,Black
Line(264-62,~10,264-62,~152,Black
For(A,0,13
   For(B,0,13
      {Blue,Red,Magenta,Green,Orange,Navy,Yellow,Orange
      Ans(randInt(1,8->C
      C->[F](A+1,B+1
      For(D,62+10B,71+10B,2
         Line(D,~12-10A,D,~21-10A,1,C,2   //drawing the boxes. It takes 24s to draw whole board...
      End
   End
End
0->A:0->B
Repeat K=45
   Repeat K
      For(Z,1,20
         getKey->K
         If Ans:20->Z   //if user presses enter, they don't have to wait for loops to finish
      End
      Pt-On(66+10A,~16-10B,3,MedGray
      If not(K:Then
         For(Z,1,20
            getKey->K
            If Ans:20->Z
              End
                End
      Pt-On(66+10A,~16-10B,3,[F](B+1,A+1)
   End
   A+(K=26)(A<13)-(K=24)(A>0->A
   B+(K=34)(B<13)-(K=25)(B>0->B


//FLOOD FILL ALGORITHM


   If K=105 and [F](1,1)!=[F](B+1,A+1:Then   //continue only if clicked color is not the same as top left color
      [F](1,1->C    //top left color stored into c
      [F](B+1,A+1->D   //clicked color stored into d
      DelVar [G]{14,14->dim([G]
      1->[G](1,1
      For(Z,0,1   //scan matrix twice, for the reason stated in the pseudocode
         For(I,1,14
            For(J,1+(I=1),14
               If [F](J,I)=C and ((J>1)[G](J-(J>1),I) or (I>1)[G](J,I-(I>1)) or (J<14)[G](J+(J<14),I) or (I<14)[G](J,I+(I<14   //if element equals top left color and there is a 1 adjacent to it in [G]
               1->[G](J,I
            End
         End
      End
      For(I,1,14
         For(J,1,14
            If [G](J,I:Then
               D->[F](J,I   //replace values in matrix
               For(Z,52+10I,61+10I,2
                  Line(Z,~2-10J,Z,~11-10J,1,D   //recolor necessary boxes
               End
            End
         End
      End
      DelVar [G]   //save memory
   End
End
I don't think the algorithm will work. What if a square is three or more steps away from the nearest 1, going backwards in the order you search? For example, let's say you're switching from red to blue here:


Code:
RRRR
GGGR
RRRR
GGGG


If you check the only those adjacent to the 1s, or adjacent to those, you'd miss the reds on row 3. Of course, I could be wrong.

As for optimizing the graphics, a combination of Pt-On(,,1,) and Pt-On(,,3,) fills in a 6x6 box. That may be a little small, but (I hope; I've only been able to borrow a friend's CSE) it's faster than five Line()s. Four of each point shape is enough for a 10x10 box, and four Pt-On(,,3,) is enough for an 8x8 box, or a 10x10 box filled in most of the way.
Thanks to PT_, I have a new algorithm that will work and is much faster than the previous one, however it is still nowhere near fast enough. It also gets slower the more boxes it has to fill in.


Code:
//FLOOD FILL ALGORITHM (PT_)

If K=105 and [F](1,1)!=[F](B+1,A+1:Then
      {0,1+[i]->L1
      [F](B+1,A+1->D
      [F](1,1->C
      While 1<dim(L1
         real(L1(dim(L1->P
         imag(L1(dim(L1->Q
         dim(L1)-1->dim(L1
         If C=[F](P,Q:Then
            D->[F](P,Q
            For(Z,52+10Q,61+10Q,2
               Line(Z,~2-10P,Z,~11-10P,1,D
            End
            If P>1
            augment(L1,{P-1+[i]Q->L1
            If Q>1
            augment(L1,{P+[i](Q-1->L1
            If P<14
            augment(L1,{P+1+[i]Q->L1
            If Q<14
            augment(L1,{P+[i](Q+1->L1
         End
      End
End


And here's what it looks like:


<<Download 2/27>>

Code:
augment(L1,{P-1+[i]Q->L1
should be

Code:
P-1+[i]Q->L1(1+dim(L1


because it's just a little longer, but much faster-- augment( is O(stack size) whereas this is O(1).

I think a scanline flood fill is the logical next step, as @Nik suggested. Graphics may be the next bottleneck, which may necessitate moving to 8x8 squares and Pxl-On as in my first post.
Okay, I have the tile rendering basically instantaneous now, using two Pt-On() commands for each tile, one point being the empty box and one being the default which fills inside the box. This is at the cost of tile size though; tile size is now 7x7, but that's not that bad.

Recoloring still takes pretty long when you have a larger area, so the algorithm needs to be sped up a lot, or else I need a different algorithm. Maybe scanline as suggested.

Also, need to start thinking about game end detection; what's the fastest and smallest way to detect if all matrix values are the same?
Edit: for end game detection, I believe taking the absolute value of each element minus the top left corner color value and then summing up all rows to see if it comes out as 0 will work, so I will try that now.
For game-over checking--

Since in most cases the matrix won't be mostly equal to its top-left value, I suggest a short-circuiting algorithm. First see if the top left is equal to all of the first column, then check equality with the whole matrix. This saves some time.


Code:
//matrix [B] is precomputed as 14x14, all ones
Matr>List([A],1,L1
If min(L1=L1(1
Then
If L1(1)[B]=[A]
1->F    //set flag or something, game over
End
The GUI is completely done! You can now change the board size and the maximum amount of colors used in the board in the middle of the game, however the game won't be updated to the new settings until you press the "New" button to start a new game. You can also change the cursor type mid-game. The first cursor type is on the board and the second is underneath the board.

Now I just have to put in the game-over checking and a few other small things and I'll be finished! I'll post a gif and have a download once that is all done Smile
Before changing to the scanline fill algorithm, here's an optimization you may want to implement.

Currently your code does this:


Code:
Initialize stack; push top left square
Top left color->C
Selected color->D
While stack is nonempty:
  Pop a square
  If its color is C:
    Recolor it to D
    For each of its four neighbor squares:
      If the neighbor is within bounds:
        Push it


I think this may be faster:


Code:
Initialize stack; push top left square
Top left color->C
Selected color->D
While stack is nonempty:
  Pop a square
  Recolor it to D
    For each of its four neighbor squares:
      If the neighbor is within bounds and its color is C:
        Push it


I think that should cause fewer total pushes onto the stack, which should speed it up a little.
Maybe you could try the implement a ScanLine algorithm, like Nik did? Just an idea, though..
And when/if you do, I'd like to see that screenie and get that download you promised. Razz
I still haven't tried any new algorithms yet, but other than that, it's completely done! Very Happy



All buttons can be pressed outside and in the middle of the flood algorithm Smile Also, there is an exit button as you can see (which pops up with an 'Are you sure' menu) but you can also press CLEAR.

Download from the Archives: Flood-It
I see what you mean about the calculation being the bottleneck; rendering really does look instantaneous.

One improvement to the flood algorithm which I haven't ruled out is a scanline algorithm, combined with some DList( trickery to find the connected squares within each line. This sort of list-operation trickery can often be fairly fast, because it eliminates interpreter overhead. I'm not sure how it would be done.

I'll start thinking about a routine that, when a list representing a row of the board is input, outputs 1s in all the positions of the list horizontally connected to it.

EDIT:The cells connected to a certain cell at position I with color C within a line are just:

Code:
L1=C->L2
cumSum(Ans
Ans=Ans(I) and L2

However, this helps significantly less than I thought it would.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are GMT - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement