• Welcome to the new COTI server. We've moved the Citizens to a new server. Please let us know in the COTI Website issue forum if you find any problems.
  • We, the systems administration staff, apologize for this unexpected outage of the boards. We have resolved the root cause of the problem and there should be no further disruptions.

Hashing on Universal Coordinates

HG_B said:
Looks like he's just trying to come up with a really random bounded value?
Click to expand...

Well, yes.

What he and I want to do is plug in a location, and get out relatively randomlike dice rolls. In other words, UWP generation driven by location location location.
 
HG_B said:
Looks like he's just trying to come up with a really random bounded value?
Click to expand...

The advantage being that, by knowing the sequence of process, and the sequence of pseudo-random numbers derived from the location seed value. one need only store the location to store the whole dataset.
 
aramis said:
The advantage being that, by knowing the sequence of process, and the sequence of pseudo-random numbers derived from the location seed value. one need only store the location to store the whole dataset.
Click to expand...

Yes, I remember now. It's been 25 years since I did a lot of programming. Back when memory, storage & processors were very limited. On micro's anyway.
 
HG_B said:
Yes, I remember now. It's been 25 years since I did a lot of programming. Back when memory, storage & processors were very limited. On micro's anyway.
Click to expand...

More usefully, it allows 3-4 different people to wind up with the same extended system generated from a given mainworld.
 
aramis said:
More usefully, it allows 3-4 different people to wind up with the same extended system generated from a given mainworld.
Click to expand...

Provided they are both using exactly the same generator function, which never changes. The problem with this approach is that your exact code, including the language, random generator library function and possibly OS platform as well (random function and math functions cam depend on platform features) become an inextricable part of the data set.

To guarantee repeat ability you need to very carefuly select your development system and may need to implement your own random number generator.

Some games that used this method ended up in a situation where a save game copied from one computer to another contained a completely different universe due to a difference in the random number generator implementation.

Simon Hibbs
 
simonh said:
Provided they are both using exactly the same generator function, which never changes. [...]

To guarantee repeat ability you need to very carefuly select your development system and may need to implement your own random number generator.
Click to expand...

Yes, the random number generator has to be specified. Thankfully, there are algorithms that will work portably and are not too complicated to implement. For example, some of Jenkins' PRNGs, and ISAAC, which work identically in Perl, Java, JavaScript (!), and Objective C.

A hash function helps prime the pump. I suppose such a hash function would therefore become a custom part of a modified PRNG.

I used to use a lagged Fibonacci sequence PNRG, but apparently that's out of vogue nowadays, superseded by other neat stuff.
 
And here's the pseudo-random-number-generator I want so badly to use, exactly because it's so dang tiny. All I need is a decent seed value (read: hashed from galactic location). http://www.burtleburtle.net/bob/rand/smallprng.html

Code: 
typedef unsigned long int  u4;
typedef struct ranctx { u4 a; u4 b; u4 c; u4 d; } ranctx;

#define rot(x,k) (((x)<<(k))|((x)>>(32-(k))))
u4 ranval( ranctx *x ) {
    u4 e = x->a - rot(x->b, 27);
    x->a = x->b ^ rot(x->c, 17);
    x->b = x->c + x->d;
    x->c = x->d + e;
    x->d = e + x->a;
    return x->d;
}

void raninit( ranctx *x, u4 seed ) {
    u4 i;
    x->a = 0xf1ea5eed, x->b = x->c = x->d = seed;
    for (i=0; i<20; ++i) {
        (void)ranval(x);
    }
}

