Sunday, February 8, 2015

Generate Mazes in AngularJS with 8-Bit Algorithms

I started programming on 8-bit machines. Back then it was normal to do amazing things with a mere 64 kilobytes of memory on a CPU that clocked in at 2.6 Megahertz. No, those aren’t typos, and I meant “mega-” not “giga-”. In those days we were forced to do a lot with a little, and “optimizing code” meant choosing op codes based on how many cycles they took to execute.

maze

It is amazing to me to look back and see what we were able to accomplish. Software exists to perform everything from advanced compression to generating a fractal Mandelbrot set. In addition to programming I spent plenty of time playing adventure games. One of my favorite games I referenced in a recent talk. It rendered a 3D landscape for a first-person view. The sky would change color from day to night and it could even rain in this Alternate Reality.

To create fun and playable games, developers often had to resort to creative coding techniques such as using algorithms to generate the game world. Disk access was notoriously slow (how many of you remember playing the Ultima series and spending most of your time waiting to load the next city or dungeon?) so generating terrain or worlds “on the fly” made for better game play.

I remember an old arcade game called Berserker and was reminded of the game when I watched a documentary called Chasing Ghosts. It followed video game “champions” (or perhaps addicts) from 1982 to present. In it, they reviewed the game and talked briefly about how it generated its famous mazes. There is a great write-up at the Robotron site about the algorithm.

To create a “room” the game essentially assumed entrances on all four walls with eight “pillars” in the middle. Each pillar was assigned a random number, and the number determined if a wall would extend from the pillar in the north, south, east, or west position. The concept is so simple, I decided to implement it in Excel. To generate new mazes or see the underlying formulas, simply choose the Data option and select “Calculate Workbook” or edit any cell if you open it locally.

Once that was done, it was fairly straightforward to move the concept to AngularJS. The bulk of the solution is more related to the algorithm and Angular is more the means to display it. I decided to use pure CSS to draw the maze, rather than SVG or some other technology, so really all that I need are a pillar and a wall:

.pillar {
    width: 15px;
    height: 5px;
    margin: 0;
    background: red;
}
.wall
{
    width: 15px;
    height: 5px;
    margin: 0;
    background: green;
}

In the game mazes are exhaustive and interconnect “rooms.” For this example I decided to create two “rooms” so there is a single maze with an entrance and exit (always rendered on the top middle and lower right). The maze is 26 x 16 with 16 columns, represented as an array of rows that each contain an array of columns. Generating the basic maze is as simple as:

for (row = 0; row < 25; row += 1) {

    cells = [];
    maze.push(cells);
    for (col = 0; col < 16; col += 1) {
        border = row === 0 || row === 24 ||
            row === 12 || col === 0 ||
            col === 15;
        cells.push(border ? 1 : 0);
    }
}

The convention is a “0” for empty space, a “1” for a wall and a “2” for a pillar. Using the CSS and Angular, this is easily rendered with the following HTML:

<table>
    <tr ng-repeat="row in ctrl.maze track by $index">
        <td ng-repeat="col in row track by $index"
              ng-class="{ 'wall' : col === 1, 'pillar' : col === 2 }">            
        </td>
    </tr>
</
table>

I then “knock out” the doors (defined as an array of row/col coordinates):

angular.forEach(doors, function (door) {
    maze[door[0]][door[1]] = 0;
});

After that, it’s a simple question of iterating through the pillars to build the walls. Initially I wasn’t concerned about each pillar having a unique wall (i.e. they can overlap) just to keep the code simple. I store an array of values for each “direction” that indicates how to draw a wall relative to a pillar. For example, “up” means the previous three rows of the same column for the pillar:

up:
    [{
        row: -1,
        col: 0
    }, {
        row: -2,
        col: 0
    }, {
        row: -3,
        col: 0
    }]

For each pillar, I draw the pillar on the map, then generate a random number. Based on the random number, I return a direction:

function getDirection(seed) {
    if (seed < 0.25) return dirs.left;
    if (seed < 0.5) return dirs.up;
    if (seed < 0.75) return dirs.right;
    return dirs.down;
}

From the direction, I can then build the wall. The initial code for the “pillar” loop looked like this:

angular.forEach(pillarCoords.row,
    function (pillarRow) {
        angular.forEach(pillarCoords.col,
         function (pillarCol) {
                var dir, rand = Math.random();
                maze[pillarRow][pillarCol] = 2;
                dir = getDirection(rand);
                angular.forEach(dir,
                    function (offset) {
                        maze[pillarRow + offset.row]
                            [pillarCol + offset.col] = 1;
        });
    });
});

