Author Topic: Fun with Math  (Read 9034 times)

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Fun with Math
« on: October 09, 2013, 10:17:09 am »
Might as well post this here, see if Keith/X/someone else has a clever idea.

Given two inputs that are the X and Y coordinates of a location, write a function that produces a single boolean output that adheres, as best as possible, to the following criteria:

1) The output will be drawn to a bitmap display.  False will draw white, true will draw red.
2) Red pixels will be less common than white pixels, exact ratio is unimportant
3) Red pixels will be _no closer_ than 8 pixels, but the ideal distance would be between 16 and 32.
4) There is to be no randomization in determining the output or storage of previous results
5) Most importantly, the resulting image should have the _appearance_ of random noise.

For example:

function generate(int x, int y) {
   //the modulo does not have a linear relationship with regards to the frequency of output
   //primes *tend* to perform better, but this is not always the case
   return ((X * X + Y * Y + (int)Math.pow(X * Y, 3)) % 27 == 0);
}


Which results in the following output (0,0 upper left, grid size is 10x10 real pixels)



This happens to have some symmetry, but I am less concerned about that than I am about the distance between each *true* point.

Another example:

Code: [Select]
function generate(int x, int y) {
   //the modulo does not have a linear relationship with regards to the frequency of output
   //primes *tend* to perform better, but this is not always the case
   return (((1+X) * X + Y * Y + (int)Math.pow(X * Y, 3)) % 257 == 0);
}



(Excel had a sign bit-overflow in the lower right corner; my usage won't care about such things, as I do want random-like results)
« Last Edit: October 09, 2013, 10:28:49 am by Draco18s »

Offline Mick

  • Hero Member Mark II
  • *****
  • Posts: 911
Re: Fun with Math
« Reply #1 on: October 09, 2013, 10:45:03 am »
When you say "Red pixels will be _no closer_ than 8 pixels", what do you mean? Manhattan distance? It appears your first example has a fail case if that is true.

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Fun with Math
« Reply #2 on: October 09, 2013, 12:41:51 pm »
When you say "Red pixels will be _no closer_ than 8 pixels", what do you mean? Manhattan distance? It appears your first example has a fail case if that is true.

The first example fails, as it was a simple example.  If I had a working example I wouldn't need to ask the question. :P
(Second example fails, too, btw near the lower right)

And I would prefer true distance (as the crow flies), though if something worked for Manhattan...well, I could use it, but the min distance would need to be slightly larger. ;)

Offline Mick

  • Hero Member Mark II
  • *****
  • Posts: 911
Re: Fun with Math
« Reply #3 on: October 09, 2013, 12:43:29 pm »
Ah OK, I was under the impression you considered your examples to be passing, which made the requirements confusing to me.

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Fun with Math
« Reply #4 on: October 09, 2013, 12:48:32 pm »
Ah OK, I was under the impression you considered your examples to be passing, which made the requirements confusing to me.

Oh god no.  I need to find a solution.  Examples provided simply to show the kind of behavior I desire, but fail the minimum distance rule.

