Infinite Parallax Starfield
In my free time I've been working on an unannounced line-art space shooter game called Hypernova. It looks a little like Asteroids, but the screen doesn't wrap around at all. Space is infinite, and there will be all sorts of things going on out there. Quests, loot, ship upgrades and enhancements, hirelings.
It will be using no bitmapped images. All the graphics are vector images described by text files. I was originally intending to follow the same path with sound effects, and rely mostly on MIDI. However, I quickly found out that many computers have no MIDI support at all.
One of the early challenges was a nice starfield background. It has several constraints:
- Can't use any bitmapped images.
- Must work over practically infinite space.
- I must be able to resize the display
- Must be fast.
And in addition, there are some unnecessary, but desirable, properties,
- When leaving a particular location and returning, I'd like to see the same starfield pattern again.
- At the same time, I never want to see that same pattern at a different position.
When I was a kid I created the effect as a project, but it didn't have the both the desired properties above. It's also the method I found over and over when searching the Internet. There is an array of stars. Star positions are translated as the camera moves. If a star ever exits the display, replace it at a random position on the edge of the screen. To create a parallax effect, each star's translation is scaled by a unique random factor.
However, there's another algorithm I like much better, and it has both the desirable properties. Space is broken up into a grid of square tiles. To determine the star pattern in any given tile, hash the tile's position, and use the hash output to generate a few positions within the tiles, which is where stars are drawn. To create a parallax effect, perform it in different layers at different scales.
Here's what it looks like in the game,
Hypernova is written in Java, with Clojure as a scripting language, so the starfield drawing function looks like this.
Assuming the origin is in the center of the display, it iterates over
each tile currently covered by the display. Positions are created by
looking at the first couple bits of the hash for X, shift a few off,
and looking at the first few bits again for Y. Repeat until we run out
of bits. It's called with different
starscales, back to
front (darker to lighter), to create layers.
STAR_SEED is just a Mersenne prime from the Mersenne
Twister PRNG. It probably doesn't matter much what you choose for the
seed, but changing it by a single bit will drastically alter the
As far as I know, Java comes with no decent 32-bit (int) hash
functions, which is really one of the biggest roadblocks in
hashCodes()s. Fortunately, I found
an excellent hash function,
Robert Jenkins' 96 bit Mix Function, to do the trick.