Justin Rogers : Software Design

New posting on MSDN about script leak patterns and how to fix them for anyone that builds dynamic web apps.

Justin Rogers — Tue, 21 Jun 2005 00:46:00 GMT

Over here on the IE team we take leaks seriously. Extremely seriously. This is contrary to the popular opinion, but I'll let you make your own informed decisions. My new posting on MSDN is specifically designed to help you identify and fix several patterns of leaks. These range from your basic circular reference to your more complex (and more popular) closure based leak. Hopefully this new material can help you identify and exterminate all of the leaks in your code. If you have questions about the article feel free to post here or over on the IE team blog and I'll try to respond to any non-flaming responses ;-)

MSDN: Leak Patterns in IE

Solving big business problems in our little toolbox application. A use case for Project Distributor.

Justin Rogers — Sat, 06 Nov 2004 07:14:00 GMT

Project Distributor: Introduction to our distributed web service model
So Darren and I have put in about a month now on the Project Distributor website. We are starting to reach that critical point where the site is pretty cool, we have plenty of users, we are thinking about running out of the allowable bandwidth for the demo site, and all sorts of other things that tend to happen all at once. Now, there are some problems you can design yourself out of, and others that you really have to throw some money at. Our latest enhancements can be summed up in a short list.

Buy a domain name and start hosting in two places. Project Distributor.com should be up fairly soon to accompany MarkItUp.ASPXConnection.com
Have people host their own versions of the application. And that means a big source release is in the future. At this juncture risk fragmentation.
Design away fragmentation with a series of ingenious features that will make everyone want to use the application at hand.

I'm here to talk about the last two, since Darren already bought some additional hosting for us. The concept will be to release a fairly stable version of the application so that groups can host tools, code snippets and other source/binary releases for their teams to share. The application is very lightweight and easy to set-up, so it won't require a bunch of hand holding and configuration to get up and running initially. From our standpoint we solve a number of issues at this juncture. The most obvious problem is what we classify the Lutz Roeder use case. .NET Reflector is the key type of application we'd love to get hosted because it makes it a bit easier to find, not that Google does a bad job, we'd just like to get a bunch of tools in one place, with some features for feedback, new releases, and some cool client tools for publishing.

Now, Lutz would put his application up and he'd whack our bandwidth. He is the prime example of someone that should be hosting their own tools, but possibly using our interface. He doesn't have to, we haven't even asked him yet in fact, but if he decides to do so, then all the better for the web application moving forward. Users such as Lutz probably want a certain level of control over their own sites as well in terms of branding and controlling access. This will only come from hosting the application yourself (and maybe some other features we'll see later).

From a security standpoint many teams will also want to host their own servers. In this manner they get control over the hardware their sources and binaries are stored on. They can accept tools up to any maximum (instead of our imposed limits) and provide unlimited download bandwidth if they choose. Or they can take advantage of our gating mechanisms to make sure their server doesn't get overloaded with downloads and open their tools up to the public.

The only major problem from this source release is that the initial problem we were trying to solve, promoting the visibility of tools, starts to erode. You see, the more sites that host their own tools the harder it is to find the right site with the right tools. We are trying to solve this in a number of ways. The first is allowing users of a site to store bookmarks to other projects and external resources. This is only a temporary fix, because it still doesn't allow a mass search and categorization infrastructure required to truly promote the visibility of the tools being hosted. We have to come up with a solution that brings all of the sites, but we don't want to create just another portal or gateway site. That is boring. Now you have the background, so how will we solve the fragmentation issue?

Designing away Fragmentation
I won't lie to you, I've implemented this model several times, but have never had a project that was capable of really showing off the feature set we are about to talk about. The concept is to unify all of the sites, by allowing them to easily manage views of data from all of the sites combined. Each site owns their own content, maintains their own users, but in turn peers with other sites to obtain additional content.

Web services provide a dual feature set in this model. At the current level they allow us to generate really great client-side tools for managing, well, your tools! We have a drop-client target right now so you can drag and drop new releases to existing projects in just a few seconds. Some new tools for working with build systems to promote the source code up to the server are in the works. We natively integrate with your RSS reader and will have our own alert services in the drop client just in case you don't have one. There aren't any search or local caching features, but those are also planned for the drop client so you can background download new releases, just like Windows Update.

That doesn't solve fragmentation though, that just makes me realize how much work I have left to do. The second feature of web services lies in the ability for each site to aggregate data from the many other sites that are out there hosting the application. Remember, everything we make available at the service layer can also now be remoted. The more caching we put into the data layer, the more performant the entire process will be, and we can even tune the caching depending on whether the data layer is merging off-site contents or database contents.

Peer Sites
I'm sure there is another name out there somewhere, but for the past 2 years I've called these peer sites. Each instance of the project distributor will have a number of options allowing for adding peers that will be aggregated and added to the local collection while users traverse the site. The first step is to get the peer sites running in a read-only mode. And set up some really great options so the entire process can be controlled. This solves a number of use case scenarios for us including the following.

Fragmentation can be mitigated through proper configuration. If everyone aggregates 5 or 6 sites into their peers, then we have a huge network now of interconnected peers and users can pick and choose which one they use for purposes of searching the tool network.
Peer connections are unidirectional or bidirectional. Access is configurable. Teams can include tools from external sites while keeping their own tools completely private. They can exist behind a DMZ or a private network.
Users can host their own personal tool sites in the same manner as the team sites. They can configure statically which projects to make available even. In this way you can build a collection of personal tools that you love, and have the latest information automatically update on your machine for your perusal.

Peer sites solve plenty of visibility issues, but that is pretty much all they solve for now. We still want to enable all of the features available to the client tools. After all, the web service methods and proxy infrastructure is in place to do so much more.

Master Sites
Well, we want to solve another problem. That is where you edit your data. A master site is where the users, groups, projects, etc... are all hosted, but thankfully, you'll be able to log in through any site (assuming it is peered with your master site) and then edit your own projects and such. This is a remote principal context and is actually one of the cooler features associated with the peering functionality of project distributor. We'll be fully secure in our login and credentials region, but unfortunately we'll still be transferring data in open text in the short term. Maybe we'll fix that with enough push back.

Clone Sites
A clone site is where we empower a site to act on behalf of a master site. For me, my local project distributor is currently cloned to the main project distributor site. What does this mean? Right now it means I get all of the data from PD, and that users who trust my site can log-in to their project distributor accounts and cross edit data. Pretty nice if you ask me. It basically means you can fully host a project distributor installation and never, ever have to install a database server. Users can just act on behalf of a remote server.

Configuration
This isn't a super reusable model like some of those you read about in the popular software architecture books, and it probably accounts for why master/peer/clone sites don't exist very often. The considerations for every option are heavily customized to the problem being solved, and I'm sure we'll be making modifications or updating the configuration context for a while. Right now you can independently configure your primary server type, whether master or clone, whether or not users can use you for a pass-through authentication and edit server, whether or not web services are enabled so peers can enable unidirectional only communications, setting up asymmetric security credentials. Man, you name it and it is in there

For the peer section we have full and selective modes. A full peer pulls all of the data on the remote peer locally for display (in a delay caching manner, just like you'd expect, unless you set up a scheduled pull which is also possible). I expect most people to configure full peers because they really are really easy to set up and maintain. A selective peer is where you specify the groups/projects that you want to display. This is best for a user setting up their own personal toolbox who wants to select a couple of items from many different peers.

We have an extensively exhaustive configuration module already and we'll be continuously adding more to it. The concept is to easily modify your toolbox to your own designs without having to touch the code. If we haven't given you enough options to satisfy your need then we'll have to make something up, because I'm just about running out ;-)

