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_...ae/output1.gif

Programmatically, 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.Collections.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.Columns[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/cshar...tieDotTest.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.

[Rabbit]

No problem, good luck with everything else.

[GaryTexmo]

To minimize garbage collection, don't create/destroy anything if you can help it. I can't see your code, but the biggest thing that helps, I find, is not creating new memory wherever possible. For example, lets say your byte array. Don't create/destroy it every cycle, just modify the values in it. Maybe you've got a couple of vectors in use for determining where things draw... don't create new ones every cycle, just modify the coordinate values of them instead.

Things of that nature.

[HaLo2FrEeEk]

Well unfortunately I have to create new items, at least the way it's written right now. It takes two bitmaps, one for "on" and one for "off" and flips and rotates it, then draws it to the proper portion of a larger bitmap, then puts the large one in a picture box. I know the logical way to do it would be to draw onto the graphics object of the paint event, and I'm working on that as we speak. You wouldn't believe how difficult it is to draw that stupid little shape.

Let me ask you something, if I write a method and call it in the onpaint event of my drawing area, and pass the PaintEventArgs to it, will that create a new instance of the PaintEventArgs? What if I made it reference the args using the ref tag in the method?

[GaryTexmo]

No everything in C# (except the primitive types) is passed by reference. Putting ref in front makes the reference itself passed by reference, which would let you modify the pointer itself. It's not creating a new graphics object when you do that, so you're fine.

As for the bitmaps, you still don't have to create two bitmaps. For one, a bitmap object does have a getpixel and setpixel method so you can always directly modify the data and, for another, you can create a graphics object on a bitmap object and draw directly to it.

You shouldn't have to create new bitmaps over and over again.

It sounds like you're onto something but for what it's worth, here would be the general approach I'd take...

private Bitmap m_result;
private Graphics m_resultTarget;
 
// constructor
{
  m_result = new Bitmap(desired_width, desired_height);
  m_resultTarget = Graphics.FromImage(m_result);
}
 
// paint method (Graphics g)
{
  // Clear the buffer
  m_resultTarget.FilledRectangle(..., /* background color, */ ...);
 
  // Draw everything using m_resultTarget to draw to the bitmap
 
  // Draw the bitmap to the form as appropriate
  g.DrawImage(m_result, ...);
}

[Rabbit]

I would have a grid of bitmaps and 4 pictures for each of the possible states. And then change the source of the picture accordingly rather than redrawing everything.

[GaryTexmo]

If there are only four possible resulting images, that's actually probably the best way to go.

I didn't read too much into this as Rabbit already did the bulk of the work. I just tried to swoop in and snatch up all the glory, muahahaha! (:P)

Back on topic, even if you had more states you could do similar to make your drawing easier. It looks like you can slice up your result image into tiles and then just paint the appropriate tile as either on or off. It'd be a bit easier than drawing all the shapes yourself.

I'd still recommend following the flow I laid out though... do all your drawing on another source, then draw that to the screen. That way you don't get to watch your screen draw ;)

[HaLo2FrEeEk]

That's what I do, I have a loop that goes through the array and paints the correct image in the correct location. There are 8 possible states, 4 for both on and off. I paint each image in the top-left of the larger bitmap, then mirror it to the right and bottom using Bitmap's rotate method. Once the loop is finished it sets the picture box's image to the large bitmap. I think it'd be easier to simply draw the shape to the graphics object in the onpaint event, eliminating the bitmaps altogether. The way I've got it now there's no flicker or anything since the entire image is drawn, then set as the picture box's image.