Deterministic bool array

[HaLo2FrEeEk]

I really didn't know how to describe that in the title, so I hope I can explain it better here. Basically I want to generate a random 8x8 array of boolean values (I'll actually be using either an array of 8 bytes, or a single 64-bit long and using the bits as flags). The thing is, I want the bottom-right "corner" of the array to have the most precedence.

Let's say that I want to limit the number of "true" booleans that can be contained in the array, and I want more booleans to be toward the bottom-right corner of the array and less to be in the bottom-left, top-right, and top-left corners. I was thinking that I could limit it to, say, 8 true-value booleans, then iterate through and randomly select whether to turn a certain boolean on or keep it off. Everytime I turn one on, I'd subtract one from the count, when the count is 0 I'd break the loop. The problem with this is that I need to start at the bottom right. Think of the array like a square, and the booleans like a radial gradient, the center of which is at the bottom-right corner of the square. The gradient is darker at the bottom right, then fades away as it moves toward the other coners. The darker section is where it's more likely to have a true-value boolean, as it fades away it gets less likely that a true-value bool will be generated since they've been mostly used up in the darker area. Does that make sense?

So basically, I just need to know how to iterate through the bits of a 64-bit long (or an array of 8 bytes) and flip them on, but in such a way that will generate my "gradient" analogy.

Can anyone think of a way to do this? The only thing I can imagine right now is that the last bit of the last byte in the array will have the highest chance of being turned on; the first bit of the last byte and the last bit of the first byte will have equal chances of being turned on, and the first bit of the first byte will have the smallest possible chance of being turned on. I just can't wrap my head around how I might program this.

And by the way, this does have to be truly, or as close to truly, random as possible, because I'll be regenerating it every 50 milliseconds or so. The purpose of this is so that I can draw a picture like this:

http://infectionist.com/images/halo_reach/auntie_dot/ae/output1.gif

Programmaticall y, for use as a loading screen.

[hype261]

So if I understand your question correctly this is how I would solve your problem.

Like you mentioned I would have a count variable that keeps track of how many squares I have turned on.

When determining whether to turn a square on or off I would first get a random number. I would then multiply that number against some percentage say for the first one 90%, the second one 80%. I would then check that value against some predetermined mark and if it was greater then I would turn the bit on or turn it off. For each iteration of the loop the percentage I multiply against would get less. This way it is random, but it also seems favor the ones first checked.

[Plater]

You find the System.Collecti ons.BitArray object useful for this?

[HaLo2FrEeEk]

The thing is, I either need to set the array backward, or set it forward and reverse it...or rotate it 180 degrees.

[Rabbit]

Just do exactly has you were describing. Calculate the chance of a bit being true equal to it's position in an 8x8 grid.

For example, if I had a 10x10 grid, with indexes of r and c to denote its row and column, then the chance of turning on that position would be (r * c)%. Meaning row 1 column 1 would have a 1% chance, r1c2 a 2% chance, r2c2 a 4% chance, r2c1 a 2% chance, r9c10 a 90% chance, r10c9 a 90% chance, r10c10 a 100% chance.

I used a 10x10 grid for simplicity but you can fudge around with the percentages.

[HaLo2FrEeEk]

That makes sense, and with an 8x8 grid the bottom right bit would have a 64% chance, which is good, I don't want any single bit to have a 100% chance of being on (I know that doesn't mean that it'll be on every time, but it increases the chances too high). My next question is how I would do this if I were working on an 8-byte array, or a single 64-bit long? I already know how to flip certain bits on and off using bitmasks, would I just start with the least significant bit and move to the most significant for each byte in the array?

[Rabbit]

With an eight byte array or a 64 bit number, you would just need to calculate where that position would fall on 8x8 array. For example, I'm going to use an imaginary 100 bit number for simplicity, if I'm at position 32,
I would divide by 10, giving me 3.2, then I take just the integer and that would give me 3, add 1 to that and that gives me row 4. Now I take the 32 and mod 10, giving me a remainder of 2, add 1 and that gives me a column index of 3.

