Around two weeks ago, I found this email in my inbox, with the subject “Complaint about Robozzle”:
Robozzle is really cute, I like it, but why on earth is it polluted with hundreds of invisible links to porn sites? From a guy like you I don’t expect to do such dirty things. pls remove them.
Did you ever see one of those auto-generated random “academic papers” like this one? When I first saw the following title, my first thought was that it is a randomly-generated “paper”:
Turing completeness, cardiac arrhythmias, XBox 360… those things don’t seem to have much in common. But, I had my interest piqued. I looked up the paper and read through it. And, it turns out that not only is the paper serious, what it has to say is also quite interesting.
Not many developers have the insights of Michael Abrash. He is a game developer with decades of experience building commercial games, including a game you may recognize as "Quake". His Graphics Programming Black Book is years old, but much of it is just as interesting as it was at the time of writing. And, the entire book is available online, for free.
The book consists of 70 chapters on optimization, graphics, and assembly programming. The entire book is insightful and interesting, but my favorite chapters are these:
- The Best Optimizer Is between Your Ears
- There Ain’t No Such Thing as the Fastest Code
- Optimizing for 286 and 386, 486 (continued), and Pentium (continued here and here).
- Algorithms for fast drawing of lines, anti-aliased lines, polygons, fast convex polygons, and 3d objects (continued)
- Quake’s visible-surface determination, 3D clipping, hidden-surface removal, span sorting, lighting, surface caching and post-mortem.
Enjoy! Again, the entire book is accessible here: Graphics Programming Black Book.
Over the past couple of years, auto-complete has popped up all over the web. Facebook, YouTube, Google, Bing, MSDN, LinkedIn and lots of other websites all try to complete your phrase as soon as you start typing.
Auto-complete definitely makes for a nice user experience, but it can be a challenge to implement efficiently. In many cases, an efficient implementation requires the use of interesting algorithms and data structures. In this blog post, I will describe one simple data structure that can be used to implement auto-complete: a ternary search tree.
Trie: simple but space-inefficient
Silverlight 2 is an awesome platform for development of rich web applications. One issue to be aware of, though, is that some browser features do not extend into Silverlight apps. For example, the Back and Forward browser buttons do not always work as the user may expect with Silverlight apps. The set of browser features you’ll miss in Silverlight apps is pretty much identical to what you’d miss in Flash or AJAX, and some of them are about to be addressed in the Silverlight 3 release.
Let’s go over the affected browser features one by one, and discuss ways of getting them working in Silverlight apps.
Feature 1: Bookmarking and deep linking
It took significantly longer than I expected, but the RoboZZle demo video is finally on YouTube.
My favorite funny comment is this one:
And finally, this is the video:
In database terminology, a view is a named query that typically aggregates data from multiple tables. When using views, it is important to remember that querying a view will evaluate the query that defines the view. Repeated evaluation of the view – say from within a nested query – may seriously impact or even kill the performance of your application.
One solution to this performance problem is to use a “precomputed view”. Unlike an ordinary view, a precomputed view is stored in a table rather than computed on demand. When data in one of the aggregated tables changes, the update operation also updates the precomputed view table.
Notice that this post was published on April 1, 2009.
For decades, computer science students have been taught that so-called NP-hard problems do not have known efficient solutions. These problems include the infamous Travelling salesman problem, subset sum, 3SAT, and many more.
But – as is often the case – where theoretical Computer Science failed, sound software engineering practices will succeed. By using loosely-coupled OOP, agile methodologies and the model-view-controller architectural pattern, I developed a solution that someone trapped in the world of formulas and big Ohs would never dream of.
Enough with the background, and let’s take a deep dive into the intriguing design.
Read the rest of this entry »
For fun, I’ll discuss different aspects of RoboZZle and assign each a letter grade.
Game Addictiveness: A
Read the rest of this entry »
After about 3 months of evening coding, the game that I’ve been working on is now live.
RoboZZle is an online puzzle game that challenges you to program a robot to pick up all stars on a game board. The game mechanics are simple, yet allow for a wide variety of challenges that call for very different solution approaches.
Here is an example of a solved RoboZZle puzzle, with the arrow edited-in to show the path of the robot: