Hackszine.com: Software Engineering Archives

Archive: Software Engineering

Page 2 of 3 << 1 2 3 >>

June 23, 2008

Algorithm Geeks

If you've ever stumbled into a tricky coding or data representation problem, chances are good that someone has already figured it out. Usually the resolution is found by speaking with the Google, emailing your resident alpha-geek, or consulting Knuth's Art of Computer Programming (you know, the 50 pound box set that's been waiting patiently on your shelf for exactly this moment).

I stumbled across a fourth option this afternoon: the Algorithm Geeks user group. It's an easy way to parallelize your problem, running it past the brains of hundreds of alphas from around the world. Even if you aren't seeking help, maybe there's a post or two in there that you can contribute to. My inner nerd is probably showing, but it's pretty fun just reading through the posts and weighing the different proposed solutions.

Hack on!

Algorithm Geeks Google Group

May 26, 2008

Code Kata: exercise for the software developer

It's no news that practice is the only path to being truly great at something. The art of software development is no different. The demand for programmers the way it is, however, means that a lot of folks jump into their careers head first with a certain level of formal subject knowledge, but very little practical experience. Likewise, even experienced developers are sometimes so busy that not enough time gets devoted to the practice of the craft. Dave Thomas recognized this problem and came up with a collection of short, defined practice exercises for software developers, the Code Kata:

Code Kata is an attempt to bring this element of practice to software development. A kata is an exercise in karate where you repeat a form many, many times, making little improvements in each. The intent behind code kata is similar. Each is a short exercise (perhaps 30 minutes to an hour long). Some involve programming, and can be coded in many different ways. Some are open ended, and involve thinking about the issues behind programming. These are unlikely to have a single correct answer. I add a new kata every week or so. Invest some time in your craft and try them.

Some of the example scenarios are expressed in Ruby, but aside from that they are language agnostic. What I like is that the exercises cover a wide breadth of scenarios, some of which I encounter daily in my work, and some only rarely. Even working through the problems and roughing out a solution in my head seems to be a useful tool for keeping the problem solving faculties sharp. Trying to solve problems like these involves no real deadlines or pressure, which is the necessary environment for devoting a little time regularly to focus on honing your skills.

Do you use any other resources for staying on top of your game? Let us know in the comments.

Code Kata

May 20, 2008

Duff's Device: loop unrolling for interpreted languages

In 1983, Tom Duff invented a really strange way to use the C language's switch and case statements for the in code "unrolling" optimization of large loops. As an example, he described a simple loop that copies an array to an output register:

	send(to, from, count)
	register short *to, *from;
	register count;
	{
		do
			*to = *from++;
		while(--count>0);
	}

On every iteration of the loop, in addition to the copy that is being performed, the count variable is decremented and a comparison is done against 0. Duff's Device allows you to achieve the same result, but with only an 8th of the overhead:

	send(to, from, count)
	register short *to, *from;
	register count;
	{
		register n=(count+7)/8;
		switch(count%8){
		case 0:	do{	*to = *from++;
		case 7:		*to = *from++;
		case 6:		*to = *from++;
		case 5:		*to = *from++;
		case 4:		*to = *from++;
		case 3:		*to = *from++;
		case 2:		*to = *from++;
		case 1:		*to = *from++;
			}while(--n>0);
		}
	}

What happens is that the loop is unrolled 8 times, so each iteration of the loop runs the internal code 8 times over without the comparison. The genius of Duff's Device is that it takes advantage of the way the C switch/case structure works. The first time through, if the iterations don't divide evenly by 8, the loop code is executed enough times to equal the remainder of iterations/8. It's a little bizarre, because the "do" statement occurs within the switch, but there are "case" statements within the "do". Nevertheless, it's valid C.

Before someone cries foul, remember that this is only really suitable for speeding up the performance of inner loops when no suitable, better algorithm is available. If you code C, most modern compilers are smart enough to automatically optimize your code and unroll loops for you.

For interpreted languages like PHP or Javascript, however, you sometimes need to do a little optimization on your own if you want to squeeze out some extra performance. Luckily, both languages have a c-style switch statement.

Andy King wrote about a slightly altered version of this loop unrolling algorithm which ditches the switch statement and breaks the normal Duff's Device into two separate loops, one for the remainder and one for the unrolling. In Javascript, it performs a simple addition loop in only a third of the time of a normal for loop (testVal++ is the normal loop's interior):

function duffFasterLoop8(iterations) {
  var testVal=0;	
  var n = iterations % 8;
  if (n>0) {
    do 
    {
      testVal++;
    }
    while (--n); // n must be greater than 0 here
  }
    
  n = parseInt(iterations / 8);
  do 
  {
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
  }
  while (--n);
}

It's not as syntactically clever as Duff's Device, but it's a good way to manually unroll an inner loop and get the best performance for your extra effort.