My current code uses an RNG (if rand.nextInt(48) == 0 {//do stuff}) but that has lead to really weird behavior:
http://i.imgur.com/RFoQn2j.png

Offline Mick

  • Hero Member Mark II
  • *****
  • Posts: 911
Re: Fun with Math
« Reply #5 on: October 09, 2013, 01:14:23 pm »
OK, I have a semblance of a solution, but I have no worked out the specifics. I'll try to explain my line of thinking.

Imagine your world is split up in a series of "streets" and "blocks". The width of a street and the width of a block is the minimum distance you want to have between points.

The first thing your function needs to determine is "am I currently on a street, or am I currently on a block?" If you are on a street, you are not going to draw a point at all, otherwise, you have the opportunity to draw a point, and the function will only determine one square within a block to be valid. So it's a two step function.

Think of it this way, your coordinate needs to generate a mega-X and a mega-Y. The first 8 positions are mega-X 1, the next 8 are megaX 2.. etc. etc.

So if your mega-X OR your mega-Y are even, then you are on a street. Another way of saying it is you are on a block if and only if your mega-X and mega-Y are odd.

So the first half determines if you are currently in a block, you need to determine which of the 64 squares within that block you are drawing your point in.

If you define your mega-X to be mX and your mega-Y to be mY, you can create some arbitrary equation like (pulling from your example:

((mX * mX + mY * mY + (int)Math.pow(mX * mY, 3)) % 64 == Z

What is Z? Z is the current point you are within the block If you look at the block as a subgrid. So the first point within the block is bX, bY

Z = bX + (bY * 8)
« Last Edit: October 09, 2013, 02:35:35 pm by Mick »

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Fun with Math
« Reply #6 on: October 09, 2013, 01:17:44 pm »
Hmm...
*Fiddles*

Offline Mick

  • Hero Member Mark II
  • *****
  • Posts: 911
Re: Fun with Math
« Reply #7 on: October 09, 2013, 01:19:25 pm »
Allow me to add more detail.

You define your "minimum distance" to be R (in your example, it's set to 8).

So:
mX = x / R
mY = y / R

if ( mX % 2 == 0 || mY %2 == 0 ) {
  return 0;
}

bX = x % R
bY = y % R
Z = bX + (bY * R)

return ( Foo % R^2 ) == Z

What is Foo? Foo is any function that uses mX and mY (NOT X or Y).
« Last Edit: October 09, 2013, 01:21:56 pm by Mick »

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Fun with Math
« Reply #8 on: October 09, 2013, 01:23:57 pm »
Yeah, I get the basic idea.  I think it'll work.  Thanks. :)

Going to go with a modulo of 67, it seems to have a reasonable distribution.  After the superdivide by 8 I can see 1 diagonally adjacent super-cell and a handful of two-distant ones, but otherwise the average seems to be about 5 (works out to ~40 chunks or ~640 blocks).
« Last Edit: October 09, 2013, 01:28:31 pm by Draco18s »

Offline Mick

  • Hero Member Mark II
  • *****
  • Posts: 911
Re: Fun with Math
« Reply #9 on: October 09, 2013, 01:27:37 pm »
You're welcome. I'd love to see the result. :)

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Fun with Math
« Reply #10 on: October 09, 2013, 02:24:22 pm »
Initial test did return two locations that were 6.4 units/pixels apart, I suspect the "Z = bX + (bY * R)" part called out two pixels in the pixel group as being valid locations.

Secondary test (and increasing the radius to 16) indicated it was two adjacent pixel groups having valid locations near the border with the other.

I can live with this. :D

Offline Mick

  • Hero Member Mark II
  • *****
  • Posts: 911
Re: Fun with Math
« Reply #11 on: October 09, 2013, 02:31:16 pm »
That's a bit odd, because the "street" vs "block" check should be making sure that the pixel groups all have a buffer between them.

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: Fun with Math
« Reply #12 on: October 09, 2013, 03:07:37 pm »
*Doublecheck*
Ok, I missed that conditional, rebuilding.

Offline keith.lamothe

  • Arcen Games Staff
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,505
Re: Fun with Math
« Reply #13 on: October 09, 2013, 04:19:22 pm »
Is there a rule/constraint preventing the addition of an "&& GetDistanceToAnyOtherRedPoint(x,y) > 8" on the end of any particular algorithm?
Have ideas or bug reports for one of our games? Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Toranth

  • Hero Member Mark III
  • *****
  • Posts: 1,244
Re: Fun with Math
« Reply #14 on: October 09, 2013, 04:30:22 pm »
Just curious, is there a reason you can't implement a PRNG with a fixed seed?  That gives you a reproducible 'random' sequence.  My_Rand(8, 40) for the distance, and My_Rand(0, 359) for the direction.  As long as you don't change your hardcoded seed, the sequence should always be identical.