[HaLo2FrEeEk]

Ok, that took me a while, but I see that by adding 1 you're going by human-count and not computer count, so counting starts at 1. If I simply omit the add 1 then I get a 0-based count, which I think is what I want. I've set up a simple program that populates a DataGridView with 8 columns and 8 rows, I also have a textbox and a button. Putting a number into the textbox and clicking the button will select the cell that the number corresponds to, so putting in 0 would select cell 0x0, putting in 32 selects cell 4x0. It seems like all I'd have to do now is start setting bits at 63 (cell 7x7, or the bottom right corner of the grid) and subtract one from the count each time.

I'll use the methods that hype261 and rabbit described. I'll generate a random number and multiply it by the result of the multiplication of the row and column indices (in this case I'd probably add 1 or 2 to the indices to make the probability higher). I'd then check if the resulting number is larger than a predetermined random number (or perhaps if it falls within (a) specific range(s)). If the result is true, then I flip the bit to on, and decrease one from the number of available on-bits.

I'll have to do some tests to see how this goes, but it might be a good method. I'll let you know how it ends up.

[Rabbit]

Sounds like you're on the right track. But just to clarify, the reason I added 1 was because if you use row times column as the percentage, column 0 and row 0 will always have 0% chance.

[Rabbit]

If you want to increase the chance of the first bits without affecting the last bits too much, you could use a diminishing returns formula. Something like percentage * (1+1/x^2) increases the chance of the earlier bits without affecting the last bits much. There are many other formulas out there but that is one of the simpler ones to understand.

[HaLo2FrEeEk]

It's actually perfectly ok if the top-left bytes have a small or zero percent chance of being flipped on, they won't be visible in the final animation :)

I'm having trouble with the math though. Using an 8x8 grid, let's say I provide a value of 32. With a 0-based index that should select column 0, row 4, but instead it's trying to select column 4, row 0. I'm doing this:

32 / 8 = 4 (row)
32 % 8 = 0 (col)

Then I'm doing this:

MessageBox.Show (col + " x " + row);
dataGridView1[col, row].Selected = true;

The messagebox shows "0 x 4", but the correct cell is selected. Am I doing it right, just misinterpreting the result? Col should be on the y-axis and row should be on the x-axis, right? Maybe on my messagebox it just looks wrong because I'm printing out col * row, which is y * x, I should be printing out row * col, x * y.

[Rabbit]

In a two dimension array, the first dimension is what would be considered the row dimension. So you should be using row, column and not the other way around.

If you are using a two dimension array to store your data, why use a single parameter? Use two variables instead, a row integer and a column integer.

[HaLo2FrEeEk]

I am, dataGridView1[col, row] is just a shorthand way of doing dataGridView1.C olumns[col].Rows[row].

I got this working, but it's super resource intensive becuse it's actually rendering an image each time the timer ticks:

http://infectionist.com/extras/csharp/auntiedot/AuntieDotTest.zip

It's actually fun to open the task manager up and watch the memory usage just go up and up and up. Stupid garbage collector is stupid. I'll have to optimize things...

[Rabbit]

Congrats on getting it up and running. If you have questions about optimization, you could make a new thread and post your code there. I'm sure someone with C# experience could offer some suggestions. I don't know C#.

[HaLo2FrEeEk]

Eh, it's not a huge deal. I know why it's doing it, and the garbage collector eventually kicks in, it just takes forever. I got it up to 33 MB of memory usage (which is high for as little as this application is doing) and then the GC finally stopped being lazy and brought it back down to around 10 MB, which is acceptable. Eventually I'll optimize it, because I do intend to distribute it so other people can use it as a loading animation (it's from a video game, and the developers of this game happen to provide an API for access to loads of stats with JSON and SOAP endpoints, so people are making all sorts of .NET applications). Right now, it works, and that's all I cared about.

Thank you so much for your help, that logic was kicking my butt, I just couldn't wrap my head around it.