I then enhanced the algorithm beyond the Excel implementation to ensure each pillar gets a unique wall that doesn’t overlap with another pillar’s wall. This is done in a simple loop that checks to see if a wall already exists in that direction, then asks for a new direction. The way it is implemented, there is a low probability a pillar could end up without a wall due to the random generator (in the rare case it always returns the same direction).

That’s it. The majority of the implementation is done in pure JavaScript (my preference), so Angular just seeds the maze with a call to the generator, and binds a click event to generate a new maze. The controller code looks like this:

function MazeController() { }
 
angular.extend(MazeController.prototype, {
    maze: mazeGenerator(),
    newMaze: function () {
        this.maze = mazeGenerator();
    }
});


app.controller('mazeCtrl', MazeController);

You can view all of the source and see the working fiddle here.

I love this approach. A simple algorithm can generate a practically limitless configuration of mazes that are all solvable. In the 8-bit days we were forced to find simple, elegant solutions to complex problems and I see that trend happening all over again with the popularity of mobile platforms. After all, this maze will run without hesitation right on your phone!

Wednesday, January 21, 2015

Real-time Communication in AngularJS with ($Q)orlate

This post introduces the lightweight ($Q)orlate library.

A popular type of engagement that iVision is hired for is the architecture assessment. For assessment projects we analyze the existing system, weigh our own experience, industry standards and best practices against what we find, then provide feedback and a potential road map to iterate towards a desired solution. I’ve participated in everything from an over-arching analysis of the entire technology stack with associates from our data center, converged networking, and infrastructure practices to provide a business/IT roadmap for cloud readiness to a very targeted analysis of AngularJS implementations.

Recently I worked with a customer that built a very mature proof-of-concept using Angular in a system that had what I call “disconnected asynchronous processes.” These are processes that are truly “fire and sort of forget” because the message goes through message queues and workflows prior to a response being generated through a different channel. Although my first step is always to challenge this type of architecture (sometimes it’s implemented with the belief it is automatically faster or more scalable when there are other approaches that can achieve the same results with less complexity), in this case it truly seemed like the right architecture needed by that system.

I am constantly looking for opportunities to simplify and/or refactor code to reuse common components, algorithms, and strategies. This makes it easier to maintain and understand the code and provides developers with a toolbox to use so they can plug in the repeatable pattern and focus on what is unique about their part of the application. This led to me brainstorming what I’ve seen in these types of systems with Angular and I came up with three very distinct scenarios that I felt could be addressed with a lightweight Angular service.

1. Cached Requests

Angular has its own built-in mechanisms for controlling a cache. It is a common pattern for a service to asynchronously request information that is used by other components. Sometimes your app may get caught in a chicken-egg scenario when a component relies on a central service for information but must wait for that information to appear. For example, it may be necessary to retrieve security information from the server prior to building a menu or servicing requests.

There are a few ways to deal with this in Angular. One is to create the promise on the route, which will delay loading a view until the promise is satisfied. This isn’t an option if you aren’t using routes and sometimes your services may not be specific to a route. Another mechanism is simply to return a common promise. Multiple callbacks can be registered, so if the service keeps track of a single promise it can keep providing it, and even if it was resolved in the past the promise will be satisfied.

To see what I mean, take a look at this jsfiddle. Notice the second call happens long after the list was already populated, but the promise still fires and populates the second list (the list is populated after 1 second, and the second promise is requested after 2 seconds). The same promise is always returned.

The following figure shows this scenario (you can assume the server simply calls out to the database, the queue and handlers will make more sense for the other scenarios).

cachedrequests

To enhance this scenario, ($Q)orlate provides an option to track multiple requests with timeouts. If timeout isn’t a concern or is handled locally, the straightforward use of $q will suffice. What ($Q)orlate does is provide a mechanism to automatically timeout and expire the request, so it keeps track of multiple requests even if you satisfy them with a single call.

The call to ($Q)orlate is passed an id that uniquely identifies the correlation (it will generate one for you if you do not pass one in). In this example a timeout is used to emulate the delayed response. Notice the resolution has an extra parameter for the correlation.

$timeout(function () {
    _this.list = [1, 2, 3, 4, 5];
    _this.qorlate.resolve(_this.id, _this.list);                    
}, qorlate.defaultTimeout + 100);

The service always returns a correlation. This is because qorlate will immediately return the last promise that was resolved or rejected, so any values (success or error) will be satisfied in the promise.

return this.qorlate({ id: this.id }).promise;

The consumers simply call the service with a standard promise, and it will either be satisfied once the data is loaded or rejected when it times out (in the example, the initial call times out but the subsequent call works because the data has been loaded). ($Q)orlate guarantees the promise, so even if a request is rejected from a timeout and the original call returns, later requests will be resolved immediately with the result.

Although this is one use case, ($Q)orlate is more suited to two other scenarios.

2. Discrete Disconnected Messages