These are the basics of the model ideas I have for project distributor. That doesn't mean Darren doesn't have other great ideas happening as well. He has some pretty extensive UI enhancements, but I'll let him talk about those. We even have another product idea that is kind of a bolt-on for project distributor, but that is probably a couple of months out putting it into next year. Unfortunately we have too many ideas for our own good right now. Better than not having any ideas I guess. I'll try to drop some code with some of the ideas above, that way you can get a look at how the entire system is implemented. I have some diagrams as well, but I'm far too tired right now to add the img tags to the HTML view.

Architecting your own cache. Speed, efficiency, memory consumption, AND it has to actually work?

Justin Rogers — Sat, 23 Oct 2004 22:53:00 GMT

For the Project Distributor application we want to implement some caching. We have a number of options that we can use for this process, including making use of the default ASP .NET caching, but since I had some spare time I figured I'd throw 30 minutes at writing my own cache. I'm looking at a number of techniques based on my performance knowledge and hopefully I've identified most of the common methods of running a cache. The first problem is allowing keyed entries and it can be solved in many ways.

Use a Hashtable or a NameValueCollection or any other key indexed collection that might suit your fancy.
Use something like a SortedArray that I've written about previously. These are fast and they work well for small numbers.
Use a tree or skip-list as noted by some other individuals.

I'll let the cat out of the bag. I've chosen the SortedArray because it really is fast until you reach an insanely large number of items. Because it is sorted, key lookups are a matter of doing a quick BinarySearch. Picking the collection is only half the problem. Next you have to decide how much additional data to store with your items so they can be properly collected. You at least need to store a last modified time, else you'll get into trouble quick. Remember cache items expire after a certain period of time in most cases (and more rarely at the occurence of an event).

If we store just the date, what does a recycling process look like? Well, we have to iterate through the entire collection and look at the dates to see if the items should be collected. This is fairly bogus and would take a large amount of time for us to accomplish. Another option would be to store an ordered list of last access times. Then the problem becomes that during each update we have to find the original item in that list, remove it, and add a new item to the end of the list with the new time. Darn, that hurts as well, but since it is ordered, and new items get appended to the end, the only management will be shrinking during a removal.

If we decide to store more data with the item we can do something else entirely. A version number that gets incremented on each access. You might ask what this accomplishes. Well, now rather than storing a collection of dates that must be managed we can store a queue of access information. Each access results in the item's key and the version number being placed in the queue. Now, during a recycle operation we can check the front of the queue, and then look up the associated item. If the version numbers are different, we continue, otherwise we do the date check. We'll cycle through the queue all the way up to the first matching version number where the date hasn't timed out. This isn't without it's trade-offs though, so I'll enumerate some of them.

The queue can grow as large as the number of accesses that occur during your cache expiration period.
Working through the queue requires a BinarySearch for each item. If the same item is being requested many times over it will have many entries into the queue and you'll spend time searching for the same item over and over.

Depending on your back-end those can be pretty hefty problems. What I'll point out here is that for a small queue of frequently accessed items, you won't use an LRU queue at all. You'll instead cycle through the entire queue for recycling. If you don't need items to preemptively remove themselves, you can wait until they are accessed beyond their timeout period and then remove them at that time. There are other structures you can add, such as an MRU queue where you keep the last N used items. Any items not in the MRU queue get removed from the system during a recycle.

How does a recycle work? Well, plenty of heuristic options for that as well.

Shortest period timeout. This option relies on finding the next item that will be removed and setting a timeout for it. One that item is removed you get the next shortest interval and set a timeout for that as well. Timeouts get allocated into buckets depending on how far in the future they reside to increase lookup performance.
Access timeouts work based on the user's use of the cache. If the user doesn't access the cache there aren't any timeouts and things sit. The more the user operates on the cache the more often the timeouts occur. This is simple enough using a basic byte. You can increment the byte each access and then recycle on a wrap-around to 0.
Cache barrier recycling. A cache barrier is when you allow only a specific number of items in the collection before you try to recycle. ASP .NET implements a mixture of cache barrier recycling (with priorities) and shortest period timeout. The benefits of cache barrier recycling are that you can throw out items until you come back under your barrier, irregardless of whether or not they've timed out. The bad thing here is that your application will be forced to fetch data more frequently.

A generic cache of any sort is actually harder to create than you might think. After all, the options that work at low loads don't scale to higher loads. The options at higher loads are very fast when there are lots of objects, but not as fast as a more specialized cache over smaller numbers of objects. In the end, the cache I'll be finalizing for storing objects will rely on a sorted array with binary search capabilities, a customized add method that handles version number consistency (write over top instead of add alongside), a customizable cache timeout (the only way for items to get removed), a linear search recycle method that upgrades to an LRU cache after a threshold, and retrieval timeouts just in case you want to turn cache recycling off.

An overview of the physical multiplayer borders in online gaming, with a focus on Poker.

Justin Rogers — Sat, 23 Oct 2004 14:53:00 GMT

This is a direct request from a reader related to some of my past Poker engine work, so if you want a .NET post, then catch me later. The primary focus of the question was the design and architecture that is instituded by the larger poker sites in order support multiple thousands of simultaneous users and games while still handling all of the more basic aspects of online gaming like account management, transactional betting, and chat. Rather than start by diving into that, let's first look at the real physical barriers to entering into a multiplayer gaming market with a piece of software.

The 2 user problem - Getting two users to play is the first hurdle. Here you are tackling the issues of getting your network communications working, really understanding the synchronization of multiple players on the server side, and basically running through the majority of the work to create a successful multiplayer game (assuming you only want to support a couple hundred users).
The several hundred user problem - There is a barrier, generally at the server level where several hundred users is almost impossible achieve. At this stage you are running into message routing issues, your CPU is getting bogged down, and you are stressing your hardware a bit. This is where you start to realize a couple of things. First, you can still double or triple your base by fixing the server, the message protocol, and performance tuning some more. We've discussed some heinously simple ways to compress cards for instance into 1 network packet along with a bunch of other information. The second thing you realize is that distribution and adding machines is also going to help, but at an expansive management cost and with synchronization problems built in that have to be handled between machines.
The several thousand user problem - If you are still working on one machine, which is possible, then you've hit a hard limit in socket and network performance. You have to start distributing at this point and/or buying special hardware. At this boundary you are most likely going to offload chat to a separate server, at least general chat, while still performing in-game chat directly through the game channel (game channel communication is fast generally and is why most games support party chat natively, but offload support for global chat to other software and/or servers). You've solved all of the distributed synchronization issues at this point, and you are able to add new servers easily when capacity rises.
The 50,000 user problem - The holy grail of network gaming, to get to 50,000 users. Very hard with MMPORG style applications, because the server clusters representing a game are really capped at their capacity near 2500-5000 users. That means they've been truly distributing and have at least 10 game worlds. Here you start to get fragmentation of your population and it is hard for people to find those they want to play with. At this point you have dedicated servers for varying levels of play and you've focused on specific servers for tournaments and competition. Solving the user connection problem is going to be difficult, but it will be the primary and possibly only goal at this stage (discounting bandwidth and throughput issues you are having with your ISP and them bitching about the cost of bandwidth going up when in fact the cost has steadily decreased. I love my ISP folks, they actually give me rebates when that happens.).

Lots of problems at every level. No reason not to tackle them though. In fact it isn't all that difficult to manage. Look at the MSN Online Gaming Zone as a great example. They've logically broken their entire site down into the concept of rooms. Once you've gotten into a room you are either sharing a server with some other rooms or you are on your own server. At this level players can logically choose opponents from those available and start a game. Each room has only 50 tables going at once and while these 50 tables probably don't represent a single server playing the game they could. Players are always running on a dedicated server and synchronization issues with the back-end are kept to a minimum. Basic security consistency checks can ensure there aren't dual-logins and that only one game server can update a players account at a time. Failures are easily assigned to particular servers and they can be brought offline and fixed quickly while games are occuring across the rest of the farm.

