Mazes, rooms, and pathways

You can tell it's the holiday season, because I've been playing games and thinking about games, a lot.

So I thoroughly enjoyed Robert Nystrom's recent essay: Rooms and Mazes: A Procedural Dungeon Generator.

Nystrom takes us through a variety of different approaches to generating dungeons for adventure games, because it turns out there are a lot of things to consider.

For example:

You could make a roguelike with perfect dungeons, and many simple roguelikes do that because generators for those are easier to design and implement.

But I find them less fun to play. When you hit a dead end (which is often), you have to do a lot of backtracking to get to a new area to explore. You can’t circle around to avoid certain enemies, or sneak out a back passage.

Nystrom proceeds to explore two basic approaches to dungeon generation:

• Start with a maze. Trim back the maze to leave holes in the space, then turn those holes into rooms.
• Start with a bunch of randomly-placed rooms. Flood-fill the spaces between the rooms with mazes, then connect things together

As he puts it:

Where Buck and Karcero start with the maze and then add the rooms, mine does things in the opposite order. First, it places a bunch of random rooms. Then, it iterates over every tile in the dungeon. When it finds a solid one where an open area could be, it starts running a maze generator at that point.

The best part of the article is the illustrations. Nystrom fills the article with live demonstrations of various techniques, which bring the code to life and make it easy to understand the alternatives and how they impact the resulting generated dungeon.

If you've ever tried your hand at generating a dungeon (and what game-playing computer programmer hasn't?!), I think you'll really enjoy reading Rooms and Mazes.

Who knows? It may even get you excited enough to start writing that game you've been putting off...

Wasteland 2: a very short review

I've been whiling away many an hour recently playing Wasteland 2.

There's no doubt about it: this is a very fun game.

You and your party find yourselves in a post-apocalyptic wasteland, loosely modeled on the territory and scenery of southern Arizona, in a chaotic world full of mystery and adventure.

You travel about from place to place, take on quests, unearth clues, unravel mysteries, defeat bad guys, and generally have yourself a wild-and-wooly rip-roaring good time.

The making of the game is rather interesting, as revealed by this Wired article: How One Guy Got Kickstarters to Give Their Profits to Other Campaigns

Fargo went on to launch other games, including the now celebrated Fallout series, and even became a game publisher himself, as founder of Interplay Entertainment. But Wasteland was his baby, and by the early 2000s, he wanted to create a sequel to the game that put him on the map, called Wasteland 2.

The problem was, the studios wanted nothing to do with it. “I got nowhere for another decade,” Fargo says.

Then, in early 2012, Fargo stumbled upon a still up-and-coming company called Kickstarter that let creators raise funding from their friends and fans.

But you don't have to care about how the game is made; it's more fun just to play the game itself.

Now, where was I? Oh, yes, back to trying to negotiate with the Servants of the Mushroom Cloud...

Christmas Eve link clearance

Get 'em while they're hot!

• On the Sony Pictures Security Breach

  Reports say Sony Pictures had trouble attracting and recruiting security talent, which isn’t too surprising for a company known for its disdainful attitude toward technology. Being on the wrong side of issues like SOPA/PIPA couldn’t have helped—what technologist would want to work for a company that is trying to break the Internet?

• Did North Korea Really Attack Sony?

  The agency's evidence is tenuous, and I have a hard time believing it. But I also have trouble believing that the US government would make the accusation this formally if officials didn't believe it.

• The Case for N. Korea’s Role in Sony Hack

  The “silent” part of the moniker is a reference to the stubborn fact that little is known about the hackers themselves. Unlike hacker groups in other countries where it is common to find miscreants with multiple profiles on social networks and hacker forums that can be used to build a more complete profile of the attackers — the North Koreans heavily restrict the use of Internet communications, even for their cyber warriors.

• What Does "Responsibility" Mean for Attribution?

  Using the Spectrum of State Responsibility, in my assessment, the US government's statements include a range of possibilities, from State-encouraged to State-integrated.

• Stupid Costly Patent Nuclear War By Microsoft & Apple Against Android Averted

  In short, this is basically Google and Cisco (with some help from a few others) licensing these patents to stop the majority of the lawsuits -- while also making sure that others can pay in as well should they feel threatened. Of course, Microsoft, Apple and the others still have control over the really good patents they kept for themselves, rather than give to Rockstar. And the whole thing does nothing for innovation other than shift around some money.