I am purposefully using the label “disconnected” instead of “asynchronous” because a direct AJAX call can be asynchronous while it is still “connected” in the sense there is a clear path from the call to the resolution of the promise. What is less clear is when the message is sent to be processed, then returns through another channel such as a websocket. The top section of the following figure demonstrates this:

CorrelatedRequests

I call this a correlated event because even though the return event is surfaced independently of the request (i.e. via a Web Sockets connection), it is correlated to the initial request. For example, you might have a form that submits to a queuing system, is validated by a handler on the backend, then the response is routed back. In these cases, you still want to keep track of the message (i.e. if it times out it is probably good to inform the user) but the API might not be so clear. Consider something like this that you may be used to:

var id = 1;
function sendRequest() {
    service.on('response', function (response) {
        if (response.id === id) {
            // do something
            // and don't forget to unregister
        }
    }
    service.send(id, request);
}

Basically you must keep track of your correlation and register to listen to all returned events, parse out the one you are interested in, then remember to unregister from the event (or just let it fire assuming the identifier won’t repeat), then finally fire off your message.

One of the nice things about the promise specification is that it helps make code cleaner and easier to read. What if you could do something like this instead:

service.request(id, request).
    then(function success(response) {
        // yes!
    }, function error(err) {
        // nope!
    });

This is a straight promise. Is that possible, even when the mechanisms are disconnected? The answer is, “Yes.” The service simply needs to establish the promise with a correlation:

var correlation = this.qorlate();
return
correlation.promise;

When the message comes in, the correlation is notified:

this.qorlate.resolve(correlation.id, response);

You can also reject the correlation, and the configurable timeout will also reject it automatically if the return message is not received within the timeout period. In the above example, the service generated the identifier. If you have GUIDs or other ways of matching messages, you can specify them when you generate the correlation and match it back. See a working example that demonstrates successful, failed, and timed out correlations here and view the source here.

If you look back at the second figure you’ll see there is another section near the bottom that indicates alerts raised by the server completely independent of the client. These are “broadcast” messages. You can certainly use mechanisms built into scope, but if you want a way that doesn’t rely on scope, still participates in digest loops (so no matter the mechanism for notification, you are always guaranteed to notify your subscribers in the context of a digest loop), and is testable, consider the next scenario.

3. Event Aggregator or Pub/Sub

The idea behind an event aggregator is straightforward. A central service “brokers” messages. You simply post your message to the service, any component interested subscribes, then the message is broadcast to the subscribers.

The subscription looks like this:

var cancel = q({subscribe:'addItem'}).always(function (item) {
    rs.list.push(item);
});

In this case, the subscriber is responding any time the message is sent. An error/rejection method may also be added so if there is a problem with the transport it will notify subscribers. I do realize always is used in a different context relative to promises, but it made sense here because that’s what is happening – the message is always notifying the subscriber.

The call to ($Q)orlate will return a function to cancel the subscription – that’s as easy as calling cancel(); and you’re unsubscribed. The API to raise an event is no different:

q.resolve('addItem', (new Date()).getTime());

In fact, as you can see from the test specifications, you can overload the same identifier with promises and subscriptions. The module is fairly lightweight. It:

  • Creates a promise when the function is called
  • Sets a timer to reject the promise if the timeout is hit (this is configurable at the provider level and the individual call)
  • Tracks the promises so when the correlation is resolved or rejected it can notify all consumers
  • Generates a fresh set of promises for recurring subscriptions

Because it is all based on the underlying $q service, you do not have to worry about a return call being generated outside of a digest loop as $q is integrated with the root scope.

You can browse the source, offer feedback, generate pull requests, read the full documentation, run the tests and read the samples online at https://github.com/jeremylikness/qorlate. Enjoy!

Wednesday, January 14, 2015

Web API Design Jumpstart

New to Web API design? Or experienced but want to know more?

Whether you're brand new to the ​framework or you want to take your design to the next level, this course has the answers! In this set of modules I walk you through Web API technology, uses, and nuances. See how the toolset makes it easy to build consumable RESTful services, accessible by a variety of clients from myriad platforms.

Are you an MVA member? Go through the course online here.

Get a good look at token-based security features, route attributes, error handling, and versioning. See why it is the ideal way to surface APIs that target browsers and mobile devices. Hear details on how you can easily use the built-in Visual Studio templates or explore customization, design, and implementation. Check out this informative and practical Web Wednesdays event!

Click here for the source code/demo projects.

Click here to rate or comment on the course at Microsoft's Channel 9.

Course Outline

  • Introduction
  • Basic Design
  • Configuration
  • Validation and Error Handling
  • Security
  • Advanced Design

Thank you! (Again, the MVA course is available too).

Jeremy Likness