How do online poker sites solve this problem? They don't! They buy the software pre-canned in almost every circumstance. There are many reasons for this, but the most basic is being licensed to serve gambling content. Ever been to a casino and play the electronic poker games? Those are extensively tested to make sure their odds are consistent and then licensed for use. You are dealing with people's money so there has to be some oversight as to how the money is handled to ensure some level of security. Think of the gambling site like a brokerage, and you the player, are a stock trader. You'd be pretty scared if the bank's software wasn't licensed and checked to make sure your money couldn't leak elsewhere. You'd be even more frosty if your shares and/or payouts weren't properly reassigned back to your account because of some glitch in the system or maybe even a server crash.

Obviously the original sites produced some of their own software, but a burgeoning market is selling full blown poker engines that are already licensed and ready to go. The company gets a support license, and after the appropriate amount of marketing has hopefully reached the critical mass and is making money to move forward. Gambling is one of the few institutions where the site can actually start breaking even in a rather short time period, especially for sites that are not bent on massive growth, but instead supporting a steady and fixed population of users. After all, 3% of a $50k table is going to yield you just as much as 3% of several hundred casual gambling tables. Gives you a market to cater to if you just want to put a small server out there and still make decent cash by playing to those that want special services.

To wrap-up I'll give some architecture design guidelines that should help to overcome many of the boundaries. Many of these are common sense for the hardware gurus or those familiar with distributed processing, but you'd be surprised how easy they are to overlook when you are designing your system.

Have a connection management plan from the beginning. There are hard limits on connections and you have to either make sure you can add servers or support more connections through better hardware (probably expensive hardware). More servers is the easier option so design for that direction. If you can write a disconnected protocol and the overhead of reconnecting doesn't swamp you, then plan for that.
Seperate core services and extended services at the connection level. It should be easy to run lobby services (extended) tournament management services (extended) account management services (required but extended) and any others on their own hardware. Core services support the game and that means everything that has to go over the wire during play. Chat is an example of a core/extended service since you can easily add it to your table services, but at the same time you may get better options from offloading it to specialized chat services. Core services also use guaranteed protocols and require you build in lots of fail-safes and contingencies, whereas extended services (yeah, I know, the account manager) don't have to be well thought out. Chat can be run over UDP and doesn't need to be guaranteed and many other services can be run on generic web servers.
Logically break down the game process into modules. This is the most important for distributed play. You have to ensure that you can easily shell off a new table to a server that is capable of handling it. Remember the 2 user problem? Well during that problem you created a consistent engine. That engine could logically run anywhere, but most likely it ran within the context of a server. Either one of the users was the server or a specialized server existed somewhere else that they both connected to. The engine hosted by the server then, is your module for distribution. Note the game servers themselves will still host services, such as authentication, connection management, message routing, and account interaction.

Just those three considerations will get you well along the way. There are still many problems to solve, but hey, if you are making the big dollars and want me to give you some more hints, then share the wealth and we'll talk ;-) These problems used to be cutting edge research, but they are now well known domains with many interesting solutions. Most solutions at the higher marks are still very customized and rather than maintain the distributed model, many implementations try to squeeze the extra performance out of what they have. I don't have a problem with that, but it does kill the reusability of their solution just so they can support an extra few thousand users that could have been supported with an extra server. In many cases they don't have proper load balancing and didn't isolate the game modules for distribution. In others they have the problem that load balancing can be overcome by the user (almost every MMPORG has no say if every user shows up in the same zone). New games have overcome these issues (City of Heroes) with ingenious solutions that we either love or hate. Hopefully we'll see more of that modular approach with a focus on reusable and portable solutions.

Type identity for data is important. How do we refactor collections in the face of Whidbey?

Justin Rogers — Wed, 06 Oct 2004 08:27:00 GMT

The reality of component design is in the contractual agreements between different components. .NET has certainly stepped in and created an excellent cross component scheme to allow just about any code to interoperate with any other piece of code. In the face of this scheme developers have found that doing things at the truly abstract or generic level is often error prone or doesn't provide the appropriate level of performance. In doing so we often find that components are designed with the most specific types in mind in place of the less specific and more general interfaces that could have been in place.

Type Identity
When a method wants a piece of data there are many options for the exact signature or type the method might accept. A method might take a strongly typed array, it might take the more general Array. Then we have the more useful System.Collection classes, where you can take an IList, ICollection, ArrayList, CollectionBase, or a strongly typed collection based on CollectionBase. Beyond that we have System.Collections.Generic where new generic interfaces/classes are added as well. This is where type identity comes into play:

public void DoSomethingWithData(ArrayList foo);

The above method greatly reduces it's ability to consume data. If you want to consume an Array, you have to create an adapter over top of the array. If you want to consume a CollectionBase or generic collection, you also have to create an adapter. Thankfully ArrayList provided a method for consuming the IList interface, else things would get nasty pretty darn fast.

Ideally - All components use the interface methods for maximum compatibility. Where the components use specific types, those types should support an adapter that converts from the interface methods. All collections in turn implement the interfaces to allow easy use or conversion where necessary.
Reality - Components like to use very specific methods that often aren't available on the interfaces such as BinarySearch and Sort and so they use specific types for maximum functionality (foregoing interoperability). Adapters based on interfaces often have to throw on type specific methods that can't pass through the interface.

Leveraging Type Identity
Initially it becomes evident that you need to leverage type identity to make your new collections work well with other components. The natural progression is to being deriving types from ArrayList, CollectionBase, and List<T>... No matter how hard you try during this process, there are still three separate type identities involved and your ArrayList derived class will never operate in the place of a CollectionBase class or List<T> class.

Leveraging type identity instantly suffers from every design flaw (note: design flaw here is meant to define any design element that prohibits proper inheritance and that some of the design flaws were in fact design features for very specific CLR performance and security purposes) in the underlying type. Both ArrayList and CollectionBase hide their internal collection in a naive manner assuming inherited classes will provide their own storage. In turn inherited classes are forced to override every single method, since all of the base class methods operate on a private, and thus inaccessible storage element. The newer classes suffer an even more unfortunate fate in that all methods are non-virtual. Again, this is a design flaw/feature in that non-virtual methods are faster and at the same time not extensible.

Ideally - Leveraging type identity would be an effective method of creating new collection classes that target existing components using the base class. Base class APIs provide proper inheritance semantics building an inheritor trust relationship with data, functionality, and implementation. Components are built using extensibility guidelines that rely on generic interface identity coupled with casting to specific identity for faster operation (CLR Example: How does List(IEnumerable) avoid the costs of expanding the internal collection?)
Reality - Leveraging type identity is not always possible based on design inconsistencies. Base classes are built to support non-inherited operation for the common usage scenarios and fail to provide an extension mechanism for more advanced implementations. Existing design guidelines recommend inherently broken classes such as CollectionBase while the community continues to extend and user equally broken classes such as ArrayList.

Whidbey Options
The Whidbey options are to advance up to the System.Collections.Generic namespace and start using the interfaces and classes provided there. Currently there isn't a generic collection base of any sort and no design pattern for implementing your own custom collections. If ArrayList is to List<T> then XXX is to CollectionBase. You'll be hard pressed to fill in the blanks.

List<T> is an awesome class with a bunch of options. Definitely a stud if you ask me. The only problem is the lack of virtual methods so you can't change behavior. I've identified a number of methods that I'd like to see in previous posts, including a list mutator (Generic predicates are pretty powerful, but the FindAll implementation doesn't show it.) and a conditional ForEach method (Stacking the Predicate/Converter functions on top of the generic ForEach method...).

