Monday, May 23, 2011

Rounding to significant digits in Ruby

A few years ago, I built a Rails application which estimated the nutritional information of entire recipes by mapping the individual ingredients to food records in the USDA nutritional database, then summing up the nutritional values across all the foods.

This is a surprisingly tricky task. In many cases there's a lot of hand-waving involved. How much meat do you get from an 8 pound turkey? How do you calculate the amount of food consumed versus the amount measured before cooking? What if the USDA only measured the nutrients for a raw sample, but you eat it cooked?

Clearly, many of these nutritional values are going to be ballpark figures, so it wouldn't make sense to display them out to the tenth decimal place. But that's what you'd get by default after doing floating-point multiplication and division: A lot of spurious digits.

Why not just round everything to, say, two decimal places, and display that? As an example, consider that one set of nutritional info may work out to contain 548.667 calories and 0.384503 mg of vitamin B6. A fractional calorie is just noise; nobody is going to worry about whether their lunch has an extra 2/3 of a calorie, even if the number is accurate. But 0.38 mg of B6 is about a quarter of the daily allowance; we can't afford to ignore those fractional milligrams.

This is where significant figures AKA significant digits come in. I only want to preserve the digits furthest to the left -- the most significant -- regardless of the location of the decimal point. I searched for a way to do this in Ruby, but rather than finding a solution, I found that many people confuse rounding to N significant digits with rounding to N decimal places. These are not the same thing.

548.667 rounded to 2 decimal places is 548.67
548.667 rounded to 2 significant digits is 550.0

So how can this be done without converting the number to a string and scanning it? Scientific notation. This notation expresses a number in terms of a fixed-point number and an exponent, and is actually similar to the way floating point numbers are represented internally. sprintf can write this format, and to_f can read it. Because normalized scientific notation always places exactly one digit to the left of the decimal point, specifying a precision of N-1 in sprintf's format string will round a number to N significant digits. A format of "%.1e" will give us 2 significant digits.

irb(main):001:0> a = 548.667
=> 548.667
irb(main):002:0> b = sprintf("%.1e", a)
=> "5.5e+02"
irb(main):003:0> b.class
=> String
irb(main):004:0> c = b.to_f
=> 550.0
This does what I want it to, so why not add a method to Float?

irb(main):006:0* class Float
irb(main):007:1>   def sigfig(digits)
irb(main):008:2>     sprintf("%.#{digits - 1}e", self).to_f
irb(main):009:2>   end
irb(main):010:1> end
=> nil
irb(main):011:0> a.sigfig(2)
=> 550.0
irb(main):012:0> d = 0.38450
=> 0.3845
irb(main):013:0> d.sigfig(2)
=> 0.38 

That works. But for the purpose of display, I'd really like to suppress the trailing decimal point and zero when the number has been rounded to an integer. The precision of the number 550 isn't clear (it could be ones or tens), but displaying it as 550.0 implies more precision than we have. I'll create a method which is designed specifically for output.

irb(main):001:0> a = 548.667
=> 548.667
irb(main):002:0> class Float
irb(main):003:1>   def sigfig_to_s(digits)
irb(main):004:2>     f = sprintf("%.#{digits - 1}e", self).to_f
irb(main):005:2>     i = f.to_i
irb(main):006:2>     (i == f ? i : f).to_s
irb(main):007:2>   end
irb(main):008:1> end
=> nil
irb(main):009:0> a.sigfig_to_s(2)
=> "550"

There's probably a better way to do this; I still tend to speak Ruby with a C accent and I may have missed a shortcut. But it does achieve my goal of reasonably clean output for tables full of Floats. Here's a page snippet from one of the sites which uses this code.

Sunday, May 22, 2011

Firefox Moiré hack (CSS abuse)

Here's a code snippet that's been sitting on my hard drive since last January. It generates Moiré interference patterns via the CSS -moz-repeating-radial-gradient property.  I find this interesting in that even a small PNG created this way requires about 1000x the storage as the code used to generate it.

The hack only works in Firefox; IE does not support repeating-radial-gradient and Webkit's -webkit-repeating-radial-gradient does not attempt to render the gradients with the subpixel (im)precision required for the effect. In Firefox, simply resizing the browser window in either dimension will change the way this is rendered, and scrolling the page will probably cause it to glitch. Try it!


