Author Topic: Fun with Math  (Read 4436 times)

Offline keith.lamothe

  • Arcen Games Staff
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,504
Re: Fun with Math
« Reply #15 on: October 09, 2013, 04:38:08 PM »
Yea, if a seed-based RNG is allowed then it gets way easier :) 

Build list of all optimal range spots
if count > 0 pick one via RNG and loop
(else) Build list of all allowed spots
if count > 0 pick one via RNG and loop
(else) break

Or break when a certain count is reached, to avoid maximum density.
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 Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,059
Re: Fun with Math
« Reply #16 on: October 10, 2013, 09:06:57 AM »
Is there a rule/constraint preventing the addition of an "&& GetDistanceToAnyOtherRedPoint(x,y) > 8" on the end of any particular algorithm?

Because I don't have a feasible way to store generated locations for later reference.

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.

I probably could, but making one that fits my criteria is hard.  I'm not going "hey I'm at 5, 3.  I will now go to 10, 7."  It's "I'm at 5,3.  Should do X?  I'm at 5,4.  Should I do X?  I'm at -4,12.  Should I do X?"

Offline keith.lamothe

  • Arcen Games Staff
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,504
Re: Fun with Math
« Reply #17 on: October 10, 2013, 12:29:08 PM »
Ah, it sounds like reworking the problem is the best solution, then ;)  Not to say it isn't interesting to try to solve it as-is.
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,233
Re: Fun with Math
« Reply #18 on: October 10, 2013, 12:39:19 PM »
Is there a rule/constraint preventing the addition of an "&& GetDistanceToAnyOtherRedPoint(x,y) > 8" on the end of any particular algorithm?
Because I don't have a feasible way to store generated locations for later reference.
Ah, now I understand.  If you have no way to check how far a potential point is away from other, pre-existing points, you couldn't do random or anything like that.

Unfortunately, I don't see any way to come up with a method that would work, except for a grid of a fixed known size.  For variable sized grids, an equation that works on one grid won't work on a different grid... 

Hmm.  What if you used a smaller grid, randomly selected points (with no restrictions) then inserted between 8 and 32 extra points between row/column of your smaller grid?  If the 'smaller' grid is big enough (16-ish points?) it'll still look somewhat random (the diagonals will be too long, but otherwise...)

Offline Mick

  • Hero Member Mark II
  • *****
  • Posts: 911
Re: Fun with Math
« Reply #19 on: October 10, 2013, 12:45:10 PM »
Unfortunately, I don't see any way to come up with a method that would work, except for a grid of a fixed known size.  For variable sized grids, an equation that works on one grid won't work on a different grid... 

My solution works on a variable sized grid.

Using a pseudo-random function for the "Foo" portion will work so long as the mX and the mY are used to generate the seed.

EDIT:

example: FOO = ( ( ( mX + ( mY * 123456789 ) )  * 1103515245 +12345 ) / 65536

Code: [Select]
public static void main( String[] args ) {
        long r = 8;
        for ( long x = 0; x < 100; x++ ) {
            for ( long y = 0; y < 100; y++ ) {
                if ( test( x, y, r ) ) {
                    System.err.println( "(" + x + "," + y +")" );
                }
            }
        }
    }

    private static boolean test( long x, long y, long r ) {
        long mX = x / r;
        long mY = y / r;
       
        if ( mX % 2 == 0 || mY % 2 == 0 ) {
            return false;
        }
       
        long bX = x % r;
        long bY = y % r;
        long z = bX + ( bY * r );
       
        long foo = ( ( mX + ( mY * 123456789 ) ) * 1103515245 + 12345 ) / 65536;
       
        return foo % ( r * r ) == z;       
    }   
« Last Edit: October 10, 2013, 01:36:44 PM by Mick »

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,059
Re: Fun with Math
« Reply #20 on: October 10, 2013, 02:25:04 PM »
I'm using Mick's solution and it is beautiful, no randoms required. :)

Code: [Select]
int R = 6;
int mod = 57;
int mX = chunkX/R;
int mY = chunkZ/R;
ch = (((mX+1) * mX + mY * mY + (int)Math.pow(1 + mX * mY, 3)) % mod);
int nx = chunkX % R;
int ny = chunkZ % R;
int Z = nx + (ny * R);
if(mX % 2 == 0 || mY %2 == 0) {
Z = -1;
}
if(ch == Z) {
//do stuff
}

Offline windgen

  • Jr. Member
  • **
  • Posts: 51
Re: Fun with Math
« Reply #21 on: October 12, 2013, 04:19:39 AM »
Had to chime in here because I've solved this exact problem in the past.

Your first thought was probably to generate pixels by using something like "red with probability p (and thus white with probability 1-p)".  But then you realize pixels might be too close together -- this is a *constraint* -- red pixels cannot be too close together.

So what you could do is generate red pixels, then destroy ones that cause the constraint to be violated.  This is harder than it sounds when working with an infinite procedurally generated world, as I think you're asking (although this isn't entirely clear from the post).