Apparently the current design goals for component developers on Whidbey will be to switch over to generic collections. That I would think is a given with the increased performance and attention to detail placed on the new classes. From a generic perspective we can continue to use the interfaces when designing our components, IList<T> and ICollection<T>, and leverage type identity on the List<T> class assuming we don't have a need to override ANY of the existing functionality. If you want custom algorithms then you can use the generic methods that take new delegates such as Predicate, Action, and Converter, as your first option. You can also continue stringing static methods off of helper classes. That is certainly an option. You can even override the List<T> and string methods off as long as you plan on routing through the List<T>'s public methods to make any collection changes and you are only looking for a new behavior, rather than change existing behavior.

At the end of the day, I wouldn't feel too bad about picking whatever collection option was easiest to implement in my configuration. Can't say that everyone feels the way I do though. If you are thinking about upgrading to strongly typed collections and like the features provided in CollectionBase then you might want to check out a first iteration of a generic version I've blown out. I didn't write this to be functionally equivalent to the non-generic CollectionBase, but instead to provide a starting point from which I'm going to produce a series of hinted collections (DWC.Collections.Generic.CollectionBase).

Optional parameter overloads in C# and cascading calls...

Justin Rogers — Sun, 03 Oct 2004 22:00:00 GMT

This is a performance versus design considerations post. You an weigh in either way and your input will be valuable.

Optional Parameter Overloads
C# implements optional parameters through overloads. Sometimes this imposes combinatorial design considerations, while other times it creates a deep stack. In either case, everyone agrees that many methods simply have default parameters and it is much easier to call them with their defaults than to figure out what the values should be. Let's take a simple example on the ArrayList in BinarySearch.

BinarySearch requires at the terminal method, start/end offsets, a value to search for, and a comparison routine used to determine relative equality. With those parameters you can affect every behavior of the method by changing one thing or the other, but a BinarySearch also has a default set of logic that you might assume, in which only the value being searched for matters. The start/end offsets are completely useless if you want to search the ENTIRE collection and the comparison routine isn't important unless you want explicit control over how the values are going to be examined. This leads to a couple of immediate overloads:

// Actual ArrayList overloads
BinarySearch(object value);
BinarySearch(object value, IComparer comparer);
BinarySearch(int start, int length, object value, IComparer comparer);

// Additional possibilities
BinarySearch(int start, int length, object value);
BinarySearch(int start, object value);
BinarySearch(int start, object value, IComparer comparer);

The additional possibilities are where the optional parameters start to fail. Since we have two integer parameters, users looking at the method description can't really understand what value the integer should take. You are also removing the concept of a range from the binary search by searching from some starting offset all the way to the end. This is a common routine in other methods, such as Substring, IndexOf, etc..., but not quite as common in BinarySearch. Managing all of those overloads is another problem altogether. After all, where do the various defaults come from?

Using Cascading Calls
A cascading call is a call routine where you start with the most basic method signature, find the closest matching signature with more parameters, and add defaults. That method may in turn do the same thing and so your methods cascade. In this way if you change the defaults in your more specific method, it updates the defaults for all of the less specific methods as well. Let's see this in action.

public int Foo(string bar) { return Foo(bar, defaultBaz); }
public int Foo(string bar, string baz) { return Foo(bar, baz, defaultBam); }
public int Foo(string bar, string baz, string bam) { return 1; }

Changing defaultBam has an effect on both itself and all methods that rely on it to fill n extra default parameters. This is a common API design allowing for changes to propagate the entire overload structure that reduces your focus to a method scope locality. Most likely you can safely work on the second overload to implement some performance optimization, change the way defaultBam is computed, or change variable names without ever touching the first overload. Once the changes are made everything just works and the less specific overloads all benefit from the changes that you made. This is definitely true of terminal methods in the call chain. Terminal methods are where most of the behavior resides. In our case our behavior is to return 1, but changing that to 2, instantly impacts and modifies the behavior of all our other methods.

Using Defaulted Constants
Often times you can replace cascading calls with defaulted constants. As you perform this operation, much of your code locality begins to break down unless you adhere to some rigid guidelines. Even then, changes to the terminal method signature mean much pain, since you'll now have to change all of the other methods to match the new signature. Defaulted constants in our sample would appear as:

// All overloads call the Terminal Method directly
public int Foo(string bar) { return Foo(bar, defaultBaz, defaultBam); }
public int Foo(string bar, string baz) { return Foo(bar, baz, defaultBam); }
public int Foo(string bar, string baz, string bam) { return 1; }

// Changing the constant name means changing in two places
public int Foo(string bar) { return Foo(bar, defaultBaz, defaultBammo); }
public int Foo(string bar, string baz) { return Foo(bar, baz, defaultBammo); }

// Changing the terminal means opening a can of beans
public int Foo(string bar) { return Foo(bar, defaultBaz, defaultBam, defaultBark); }
public int Foo(string bar, string baz) { return Foo(bar, baz, defaultBam, defaultBark); }
public int Foo(string bar, string baz, string bam) { return Foo(bar, baz, bam, defaultBark); }
public int Foo(string bar, string baz, string bam, string bark) { return 1; }

We obviously get more performance and a smaller stack out of the direct call methods, but changing the name of that constant meant hitting two methods. Well it is covered by refactoring right? Not much of a hit at all if the tool does the work for us. but what about changing the terminal. That meant not only adding a new method, but updating all three existing methods. That won't be covered by refactoring and it'll be left up to you.

The Decision!
Cascading calls in APIs are definitely a great tool, especially if there are a large number of parameters, perhaps 5-10 or even more. They introduce a level of flexibility that allows you to change the terminal, add or remove terminal functionality, and provide method locality for changes to default parameters. On the flip side they hurt your performance a bit, enough that you'd want to refactor them out of often used methods. They increase your stack frame size, so calling them from recursive functions might be a bit dangerous (especially if your recursive functions are designed to approach your stack ceiling). The BCL is a mixture of both cascading calls and direct calls depending on the APIs so there must be a design criterion that changes when you use one over the other? Or maybe it is just a personal developer decision?

Custom event subscription methods can help remove redundant code.

Justin Rogers — Wed, 22 Sep 2004 09:53:00 GMT

When working with a data-layer and trying to retrieve some list or collection for consumption by a number of different UI elements you run into the situation of having lots of redundant code. As an example, a common approach might have to utilize the following fields, properties, methods and events to cover all of the bases.

public class ComplexDataLayer {
    private bool dataAvailable = false;
    private ArrayList dataCollection = null;
    private readonly object loadingLock = new object();
    private bool loading = false;

    // Fire an event for consumers
    public event EventHandler DataLoaded;

    // So you can see if data is
    public bool DataAvailable { get { return dataAvailable; } }

    // Use a strongly-typed array instead
    public ArrayList DataCollection {
        get { return this.dataCollection; }
    }

    // Tell the darn thing to load
    public void RefreshDataAsync() {
        lock(loadingLock) { if ( loading ) { return; } loading = true; }

        // Schedule Async Loading
    }

    // Finish the data load
    private void RefreshDataAsyncCallback() {
        lock(loadingLock) {
            dataCollection = loadedData;
            dataAvailable = true;
            loading = false;
        }

        if ( DataLoaded != null )
            DataLoaded(this, EventArgs.Empty);
    }
}

Wow, that is a bunch of code to handle all of the potential code-paths. The pattern allows a newly loaded control to investigate and find if data is available. They would do this by checking DataAvailable and DataCollection. They can then load their collections. They still have to subscribe to the DataLoaded event in case someone refreshes the data source. Optionally, if the data wasn't already available they'll instead call RefreshDataAsync to get some data and wait for the event to be loaded. We can get rid of much of the above code by writing custom event subscription code. For now, let's see what the client consuming the above data source might look like.

