Virtual Worlds: Minecraft

Minecraft!

I’d heard about an interesting new world called “Minecraft,” so I thought I’d see what it was like. A short download later, an icon looking like a block of earth appeared on my desktop. Double-clicking it and filling in some information (Name the world? Okay. Random seed? Let’s go with 1024 for reproducibility. Graphics detail? Sock it to me. Do I want monsters? Naah — not just yet…), I found myself looking at a sunrise over a sandy tidal pool, with low hills on both sides.

A new, blocky world awaits! (Click for larger.)

Something about this world was strange, though. It seemed that its creator followed the Integer Mythos. Think “Mario Brothers” (or “Donkey Kong,” for those of us old enough to have first associated Nintendo with Atari 2600 cartridges and coin-op arcade games.) In contrast to other worlds I’d visited, such as Cyrodiil, nearly everything in Minecraft is rendered in 1m x 1m x 1m blocks.

At first, this looks like a cheap way to avoid a lot of the work associated with creating a 3D virtual world. Make everything out of identical blocks, and lots of tasks become a lot easier. The gods must be lazy, I thought.

This kind of world has a definite appeal, though. Nearly all of the blocks in the world can be modified by digging and/or placing them. Various constructs can be made this way, from houses to mines to railroads and rudimentary roller coasters. The beauty of such an integer-based world is that it’s reproducible. A complex, intricate mechanism built in one location can be duplicated in another, given the same resources and space — and it will work exactly the same. One block of cobblestone (or dirt, or lava) is identical to any other block of the same type. Once you know how to build something, you can reproduce it elsewhere and be assured that it will work exactly the same way. (The framerates are excellent, too; glass-smooth throughout.)

There’s a lot to build, too. The world contains many kinds of raw materials, and there are many “recipes” for combining these to make different items. Some of the more useful ones are pickaxes, torches, shovels, axes, storage chests, etc. Get a block of wood from a tree and turn it into planks; take these planks and make a crafting table; use the larger surface of the crafting table to make a wood pickaxe; mine stone to make a stone pickaxe and a furnace; use the stone pickaxe to mine iron to melt in the furnace to make iron ore; use the iron ore to make an iron pickaxe… you get the point.

Even with the uniformity, though, there’s plenty of variety. There are over 100 kinds of blocks (so far); even in a modest 10x10x10 cube of blocks, there are more than 100^1000 possibilities. (That’s a one with 2,000 zeros after it.) And the world of Minecraft is much larger (much MUCH larger) than 10x10x10!

Eventually, I started to wonder — how big *was* this new world I found myself in? Would I eventually fill it up and run out of things to do? I climbed a nearby hill and looked around. The world seemed to end in fog some distance away. Not quite as big as Cyrodiil, then — I could walk over there without too much effort, I thought. I made a note of what the edge-of-the-map features looked like in one direction and started walking / swimming.

The view from a local hilltop. (Click for larger.)

Halfway there, I climbed another low hill to take a look. The features that were on the edge of the map were closer, with other features beyond them. This world was larger than it seemed; there was as much land ahead as I had seen before. Such a world was no doubt rendered by sections — and if these were programatically generated, the end of the world could be a long distance away, indeed. I turned back, deciding that there was a high probability that I wouldn’t be able to answer this question in-world anytime soon. (As it turned out, this was correct. Minecraft is very VERY big, and would take some 820 hours of constant walking to reach even the closest definition of the “end of the world.”)

The view after traveling a bit. (Click for larger.)

I couldn’t find out how far the world extended in the cardinal directions — at least for now — but what about height and depth? Not knowing much about mining, but having had some luck moving dirt blocks around, I started building a tower. Blocks, as it turns out, can float in midair; physics works a bit differently here. This is unintuitive at first, but allows very minimalistic towers to be built: a 2×2 square of blocks, with one block per level in an ascending helix. (Just don’t fall more than a few meters!) A bit after reaching the clouds (58 levels up from where I started), the world topped out. Blocks could no longer be placed above this level. So there is a definite, reachable-but-reasonable limit to height.

A helical stairway rising above the clouds. (Click for larger.)