Burtle said:
This is a small fast pseudorandom number generator, suitable for large statistical calculations, but not of cryptographic quality. Although there is no guaranteed minimum cycle length, the average cycle length is expected to be about 2^126 results. If raninit(seed) is used, no seed is expected to hit a cycle (or any other seed's sequence) in less than 2^64 results.


I have not found any test in any configuration that it does not pass. It passes DIEHARD. Sampling just the bottom byte, it passes the run test (both up and down), and the gap test (for gaps up to length 32) for 2 trillion values (chi.c). The frequency test (again on the bottom byte) looked suspicious at 1 trillion values (chi-square=5), so I ran it for 4 trillion values (chi-square=0.42), showing the earlier result was a fluke (freq.c). A test that counts bits per value for five consecutive values (countx.c) passes for at least 16 trillion values, both for normal and for graycoded values. It passes Geronimo Jones' nda test for at least 1 trillion values (4 trillion bytes).
Click to expand...
 
That fails the portability test. Java, Python, Perl and many other languages don't support unsigned types. Unless you never intend this data set to ever be used in any app using any of these languages, this algorithm won't fly. I primarily work in Python and there are some external libraries that provide unsigned types, but they're not available on all platforms.

Portability for this sort of thing can be hard. One tiny slip up and you're locked into a single language or platform implementation forever.

Simon Hibbs
 
simonh said:
That fails the portability test. Java, Python, Perl and many other languages don't support unsigned types. Unless you never intend this data set to ever be used in any app using any of these languages, this algorithm won't fly. I primarily work in Python and there are some external libraries that provide unsigned types, but they're not available on all platforms.
Click to expand...

Yes: I had to modify Jenkins' code to use plain old 'long' types, rather than unsigned long. And in the case of JavaScript, Joshua had to use, well, you know, doubles.

In JavaScript: http://calormen.com/tmp/prng/burtle.html

Same output as Perl and Objective-C and Java. Try it with Python (it's short).
 
Last edited:
My first attempt at "Universal Galactic Coordinates"

Forget a Cartesian system. For now, anyway. The numbers are really really big. No, instead, I want to constrain a location based on the galaxy, a coarse-grained distance ("rho") from the center, a sector offset ("theta"), and the hex coordinates within that sector.

In other words:

galaxy abbrev-bXX-YYYY/HHHH

where

XX is the band number,
YYYY is the sector offset along that band,
and HHHH is hex coordinates within that sector.

So for example, say Regina is in the Milky Way, Band 32, sector 900, hex 1910. The Universal Galactic Coordinates for its sector would be

MW1-b32-0900

And the UGC for the system itself would be

MW1-b32-0900/1910

Those are the values to be hashed, which seed the random number generator.
 
Hashing, again

Joshua Bell just recommended MD5 to me, since it is ubiquitous and excellent for our purposes. It seems relatively fast too, and I'm liking it a lot. So for the moment, I'm using MD5 to hash the "Universal Galactic Coordinate" to seed the random number generator.
 
Putting it together

OKAY.

Taking my draft "Universal Galactic Coordinate" system (GGG-bBB-SSSS/HHHH), I get a unique identifier for every single hex in the universe.

Using MD5, I can get a 128-bit hashcode from that. I get it as a hex string.

I then keep the leading 16 characters of that hex string -- that's 64 bits -- and throw the rest away (for now).

I feed THAT into my "burtle" fast-n-easy PRNG.

I rigged up the PRNG to get out an array of eight 1D rolls with each integer returned. 6^8 is, roughly, 19 bits. Since the PRNG returns 32 bit numbers, I'm good.

The output *looks* random to me. Tonite I will feed it through my system generation code and see if the output looks kosher.
 
Arm-based UGC

SUMMARY: coordinate = <galaxy>-<arm>-<offset>/<hex>

EXAMPLE: MW-Kishad-c45s30/1910

Another poster in another thread noted that he's mapping out local space along a different arm of the galaxy.

That made me think that perhaps the arm is the logical mapping unit for galactic coordinates. After all, an arm is so exceedingly long that, if one managed somehow to map it all out, it could be safely "projected" along a horizontal axis without any meaningful distortion. In fact, the distortion would only be evident when travelling between arms -- which is a secondary concern, not a primary one.

This solves three problems.

1. It pushes the "coordinate" problem into a lower level of abstraction. Managing coordinate transforms between large hunks of the galaxy is still polar, but doesn't matter to 99% of all situations, and thus can be safely ignored.

2. It implicitly "points" all sectors so that they have the same origin, without requiring up-front work: every sector has coreward as "down", in other words.

3. All sectors can reasonably be 32x40 hexes, without worrying about the transit length around the galaxy at a given distance. Mapping is localized to the arm, which can be assumed to be regular for 99% of all purposes.

This feeds back into point #1: plotting a jumpline to another arm of the galaxy only requires knowing an anchor point of each arm and the local offsets from those anchors. For groups that don't care, the referee can pick a "close enough" point by looking at a galactic map, and noting the relationship ("hex 2340 in Arm ZY90 to hex 2340 in Arm AA03: 5 kiloparsecs"). For groups that DO care, they can get out their calculators and work the polar equations.
 
Last edited:
UPDATE on Coordinates

This post (http://www.travellerrpg.com/CotI/Discuss/showthread.php?t=30730) has some good suggestions that I can borrow.

In brief, Jim takes a segment of a galactic arm 10 sectors long and assigns each sector a column (A thru J) and a row number. This is a gigantic amount of space to work with -- 320 parsecs long, and typically as many parsecs from coreside to rimside.

In only taking a small segment of an arm, he doesn't have to worry about the galactic curve locally; he's pushing the problem higher, which is where it belongs. Thus every sector still points "downward" toward the core, which keeps my head from spinning.

Thus my modified scheme is as follows:

Code: 
<galaxy>-<arm segment>-<column><row>/<hex>

Where

"galaxy" is an abbreviation or code for a galaxy, and is omitted for the Milky Way.

"arm segment" is a unique identifier of the arm segment in question. It could be numeric, it could be a name plus a number, it could just be a name. Whatever, as long as we all know who its neighbors are.

"column" is a single-letter sector column ID, from A thru J.

"row" is a two-digit sector row number, from 01 to (theoretically) 99.

"hex" is the sector hex.


Examples

So, hex 1910 in sector column E, row 42, of the zero-th segment of the Kishad Arm in the Milky Way is:

Code: 
Kishadan-E42/1910

Thus, hex 1910 in sector column E, row 42, of the zero-th segment of the Kishad Arm in Andromeda might be:

Code: 
ANDR-Kishadan-E42/1910
 
You must log in or register to reply here.

Similar threads

kafka47
Megatraveller Tidbits from HIWG CD Rom
Replies
19
Views
6K
Vargr Breath
V
Back
Top