• Why String Theory Still Offers Hope We Can Unify Physics

  Most gratifying, the mathematics revealed that one of these notes had properties precisely matching those of the “graviton,” a hypothetical particle that, according to quantum physics, should carry the force of gravity from one location to another. With this, the worldwide community of theoretical physicists looked up from their calculations. For the first time, gravity and quantum mechanics were playing by the same rules. At least in theory.

• Cerebros and the art of drug smuggling

  This is not the work of a pickaxe army of drug war foot soldiers. These are multi-million-dollar underground networks, created covertly with professional machinery under the guidance of top-end engineers or architects who have been pulled—willing or not—to the dark side.

• The Future: A Cat Litter Box and DRM

  I did some Googling, and I found that the “Smart” in SmartCartridge is that it has an RFID chip inside of it to keep track of how much solution it has, and once it runs out, well, you can't refill it. I honestly did not believe this and tore one of the cartridges apart, and there it was, looking back at me, a tiny chip holding up it’s little metal finger.

  Seriously CatGenie, you added fairly sophisticated DRM to a litter box? I’m a tad hurt you spent my money on building in a restriction instead of figuring out how to avoid constantly cooking poop.

• Drobo vs. QNAP vs. Synology vs. G-Drive and MORE! Which Storage Should You Choose?

  To me, the ideal size for a NAS device is at least 4 drives. You can get them with as few as two if you’re really never going to use much storage, and if you are going to do that I’ve got a recommendation for you in a minute, but with 4 or more you can have plenty of space without sacrificing redundancy. And I’ve got three different options for you here. The QNAP TS-470 Pro, The Synology 1513+, and the Drobo 5N.

• The Top Metrics You Need to Track to Improve Operational Performance

  At PagerDuty we’ve thought hard about what you should monitor and why from a systems perspective, but what about monitoring data on your operations performance? We’d like to share some specific metrics and guidelines that help teams measure and improve their operational performance.

• Interesting papers from NIPS 2014

  NIPS is the premier conference on Deep Learning. Given the accelerating state of the art, it’s interesting to see what is new.

• Testing TokuDB's Group Commit Algorithm Improvement

  As part of our effort to verify the new Binary Log Group Commit functionality introduced in TokuDB 7.5.4 for Percona Server, we wanted to demonstrate the substantial increase in throughput scaling but also show the bottleneck caused by the skewed interaction between the binary log group commit algorithm in MySQL 5.6 and the transaction commit mechanism used in TokuDB 7.5.3 for Percona Server.

• Are We Consistent Yet?

  Traditional systems provide strong consistency, where clients can immediately view updates. Some distributed systems relax their consistency model to allow greater availability or better performance. Eventual consistency manifests itself to clients as stale views of data.

• The Softsel Hot List for the week of December 22, 1986

  Back in the days before Internet-based software distribution, heck back even before the Internet existed in a form resembling what it is today, one of the most important ways of keeping track of the consumer computing industry was to subscribe to the Softsel Hot List, a weekly poster of the top sellers in various categories. Here is the Softsel Hot List for the week of December 22, 1986

• Our local fill

  The original wetland that became Lake Merritt was known as San Antonio Slough. From Oakland’s earliest days, the locals kept trying to “reclaim” it by turning it into dry land, just as they did all around the bay. The whole waterfront is reclaimed land. The basic technique was to haul dirt and rock and rubbish down to the water, shove it in and tamp it down. In Gold Rush San Francisco they’d use abandoned ships for fill, but Oakland’s founding fathers had advanced beyond such crude strategems.

For my Christmas Eve meal, my grand-daughter made me hand-made crab-and-shrimp sushi.

Life is good.

Some links for understanding CVE-2014-9390

This is a particularly interesting CVE for me, because it's "right up my alley", as they say.

• Git 1.8.5.6, 1.9.5, 2.0.5, 2.1.4 and 2.2.1 and thanking friends in Mercurial land

  Git maintains various meta-information for its repository in files in .git/ directory located at the root of the working tree. The system does not allow a file in that directory (e.g. .git/config) to be committed in the history of the project, or checked out to the working tree from the project. Otherwise, an unsuspecting user can run git pull from an innocuous-looking-but-malicious repository and have the meta-information in her repository overwritten, or executable hooks installed by the owner of that repository she pulled from (i.e. an attacker).

