Tim's Blog

Another code blog

  • Revisiting War of Words: Postmortem

    A postmortem usually happens within a small timeframe after release.  Well, I waited 3.5 years, lol.  Anyway, this is my take on what went right with design and development and what went wrong.

    What Went Right

    1.  Word Graphs and AI characters

    Implementing a word graph to store the word list was a great idea because it gave me so much flexibility in solving problems.  I was able to search the graph with the AI engine and find words very quickly.  I loved that the Game Studio Content Pipeline allowed me to create processors that could take lists of words and create a word graph structure out of them.  I saved off this structure to disk and loaded it very quickly at game startup.  I played other word games on the XBox Indie Games platform and many had long load times (probably because they were processing giant XML files or something).

    The AI was also a pretty good implementation IMO.  It looked very natural, and it scaled up and down in difficulty nicely.  It wasn’t perfect, but extending it and tweaking it was pretty simple.

    2.  Overall Game Concept

    The RPG/word game concept is a good idea and I think I executed it well enough when it came to the core game play features.  I’m pleased with it and would use it as a template for a sequel if I wanted to.

    3.  Getting an Artist to do the Artwork

    Obviously this is a no-brainer if you want something to look good.  I simply don’t have the artistic talent.  The take away here is that if you want something to be professional, you need to put the money up to get an artist.

    What Went Wrong

    1.  Some Graphics were not done by the Artist

    I decided to do some of the graphics myself which was stupid and I think it led to it looking a little unprofessional at times.  I also think the box art could have been better but I didn’t do anything about it.  A lot of people judge a game by the box art.

    2.  The story made no sense and was bad

    There’s not much to say here.  It wasn’t good.  It wasn’t interesting.  Maybe it was even laughable.  I’m not a writer and I don’t pretend to be one.  In the end, a lot of reviewers pointed this out but many would then positively point out that it didn’t matter if the story sucked because the game play was good.  The presentation of the story was low tech and uninteresting too.

    3.  The map was not implemented well and was not interesting

    The map needed to be a little better drawn and more interesting IMO.  The controls on the map were not done very well.  I should’ve used a model where the cursor was more freely controllable by the player.  The icon stand-in for the player was stupid.

    4.  Random encounters were confusing

    When you moved between locations on a map, you might randomly be attacked by an enemy.  At that point, you can either flee or fight.  If you fled, you incurred some HP damage.  If you fought, you could usually win the battle but it took too long.  This whole process was just not done very well and needed to be re-thought.

    5.  Shields were a dumb concept

    In combat, you could earn shields by scoring big words.  The AI character also had shields.  If you were about to get attacked, you could tap a button and raise the shields for 5 seconds or so of 50% or better armor.  The problem was, however, that human players couldn’t quickly raise the shields and ended up getting hit and then raising them.  I bet this made them feel like an idiot.  The AI of course perfectly handled shields and it was very unfair.  The shield concept should go!  You already wear armor so I don’t know what I was thinking.

    6.  Quests were not interesting

    A “Quest” in War of Words was just a scripted encounter (a single battle).  There were no other variations on this theme.  I should have went for more complicated quests that involved multiple encounters, travel, other game types, etc.  I have a lot of new ideas but they didn’t make it into the original and it got boring after a while.

    7.  Battles lasted too long

    Sometimes you’d spend 10 minutes or more on one character.  This isn’t good.  I did try to make this better at one point but still didn’t turn out as well as I had hoped.  If they were shorter, we could have had more of them or they could’ve been more interesting.  Another variation on this is that it might have been too difficult to beat.  If you got wasted at the last minute, you had to repeat the (long) encounter all over again.  I don’t know, I didn’t want the game to be too easy though.  It is really hard to judge the difficulty of your own game.

     

    There’s probably a lot more “wrongs” to write about, but I don’t want to beat up on myself too much here :).  I think the overall theme here is that polish was lacking in many areas and polish is what makes a game great. 

    Categories: Games

    Tags: War of Words

  • Building a Dynamic Application Menu with Durandal.js, Knockout, and Bootstrap (Pt. 3)

    In the last two posts of this series, we built a dynamic menu system.  Now it is time to wrap it up with a discussion on how to actually populate and use these menus.

    One idea is to create the concept of a workspace which represents the UI that the user sees for the application.  The workspace is like a top-level window in a desktop application.  The following module defines a workspace that contains a list of menus and defines a routine to take arbitrary menu layout objects and convert them to Menu and MenuItem instances:

    define(function (require) {
        var Menu = require('ui/menu'),
            MenuItem = require('ui/menuItem'),
            menus = ko.observableArray([]);
    
        function setupWorkspace(cmds) {
            menus([]);
    
            var menus = {
                "File": [
                    { text: "New", command: cmds.new },
                    { text: "Open", command: cmds.open },
                    { divider: true },
                    { text: "Save", command: cmds.save },
                    { text: "Save As", command: cmds.saveas },
                    { divider: true },
                    { text: "Sign out", command: cmds.signout }
                ],
                "Edit": [
                    { text: "Cut", command: cmds.cut },
                    { text: "Copy", command: cmds.copy },
                    { text: "Paste", command: cmds.paste }
                ],
                "View": [
                    { text: "View Mode", subItems: [
                        { text: "Simple", command: cmds.toggleSimpleView },
                        { text: "Advanced" command: cmds.toggleAdvancedView }
                    ]}
                ],
                "Help": [
                    { text: "Contents", command: cmds.helpcontents },
                    { divider: true },
                    { text: "About", command: cmds.about }
                ]
            };
    
            loadMenus(menus);
        }
    
        function loadMenus(menuDefinitions) {
            var menuText, menu;
            for (menuText in menuDefinitions) {
                menu = addMenu(menuText);
                addMenuItems(menu, menuDefinitions[menuText]);
            }
        }
    
        function addMenuItems(menuOrMenuItem, itemDefinitions) {
            for (var i = 0; i < itemDefinitions.length; i++) {
                var definitionItem = itemDefinitions[i];
                if (definitionItem.hasOwnProperty("divider")) {
                    menuOrMenuItem.addDivider();
                }
                else {
                    var menuItem = new MenuItem(definitionItem.text, definitionItem.command);
                    menuOrMenuItem.addMenuItem(menuItem);
                    if (definition.hasOwnProperty("subItems")) {
                        addMenuItems(menuItem, definitionItem.subItems);
                    }
                }
            }
        }
    
        function addMenu(text, position) {
            var menu = new Menu(text);
            if (position) {
                menus.splice(position, 0, menu);
            }
            else {
                menus.push(menu);
            }
    
            return menu;
        }
    
        var workspace = {
            menus: menus,
            addMenu: addMenu,
            setupWorkspace: setupWorkspace
        };
    
        return workspace;
    });
    
    

     

    The main application shell should call the workspace singleton’s setupWorkspace() function and pass in an object that contains references to the desired ko.commands that will get attached to the menu items.  It can also use the menus property in its data-binding to automatically create the UI (as seen in part 2 of this series).

    The setupWorkspace() function creates a menu definition which is just an inline object literal.  The source for this could actually come from the server as JSON, or be in another file, or loaded by a plugin.  The point is that there is a definition format that gets fed into the loadMenus() function that builds the menus by converting the definition into real Menu and MenuItem instances and adding them to the collection.

    The workspace module also exports the addMenu() function which allows someone to add a menu to the menu bar after the initial setup has taken place.  I think more functions (like remove) could be added if you really want to make this robust as far as configuration of menus is concerned (I’m just demoing this to illustrate a point).  And obviously, the commands aren’t built and this is very demo-specific, but you can just swap that out for whatever you want.  You could even send the menu definitions to the setupWorkspace() function instead of embedding it directly in the function.

    You can view a live demo of this series at: http://tblabonne.github.io/DynamicMenus/

    The complete source to the demo can be found at: http://github.com/tblabonne/DynamicMenus

    Categories: JavaScript

    Tags: Bootstrap, Durandal, Knockoutjs, KoLite

  • Revisiting War of Words

    Back in March 2010, I released a game called War of Words on the XBox 360 platform (Indie games).  This game was a hybrid RPG/Word game that used word spelling as the princaipal combat mechanism in the encounters.  It was very similar to Puzzle Quest in spirit, although the core game play mechanisms were quite different. 

    I had a lot of fun working on that game (and a lot of frustrations too).  I had hoped that it would have done better in the marketplace than it did, but Indie Games was not promoted by Microsoft much and I think the game also lacked some polish that would have made it more professional like an Arcade title.  For example, some graphics weren’t so great (as they were created by me) and the storyline was not very interesting (my fault again, as I am not a good writer either).  I do think the game was better than the average Indie game.  It currently is rated as 3.5/5 stars on the XBox marketplace with 232 votes (hardly any Indie games score over 3 stars, and many Arcade and AAA titles struggle to get over 4 stars). 

    Economics

    This game cost me about $600 USD to make.  About $250 of it was for a few hours of an artist’s time to draw the majority of the graphics.  Another $200 was spent on audio/music licensing.  I also had a domain name and website (which has been taken down) which cost $100 for a year.  I bought a few misc. things like video capture software to take video for promotions.

    As far as revenue, I can’t say exactly how much it made because the history of payment is long gone (most of the profits were made in the first 3 months of release and Microsoft does not keep more than about 18 months of history).  I started out selling the game for 400 points ($5 USD) but later dropped it to 240 points ($3 USD).  I make about 70% of that amount per game.  I do know that dropping the price increased the purchase to trial ratio to almost 25% which is quite excellent.  I think before the price drop, the ratio was between 10-12%, which is pretty good too. 

    I can tell you that I did not become rich with this game, obviously.  The real reason was downloads.  If people downloaded the game, you were pretty certain that at least 1 in 10 would buy it.  If 100,000 people downloaded it, you’d make a decent amount ($30,000 - $50,000).  But I didn’t get download numbers like that.  I pretty much blame this on the fact that Indie games is not a great service if you want to get noticed.  There’s too many bad games and demos that squeeze out good titles.  Also, you have to think of the audience and I think a word game on a console is probably not optimal.  If your game wasn’t about farting or beer drinking, it would not make it to the top of the list.  If you got on the top downloaded or top rated lists, you were going to actually get noticed in the dashboard because of the promotion you received.  If you didn’t get in these lists (I was in the recent released list for about 1-2 weeks and then gone forever), you got buried in the dashboard.  Frankly, I’m surprised that any one finds it today (there’s still a few purchases a week).  I know I didn’t really market it too much, but how was I supposed to do that exactly?

    I also could not translate the game to multiple languages (the fact that it is an English word game makes this doubly challenging than perhaps a simple shooter game).  I sold it in all XBox markets in the hopes that English speakers there would play it.  Foreign sales were pretty strong actually compared to what I thought.

    Sequel Plans

    I originally was very optimistic about a sequel even with low sales numbers.  I knew that I could take all of the money I made and the code/content I had and make a better sequel that would probably have made more money and taken less time to create.  But I lost interest.

    I basically quit Indie Games because I felt that the peer review concept was not optimal.  In fact, I was pretty much correct as Microsoft has basically dumped the technology behind Indie Games (XNA) and has focused instead on DirectX 11 for Windows 8 and whatever XBox One has.  Their stance on Indie publishing on the XBox One makes it likely that Indie Games won’t even run on it let alone Game Studio being ported to it.  You could tell something was up when guys like Shawn Hargreaves started to leave the team.

    I have a lot of design documents and ideas in my head for a sequel (including turning it into a turn-based game), but it will never happen with XNA, which is a real bummer to be honest.  I liked the platform and Game Studio was really cool.

    I toyed with putting it on Windows Phone 7 for a while and even had a very small prototype but in the end, it just didn’t feel right on a phone (without major changes to its design) and WP7 has no users and so a very small market.  I could try iOS, but it’s flooded and I don’t like Apple and I’m not versed in any of their programming languages/platforms.

    I think turning it into a HTML5 game would be interesting.  This type of game would be best for touch or mouse-clicking I think than using a controller.  But I’m pretty busy doing real paying work and being with family than doing this kind of thing.

    More to Come

    I’m planning on blogging about this game in more detail, especially with technical stuff like building directed acyclic word graphs (DAWGs), searching word graphs, building AIs that play games, character and RPG stats systems, etc.

    Categories: C#, Games

    Tags: War of Words

  • RavenDB Survival Tip #2: Simulating select count(*)

    A lot of the time a user will ask for a count of some business entity on a report so they can tell how many of something is happening.  With SQL, this is a very natural process with aggregate operations:

    select count(*) from Users where IsAdmin = true
    

     

    But with RavenDB, I found it difficult to wrap my mind around how you would do this with an Index.  Aggregate operations like this are implemented with map/reduce indexes.  Since the reduce step of the index needs to have the same output shape as the map, we can’t simply return a single numeric value as is the case with SELECT COUNT(*) in SQL.  We need to perform a LINQ group-by.  But in this case, I don’t really want to group by anything in a document, I just want a count. 

    After a little thinking and digging around, I found a solution.  Maybe this is obvious to most, but I found that if we simply group by a constant, we can get a single numeric value for that constant the represents the total count.

    Here’s a sample Index definition that demonstrates this concept.  In the Index, I am trying to find all User documents that qualify as admins (IsAdmin = true).

    public class Users_AdminCounts : AbstractIndexCreationTask<User, Users_AdminCounts.ReduceResult>
    {
        public class ReduceResult
        {
            public string Name { get; set; }
            public int Count { get; set; }
        }
    
        public Users_AdminCounts()
        {
            // the Name parameter to the reduce function is dummy
            // to get it to aggregate to one single value
            Map = users =>
                from user in users
                where user.IsAdmin = true
                select new { Name = "Total", Count = 1 };
    
            Reduce = results =>
                from result in results
                group result by result.Name
                into g
                select new { Name = g.Key, Count = g.Sum(x => x.Count) };
        }
    }
    

     

    When you run the query and get the result (ReduceResult), you will get just one single result and the Count property will contain the count aggregate you are looking for.

    Categories: RavenDB

    Tags: RavenDB, SQL

  • Building a Dynamic Application Menu with Durandal.js, Knockout, and Bootstrap (Pt. 2)

    In the previous post, I laid out a design for creating a dynamic menu system, specifically the object model that will be used in data binding.  In this post, we’ll look at the Knockout bindings and HTML structure to render the menus.

    This will be pretty straightforward as far as taking our object model and applying markup to it, however, the one complicated part is dealing with sub-menus.  Because menu items can themselves contain other menu items, we need the ability to render a menu within a menu and so on.  We can do this with Durandal’s compose binding handler for KO.  It allows recursive composition that is perfect for hierarchical things like menus.

    Here’s the contents of views/menu.html which is the view component for a single Menu rendering:

    <ul class="dropdown-menu" data-bind="foreach: items">
        <!-- ko if: $data.text !== undefined -->
        <li data-bind="css: { disabled: !command.canExecute(), 'dropdown-submenu': hasSubMenu }">
            <!-- ko ifnot: $data.hasSubMenu -->
            <a href="#" tabindex="-1" data-bind="command: command">
                <span data-bind="text: text"></span>
            </a>
            <!-- /ko -->
            <!-- ko if: $data.hasSubMenu -->
            <a tabindex="-1" data-bind="text: text"></a>
                <!-- ko compose: { view: 'views/menu.html', model: $data } -->
                <!-- /ko -->
            <!-- /ko -->
        </li>
        <!-- /ko -->
        <!-- ko if: $data.divider !== undefined -->
        <li class="divider"></li>
        <!-- /ko -->
    </ul>
    

     

    This markup is a bit complicated so let’s go through it:

    1. In Bootstrap, applying the dropdown-menu class to a <ul> will style it as a drop down menu container.  The data-bind here is also set to loop over each item in the Menu object.
    2. Within the <ul>, we need to decide if the MenuItem is a text-based menu item or a divider.  We do this by detecting if the divider property exists and/or there is text to display.  If the MenuItem is a divider, the special divider class is applied to a <li> and Bootstrap renders it as a thin gray line.
    3. If the MenuItem is actually a text-based item, we style it appropriately in its <li> element.  Notice the binding to command.canExecute().  In KoLite, if you provide a canExecute() function on a command (with is a computed observable), it can determine if the command can be executed or not.  In this case, we want the UI to gray-out or disable if the command cannot execute.  Once the command can execute, it will immediately synchronize the UI element to be a clickable command.
    4. Inside the <li>, we check to see if the MenuItem is a sub-menu or not.  If it is not, we create an <a> element as desired by Bootstrap to create the link to click on, binding the appropriate command to it.  We also bind the text in a <span> element inside the <a>.
    5. If the MenuItem does have a sub-menu, we assume that the MenuItem can’t be clickable, but instead, simply groups other elements.  In that case, we call upon the Durandal compose binding handler to recursively call this view sending the MenuItem as the view model to bind to in that context.

    Now, to render the top-level menu bar, in our main view we’d add the following markup (I’m using nav-pills in Bootstrap to represent the top-level menu items, but you don’t need to do that):

    <ul class="nav nav-pills menu-bar" data-bind="foreach: menus">
        <li class="dropdown">
            <a class="dropdown-toggle" href="#" data-toggle="dropdown" role="button" data-bind="text: text"></a>
            <!-- ko compose: { view: 'views/menu.html', model: $data } -->
            <!-- /ko -->
        </li>
    </ul>
    

    This assumes that the view model for the main view has a collection of Menu objects in an observableArray called menus.

    It renders a <li> element for each Menu giving it a dropdown class.  The <a> element will trigger Bootstrap to open the <ul> element that immediately follows the <a>.  That <ul> is generated by a compose binding calling onto the Menu view to render that one Menu and all of its children recursively.

    Categories: JavaScript

    Tags: Durandal, Knockoutjs, KoLite

  • Building a Dynamic Application Menu with Durandal.js, Knockout, and Bootstrap (Pt. 1)

    I’m going to do a longer series here about how to create a dynamic menu bar system with Durandal, Knockout, and Twitter Bootstrap.  This menu bar is going to emulate the traditional desktop application menu bar you find in apps (like the File, Edit, or View menus, for example).  The special thing here is that it will be 100% dynamic.  This will allow interesting scenarios such as dynamically altering the application menu when the application is in a different mode or allow something like plug-ins to alter the menu structure adding new commands.

    We will use the following libraries/frameworks to perform this task:

    • We’ll use Bootstrap to style the menus and get basic drop down menu support.  The menus in Bootstrap look very pretty and work very well using just one .js file for behavior and a little bit of markup.
    • We’ll use Durandal to structure the application and to take advantage of the composition engine it has.  I assume you know how to get a basic Durandal project up and running so I’m not going to spend a lot of time discussing how Durandal works.
    • We’ll use Knockout to do all of the data binding.  Our menu items will have observable properties in them so that menus will dynamically change when you change things about them in code.
    • We’ll also make use of KoLite by John Papa which provides a simple KO extension (the command) to abstract the idea of a UI command.  A single menu item will wrap a ko.command().  If a command does not allow execution, the corresponding menu item(s) will not allow it and will appear disabled.  Also, when clicking on a menu item, the command will execute.  This will all happen through data binding and will not

    For this first part, let’s build the JavaScript object model for the menu system.  A Menu object (defined in ui/menu.js in my project) represents one menu on a menu bar (such as a File menu).  It will contain zero or more MenuItems which are the individual menu selections in the menu.  There is also a special menu item that acts as a divider or separator.  These dividers draw thin lines between menu items to help visually group commands.  They are not clickable.

    Here’s the code for the MenuItem class (defined in ui/menuItem.js as a Durandal module):

    define(function (require) {
        var MenuItem = function (itemText, command, items) {
            this.text = ko.observable(itemText);
            this.command = command || ko.command({ execute: function () { } });
            this.items = ko.observableArray(items || []);
            this.hasSubMenu = ko.computed(function () {
                return this.items().length > 0;
            }, this);
        };
    
        MenuItem.prototype.addMenuItem = function (menuItem, position) {
            if (position) {
                this.items.splice(position, 0, menuItem);
            }
            else {
                this.items.push(menuItem);
            }
        };
    
        MenuItem.prototype.addDivider = function (position) {
            var item = { divider: true };
            if (position) {
                this.items.splice(position, 0, item);
            }
            else {
                this.items.push(item);
            }
        };
    
        return MenuItem;
    });
    

     

    A menu item takes a menu item text (the text to appear in the menu), an optional KoLite command, and an optional set of child sub-items.  The sub-items are used for when the menu item is actually a menu within a menu and will be rendered with a an arrow to the right of the menu item using Bootstrap.

    A Menu class also exists as a top-level container for MenuItems.  Think of this as the File menu or Edit menu.  It is defined in ui/menu.js as a Durandal module:

    define(function (require) {
        var MenuItem = require('ui/menuItem');
    
        var Menu = function (text, items) {
            this.text = ko.observable(text);
            this.items = ko.observableArray(items || []);
        };
    
        Menu.prototype.addMenuItem = function (menuItem, position) {
            if (position) {
                this.items.splice(position, 0, menuItem);
            }
            else {
                this.items.push(menuItem);
            }
    
            return menuItem;
        };
    
        return Menu;
    });
    

     

    This class takes the text of the menu item (“File”) and the collection of MenuItems to add to the menu.  You can call addMenuItem() to add a menu item after the initial creation of the menu.  The position parameter will add the menu in the specified position.  If you don’t specify a position, it will be added to the end of the menu.

    In the next part of the series, we’ll look at the HTML and KO data-bindings that will render the menus.

    Categories: JavaScript

    Tags: Bootstrap, Durandal, Knockoutjs, KoLite

  • Tree Traversals with JavaScript

    Let’s do this one more time – this time with JS.  Here is a constructor function for a generic tree node that has one parent and possibly N children:

    var TreeNode = function (data) {
        this.parent = data.parent || null;
        this.children = data.children || [];
    };
    
    TreeNode.prototype.isLeaf = function () {
        return this.children.length == 0;
    };
    
    TreeNode.prototype.isRoot = function () {
        return this.parent == null;
    };
    

     

    Here is how we’d traverse the tree with a depth-first search (note that I’m using the underscore.js library for the each() function – you could also use ES5’s Array.forEach() if you do not want to support older browsers – or use a polyfill):

    function visitDfs(node, func) {
        if (func) {
            func(node);
        }
    
        _.each(node.children, function (child) {
            visitDfs(child, func);
        });
    }

    Doing a breadth-first traversal is also straightforward thanks to JavaScript’s Array class and its queue/stack-like functionality:

    function visitBfs(node, func) {
        var q = [node];
        while (q.length > 0) {
            node = q.shift();
            if (func) {
                func(node);
            }
    
            _.each(node.children, function (child) {
                q.push(child);
            });
        }
    }
    

     

    Finally, let’s do something tangible with a depth-first traversal.  In the next code snippet, the prune() function will prune out nodes that are single children to their parents in order to collapse the tree into a simpler structure.  This will eliminate groupings of nodes that aren’t really grouping anything because their branching factor is 1:

    function prune(root) {
        visitDfs(root, function (node) {
            if (node.isRoot()) {
                return; // do not process roots
            }
            if (node.children.length == 1 && !node.children[0].isLeaf()) {
                var child = node.children[0],
                    index = _.indexOf(node.parent.children, node);
                node.parent.children[index] = child;
                child.parent = node.parent;
            }
        });
    }
    

     

    This code works by doing a DFS and calling a function on each node.  That function examines the node to see if it has exactly one child and that the one child node is not a leaf (we don’t want to prune out leaves or roots).  If it is, the child node is extracted out and assigned to the node’s parent’s children and then the child’s parent is reassigned to the node’s parent.  This effectively eliminates (prunes) the node out of the tree collapsing it into a simpler structure.

    Categories: JavaScript

  • Another Technique for Tree Traversals

    In the previous post, I talked about doing a DFS on a rooted tree using the C# foreach loop/iterator concept.  In this post, I will discuss a different technique that is more function-based.

    A common task on a tree is to traverse it in some defined order – pre-order, level-order, post-order, etc.  When we visit a node, we’d like to perform some action on it.  We can use delegates in C# (reference to a function) and lambdas to make this really compact and elegant:

    public static void VisitDfs(TreeNode node, Action<TreeNode> func)
    {
        if (func != null)
            func(node);
        foreach (TreeNode child in Children)
        {
            VisitDfs(child, func);
        }
    }
    

     

    If you pass in the root node to this method, you can call the function you send in on each node in that order.  You can apply this concept for other traversal patterns too:

    public static void VisitBfs(TreeNode node, Action<TreeNode> func)
    {
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(node);
        while (q.Count > 0) 
        {
            node = q.Dequeue();
            if (func != null)
                func(node);
            foreach (TreeNode child in Children)
            {
                q.Enqueue(child);
            }
        }
    }
    

     

    This performs a breadth-first traversal (also called a ‘level order’ traversal with trees), calling the specified function at each node visit.

    Here’s a sample usage of the DFS to count the number of leaves in a tree:

    public static int CountLeaves(TreeNode root)
    {
        int leafCount = 0;
        VisitDfs(root, node => {
            if (node.Children.Count == 0) {
                leafCount++;
            }
        });
    
        return leafCount;
    }
    

    Categories: C#

  • Performing a DFS over a Rooted Tree with a C# foreach Loop

    I’ve been working with trees a lot lately and one thing that occurs quite frequently in my problem space is the action of performing a depth-first search (DFS) or a 'pre-order traversal’.  In a DFS, you visit the root first and then search deeper into the tree visiting each node and then the node’s children.
     

    Since this is so common, I’d like a routine that helps me do that very simply.  What I’d really like to do is simply do a foreach loop over the tree and with each iteration pull out the next node that would satisfy a DFS.  This is where the C# yield keyword comes into play.

    The following snippet presents a TreeNode class which is just a generic node in a tree that has N children:

    public class TreeNode
    {
        public TreeNode()
        {
            Children = new List<TreeNode>();
        }
    
        public TreeNode Parent { get; set; }
        public List<TreeNode> Children { get; private set; }
        public bool IsLeaf { get { return Children.Count == 0; } }
        public bool IsRoot { get { return Parent == null; } }
    
        public IEnumerator<TreeNode> GetEnumerator()
        {
            yield return this;
            foreach (TreeNode child in Children)
            {
                IEnumerator<TreeNode> childEnumerator = child.GetEnumerator();
                while (childEnumerator.MoveNext())
                    yield return childEnumerator.Current;
            }
        }
    }
    

     

    Most of the functionality is in the GetEnumerator() method.  When a class in C# has a method called GetEnumerator() that returns a type IEnumerator or IEnumerator<T>, you’ll be able to use that type in a foreach loop.  Also notice that the type returned by my method does not return IEnumerator<TreeNode> but rather just TreeNode.  The C# compiler will fill in the proper details automatically.

    In order to do a DFS, we first visit the node itself by returning it (this) in a yield statement.  When the iterator executes the next loop, the GetEnumerator() method remembers the execution state of the method and picks up right where it left off.  At that point, we enter into a loop over the Children collection.  We basically repeat the enumerator process over this collection manually by doing a while loop where we exit the loop if no more children exist.  In the body of this while loop, we execute another return within a yield, returning each child node.

    To use this enumerator to perform a DFS, you’d foreach over the root node of your tree (I’m assuming a singly rooted-tree here):

    foreach (TreeNode node in root)
    {
      // perform action on node in DFS order here
    }
    

    Categories: C#

  • Using ASP.NET MVC and Shibboleth Authentication

    If you’re using Shibboleth as your resource authentication method, there’s a few things you need to do in order to use it effectively with ASP.NET MVC.

    The first thing to do is to configure routing correctly.  Shibboleth uses a special route against your website that is intercepted by the ISAPI filter that is part of the Shibboleth install on your web server.  However, in integrated pipeline mode, your application will receive these Shibboleth requests and won’t know what to do with them and issue a 404 not found.  The solution is to ignore the routes that Shibboleth uses and let them pass through to the Shibboleth system:

    routes.IgnoreRoute("Shibboleth.sso/{*pathInfo}");
    

     

    The ‘routes’ variable is a RouteCollection type passed to your RegisterRoutes() method in the RouteConfig.cs file of an MVC 4 project.  This ensures that the Shibboleth routes are never processed by your application.

    The second thing is to turn off all authentication for your web site.  Since Shibboleth’s single sign-on is going to handle protecting your resources, you will not need to configure any authentication in your web.config or in IIS.  Instead, you will configure it with your shibboleth2.xml file.

    Categories: ASP.NET MVC