What about depth? Along the same lines as the tower, I found that a 2×2 square could contain a spiral staircase down into the earth, lowering one meter for every 90 degrees turned. Whereas one block needed to be placed per level for the tower, three need to be excavated for a staircase in rock. (People in Minecraft are exactly two meters tall; the third block is needed for headroom when ascending and descending.)

A 2x2 spiral stairway down into the earth. (Click for larger.)

After several meters, it got too dark to see, so I had to turn back (and learn how to make torches). Torches are formed from coal (or charcoal), plus a stick; you need to either mine charcoal using a pickaxe, or build a furnace and burn wood blocks. Once torches were available, I was able to continue my spiral staircase downwards for another 64 levels, eventually reaching impermeable bedrock (or “adminium” as it’s also called.) In places, reachable areas extended another four levels, making a total of 126 level changes — 127 levels — between the bottom and the top of the world. Add another level since avatars in Minecraft span two blocks, and you get 128 levels. A nice even number for computers, but not quite as nice and round as 256. Perhaps performance considerations limited the level span?

Impermeable bedrock at the bottom of the world. (Click for larger.)

Weight and volume are definitely more a state-of-mind thing than actual physical limitations. For instance, a Minecraft character can carry 36 items, including nine “equipped” slots, but not counting armor. Each of these “items” can be as many as 64 of a “stackable” object type, such as rock. This means that — even though each “stone block” represents a 1m x 1m x 1m block of stone, a Minecraft character (ostensibly human) can carry 2,304 of them without even really trying!

I decided it would be fun to show this graphically, so I loaded up my avatar with cobblestones and started building a 13x13x13 cube. This took 2,197 blocks, so I had 107 left over for decorations. Here is the result, with a 2x1x1 (avatar-sized) stack of dirt blocks in front of it, representing a Minecraft avatar.

This is how much stone an avatar can carry at once. That cube is solid stone. (Click for larger.)

Technology exists in Minecraft, too — boats, railroads, gates, pistons, and even digital logic elements. It’s possible to build a working computer in Minecraft — but that’s a topic for another time.

 

Posted in Coding, Digital, Digital Citizenship, Games, Minecraft, Science, Toys | Tagged , , | Leave a comment

Pretty colors! (uOLED-160 review)

Recently, I found out that I had won a door prize in the 555 contest. I expected that it would be something small like a solderless breadboard or maybe a pocket DVM. Instead, I was pleasantly surprised to learn that I had won a modern, 1.7″ micro-OLED display from 4D Systems. With a MSRP of $70-something, it might have otherwise been a while before I got around to trying it out. Thanks to the generosity of Chris Savage (of Savage Circuits) in sponsoring this prize, I have the chance to experience this cool toy firsthand. (Thanks, Chris!)

The uOLED-160-GMD1 display (click for larger)

Interfacing with the display is very straightforward: supply 5VDC and ground, and connect a 1k resistor in line with the serial input, if driving it from a 5V TTL serial source. The display autodetects the baud rate up to 256k, according to the data sheet. (The Arduino I’m driving it with is known to work up to 115200 baud, so I used that.) For this application, display ground is gated via a 2N3904 transistor, allowing the Arduino to switch the display on and off (40mA is a bit too much for the Atmel to switch on its own.)

From there, it’s just a matter of sending the right commands (clear screen, set pixel, etc) to the display over the serial line. Half an hour of tinkering later (mostly because I initially didn’t read the description of the startup protocol in the instructions), I had an Arduino sketch running to display a raster scan of randomly-colored pixels.

Randomly-colored dots (click for larger)

 

Next, I wrote my graphics “Hello, World!” stand-in: a Mandelbrot Set program. The display uses a 65,536-color scheme: five bits each for red and blue, and six for green, so I set it up for 31 iterations and used that value for Red and Blue, and twice that value for Green. This produced a distinctly red-tinted display, so I backed off on the Red value by a constant 5 (clipped to remain nonnegative), which produced a decent grayscale Mandelbrot Set image.

A Mandelbrot Set image, rendered on an Arduino (click for larger)

 