Here's a screencap from Firefox, which is pretty much guaranteed not to look exactly like the above...even if you're viewing this in Firefox.


The code contains several magic numbers which were selected just to make this look funky.

<div style="height: 500px; overflow: hidden; position: absolute; width: 500px;">
<div style="background: -moz-repeating-radial-gradient(red, red 2px, blue 2px, blue 3px); height: 800px; position: absolute; top: -200px; width: 800px;">
<div style="background: -moz-repeating-radial-gradient(black, black 1px, transparent 1px, transparent 2px); height: 850px; left: -150px; position: absolute; top: 100px; width: 830px;">
</div>
</div>
</div>

You can also fill the entire viewport with pretty interference patterns using a tiny HTML document. Resize the browser for eye candy. Endless fun for the whole family!

<!DOCTYPE html><html><head><title>Moire</title></head>
<body>
<div style="background: -moz-repeating-radial-gradient(black, black 1px, transparent 1px, transparent 2px); position: absolute; top: 0; left: 0; width: 100%; height: 100%">
</div>
</body>
</html>

Warning: Applying the gradient directly to the body element may cause Firefox to hang and eat a ton of memory. It looks like a bug was filed on this over a year ago with priority "critical", but it's still open. So...don't do that.

Tuesday, April 26, 2011

Starry night / topographic oceans

This has nothing to do with either van Gogh or Yes.

It's what I made of the volume beneath a Minecraft spawn point over a period of weeks, culminating in the use of a couple of simple Python filters.  The first converts 1% of a selected volume to glowstone.  The second converts all the blocks immediately adjacent to water into glass.  I used both on the ceiling of a 240x240x56 block volume, resulting in the following.

This view shows the effect of glowstone set in the obsidian ceiling. Sunrise is visible to the left; the far wall is too far away to render. The Temple of Rule 30 exterior is visible on to the right.

Starry Night
Replacing the ocean bottom with glass makes the ocean appear as a contour map of itself.

Topographic Oceans

Here's the MCEdit filter. It only replaces air adjacent to water with glass, so it's up to you to remove the rock/dirt/whatever from the surrounding volume before running the filter. Fair warning: I'm a Python newb.

from numpy import zeros, array

def perform(level, box, options):
 schema = level.extractSchematic(box)
 schema.removeEntitiesInBox(schema.bounds)
 schema.removeTileEntitiesInBox(schema.bounds)

 block_id = 20 # glass

 for y in range(1,schema.Height):
  water = schema.Blocks[:,:,y] == 9
  air = schema.Blocks[:,:,y] == 0
  
  # Shift the position of the water on this level to the four surrounding blocks and intersect this with air
  # to determine which sides should be contained in glass
  
  c= zeros(water.shape)
  c[:-1, :] += water[1:, :]
  c[1:, :] += water[:-1, :]
  c[:, :-1] += water[:, 1:]
  c[:, 1:] += water[:, :-1]
  glass = ((c > 0) & air) * block_id
  
  schema.Blocks[:,:,y] += glass

  # Now place glass below
  
  air = schema.Blocks[:,:,y-1] == 0
  glass = (water & air) * block_id
  schema.Blocks[:,:,y-1] += glass

 level.copyBlocksFrom(schema, schema.bounds, box.origin)

Monday, March 28, 2011

My sentiments exactly

"They probably taught you different in marketing, but renting property, it's never seemed an honourable way to make money to me," Yasar says.  "Using money to make money."

"Isn't that what this is about, getting finance to make more finance?"

"This is getting finance to make something that will change the world. Notice the two little extra words in there? 'Make something.'"

  - From The Dervish House, by Ian McDonald

This quote has been on my mind lately, as I consider new employers with the hope of finding something more fulfilling to do than leveraging technology to market products to people who really don't need them.

"Make something."

I heartily recommend, well, everything by Ian I've been able to get my hands on.  His treatment of a future India as told by River of Gods and Cyberabad Days was startlingly good -- not because I had low expectations, but because he starts with a culture which is already foreign to me and extrapolates it into places which you can't help but be changed by visiting.

Tuesday, March 8, 2011

KB2505438: Windows Update fail

Windows Update KB2505438 gives users the following description:  "Install this update to resolve issues in Windows."

Issues?

Issues.