• [ANNOUNCE] Git v2.2.1 (and updates to older maintenance tracks)

  Fixes since v2.2
  ----------------
  
   * We used to allow committing a path ".Git/config" with Git that is
     running on a case sensitive filesystem, but an attempt to check out
     such a path with Git that runs on a case insensitive filesystem
     would have clobbered ".git/config", which is definitely not what
     the user would have expected.  Git now prevents you from tracking
     a path with ".Git" (in any case combination) as a path component.
  
   * On Windows, certain path components that are different from ".git"
     are mapped to ".git", e.g. "git~1/config" is treated as if it were
     ".git/config".  HFS+ has a similar issue, where certain unicode
     codepoints are ignored, e.g. ".g\u200cit/config" is treated as if
     it were ".git/config".  Pathnames with these potential issues are
     rejected on the affected systems.  Git on systems that are not
     affected by this issue (e.g. Linux) can also be configured to
     reject them to ensure cross platform interoperability of the hosted
     projects.
  
   * "git fsck" notices a tree object that records such a path that can
     be confused with ".git", and with receive.fsckObjects configuration
     set to true, an attempt to "git push" such a tree object will be
     rejected.  Such a path may not be a problem on some filesystems
     but in order to protect those on HFS+ and on case insensitive
     filesystems, this check is enabled on all platforms.
  
  A big "thanks!" for bringing this issue to us goes to our friends in
  the Mercurial land, namely, Matt Mackall and Augie Fackler.
  

• 3f1509809e728b70ea7912e4e1b40f22965e45ee

  fsck: complain about NTFS ".git" aliases in trees 
  read-cache: optionally disallow NTFS .git variants 
  path: add is_ntfs_dotgit() helper 
  fsck: complain about HFS+ ".git" aliases in trees 
  read-cache: optionally disallow HFS+ .git variants 
  utf8: add is_hfs_dotgit() helper 
  fsck: notice .git case-insensitively 
  t1450: refactor ".", "..", and ".git" fsck tests 
  verify_dotfile(): reject .git case-insensitively 
  read-tree: add tests for confusing paths like ".." and ".git" 
  unpack-trees: propagate errors adding entries to the index
  

• Git vulnerability with .git\config

  Normally the git client avoids ever overwriting that file. Even if you commit a .git\config file and push it to a shared repo, no one else’s Git client will check it out into their private repos. However, a bug was discovered where various permutations of the .git folder name (e.g. mixed case, gIT, GiT, etc, Windows filename shortening .git~123, Ignorable Unicode codepoints .g\u200cit\config, etc) were not caught be the Git client’s filtering logic. As such, if someone pushed a malicious config file with one of these permutations, other people’s Git clients would check them out, overwriting their personal config file and hijacking their Git commands. This affects, at least, Windows NTFS and Mac OS X HFS+ filesystems, both of which are case insensitive filesystems.

• Vulnerability announced: update your Git clients

  Repositories hosted on github.com cannot contain any of the malicious trees that trigger the vulnerability because we now verify and block these trees on push. We have also completed an automated scan of all existing content on github.com to look for malicious content that might have been pushed to our site before this vulnerability was discovered. This work is an extension of the data-quality checks we have always performed on repositories pushed to our servers to protect our users against malformed or malicious Git data.

Some resources for trying to understand the SPE hack

If you're trying to make sense of it all, here are some fairly well-reasoned essays, from a variety of smart people:

• North Korea and the attack on Sony Pictures Entertainment

  In HPSR Security Briefing Episode 16, we profiled North Korea’s cyber threat landscape, highlighting the regime’s known capabilities and deficiencies in cyberspace. In that report, we noted North Korea’s initial response to The Interview. Based on our previous research of North Korean cyber capabilities, it is difficult to discern whether the regime acted alone. It is plausible that the actors responsible for this attack relied on the assistance of an insider.

• FBI: North Korea to Blame for Sony Hack

  While the United States government seems convinced by technical analysis and intelligence sources that the North Koreans were behind the attack, skeptics could be forgiven for having doubts about this conclusion. It is interesting to note that the attackers initially made no mention of The Interview, and instead demanded payment from Sony to forestall the release of sensitive corporate data. It wasn’t until well after the news media pounced on the idea that the attack was in apparent retribution for The Interview that we saw the attackers begin to mention the Sony movie.

• Lessons from the Sony Hack

  This could be any of us. We have no choice but to entrust companies with our intimate conversations: on email, on Facebook, by text and so on. We have no choice but to entrust the retailers that we use with our financial details. And we have little choice but to use cloud services such as iCloud and Google Docs.