private void Control_Loaded(object sender, EventArgs e) {
    DataLayer.DataLoaded += new EventHandler(this.UpdateList);
    if ( DataLayer.DataAvailable ) {
        UpdateList(DataLayer, EventArgs.Empty);
    } else {
        DataLayer.LoadDataAsync();
    }
}

private void UpdateList(object sender, EventArgs e) {
    ArrayList foo = DataLayer.DataCollection;
    if ( foo != null ) { ... }
}

That relays the basics of a system where data is available in more than one location depending on the current state of the application. You have to check properties like DataAvailable to get an intial set of data and hook events to get updates. It would be nice to have a single code-path that handled loading our data and getting refreshed data.

public class SimpleDataLayer {
    private EventHandler dataLoaded;
    private ArrayList dataCollection = null;
    private readonly object loadingLock = new object();
    private bool loading = false;
    private bool autoLoad = false;

    public event EventHandler DataLoaded {
        add {
            dataLoaded = (EventHandler) Delegate.Combine(dataLoaded, value);

            if ( dataCollection != null ) {
                if ( value != null )
                    value(this, EventArgs.Empty);
            } else if ( autoLoad ) {
                RefreshDataAsync();
            }
        }

        remove {
            dataLoaded = (EventHandler) Delegate.Remove(dataLoaded, value);
        }
    }

    public bool AutoLoadData { get { return autoLoad; } set { autoLoad = value; } }

    // Tell the darn thing to load
    public void RefreshDataAsync() {
        lock(loadingLock) { if ( loading ) { return; } loading = true; }

        // Schedule Async Loading
    }

    // Finish the data load
    private void RefreshDataAsyncCallback() {
        lock(loadingLock) {
            dataCollection = loadedData;
            dataAvailable = true;
            loading = false;
        }

        if ( DataLoaded != null )
            DataLoaded(this, EventArgs.Empty);
    }
}

I called it SimpleDataLayer, but it is actually slightly more complex, because we've now written the event subscription code by hand. Basically, we allow the user to simply add an event, and we'll immediately call that event if data is ready. In addition, a special setting on the data layer enables automatic fetching of data whenever someone subscribes making it great for automatic delay-loading. If the data layer is asynchronous then the UI gets asynchronous event callbacks for free. Just make sure you do your marshalling (also required in the original scenario).

private void Control_Loaded(object sender, EventArgs e) {
    // DataLayer.AutoLoad = true; // This should already be handled
    DataLayer.DataLoaded += new EventHandler(this.UpdateList);
}

private void UpdateList(object sender, EventArgs e) {
    if ( InvokeRequired ) { ... }
    ArrayList foo = DataLayer.DataCollection;
    if ( foo != null ) { ... }
}

So we make a slight trade-off between data layer complexity and UI complexity. I'd recommend putting the complexity into a single reusable location. The data layer can now be used to implement multiple user interfaces or in a console application with relative ease. This method of code-path reduction relies on the concepts of moving all data layer services out of the UI altogether. UI is often a hodge-podge of handlers that contain a mixture of UI state changing code and running functional code (behavior). For each behavior you can either properly encapsulate the code in a helper method, or make the mistake of rewriting it several times in several different places. In addition, you can make some heinous asynchronous mistakes.

This is only one of many models depending on your requirements. I don't consider this a final revision, and welcome any feedback users might have.

Card Games: Enhancing poker to a commercially viable engine.

Justin Rogers — Mon, 20 Sep 2004 11:58:00 GMT

Every wondered what would be involved in taking that basic game you might have in your archive of personal projects and create a commercial project out of it? Well, depending on how you feel about the information in this article, you'll either soon be looking for a publisher or content with having your own small pet project with no commercial stresses.

The game here is poker, a game I've covered a bit in the past, and a game that I think is an extremely different beast when you start to talk about producing a commercial product out of an existing pet project. There are plenty of parts to look at, but I've broken the diagram to the right down into three different categorizations.

On the left side you see an abstract. These are the basic commands that are occurring and would be the start of a design process. You'd think of each of these abstract concepts and design them with story boards, state diagrams, or out loud while you are in the shower (hopefully with some steam so you can jot down notes on the glass).

The middle shows you a kind of code-path that you might follow. These are never as complete as I'd like them to be, but this does a good job of defining the final section, or Discipline. These are the types of coding or design that are going to take place in order for the project to come together.

Why?
Why am I taking this path? Well, first it is nice to value and note the amount of work that existing games have gone through to achieve their final product. Second, I want to point out that just because you might be able to program a fixed card engine for a specific game, there are an astounding number of gotchas waiting in the wings when you start to take it to the next level. We'll primarily look at the complexity of customization and how it plays a major role in every aspect of the game engine.

Initialize
Every game starts with some sort of setup menu where you get to decide your options. This is literally the bane of existence for a game like cards because it amounts to the majority of the complexity of the programming. In larger games this complexity is minimized, but check your local options menu and see how few things you actually get to play with. You'll find most options are limited to basic boolean flags that don't have a large impact on how the game is played, but rather turn some basic feature on/off.

Initializing any game starts with some set of rules that can be changed along with some defaults. From the diagram, you'll see I've defined three different game types, and each game type would in turn allow you to set various options. These game types are going to be extremely important as the remainder of the game engine is defined. In order to define a series of game types you need a game designer. For poker, go out and buy a few books on popular rules for games. Even after you do that, let someone knowledgeable with the game tell you which games are similar and define your game types with respect to how similar each game is in terms of graphical arrangement, rules that affect play and winning conditions, turns and rounds, etc... Dissimilar games should be separate game types, but similar games could be sub-games of a single game type. A common name for this setup pattern is called a profile, especially if you give fixed sets of options names, but still allow a custom game where all of the options can be manipulated.

Once the rules are defined you need some container for holding all of the values to be passed on to the game engine. The various settings for different games can be very different and you'll find it very hard to come up with a generic setup object. Now matter how you cut this, when you are talking about a large number of rules, you'll either end up with specialized configuration objects on a per game type, or a single, very complex class with the ability to not only set values, but also have some way to turn them off. Bool gated values (a bool paired with a field) or Nullable types are a wise investment.

The same level of complexity is going to exist at the UI level, but you do have some options. Remember, that no matter how ugly the configuration object, you can give your user a much prettier picture. The use of a wizard can allow setting variables based on previous selections in a directed manner, while the use of game profiles can automatically set most of the values the player needs and only supply them with the UI to set optional values. Do you really need a separate UI programmer for this step? It would certainly help prevent the creation of an overly complex or unintuitive UI. Not to mention, this complexity cascades for the remainder of the game engine and results screens as each game parameter and setting needs to be obeyed when showing users their cards.

Play
With the settings object in place you are ready to roll. Is your game engine prepared to handle all of the incoming settings? Probably not. For instance, the winning conditions of the various games are going to have to be re-prioritized and manipulated based on the game being played. The number of various turns and how the turns advance is going to be drastically different between games. Something simple like turning on betting may add generic rounds in between the actual playing of the game.

To start the process, you are going to need a programmer to set up the basic game loop. Poker really isn't a game loop, but more a turn based type engine or finite state machine. The turn manager is going to be initialized based on whatever the game rules might be. This is yet another step where the game designer would be essential in making this entire process as elegant as possible by defining the various turns for you. As various turns are encountered the engine will be able to process user input. Depending on which players need to process that user input, you may be grabbing information from the network or an AI component.