I'd like more information, please.  Fortunately there's a "More information" link provided for those who'd prefer not to blindly patch their operating system with no prior notification of what is about to be changed.  Here's what happens when you click the link:

You are redirected to a parking domain which is not owned by Microsoft.  It comes complete with a catchy title:  "Bug free software just has random features."  The screenshot may be missing the full glory of this page because I refuse to display it in IE.

UPDATE:  This is apparently due to a typo.  Someone at Microsoft misspelled Microsoft.
More information:
http://support.micrososft.com/kb/2505438
What amazes me is that it's even possible to make a typo here.  There's no macro for the knowledge base domain name?  This just can't be stored as unconstrained text in hundreds of thousands of documents.  Can it?

Saturday, March 5, 2011

Minecraft procedural texturing success

Followup to the Temple of Rule 30:  I made another attempt at mapping the output of a 2D cellular automaton to 3D objects in Minecraft and had better luck with a different ruleset.  It can work, provided you choose the rules carefully and work only with large objects.

Here's a sampling of various block mappings used with the same algorithm on a 125 block diameter sphere.

Subtle & mossy
Nested bands of ore
Not-even-remotely-subtle edition
Pig approves.


With a little more work, I might be able to recreate Planet Bitmap from STNG...

Hmm, there's an idea:  Glowing planets in the night sky.  Pity the world is 30 million blocks wide but only 128 blocks tall.

Wednesday, March 2, 2011

Minecraft, Python, and the Temple of Rule 30

I've noticed in my recent job search that Python is a commonly requested scripting language.  I haven't really had much interest in learning it; several years of Ruby (on Rails), a long stretch of Perl, and various other languages at various levels of abstraction ranging all the way down to assembler have made it quite clear that there are only so many ways to express a control flow statement.  I feel that a computer language, as with any tool, should include staying out of your way as a central part of its design philosophy.  Ruby is very good about that.

So why learn Python?  Because it's frequently used as an embedded interpreter.  It's used to control and extend other software.  But what does this have to do with Minecraft?  MCEdit includes a Python interpreter, and I've been using MCEdit quite a bit.

I decided one day that I'd try to clear a large ziggurat-shaped space underground using more or less the same techniques used for TNT drift mining, only without leaving any of the intervening walls standing.  I'd clear the whole space and make the walls nice and tidy.

Right.

As amusing as it is to blast the hell out of stuff in Minecraft, clearing layers of 5x5x5 chunks became mighty tedious by the 5th layer down, at which point the floor was roughly 45x45.  Roughly, because some very large dirt and gravel inclusions were making a mess of things.  There was still a long way to go to bedrock.  I have my kinks, but holding down a mouse button long enough to remove or replace c. 73,000 blocks and calling that "fun" isn't one of them.  It was time to bring the power tools into the sandbox.

A long editing session brought the the pattern down to bedrock, exposing an existing railway and a bunch of deep caves I'd explored earlier.  I cleared out the lava and cleaned up the walls.  Here's the result.  The floor is 125 x 125, with torches in the middle of each visible 5x5 face.


Great!  All done.  The simple repeating patterns of light and dark and the hundreds of pinpoint torches looked quite nice.  But after riding through it and viewing the room from many angles, I thought it was missing a little something.  How about some texture?

This is where Python comes in.  Why not script a volumetric texture generator and use it to "paint" the world?  I had a vague idea that cellular automata might be up to the task, rather than using discrete samples of continuous functions.  Water and lava already appear to follow CA rules, and Minecraft is basically a voxel space you can walk around in.  This seemed a perfect match.  Elegant, even.

It's been a long time since I played with CA.  It's a topic I revisit every few years as a sort of touchstone for how insanely fast microprocessors have become,  like watching real-time fractal renders on a GPU while still having a memory of waiting for a single low-res Mandelbrot render to fill in one scan line at a time on workstation-class hardware.  Well, it's 2011, and now we have Golly and people simulating Conway's Life inside Conway's Life (sort of) just because they can.  I love it.

I experimented with Golly for a while and decided to implement a Generations algorithm with NumPy.  Generations is Life-like, but cells which are marked for death are not zeroed out immediately; instead they age for a certain number of iterations before they are removed from the grid.  This spreads out the active growth regions and tends to make the patterns flow rather than shimmer.