You want to display what the player can see.  But it's not obvious how to make a "generate-and-destroy" type algorithm work, because you don't know that one of the pixels the player *can* see won't later be destroyed because it involves a constraint of a pixel the player *can't* see.  An even worse problem is that, depending on how destroy() is implemented, you might never be able to fix it by generating just a little more than the player can see, because there might be "chain reactions" that propagate over long distances.  E.g. if A and B are really close, maybe A normally causes B to be destroyed -- but if there's a further pixel C that would cause A to be destroyed when a different viewport is rendered, maybe B sometimes survives, depending on the viewport!  And maybe there's a further pixel D that affects whether C is destroyed, and so on, allowing arbitrarily long chain reactions!

The generate-and-destroy idea can be made to work; you just have to be a little careful about it.  Divide your map into chunks (I suggest a grid of square power-of-two chunks).  Our goal is to design a function create() that builds all the red pixels in a chunk.

First, implement a function called generate() which takes a chunk address and picks a rough set of pixels inside the chunk, which I'll call "green pixels."  Green pixels do not obey the distance constraint, and will not be displayed in the final result; they are for intermediate computation only.  So for example you can just use the chunk address as a random number generator seed to pick green pixels in generate().  To reiterate, green pixels may collide with each other or with pixels in other chunks.

Higher-level game code asks create() for a chunk at a given chunk address, call this the "requested chunk."  create() begins by calling generate() to get the green pixels inside the requested chunk and all neaby [1] chunks.  Then create() colors all the green pixels in the requested chunk red, leaving the nearby chunks green.  Then create() checks the red pixels one by one for collisions, deleting any red pixel which collides with either a green pixel or another red pixel; this is the "destroy" phase.  Then create() returns the remaining set of red pixels.

NB multiple calls to create() are independent.  So if your chunks are 16x16 and addressed by upper-left corner, create(5, 1) might be the chunk with upper-left corner at (80, 16).  When calling create(6, 1) to generate the next adjacent chunk to the east with upper-left corner (96, 16), that create() call will ignore the red pixels computed at (5, 1) and use the green pixels instead.  This guarantees that (6, 1) will return the same result regardless of what values were computed for the red pixels in (5, 1).  In other words (6, 1) depends only on the *green* pixels of (5, 1).  The red pixels for a chunk other than the one currently being worked on by create() are simply irrelevant to what create() does.

In the grand open source tradition of helping best those who help themselves, I'm leaving plenty for the requester and others in this thread to do.  Like writing working code.  Or a more complete explanation of why this algorithm can produce neither chain reactions nor between-chunk collisions.  Or how this algorithm might work with a vector world rather than a raster world.  Or a purely algebraic workout of what's going on here with no appeal to physical intuitions (hint:  think triangle inequality).

I highly recommend implementing some sort of caching of generate() results.  And I also recommend modifying generate() to include a post-process phase where you remove within-chunk collisions, then removing red-on-red collision check from create().

[1] Close enough to affect pixels in the chunk passed to create() -- this is simply all adjacent chunks if the chunk size is greater than your no-collisions-allowed radius of 8.

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,059
Re: Fun with Math
« Reply #22 on: October 17, 2013, 09:37:49 AM »
Hehe, thanks for that.

The only real problem with that method is that I can't actually call create() on neighboring chunks.  :p

Working within the constraints of the Minecraft system, where my code is called from the base (unmodifiable) system when a chunk is created (so that I can populate it).

Now, I could maintain an array of locations that have been generated and call distance calculations on them, but this would get overburdened rapidly.  Now, a normal Minecraft world isn't that big (few square kilometers) but there are multiplayer worlds that are downright MASSIVE.  Not to mention that generating chunks in a different order could lead to different results, which is not exactly kosher.

This is also why the occasional grouping is OK, as the player won't ever be able to see more than 3 "red pixels" at one time: each pixel is 16 meters across!  (A pixel in my opening post refers to a Minecraft chunk area).  Which is why Mick's solution of working with "superchunks" (and then ignoring all of the ones with even indices) was actually quite ingenious.  Add in the fact that typically a world isn't all one biome, and voila.  Impossible to see patterns.
« Last Edit: October 17, 2013, 09:41:00 AM by Draco18s »

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,059
Re: Fun with Math
« Reply #23 on: October 30, 2013, 10:47:09 PM »
An oopsie with regards to if(mX % 2 == 0 || mY %2 == 0) did this recently:



An easy fix, but really amusing.

Offline keith.lamothe

  • Arcen Games Staff
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 19,504
Re: Fun with Math
« Reply #24 on: October 31, 2013, 09:36:46 AM »
Castle technology: now with retractable walls! ;)
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 Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,059
Re: Fun with Math
« Reply #25 on: October 31, 2013, 10:02:23 AM »
Castle technology: now with retractable walls! ;)

Hehe.
They're actually wizard towers.  The point of this thread was to prevent more than one appearing in a small space.  Which was originally "about two or three, when it happens."  One attempt at a random buggered up and kept resetting the seed value and just COVERING the landscape in them. XD

Now that the bugs are fixed, it works wonderfully.