While poker is simple enough that a network programmer might not be needed, you'll want someone fairly knowledgeable in network protocols to make you aware of all the various cheating scenarios and denial of service style attacks. Network IO should always be managed by some time-out period and creating a voting system to remove existing players can be quite a burden on top of the rest of the code that needs to be written. If money is on the line this process is even more important. An AI programmer might not be necessary either, especially if you are a great poker player, right? Wrong! The better you are at a given game the more likely an AI programmer will be extremely useful. Remember these guys are specialized in creating personality, erratic behavior, and managing statistics. This last quality is very important when working on a Poker game and it is nice to have an applied mathematician around when you have questions about how fair your game might be.

Notice how the game types affect not only the rules and turn manager, but also the graphical display. Think of the hundreds of different ways that cards can be displayed based on what type of game is being played. New games means new layout logic, and even worse, new user input routines. Each game has a specific UI that will maximize the play experience and creating that specific UI for say 10 games is a daunting task, let alone a few hundred of them. At some point you are going to have to put a script kiddy to work or have the UI designer work on a data-driven layout approach. Remember testing? Every single UI, especially data-driven UI needs to be thoroughly tested to make sure all of the hooks are in place. The last thing you need are input elements that don't do anything. If you planned for a data-driven UI from the very beginning, then you may have also applied it to the configuration UI and the following results UI.

Results
When working with the final product results are going to be insanely important or a bunch of filler. If you have separate games that don't maintain any state in between then you are talking about a basic results screen and the users won't even bother looking at it. If every hand is going to result in some passing of money then you better darn well get the results screen perfect because everyone is going to want to check the hands, make sure the game engine did the right thing, and make sure money was properly credited to each user's account.

The UI designer and game designer are both important at this stage so the results make sense. Results are just as dependent on rules as the rest of the application and you can imagine there are a number of things you need to show and a number of others you don't. The game designer will know exactly what should be in this final screen and your UI guy is going to make it happen.

Wrap-Up
There is so much stuff to think about to take a basic poker engine and make it a professional engine. To do it right, with all of the associated testing, UI, and graphics you'd want at least a 6 month cycle on this project. I think an 8 to 12 month cycle is more appropriate if you are going to have lots of rules, true network play, and some decent AI opponents. Removing any of the components will help drop some time off the schedule. Network play is an easy component to add, but a hard component to do right making it a key location for short-cuts. The AI is the same, with a basic AI being purposed in only a few hundred lines of code including all rules variations. Don't expect that AI to kick any decent player's butt, because it is likely to make some definite betting errors.

If you have any particular areas you are interested in seeing blown up with some actual code, drop a comment or two. Keep the areas you are interested in small enough that they might fit in a single posting. I'll also expand the design diagram to contain the additional levels of detail for those interested. You can head back through some of the older postings and see the network design diagrams to get an idea of how much detail the above diagram is leaving out.

Testing: Pair-wise, upper and lower boundings

Justin Rogers — Tue, 14 Sep 2004 10:08:00 GMT

You'd think there would be more math on this. Maybe I'm looking in the wrong places? Well, I wanted to try and formalize some boundings for sequences of features that have identical numbers of options.

f = number of features
n = number of options
n^2 = number of tests required to pair-wise match 2 or more features
Cn^2 = multiplier function for supporting increased numbers of features by adding tests

// Given a constant multipler give the maximum features supported
f = n+(C-1)n^2+1

// Given a number of features and their options, find out the max test boundings
max = ceil((f+1)/2n)n^2, f >=2
min = (ceil((f+1)/2n) - 1)n^2 + 1, f >= n^2

max = ceil((20+1)/2(10))10^2 = 2*100 = 200
min = (ceil((20+1)/2(10)) - 1)10^2 + 1 = 1*100 = 101

These methods are fairly fragile right now, definitely not the rigid generating functions I'd like to have. There is also the issue of large boundings, 101 to 200? What kind of bounding is that. Especially since we know that pairWise(20, 10) is somewhere around 180. pairWise(4, 2) is actually 5 while maxPair(4, 2) = 8 and minPair(4, 2) = 5... Naive attempts to limit pairs at 4, 2 would yield 6, but you can actually achieve 5 using a handy counting routine:

Name the features F1...F4... Remember that F1...F3 are already solved, so fix them in place.
Now, add F4 to existing line-items. As you add F4 features count each new pair generated with an existing feature.
- Example: F1-4, F2-2, F3-4
- Note: I actually ran through the possibilities so the above is a sample of pairWise(4,2) counting
At the end, you'll have what we call a deficit of pairings. F1 and F3 are both complete, they have 4 pairings, F2 doesn't.
For every 1 in deficit you have to make an extra combination.
- F1-4, F2-2, F3-4: 2 new combinations need to be made to solve F2's deficit
- F1-3, F2-3, F3-3: 1 new combination may solve all 3 deficits!

Now that we have a kind of counting routine, maybe it can be extended to geometrically produce optimum pairings. The core of a pairing is easy to generate and is necessary to procedurally generate the remaining combinations. Each core is fixed, while extra-core pairings can have a degree of freedom, similar to arrangements. You'd have to compute the various arrangements of a given test series if you plan on doing a best fit matching to existing tests to determine the minimal number of new tests that are going to be required to fulfill a pair-wise matrix or make recommendations on changing the focus of existing tests.

Testing: The pair-wise problem and fertile ground for improvement.

Justin Rogers — Tue, 14 Sep 2004 07:41:00 GMT

Apparently pair-wise testing is a pretty big thing. Hell, I'm not a tester, but I know I've used some of the same techniques writing my own tests. So I guess it was only a matter of time before I learned there was a name for what in the hell was going on. Because there are math problems in pair-wise testing it becomes something that I can really sink my teeth into. Most importantly, I'm really intrigued at the number of tools (fewer than I would expect), and that there is a single tool, usable over the web, that seems to be the master of all that others compare their own algorithms to. Here is the metric I've seen used:

20 features
10 options

High Combination = 235 (AllPairs), Low Combination = 180 (AETG)

Since the AETG guys apparently spearheaded the pattern, I'm guessing that gives them some advantage of time and resources into reducing the problem set... I think we should start with a smaller sample so we can visualize this pair testing... I think a 3 features, 3 options problem should be fine to start, and I like it because we can use a cube to show how it works, along with a tabular layout.

Feature 1	Feature 2	Feature 3
0	0	0
0	1	1
0	2	2
1	0	1
1	1	2
1	2	0
2	0	2
2	1	0
2	2	1

If you are curious about the cube, it has been rotated counter-clockwise a few degrees. Each tier represents an option of Feature 3 (y-axis), Feature 2 is oriented on the (z-axis) and Feature 1 is oriented on the (x-axis)... You can see an interesting pattern arise in both the table and the image, so I've placed both.

When working with the test cases there is always going to be a simple minimum bounding. The minimum bounding may not be possible, but it gives you a good idea of something approchable. Take the two features with the most options and multiply them together, you'll need to implement at least that many tests (3*3=9) in our case. For an interesting study, it also takes 9 tests in order to solve a 4 feature problem with 3 options per problem. Must be some math in there somewhere? For all square arrays you always wind up with n*n minimum test cases. You can then encode one additional feature that doesn't rotate with the rest of the matrix, but must have the same dimension or number of options.

Well, like I said, lots of room for improvement. This is just an introduction. I'll cover some interesting code samples a bit later and maybe work out a competitive algorithm for those AETG guys. If you like testing stick around for a couple of days. If you are waiting for my binomial coefficient posting, I'm still working on some way to spatially describe the process. Tisn't easy, but I'll get to it.

Terrarium: Did we do the right thing with the creature event model?

Justin Rogers — Sun, 05 Sep 2004 00:51:00 GMT

History
Why did we use the eventing model? Well, because it made sense that creatures only needed to spend processing time on things they were curious about. It seemed like it might make things easier because a basic creature could hook only one event while a more complex creature could hook many events. It was also a great demonstration of how you would build pluggable apps within the .NET Framework. However, at some point we broke the model a bit and added some virtual methods for serialization and deserialization of creature data.

