I guess I wasn’t quite finished with this project. It annoyed me to not have a fully automated backtrace of my deathtrap dungeon solver so I finally added it. Here’s the complete maze with the solved path highlighted:

custom_complete_maze_with_solution (pdf)

complete_with_solution (graphviz dot file)

Here’s how the system works:

1. Solve the maze forward using breadth-first search, propagating acquired “satisfiers” forward to child nodes (ie if your parent had a given satisfier like “SHIELD” then the child node has the same satisfier). The only trimming I do at this point is making sure I don’t add any child nodes where I don’t have the satisfier required for a given edge.

2. Backtrace from the endpoint of the maze by only following parents that meet the “requirements” that have been discovered so far. If a transition along an edge requires something, I add that requirement, and then only add subsequent parents who have that satisfier. For example, if the final node in the maze is 399->400 and it requires “DIAMOND”, I add “DIAMOND” as a requirement. Because we are only working with the possible parents available from the forward solve (meaning, it can only be a parent if at least some path arrives at the parent node with the DIAMOND) we know that at least some parent will have the required DIAMOND. If we discover at some possible point, lets say 397->399 and 398->399 that only 397 has the DIAMOND, then we can prune 398. It turns out this is sufficient to provide a single possible path (well, when I avoid all unnecessary battles) through our maze.

I just found a new favorite toy called Graphviz! I used it to draw the Deathtrap Dungeon graph in its entire form (all nodes) and in its solved form (only encluding nodes encountered during backtrace).

The complete map as pdf: deathtrap.pdf
The complete map as .dot (change extension): deathtrap.txt
The solution as pdf: solution.pdf
The solution as .dot (change extension): solution.txt

Deathtrap Dungeon Solution

When I was a child, I played Deathtrap Dungeon, a “Fighting Fantasy” novel by Ian Livingstone. These books were magical in their ability to give kids the sorts of agency, adventure, heroism, and excitement that videogames would later provide. The covers were lurid, and promised action and violence and magic, all things a healthy ten year old wanted:

Read more »

I’m so busy with jobhunting and consulting that I have been neglecting my thesis work. My project is to develop the physics and graphics engines sufficient for doing realtime simulation of “The Neverhood”, a claymation videogame from the 90s. My professor said “Start with a spinning box!” so I did. It’s a humble beginning, but it means my dev environment is set up and I’m thinking about OpenGL again.

I’ve completed almost all my degree requirements at SJSU and have started my two semester thesis. I’m still trying to narrow my thesis scope, but early on I picked out a good thesis advisor. This professor is in high demand among the graduate students, and no wonder: He’s extremely bright, an excellent instructor, and a prolific developer himself. He’s also extremely busy, and could take only two more graduate students. Over the Christmas break he held a coding competition with the two top submissions getting the spots.

The challenge was the following: Given a URL, implement (in PHP) a hashing function that produces a fixed length, approximately unique key that can still identify some of the “tokens” that created it.

Read more »

If you are regular readers of this site (me, my mom, and my fiancee) then you have noticed that the site has been down for a month! It was caused by what I fear is a rather common occurence: Some WordPress plugin. The delay in repairing it was caused by school!

Now that I’m back on the job hunt, I wanted to get my “web presence” back up so I decided to spend some time fixing the site. This involved tinkering in an ignorant and dangerous way with WordPress and then calling my hosting service where “Justin” (I didn’t quite catch his name) told me that I needed to upgrade my account to be eligible for helpdesk support and then went ahead to find and fix my problem anyhow. So, thanks Justin! And if anyone needs a bangin’ web hosting (and wordpress troubleshooting) service, I am one satisfied Lunarpages customer.

I was studying compilers and Babbage and got a bit obsessed with “Victorian Computing”. So I made a clockwork man outfit.

I recently purchased a pull up bar to get chiseled in preparation for my photo shoot in the MindTribe Christmas calendar.
Tim, our director of Electrical Engineering, took a look at the contraption and concluded the load is borne solely on the door trim, a design choice of which he disapproved. This didn’t seem quite right to me, and it nagged enough to get me out of bed early Saturday morning to figure it out.

Read more »

I found this quote recently and wanted to put it somewhere I could find it again. It’s from Alfred Delp, a Jesuit priest executed by the Nazis: Read more »

I went to an interesting talk by Stanford Management Science professor Stephen Barley, discussing his book “Gurus, Hired Guns, and Warm Bodies”, an analysis of the role of contractors and contracting in the United States. The talk was two hours long so I won’t attempt to summarize it all here but I did want to share some of his insights. Read more »