• Did the DPRK Hack Sony?

  Drawing positive conclusions from the public evidence is incorrect. The NSA and the CIA may (or may not) have many other details they'll never disclose. The much-ballyhooed language setting, for example, is completely useless.

• Why it's possible North Korea was behind the Sony hack

  NSA analysts might start with what’s known as “flow records,” which are very similar to Netflow. Each of these records details a communication between computers and the ports they used to initiate said communication. It might read something like this: "Computer A, port X sent K bytes of data to computer B, port Y between T0 and T1". Although flow records are the simplest data collected by the NSA’s wiretaps, it’s a powerful tool for tracking online activity.

• What is happening?

  It's not about a movie or even Sony, at all. When you build a nuclear program, you have to explode at least one warhead so that other countries see that you can do it. The same is true with Cyber.

• goodbye horses

  I suppose the more nuanced point Dave is trying to make, is not so much that this is an Act of War, or even that it should be. But more that this Sony thing is not about Sony, it's about the US necessarily having to prepare for a future where it will have to politically and publicly address and respond to a game that up until very recently, was only played in the shadows.

Hacker School publications are quite impressive

Somehow I stumbled across the inaugural issue of the Hacker School journal: Code Words: A quarterly publication about programming from Hacker School.

I haven't had time to read the entire issue yet, but so far I'm really pleased.

You know that you're really reading a publication targeted at programmers when the first paragraph of the first article is as follows:

Floating point is a giant mess. There are known best practices for most issues that come up in everyday use (e.g., using Kahan summation or adding stochastic noise to reduce aggregate numerical error), but there are still corner cases. Different libraries and implementations give different results because there’s no generally accepted standard.

"Numerical error"? "Kahan summation"? "Stochastic noise"?

Oh, yes, yes, YES! Bring it on!

And I also really enjoyed An introduction to functional programming, with its straight-forward, plain-english approach:

When people talk about functional programming, they mention a dizzying number of “functional” characteristics. They mention immutable data, first class functions and tail call optimisation. These are language features that aid functional programming. They mention mapping, reducing, pipelining, recursing, currying and the use of higher order functions. These are programming techniques used to write functional code. They mention parallelization, lazy evaluation and determinism. These are advantageous properties of functional programs.

Ignore all that. Functional code is characterised by one thing: the absence of side effects. It doesn’t rely on data outside the current function, and it doesn’t change data that exists outside the current function. Every other “functional” thing can be derived from this property. Use it as a guide rope as you learn.

They seem to be off to a great start, so I'm hoping that Hacker School continue to find success, and continue to publish more issues of their journal.

Meanwhile, reading the journal led me to the Hacker School blog, which seems pretty great too; I particularly like their "Read Along" feature, in which they select a research topic each week, post a pointer to the paper with some introductory thoughts, and encourage the audience to read along with the paper and contribute their own reactions.

If you're looking for some good reading to strengthen and extend your programming skills, give the Hacker School publications a try!

I suppose I should pay more attention to my investments...

Frankly, I don't monitor my retirement accounts anywhere near as closely as I should.

Who has the time?

But I do try to look at them every quarter or so, to think about how they are doing and what I should change, if anything.

So I signed on and looked at my IRA, and was reading through the various positions.

And I noticed information for a company I'd never heard of!

How did a company I'd never heard of appear in my account? Did I fumble-finger some trade, months ago? Was I hacked? The "purchase history" for the new company showed three apparently legitimate trades, dating back to 2011.

Then I did some web surfing, and arrived at: Kimberly-Clark Announces Details for Completion of Kimberly-Clark Health Care Spin-Off

Kimberly-Clark Corporation (NYSE: KMB) today announced the record date, distribution date and distribution ratio for the previously announced tax-free spin-off of its health care business. The spin-off will form the new publicly traded company, Halyard Health, Inc. Kimberly-Clark also increased its 2014 share repurchase program to take into account expected proceeds as a result of the spin-off.

Kimberly-Clark shareholders will receive one share of Halyard Health common stock for every eight shares of Kimberly-Clark common stock held as of the close of trading on Oct. 23, 2014, the record date for the spin-off.

And, sure enough, the dates of the three trades are precisely the three occasions on which I purchased Kimberly-Clark stock in my IRA.

The computers had quietly taken care of it all.

But, really, I ought to pay more attention to my retirement accounts.

Maybe next year, he says...