Reading through the datasheet, it turns out that the display supports many useful graphics primitives. So far, I’m only using clear-display and set-pixel, but the native GOLDELOX controller supports pixels, lines, polygons, circles, images, and bitblt operations, among others. It even has a slot for a microSD card.  The display draws about 40mA of current (at 5V) when running.

Overall, I’m impressed. The uOLED-160 isn’t cheap (OLEDs generally aren’t, yet), but it does provide an easy-to-use way to incorporate full-color graphics into almost any embedded system. (It wouldn’t even be too hard to drive it with a really small MCU like a PIC10F200, if need be.) The incorporated GOLDELOX daughterboard does a good job of handling the graphical heavy lifting, allowing your code to describe the display in terms of basic elements. It would make a really cool DIY programmable watch display, for one thing. (Hmm…)

Given that I got such a cool display as a freebie, there are a lot of awesome people to thank. First, Jeri Ellsworth and Chris Gammell deserve a lot of credit for coming up with the idea of the 555 contest, getting it rolling, and organizing the whole thing. They managed to attract a lot of prize sponsors while keeping the whole contest vendor-neutral — a very good idea. They also got together an all-star group of judges, including Forrest Mims (of “Engineer’s Mini-Notebook” fame) and Hans Camenzind (the inventor of the 555). Through their efforts, the contest was hugely successful, and a lot of fun!

Also, as I mentioned, this particular prize was generously sponsored by Chris Savage, who runs the blog / forum / site Savage Circuits. I actually first heard about Savage Circuits through the contest, and signed up. They have blogs, videos, and a great forum — a very cool resource for a DIYer. Since I won the door prize, Chris Savage has been in touch with me, making sure it got here OK as well as encouraging me to post a Maker Profile on the site. (Hopefully I’ll get everything together for that soon.) Thanks again, Chris!

 

Posted in Arduino, C, Coding, Components, Digital, Electronics, Toys | Tagged , , , , | Leave a comment

Puzzle cube

Like many geeks, I enjoy unique puzzles, especially when the solution is mathematically interesting. (Puzzles with nicely-defined moves / positions / candidate solutions, and which require more thought than dexterity are the best.) I have a small collection of interesting physical puzzles (which might make an interesting article someday.)

A while ago, my wife found a wooden puzzle cube.  Figuring that it was inexpensive, somewhat educational, more or less nontoxic, and might keep me from bothering her for a few hours while she studied for her Pharmacy exams, she bought it for me. (Guys never really do grow up…)

The cube in a solved state.

The premise is pretty simple. Twenty-seven wooden blocks are joined together by elastic thread. At sixteen points in the chain, the thread makes a right angle. When twisted into the right configuration, the blocks can be formed into a 3x3x3 cube. This is more difficult than it seems: there are some four billion possible combinations, most of which seem to be impossible, since the blocks would overlap. At least one solution must work, since the cube was initially in solved form when bought.

I played with the cube for a while, eventually solving it again, and decided it would make an interesting problem for a genetic algorithm.

The cube in an unsolved state.

Two things are needed to make a genetic algorithm (GA) work: a way to express the solution as a bitstream (or string using a fixed alphabet of characters), and a method of evaluating a candidate solution (bitstream or string).  With these two pieces, the genetic operators of crossover and mutation (with possible others added) can be repeatedly applied to a population of solutions. Artificial selection using the fitness function is used to choose the next population.

Since at each point in the cube, four directions are possible, I settled on expressing candidate solutions as strings of characters — either N, S, E, or W.  I arbitrarily chose “North” to represent “up” (positive Y direction) wherever possible and “away” (positive Z direction) when “up” was not possible. Every string of these directions would represent a valid — if not viable — candidate solution. (The distinction is central to how Genetic Algorithms work; each candidate solution, even completely randomly-generated ones, must be valid. That is, it must be a string of the right length, drawn from the acceptable alphabet — in this case, N, S, E, or W. The solution may make no sense at all — with blocks overlapping multiple times and still not fitting into the desired 3x3x3 square — but it will be able to be evaluated, since any possible solution is “gramatically” correct.)