At no point did we consider revisiting the model and changing it out for another model that might be more appropriate. The backwards compatibility mindset was always in place and we didn't want people to have to recode their creatures entirely as versions changed. It also became rather difficult to change the pattern away from the 10 or so events and large eventing infrastructure that was in place. With that in mind we kept the pattern.

Pattern
Our pattern was to simulate the concept of discrete inputs. Certain things may or may not happen in a given round, and other things may not happen for the entire life-time of the creature. No reason to check for these conditions every tick of the game loop. We created several separate events that comprised certain worldy actions such as attacking, defending, eating, etc... We also needed the creatures to be notified even if nothing of importance happened. This ensures the creature gets some time to process irregardless of the state of the world. These are the Load and Idle events. The Load happens before all other events are called, while the Idle happens after all other events are called. Load allows you to set things up and prepare for action, Idle lets you operate after world notifications have been propagated. Easy enough right?

Complexity
We definitely made some mistakes. First, there are a lot of events. Many creature authors are curious about which events they need and the order the events happen in. We have some documentation, but that doesn't help when you are first picking up the Terrarium for the first time. You want things to be as plain and simple as possible. Another level of complexity is added in that many developers wind up doing work in each event that may or may not overwrite work done in other events. You could blame this on the person writing the code, I rather blame it on the model and blame myself for allowing it.

Additionally there is the problem of storing information about discrete events having happened. The author could store the information, but we already store it within the base class. This isn't immediately obvious. I mean why would we store the information for you and give you an event that gives you the same information? It makes more sense for you to be notified that it is your turn to process and then allow you to investigate the state of the world.

What about time-slicing? Since we time-slice you, each event we call is taking a bit more of your time. Additionally it is harder to load balance your time across ten events than it would be across a single event. You have to store the amount of time spent in each of your events in order to get an accurate measure of how much time you used and how much you have left to process. For path-finding algorithms you may want to make the most effective use of your time by knowing about how much time you have left, even if the measure is somehow relative.

No Guarantees
We don't guarantee that your events will fire. In fact, we can skip you if you are taking too long, and the only way you know is by examining a special property that tells you for how long you were skipped. Any in process events continue processing, so while you aren't being notified, your move may complete or you may get teleported. If you are relying on the eventing model to keep your private state in check you are in for a rude awakening.

Single Cast Events
Having single-cast events isn't very useful in our model as you can tell from some of the downsides. In fact, in trying to demonstrate a plug-in model, we desperately failed. Normally, plug-ins will hook up to some global events that exist on the game engine and not exhibit a bunch of local events that are only consumed by the plug-in.

Fixing the Model
The model is quite easy to fix. Simply don't use events. There is no reason to use events in our model, rather with a base-class already in place we simply supply a single callback method, virtual of course, for the creature to implement all logic. This drastically reduces the complexity of the code required to implement the creature into a single entry point program. While you might think that authors couldn't code creatures that were nearly as functional as before, they actually have more time to operate now and have a less complex model to program against. As I'm making these changes to the source it simplifies other portions of the engine and helps refine the layout of the interfaces between the creature base, the engine, and the UI.

Working With What You Have
You have some options already as a creature developer. By writing a simple base class that manages all of the events for you and stores local information in a very minimalistic format, you can write your derived creatures to use the new local information from within a single method that is fired by the Idle event. At one point we had a work-item open to ship this class within OrganismBase itself. The idea would have been to have the Animal class for anyone interested in programming the old model, but also a new SingleCallAnimal supporting the new, simpler syntax.

NumericUpDown in Windows Forms and a small acceleration hack...

Justin Rogers — Fri, 03 Sep 2004 01:55:00 GMT

Since I've been chatting about acceleration, I figured I'd point out how and where these types of methods could be used to make your life simpler and how sometimes a basic hack will do. The first exercise is going to be taking a NumericUpDown and setting the maximum value to somewhere around 1 million. Next, run the app, press and hold the up button. What you'll notice is that the longer you hold it the faster the increment gets. The problem you'll quickly find is that reaching 1 million is going to be hard. You could mess with the interval, but then users won't be able to set values in between the interval without editing the text of the control directly.

How does the NumericUpDown achieve acceleraton? First, they use a timer while the user holds the mouse button down. The timer is set to 500 milliseconds initially and is then modified by 0.7 and truncated (well, they appear to multiply by 7 then divide by 10). As you can see the timer messages will get more and more frequent. Each time a message is processed the control is incremented or decremented by the current interval. This is pretty much just an acceleration hack. In fact, the fastest the control can move is the speed of a propagating timer event, which is something like once every 50ms and it will always move at some constant velocity once it achieves the maximum speed of a timer.

Could we make the control a bit more robust? Sure, we could fix the timer at something like a quarater of a second, and then run the physics to figure out how many spaces have been sped past. Our initial velocity is 1, since we'll update the control by at least once each time. Our acceleration might be 4items/s^2. The Windows Forms control gets up to speed pretty fast. In fact, it hits the 20 increment (1000 / 50) point around 1 and a half seconds. Our new acceleration function would hit 20 items per second after 5 seconds... That makes it a bit slower to start, but much faster later. The designer for the control would allow you to set the actual physics though and you could modify exactly how fast the control would go. For instance, the acceleration itself might be a function. You could even have the acceleration ramps geared towards how the user operates with the control. Given enough user input on the spinner and seeing how often the user has to correct or how long they have to depress a button to get a desired result you can try to optimize the entire process.

I also want to talk about another popular style of control that you often see on TV, but rarely get a chance to experience on the computer. The counting label is constantly used to graphically animate some score or value into existence. Before the control starts all the fields are 0'ed out of course. Then the control operates for some fixed period of time, or sometimes not, and eventually settles into a final result. There are plenty of hacky ways to do this:

Rotate all spinners simultaneously, stop each digit place on the appropriate digit. This is a reel approach and isn't a counter.
Add a fixed amount at each time step. This is the most popular and produces those 10-15 second waits when you get a bitchin score.
Scale the fixed amount to to the operation time. Another popular approach resulting in a fixed time to score.

If you really want to be cool, you have to use acceleration and deceleration. You want to haul butt to some point in the count-down and then you want to ease off and decelerate the final digits into place. You might set the acceleration period to something like 4 seconds, and the deceleration period to 2 seconds. The total 6 second animation would be very pleasing overall.

using System;

public class AccelerationModeler {
    private static void Main(string[] args) {
        int previous = 0;
        for(int i = 0; i < 25; i++) {
            int currentScore = GetScore(1000000, 4f, 2f, 0.25f * i);
            Console.WriteLine("Current: {0}, Delta: {1}", currentScore, currentScore - previous);
            previous = currentScore;
        }
    }

    private static int GetScore(int totalScore, float tAccel, float tDecel, float tCurrent) {
        // We want the acceleration period to cover a distance proportional to it's time.
        float accelDistance = totalScore * (tAccel / (tAccel + tDecel));
        float acceleration = (2*accelDistance)/(tAccel*tAccel);
        float finalVelocity = acceleration * tAccel;

        // Now, we need to slow down system
        float decelDistance = totalScore - accelDistance;
        float deceleration = -(finalVelocity / tDecel);

        if ( tCurrent > (tAccel + tDecel) ) {
            return totalScore;
        } else if ( tCurrent < tAccel ) {
            return (int) (0.5*acceleration*(tCurrent*tCurrent));
        } else {
            return (int) (accelDistance + (finalVelocity * (tCurrent - tAccel) + (0.5*deceleration*((tCurrent - tAccel)*(tCurrent - tAccel)))));
        }
    }
}

