(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:

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:

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:


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:


And here's what it looks like:


<<Download 2/27>>

Code:
should be

Code:


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:

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

Before changing to the scanline fill algorithm, here's an optimization you may want to implement.

Currently your code does this:


Code:


I think this may be faster:


Code:


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.

I still haven't tried any new algorithms yet, but other than that, it's completely done!



All buttons can be pressed outside and in the middle of the flood algorithm 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:

However, this helps significantly less than I thought it would.