Candidate solutions are graded on the size of the rectangular prism “bounding box” needed to contain the resulting configuration, with smaller numbers being better. (The ideal 3x3x3 nonoverlapping solution would have a fitness of 27.)  The problem of overlap was handled by penalizing solutions which overlapped — in this case, ten blocks per overlap was chosen as an arbitrary penalty.)

I first wrote a fitness evaluation routine, and tested it on a known-good solution. It returned the expected value of 27, so I set up a naive random-string-generator algorithm which simply tried random strings, keeping the best-so-far solution. It came up with reasonably good guesses in a short amount of time, but took 21.17 hours to come up with an optimal, fitness-27 solution: SNNESESSNWWWSEESN.

The results for a random search. After more than 21 hours, it finally found it...

Next, I tried a genetic algorithm approach. An initial population of sequence strings was generated and evaluated. (The fitness function used was the same as before — the size of the bounding box needed to contain the result, plus ten times the number of overlapping cubes.) The fitness results were used to select individuals to be used to create the next generation. Uniform crossover and uniform random mutation were applied. It took a bit of tweaking to find optimal values (more on that later), but one GA run found a correct solution (although a different solution than the random one: SSNWSWSNNWEESEWSS) in 20.45 seconds (the 40th generation with a population size of 1000). A slightly different run found a third optimal solution — NWSSNNNESSWWNSENW — in 7.16 seconds (14 generations).

Optimal solution found in 14 generations (with population size 1,000). Only 15,000 candidate solutions (out of over four billion) were searched!

Those results represent GA runs where an optimal solution is found, so they’re a bit optimistic. Using the GA settings that I’ve come across so far, I’ve found that the GA tends to either find an optimal solution relatively quickly, or doesn’t find one within quite some time (if ever).

I’m currently working towards characterizing the effects of varying the mutation rate and fitness / selection criteria on the overall probability of the GA finding an optimal solution. For now, though, restarting randomized runs of the GA after a hundred or so generations pass without a solution seems to do the trick; a solution is usually found sometime in the first five or ten minutes — still a speedup of over a hundred times compared to the blind random search procedure.

Myth confirmed: Darwinian evolution does work — at least in silico.

 

 

 

Posted in BASIC, Coding, Math, Science | Tagged , , , , , | Leave a comment

Full of hot air

There is a definite trend in electronics away from the older, larger through-hole components in favor of smaller, denser (and often more complex) surface-mount components. For now, many microcontrollers and support chips are available in through-hole DIP form, suitable for breadboarding or soldering using through-hole PC boards.

The writing is on the wall, though: to work with smaller components and/or more complex components with higher pin count, surface-mount techniques and equipment are needed. For one thing, FPGAs are difficult or impossible to find in DIP form factor; the only options are to use dev boards for everything (expensive and unwieldy for finished products) or to be able to work with QFN and other surface-mount packages.

I had recently come across an old parallel-port scanner being given away at a yard sale, and picked it up. My wife thought I was crazy — but scanners need stepper motors to work, and stepper motors are useful to have and normally cost actual money. I figured if nothing else, I could always just take out the stepper and throw away the rest. I hate to see technology go to waste, though, so I resolved to salvage whatever I could from the scanner. I got the stepper motor, a few gears, a lens assembly, a cold cathode light tube and its easy-to-use high voltage supply — but the rest of the components were mostly surface mount.

I’d been thinking of getting a hot-air rework station for a while, and this made the decision for me. So many devices are thrown away or sold for next to nothing at thrift stores and flea markets. Rather than seeing these components go into the Dumpster, why not build a stock of SMT components and teach myself surface-mount techniques at the same time? I ordered a nice-but-not-too-expensive Aoyue 852A++ rework station with a vacuum pick-up tool, and set the circuit boards from the scanner aside.

Last week, the rework station arrived. I tried it out at work (we’re seriously considering getting one for a device we’re developing). Here is a video showing how relatively easy it is for a hot-air-rework newbie to recover small components (most likely logic drivers and a couple of capacitors) from a board…

Now for the next steps: classifying and reusing the recovered components in new circuits!

Posted in Electronics, Tools | Tagged , , , , | Comments Off on Full of hot air