Math: A bi-weekly journal describing the use of math in solving programming problems

Justin Rogers — Thu, 12 Aug 2004 13:10:00 GMT

This is just an introduction to the series. Basically, I've been challenged to point out various ways that I use math in order to solve programming problems and create business solutions. Now, thinking back over the past week, I constantly use math, but normally this results in simple arithmetic, counting, and some basic usage of sets. That isn't really a crowning endorsement to go out and study complex maths though if in 20,000 lines of code written each week only grade school techniques are required.

Over the course of a week, the majority of the code that I write currently is for a number of game engines soon to be released on G4. Lately, I've been working on the children's section of the site, and teaching kids that are already good at games, why they are good at games is the goal. That is going to give me a large number of commonly played miniature games to examine using math. And I definitely mean a lot. Of course games use a lot of math. In fact the original assertion was to leave out anything to do with path finding and collision detection. I could have given about 50 more areas I should stray from.

Another place I tend to use a lot of mathematics is in working with UI. Everything dealing with UI is math based from the layout and sizing of controls to the counless uses of functional interpolation in rendering shapes and other features. I've been living in Pov-Ray as well, so I should be able to point out where math comes in handy for creating things that we'd normally think are quite simple.

The remainder of the series will be related to hodge-podge items. I'll definitely throw some of the voodoo that is performance in there. I also use math for regular expressions, even if it does just come down to counting, so I"ll probably hit on a few of those. If I actually accomplish anything in artificial intelligence that isn't game related I'll toss that in as well.

The only stipulation is that none of the things I write about are made up. I have to be actively working on actual projects. That won't be a problem I can assure you. I'll try and keep the postings short and to the point, and I'll make sure to include the actual math with some pointers to MathWorld so you can check everything out. Well, see you 3 to 4 days from now (or maybe sooner, not sure yet).

Describing the limits of the generic Deck previously created for the Poker application.

Justin Rogers — Sat, 17 Jul 2004 06:11:00 GMT

Jason Olson has some comments about the Poker Deck I developed and I am starting to agree with some of them. Not that the integrated Hand is bad, but more that the integrated Hand is not tightly integrated enough to be sufficiently useful. So what am I going to do about it? Well, I'm going to fix it darnit. Or better, yet not fix it quite yet, but explain the names a bit better. I'll start by taking a few sample definitions with respect to where cards are located in several games.

Poker

Initial Deck - 52 Cards - Cards are dealt with one hand per player
Hands - 5 Cards at a time in general - Cards can be discarded and new cards retrieved.
Discard Pile - A pile where all dealt cards that get discarded go, and after the Initial Deck is finished, Cards can be reshuffled into the Initial Deck

Solitaire

Initial Deck - 52 - ((7*8)/2) - or basically 52 - 28 where 28 is the initial set of cards in the 7 tiers
7 Tiers - This is where the game is played
Top of Deck - 1 Card that you can see, maybe three, depending on how the settings are laid out
Discard Pile - Cards that have been moved from the playable hand back to the pile.
4 Suit Stacks - Where you place all of the cards that will win you the game.

Magic the Gathering

Two Initial Decks - Ouch, does our deck fail at this point? Kind of, but I'll fix that.
1 Hand per player
1 Discard pile per player
Many Board Locations for placing cards

Now, all we need to do is define the appropriate definitions and everything works. What is a Deck? Well a deck is the initial set of cards. It is the source of cards. A deck in Poker is 52 cards, Solitaire, the same deck. What about Magic the Gathering? Well, the deck is the same, but it is comprised of cards from two players, so you logically have two decks, but from an abstract standpoint the deck is the set of all other decks. Using some set theory here isn't but so bad eh ;-)

What is a Hand? Well, a hand is a pile of cards. A hand holds onto cards, but it doesn't own them. That is the job of the deck. The deck controls the entire process of making sure all cards are properly initialized and then placed in their initial spots. The current Deck does this well, but there is some work left. Just as the Card definition is meant to be overriden and slightly changed, so is the Deck. With that in mind I'll be releasing a new Deck that offers a number of extra features and is consistent with this new model I've defined. The new process would be defined as follows:

Deck<StandardCard> deck = Deck<StandardCard>.CreateDeck(
    new HandInfo[] {
        new HandInfo(“Initial Deck“, 0, StandardCard.StandardDeck),
        new HandInfo(“Hands“, 0, null),
        new HandInfo(“Hands“, 1, null),
        new HandInfo(“Hands“, 2, null),
        new HandInfo(“Hands“, 3, null),
        new HandInfo(“Discard“, 0, null)
    }
);

What does the above do? Well, it creates a deck of cards with several named hands. One of the hands is the InitialDeck and it contains a set of StandardDeck cards. You can pass in more decks if you need to. The Hands are a single collection of hands, each indexed by a different number 0 through 3. Finally there is a Discard pile. All of the commands on Deck now manage the passage of items between hands. Remember, a Deck should be contained within an Engine, so that the user never has direct access to the Deck. The Deck still has the basics of internal protection, but it is truly protected by the Engine itself.

deck.Shuffle(“Initial Deck“, 0); // That'll handle your shuffling
deck.Deal(“InitialDeck“, 0, “Hands“, 0, 5); // Deal 5 cards to the first hand
deck.Deal(“InitialDeck“, 0, “Hands“, 1, 5); // Deal 5 cards to the second hand
deck.Transfer(”Hands”, 0, “Discard”, 0, 3); // Transfer card 3 from Hands 0 to Discard pile

I think just about everything is possible with this feature set and the deck is a bit cleaner. It can still protect it's children and hold their hands (terrible association). The diagram shows the process in action and is described as follows:

Deck is the init class. Everything happens through Deck.
Hands is an indexed property that is indexed by Name or by Name, Offset combo. By Name defaults to the 0th hand of that name or the default hand.
Named Hand is a collection of the various hands. Sometimes this will be a list of length 1, other times it will be a larger list.
Offset 0 is the default hand
Offset 1-N are the N additional offset hands in the named hand.

I am hoping this makes logical sense to everyone. I can easily show some games, including Solitaire and Poker being played using this new deck and rules.

Poker using the IM Protocol and Server as Client models... some more eye candy.

Justin Rogers — Fri, 16 Jul 2004 22:39:00 GMT

Well, with such a quick response from Jason, I got kind of excited and figured I'd throw out the IM based Server as Client model that I mentioned in the previous entry. This is a simplification protocol in that it doesn't rely on a server, and many of the features of voting players out are now delegate toa single client that is acting as the server. There is no match-making since all game-play is done on the invitation model which is simply easier.

How are we doing to take advantage of the invitation model? Well, for now, you can invite any of your messenger buddies. However, they won't respond with a yes/no, unless they are actually running the poker application, so give em a quick IM, tell them to get off their arse, and jump on the poker game. While playing poker, the IM layer is being used exclusively by the poker game itself. You can build in some chat features in case someone sends you a message while playing (see the IM Chat in yellow?) otherwise a simple busy message can be sent over each new conversation, followed by a prompt disconnect.

The IM Networking protocol is where the client's actually respond, as each responds in turn they are added to a game conversation. At this point, you can chat, and the network protocol can send any game related messages. The games will begin and the users can start playing. The actual protocol used for the game to operate is pretty basic, and will have to be covered in code later. For now, just realize a series of messages, basic text messages, are sent for poker commands, and that GUIDs are used to identify cards. To prevent any form of cheating adding some encryption on top of the text messages is easily done when doing private things like sending card information.

If you followed the RTC web-cast or want to view it online you can see how easy the network layer will be when we rely on an existing networking protocol to make things happen.

More to come, so stay tuned. I'm doing the Visio diagrams for now, but I'll be switching over to the whiteboard photocopies soon enough as I start doing the real design work.