Duff's Device
Andy King's Optimizing JavaScript For Execution Speed

May 9, 2008

Processing.js - visualization library for Javascript

John Resig, of jQuery fame, released a port of the Processing visualization language for Javascript. Seriously, John is on fire:

The first portion of the project was writing a parser to dynamically convert code written in the Processing language, to JavaScript. This involves a lot of gnarly regular expressions chewing up the code, spitting it out in a format that the browser understands.
It works "fairly well" (in that it's able to handle anything that the processing.org web site throws at it) but I'm sure its total scope is limited (until a proper parser is involved). I felt bad about tackling this using regular expressions until I found out that the original Processing code base did it in the same manner (they now use a real parser, naturally).

The full 2D API is implemented, with the exclusion of some features here and there between browsers (Firefox 3 is pretty full featured). You can interact with the Processing API directly from standard Javascript. This lets you make use of these drawing features by simply instantiating a Processing object, and then calling its various drawing methods.

Another capability is to write code natively in the Processing language. This allows you to make use of extended language features such as method overloading and classic inheritance, though it looks like type information is pretty much ignored.

John has many of the demos from processing.org working. Most of them are going to peg your CPU, but this is some seriously cool stuff to see working in a first release.

Javascript just got a lot more interesting.

Processing.js
Processing: open source data visualization language

May 8, 2008

DIY multi-touch on OS X

Bridger Maxwell has been blogging his progress on creating a homebrew multi-touch platform in OS X. Prior to this, there's been a lot of activity around building multi-touch systems on Windows using the Touchlib library, but this is the first time I've seen a concerted effort on OS X.

The basic hardware is the same for both environments: LEDs surround a sheet of acrylic, causing a backscatter of IR when fingers are pressed to the screen. On the software side, though, the multi-touch interface is provided through Pawel Solyga's OpenTouch library. From the sounds of things, though, it's not super simple getting the interface messages from OpenTouch to your multi-touch enabled Cocoa apps:

Both OpenTouch and TouchLib send the touch data to other applications by sending Tangible User Interface Object (TUIO) network messages. TUIO is a protocol that is designed for transmitting the state of multi-touch systems. TUIO is built upon another protocol, Open Sound Control (OSC). While libraries for receiving TUIO messages are available in a few languages such as C++ or Java, there was not a solution for Cocoa applications. My first step was to build a library for receiving TUIO messages in Cocoa.
Because TUIO is built upon OSC, I looked for a library that could parse OSC messages. Unfortunately, I could not find one that would fill all my needs. WSOSC was a library that came close though. There were a few issues to work around (use NSData instead of NSString), but eventually I was able to use WSOSC to parse the OSC packets. When finished, my framework had the ability to parse TUIO messages and had a method to delegate the TUIOCursor objects it created to another application.

From the blog comments, it sounds like Bridger is planning on releasing this middle layer when it gets a little further along. At the moment, though, he's released a demo comic viewing application that uses his multi-touch project framework. If you're interested in developing multi-touch apps for OS X, some of the discussions on Bridger's blog would be a good place to start.

Bridger's Multi-Touch Blog
OpenTouch Library

April 23, 2008

Scriptographer - Javascript for Illustrator

My friend Barrett sent along a link today to an Illustrator scripting plugin called Scriptographer. I'm sort of a slouch at Illustrator, so I had him give me the quick 411 and I must say, this is pretty cool.

If you're familiar with Javascript, Scriptographer will enable you to crank out little scripts that can generate illustrations procedurally. As an example, the bubbelbubbling script, show above, tuns your pen tool into a fountain of random bubbles that follow your drawing path. There are certain styles of artwork that could really lend themselves to a procedural drawing tool: fractals, patterns, random "particle" effects. These things would take forever to generate manually, but by defining the effect programatically, you can quickly experiment with your work in a more dynamic fashion, tweaking variables and fine-tuning your work as you go.

The project website also has a growing library of user-contributed scripts that are worth checking out. It's a good place to start for your own creations, or you may just find exactly what you're looking for, already crafted for you by another designer-coder.

Scriptographer

April 22, 2008

Encoding JPEGs client-side in AS3

I've been doing a bunch of Flash Actionscript 3 development lately at work, and one of my favorite features with the new drawing API is the ease and speed with which you can rasterize vector data and manipulate image bitmaps.

What's killer is that Adobe's as3corelib addon library finally gives us some essential tools that have been sorely lacking, none the least of which is a client side JPEG encoder. With this, you can turn any drawable object like a sprite or a movieclip into a ByteArray holding the compressed JPEG data in just a few lines of code. It's as simple as this:

import com.adobe.images.JPGEncoder; var clipbmp:BitmapData = new BitmapData (aclip.width, aclip.height); clipbmp.draw(aclip);
var jpgEnc:JPGEncoder = new JPGEncoder(90); var jpgbytes:ByteArray = jpgEnc.encode(clipbmp);

This turns the "aclip" sprite or movieclip into a rasterized, flattened, BitmapData object. The BitmapData is then run through the JPEG encoder with the quality setting of 90 and you're left with the raw JPEG-compressed image in a ByteArray object. The as3corelib also provides a PNG encoder, with which you can just use the static method PNGEncoder.encode(clipbmp).

This is perfect for saving a capture of user-generated artwork to the server. Just set the data member of a URLRequest object to the ByteArray and post it. For more detailed information on how to put all the pieces together, Henry Jones has a really thorough post of compressing JPEG data and pinging it off a server to force an image download.

Unfortunately, to trigger a JPEG download, you still need to post the image data up to a server script and have it echo it back to the browser. The difference now, though, is that you can do the compression on the client end, saving both server CPU time and the time to upload the image data. This means saving a large image is a few second process instead of taking a minute and a half.

Actionscript 3 Core Library (as3corelib)

April 8, 2008

Relational database using jQuery and HTML tables

Here's a novel use for the HTML <TABLE> tag: storing client side database tables. Nick Kallen came up with a slick hack that uses the jQuery syntax to perform simple selects and joins on HTML tables. By using CSS3 selectors, you can easily target fields which match or contain your search terms, and Nick's jQuery-based API provides a simple query language, similar to a rudimentary SQL:

Today I was thinking aloud about Tree Regular Expressions and how they might make a nice query language for document databases like CouchDB. Someone pointed out that CSS3 selectors might make a great concrete syntax for this. One thing lead to another and I thought, why not build a relational database in HTML? So I did. I even got inner joins working.
Let's start with a few tables:
<table class="users">
  <tr>
    <td class="id">1</td>
    <td class="first_name">amy</td>
    <td class="last_name">bobamy</td>
  </tr> 
  ...
</table>
<table class="photos">
  <tr>
    <td class="id">1</td>
    <td class="user_id">1</td>
    <td class="url">http://www.example.com/foo.png</td>
  </tr> 
</table>
Now we can express some queries:
$('.users')
  .where('.id:eq(1)')
  .select('*')
This is equivalent to SELECT * FROM users WHERE id = 1
$('.users')
  .where('.id:eq(1)')
  .select('.id, .name')
This is equivalent to SELECT id, name FROM users WHERE id = 1

How cool is that? Check out Nick's blog post for an example of text search and an inner join. The API in his jquery.db.js is quite straightforward and only about 50 lines of code. Adding a sort function shouldn't be too difficult.

I'm pretty much convinced now that jQuery is black magic.

Building a relational database using jQuery and <TABLE> tags
Download the jquery.db.js library

April 7, 2008

Javascript marker clustering for Google Maps

Everyone who works with large data sets in Google Maps has come across the problem of displaying a bunch of markers in a small area. Not just an eyesore, displaying anything more than a hundred marker icons at a time can bog the browser down on a lot of platforms, Safari on PPC Macs delivering the most pain.

The solution is to cluster nearby markers into an aggregate marker when there are too many markers being displayed, or when markers are so close at a particular zoom level that they completely overlap. For extremely large datasets this is most efficiently done on the back-end, with successive AJAX calls refreshing the marker set from a PHP script that filters out the visible markers from the set.

You can also handle the clustering on the client side, using javascript to scan the entire set of locations and dynamically determine what's visible and what should be clustered. The downside is that you have to download the entire set and store it in the browser's memory, but unless you start getting well into tens of thousands of markers this isn't a big deal. The benefit to the client side method is that it's less complex, it lets you work around large result sets from back-end APIs that you can't control, and with ACME Labs' Clusterer javascript library it's extremely easy to code.

To use Clusterer, first download and include the Clusterer2.js file from the link below in your maps page. Then you need to instantiate a Clusterer object, passing your map object to its constructor:

var clusterManager = new Clusterer(map);

From there, you use it in place of the traditional MarkerManager or any addOverlay calls by calling the Clusterer's addMarker method. It takes two parameters, the marker to add, and a text string that will be listed in the cluster's contents when it is clicked:

clusterManager.AddMarker(marker, "Marker Description");

The cluster manager will take care of all the dirty work, only displaying items when they are within your view, and dynamically clustering them appropriately when there are too many on the screen at once. When one of the clusters is clicked, it will display a list of the locations inside of it. Most of what you'd want to tweak, like the threshold at which to start clustering and the icon used for representing a cluster, are all adjustable through the API via some self-explanatory methods such as SetMaxVisibleMarkers(n) and SetIcon(icon). Follow the link below for more information, or read the source for a few of the less-documented options.

Clusterer documentation
Clusterer source

April 3, 2008

Practical fluid mechanics

Mick West from Cowboy Programming posted a two part series to his blog titled Practical Fluid Dynamics. Originally written for Game Developer Magazine, it covers a number of clever (and down-to-earth) techniques for simulating the movement of fluids in games and other software environments where real-time speed and visual authenticity matter most.

Special attention is paid to the simulation of particulate matter being carried around within a fluid volume—think effects like smoke, fire, and bubbles. I know I've seen a number of people using particle systems to do this sort of thing, but the methods Mick describes are all based on a grid model where you represent the system with a velocity field and a density field. Unlike a particle system, these fields represent a continuous fluid surface, allowing you to measure the density and velocity of the fluid at any location on the surface by interpolating the values from the nearest cells in the field array.

Practical Fluid Mechanics

March 19, 2008

From Nand to Tetris in 12 Steps

Shimon Schocken gave a really interesting Google Tech Talk titled From Nand to Tetris in 12 Steps. In the video, he describes a course where students design a complete virtualized computer system from scratch, building from the humble nand gate, to a functional cpu and memory architecture, to compiler software and an operating system, all culminating in a simple game that runs on the virtual hardware.

The hardware projects are done in a simple hardware description language and a hardware simulator supplied by us. The software projects (assembler, VM, and a compiler for a simple object-based language) can be done in any language, using the APIs and test programs supplied by us. We also build a mini-OS. The result is a GameBoy-like computer, simulated on the student's PC. We start the course (and this talk) by demonstrating some video games running on this computer, e.g. Tetris and Pong.

Building a working computer from Nand gates alone is a thrilling intellectual exercise. It demonstrates the supreme power of recursive ascent, and teaches the students that building computer systems is -- more than anything else -- a triumph of human reasoning.

It looks like most of the course materials are available online. The necessary hardware emulator and simulator software is open source and available from Shimon's website.

CS101 Digital Systems Construction
Video - Building a Modern Computer from First Principles [via Slash7]

March 10, 2008

SketchUp has a Ruby API

I guess it's been available for a few months, but I just noticed that there's a Ruby API for Google SketchUp. Looks like a cool tool for extending the building interface, integrating SketchUp entities with external software, and building procedural stuff, like making terrain or stairs.

Here's a video of SketchUp developer Mark Limber talking about some of the possible ways to extend the software with the Ruby API.

Google SketchUp Ruby API - Link
SketchUp API Blog - Link

March 6, 2008

Microsoft Excel 3D engine

Peter Rakos wrote an article for Gamasutra today which demonstrates how to hack yourself a simple 3D engine by subverting an Excel worksheet. It's not going to win any FPS awards, but the fact that you can even get Excel to draw raw shapes blows my mind.

In his demo, the worksheet is used to calculate values for all the polygon vertices and a very small macro loop draws the resulting mesh to the screen.

After downloading the source XLS, run the demo by hitting alt-F8 (option-F8 in Mac Excel). You'll find the code under the "Tools->Macro->Macros" menu.

Microsoft Excel: Revolutionary 3D Game Engine - Link
Peter's Example 3D Excel files - Link

February 29, 2008

Single character commenting

It's a pretty common practice to comment and uncomment big chunks of code during the development and testing of software. Here's an odd little hack from the ajaxian blog that can make this a little easier for blocks that you're constantly flipping on and off during development.

For C style comments, the following will be commented out:

/* if ( foo == bar ) { dosomething(); return(); } // */

And the addition of a single '/' will uncomment the block:

//* if ( foo == bar ) { dosomething(); return(); } // */

In languages that don't have the single line comment, such as CSS, you can do the same thing with only the block level comments.
Commented:

/*/ min-height:100px; /**/

Uncommented:

/**/ min-height:100px; /**/

You are probably talking to your screen right now, saying, "hey Jason, that commenting trick is marginally useful at best." I can only respond by reminding you that every keystroke is a beautiful and unique snowflake that must be cherished and never wasted.

A neat commenting trick - Link

February 10, 2008

Extracting GTA3 art assets for use in your own game

One of the most frustrating things about homebrew game development is that there's almost an insurmountable amount of work that needs to be done just to get something decent to display on a screen. You can roll your own complete graphics and physics engines and still have nothing to show for it if there are no art assets to load.

QuantumG's solution to the problem was to focus on developing the game engine using the model data from GTA3. Knowing that the art is already functional in another game allows you to focus on your code, and it's more fun when you can see the immediate results of your work.

The blog entry walks you through his experience with extracting and using the mesh, texture, city, and character data and making use of it with the OGRE graphics engine. If you've ever played around with making a game before, but got discouraged for lack of art assets, this is really worth a read.

Using GTA3 art assets in OGRE - Link
OGRE 3D graphics engine - Link

Page 2 of 3 << 1 2 3 >>