After a lot of trial-and-error, I was able to fill a 3D selection within MCEdit using two dimensions for the CA grid and one for time.  It worked, and I learned a bit of Python and NumPy in the process.

There was only one problem:  The results looked awful.

Within Golly, iterations of the Generations rule are expressed as video, with subtle changes in color indicating the changing age of each cell.  The result is a gnarly, mesmerizing wash of color.

Generations rule S2/B13/15 starting with only 5 living cells,
at 20, 100, 500, and 1000 iterations



But regardless of how I mapped the CA into the world, the subtlety was lost.  It always looked either streaky or random.  Part of the difficulty was the deliberate lo-fi look of Minecraft itself -- a smooth color palette isn't really possible -- but it was mostly due to the translation of time into depth.

Back to the drawing board.  I could continue to tweak the 2D CA and mapping rules to look for a pleasing translation, but a different approach might be more appropriate for this particular application.

How about a 1D CA instead?  I could run a 1D rule to create a 2D array and then project that into the 3D world.  This simpler approach actually looked much nicer in tests.  The most complex part turned out to be the projection of the texture onto the "front" of an MCEdit selection volume which has no knowledge of where the camera is located.  I handled this by requiring that the center of one side of the selection contain nothing but air; it's assumed that the camera isn't inside a solid object.

Here's the final appearance.  All the torches have been eliminated and the walls "textured" with glowstone and obsidian based on Rule 30.


Sort of a cross between TRON and the Luxor Las Vegas.  :)

Sunday, February 13, 2011

Large Constructions in Minecraft

I've been goofing around with Minecraft single player since alpha-something-or-other.  Legitimate spelunking can still be fun, but I also enjoy building improbably large things.  This is really only made practical by the wonderful MCEdit.

Here's a 144x144x128 mob trap.


Outside view showing the scale of the building. (v.2, different world)


The top half is made of pitch-black spawning trays and short canals ending in 2x2 holes.  The bottom is mostly empty space, partly filled by a large number of falling / drowning traps.  The key to the design is the observation that the potential spawning zone is (currently, as of beta) a subset of a 17x17 chunk volume, which contains many millions of blocks, but the active mob cap is quite small.  The goal here is to both control most of the spawn volume and to kill everything in it as quickly as possible in order to allow new mobs to spawn.  None of the canals in the spawning zone is more than 15 blocks long.  Each one ends in a very long fall into shallow moving water, which then leads to a drowning trap for the mobs not killed by the fall.  The very bottom of the structure is just a network of collection canals.

The distant wall appears to be made of floating blobs because I converted all the rock in the surrounding areas into glass; the sky blue color is actually distance fogging and the blobs are everything that isn't rock.



I liked the "visible Minecraft" effect so much that I built a 10 km railway with all the surrounding rock, dirt, and gravel converted to glass.  Gold ore was converted to lightstone for additional underground illumination. 


The effect is visible at night through the bottom of the ocean.


Sunrise seen through a hillside.




And now for something completely different:  A forested crater which extends all the way to the rendering horizon.


Night view.


The original site was mostly ocean.  The crater was constructed in MCEdit by creating a very large sphere of dirt using the brush tool, then creating a slightly smaller sphere of air centered within the dirt, also using the brush tool.  Technically this was only a section of a sphere, as it was made much larger than the 128-block maximum height in order to keep the steepest part of the bowl shallow enough to hold trees.  The portion of the bowl above sea level was then deleted, and the crater rim integrated with the surrounding landscape in-game using pick, shovel, and dynamite.

But this just left a big bowl of dirt.  I wanted the area to be heavily forested.  How do you generate thousands of trees?

MCEdit filters to the rescue!  I learned enough Python to write a filter which picked random x,z coordinates within a selection block, located ground level, added a sapling there, and changed a nearby empty block to lightstone to help the sapling grow.  Then I entered the game and waited.

Once the forest was fairly dense, I dynamited several points on the rim and cleared out some of the foliage in order to create a network of waterfalls and rivers leading to pond in the center.  Next I added a rail terminus leading to my spawn point.  The last few steps were cleanup:  Removal of ungrown saplings and redundant lightstone blocks, both of which were performed with Python filters, along with a lot of detail tweaking in-game.

I'd originally planned to remove the lightstone after the trees were grown, but I found I really liked the effect at night.