Does anyone have a good algorithm for filling in a box randomly with pixels until it is completely filled? I couldn't think of a good way of doing this.

The only way I can think of doing it is by randomly generating an X- and Y-coordinate, checking if it's on, and if it isn't then turn it on. The only issue with this is that the bigger the box gets and the more pixels you fill the longer it can take to find a pixel that is turned off. The point of it is to seem random but it doesn't have to be necessarily. Any help would be greatly appreciated

The purpose for this is to materialize a title from nothing into the final results fast but supposedly random.

Note:
I tried searching on Google but couldn't think of good keywords to find something like this. All I kept coming up with is space filling algorithms for like filling shapes into.

Huhm..... Mayb this

Its in TI Basic Right. If not disregard this


Code:

Just code off the top of my head. Not sure If it will work. I am sure there is probably a better way.

The first one won't work at all, and the second one isn't random. One way that I can think of doing this would would be to create random arrays for the X and Y coordinates of pixels, randomly select an element from the array, turn that pixel on, and delete its coordinates from the array.

Ya I knew the second was not random as I said. He said it did not have to be random.

But it does have to seem random; filling up a screen line by line doesn't seem random.

TI-BASIC works, since I know it very well. I need to eventually port it to C++ but I can do that on my own, hopefully, with an algorithm.

But I don't really see how those are to efficient. The first one will just randomly turn pixels on indefinitely, and [tt]rand[/tt] won't work with [tt]Pxl-On()[/tt] since it they produce real numbers and not integers. The second set of code will just draw a diagonal line. Thanks though.

Edit:
Ninja'd^2

As souvik said. It is still supposed to seem random even if it isn't random in nature.

ok. Well I know nothing about C++ So I iwill leave it to the pros.

After I try this out.

Mayb this??

Code:

I don't need C++ code necessarily. All I really need is a general algorithm. Whether that is given with code (in pseudo-code, C++, TI-BASIC, anything) or not.

Souvik, ya I thought of something similar by having an array with all the coordinates and then shuffle them around with an algorithm. The only thing about that is that the array would take up a lot of space. Which probably isn't a big deal now that I think about it.

Edit:
The only problem with that is that it will take it forever to fully fill the area. Similar to the process I described in my first post where I check to see if the space is filled then react accordingly. The only real way to stop it is to have a counter that increases with every turned on pixel and stop when it reaches 5985.

You could also have that array keep, maybe, 20x20 blocks of pixels that need to be filled, and when you fill them, you just have another smaller array and randomly get rid of blocks in that 20x20 area. So that you fill in large blocks, but each block still looks kind-of random.

Edit: The other thing is, if your language allows it, you can pop the old pixels that you don't need to draw off the array.

Oh. Ok. thats the only way I can think of off hand. I will sleep on it. If it is not answered by then.

This. Generating random coordinates until the area you want to fill is full will work, but the runtime is potentially infinite and (if I did this right) has exponential amortized algorithmic complexity.

Python pseudocode (shouldn't be difficult to translate, but I can offer assistance if needed) for a 10x10 square:
Code:


The tricky bit of this is generating the set of points in a space-efficient manner when you have irregular shapes. An easy approach might be simply to store a bitmap and fill the set of points from that just by scanning the bitmap, but a more sophisticated approach could be found, depending on the exact shape, via silly math tricks. That's highly dependent on your shape though.

I think shuffling is the best way to do it. It's really easy in TI-BASIC by sorting a random list linked with your list of points, and you can do it in a similar way in Axe -- take a random number for a pointer and somehow use the data there to poll from your array of points to cover.

Thanks guys. I ended up just generating an array with all the points in it and then shuffled those points around and then displayed it. It seems to work pretty well Thanks for everyone who helped.

Glad it worked well for you. Now to for me to figure out how to do this in Ti Basic. And please dont tell me. I want to figure it out for myself. Just one question about it. Would Lists work to store points you have then already so that point does not get activiated.

Also to end the loop Would this work

Code:

Hint: SortA(LIST_1,LIST_2) sorts LIST_1 in ascending order and then rearranges LIST_2 to match

Lists would not be a very good way to do it if you were filling the entire screen. However, if you were filling a area with less than or equal to 999 pixels then it would be a good way.

Oh. Ok. Huhm. Mayb Make 3 lists or using multiple squares . Mayb use 4 loops for 4 quarters of the screen.

Idet:
Mayb this?

Code:

Are you trying to do the entire screen on the calculator?

Ya. My new program is on This Thread Althought I still have one more update to make on it.

Short answer. I am going to divide the screen into 12 boxes. and fill them up as 12 different blocks of code.

One method would be to generate a list of all the pixels and sort it randomly. Or generate a 1-to-1 mapping function, but that's very tricky. Tari, for your solution, you could make the max array size X*Y*0.5 instead of X*Y by adding items filled to an empty array until size=X*Y*0.5, then swapping in the items still unfilled, also X*Y*0.5, and removing items until empty.