Author Topic: Random Space Filling  (Read 3440 times)

0 Members and 1 Guest are viewing this topic.

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Random Space Filling
« on: October 19, 2011, 08:51:08 pm »
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 :)

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.

Edit:
The purpose for this is to materialize a title from nothing into the final results fast but supposedly random.
« Last Edit: October 19, 2011, 08:53:28 pm by meishe91 »
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1591
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Random Space Filling
« Reply #1 on: October 19, 2011, 10:04:52 pm »
I know one easy way to do it, though I'm not sure how good it would look. I really have no way to describe it other than in steps:


1. First, you need a counter, I will make it 8-bit and call it _C, the counter starts at 00.
2. Clear your buffer

OuterLoop:
3. Set a pointer to the beginning of the picture buffer

InnerLoop:
4. Take a random 8-bit number, AND it with _C, then OR it with the current data in the picture buffer and store it
5. Rotate _C by one bit (left or right doesn't matter, just keep it consistent)
6. Increase to the next byte in the picture buffer
7. Goto InnerLoop until you are at the end of the buffer

8. Increase _C by 1 (the real _C, not whatever kind of rotated crap you ended up with after the inner loop)
9. Goto OuterLoop as long as _C is not equal to 256 (0)

10. Goto OuterLoop a few more times with _C = 255 just to make sure any stragglers get filled in


That aught to do it. The only thing that will break it is if your random routine isn't truely random. ;D You might also get interesting results if you randomly rotated _C rather than just rotating it by 1.

Edit:
    The second AND is an OR
« Last Edit: October 19, 2011, 10:18:07 pm by thepenguin77 »
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Random Space Filling
« Reply #2 on: October 19, 2011, 10:08:39 pm »
Thanks. But any chance that could be translated into more layman's terms? I don't know much Assembly so I'm getting lost in the ANDing and rotating and such things. Thanks though :)
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Random Space Filling
« Reply #3 on: October 19, 2011, 10:22:54 pm »
Meishe, are you looking for Axe or TI Basic advice?

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Random Space Filling
« Reply #4 on: October 19, 2011, 10:25:17 pm »
Either, but preferably TI-BASIC since I know it a lot better. Even just a general algorithm without any code would suffice. Eventually I have to port it to C++ but since we don't really have a general programming help section I thought this would be a good place since I can just port it later on my own.
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: Random Space Filling
« Reply #5 on: October 19, 2011, 10:27:55 pm »
You could always do the brute force way and create an array of all the points of the rectangle and then mix them up

Offline meishe91

  • Super Ninja
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2946
  • Rating: +115/-11
    • View Profile
    • DeviantArt
Re: Random Space Filling
« Reply #6 on: October 19, 2011, 10:30:18 pm »
I actually just thought about doing that.

Edit:
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.
« Last Edit: October 19, 2011, 11:16:13 pm by meishe91 »
Spoiler For Spoiler:



For the 51st time, that is not my card! (Magic Joke)

Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1591
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Random Space Filling
« Reply #7 on: October 19, 2011, 11:18:23 pm »
I was going to port my example over to C++, but I realized that if you are writing it on the computer, my technique won't work. I specially optimized mine for the calculator and it relies on the fact that you are storing your picture in monochrome. Most likely you'll have 24-bit pixels so for mine to work correctly would take a lot of work.

I'd go with the mixing up idea.
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Random Space Filling
« Reply #8 on: October 20, 2011, 04:19:25 pm »
Here's my quick demonstration of an incredibly simple "random" space filling method. I wrote it in Axe, although it's easy enough to translate to Assembly.

Code: [Select]
$0904->A
Repeat getkey(15)     //Loop until user presses Clear
{A} or {A and 511+L6}->{A and 511+L6}
A+1->A
Dispgraph
End

0x0904 is just a location in memory on my calc that has "random" values that are ORed with the contents of the screen. It takes almost no additional memory to implement. The ANDing A with 511 is equivalent to taking A mod 512, which is an arbitrarily chosen constant to prevent A from overflowing the screen and ORing RAM with random values...

All it needs is the appropriate bitmasking to get it to work within a box onscreen.
« Last Edit: October 20, 2011, 04:20:00 pm by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