Microsoft has been not-so-subtly trying to phase out Windows XP for quite some time now. Who can blame them? XP is 9 years old. However, some of us are still stuck in 32-bit Windows XP because of insane hardware issues (don't ask, I don't even understand) or because we are Luddites. If you fall into either one of the preceding categories and you really want to develop games with XNA Game Studio 4.0, you probably have had a hell of a time trying to find the XNAGS4 installer. You know, the one without all that Windows Phone crap that you do not care about that requires Windows Vista or Windows 7. Or perhaps that's just how I feel.
Here is the (hopefully) permanent link to XNA Game Studio 4.0 that works with Windows XP:
http://www.microsoft.com/downloads/en/confirmation.aspx?FamilyID=9ac86eca-206f-4274-97f2-ef6c8b1f478f
If that link is somehow down, get XNA Game Studio 4.0 from me:
http://www.prism.gatech.edu/~tgockel3/blog/xnags40.exe
Hoo-ray!
11 October 2010
22 September 2010
A Fast, General A* in C# (Part 1)
As I work more on moving things into the Vapor .NET Client Library, sometimes I add functionality that I feel needs to be covered in a place which is more expressive than the XML comment system. For that, I turn here. I will be talking about Vapor.Graph.Searcher.AStar (snapshot as I write this).
Before I present the algorithm itself, I would like to mention two of the data structures that I use from the library which are not specific to A*. The first is the HashedSet<T>, which is almost identical in behavior to .NET's HashSet<T>, except that it is available on the .NET Compact Framework and does not allow for removing individual items, just clearing the whole set. I also use a structure called an OrderedQueue<T>, which is similar to a priority queue, except that the items themselves provide the ordering (through an IComparer<T>). It is backed by a min-heap, which means it is quite ideally suited for use in this algorithm.
Well, I have delayed quite long enough. Without further ado:
In general, this is a pretty good demonstration of just how general the type system of C#/.NET will allow you to go. Although that does not address the underlying question of: WHY? This started as a quick way to search for best paths on a 2D grid and worked quite nicely. Soon after, I needed to use a graph search algorithm for image unification. Instead of writing another implementation of A* (or any other graph-search algorithm), I decided to generalize the one I currently had. The ultimate reason why I want this to be as general as possible is because it is way easy to specialize a function for ease-of-use with wrapper functions, but almost impossible to generalize.
I do have a reason for every single type parameter!
TNode and TTransition
These are unavoidable type parameters. TNode is the type of nodes we are searching on and over, while TTransition is some transition which takes us from one TNode to another. There is no way to know what domain-specific types a user would want here.
TScore
This is the type of score value used in all cost calculations: it is the return type of a CostFunction<TNode, TScore> and HeuristicFunction<TNode, TScore>. Here's where my judgement gets questionable. Why would one need to do this? Aren't all scores just ints? Somebody might have ready that last statement an thought: What about float/double/long/MyOwnScoreType? The difference in effort of implementing one type of score and all types of scores (including those not yet made) was minimal. I do not care what type of score that you use, just that I can add it to another and tell if one is smaller than another (like concepts in C++).
TAdder
This is an IAdder<T> which takes two scores and adds them together. Why have the type parameter and not just pass an IAdder<T>? This allows the compiler to do some crazy optimizations for us. The contents of a IAdder<T>.Add probably look something like this:
Why aren't nodeEqualityComparer and scoreComparer done like this? In 99% of cases, people are going to be using EqualityComparer<T>.Default and Comparer<T>.Default for these parameters, which will force the system to fall back to the worst-case of making the virtual calls. Perhaps I will change it in the future, but right now the advantages are very few.
Wow, all this talk and I've only managed to justify the function signature!
Before I present the algorithm itself, I would like to mention two of the data structures that I use from the library which are not specific to A*. The first is the HashedSet<T>, which is almost identical in behavior to .NET's HashSet<T>, except that it is available on the .NET Compact Framework and does not allow for removing individual items, just clearing the whole set. I also use a structure called an OrderedQueue<T>, which is similar to a priority queue, except that the items themselves provide the ordering (through an IComparer<T>). It is backed by a min-heap, which means it is quite ideally suited for use in this algorithm.
Well, I have delayed quite long enough. Without further ado:
public static Path<TNode, TTransition> AStar<TNode, TTransition, TScore, TAdder>
(
TNode startNode,
TNode goalNode,
[NotNull] CostFunction<TNode, TScore> travelCost,
[NotNull] HeuristicFunction<TNode, TScore> estimateCost,
[NotNull] GenerateFunction<TNode, TTransition> nextGenerator,
[NotNull] TAdder scoreAdder,
[NotNull] IEqualityComparer<TNode> nodeEqualityComparer,
[NotNull] IComparer<TScore> scoreComparer
)
where TAdder : IAdder<TScore>
{
var searched = new HashedSet<TNode>(nodeEqualityComparer);
var toSearch = new OrderedQueue<AStarSearchNode<TNode, TTransition, TScore>>
(
new AStarSearchNodeComparer<TNode, TTransition, TScore, TScoreComparer>(scoreComparer)
);
{
var initCost = estimateCost(startNode, goalNode);
toSearch.Enqueue(AStarSearchNode.Create
(
Step.Create(startNode, default(TTransition)),
default(TScore),
initCost,
initCost,
null
));
}
while (!toSearch.IsEmpty)
{
var current = toSearch.Dequeue();
// skip if we've already searched this
if (searched.Contains(current.Node))
continue;
// check if this is the solution
if (nodeEqualityComparer.Equals(current.Node, goalNode))
return BuildPath(current);
searched.Add(current.Node);
foreach (var next in nextGenerator(current.Node))
{
var costForNext = scoreAdder.Add(current.CostToHere, travelCost(current.Node, next.Result));
var heuristic = estimateCost(next.Result, goalNode);
var estimated = scoreAdder.Add(costForNext, heuristic);
var nextNode = AStarSearchNode.Create
(
next,
costForNext,
estimated,
heuristic,
current
);
toSearch.Enqueue(nextNode);
}
}
return null;
}
What is with this insane amount of generality?
In general, this is a pretty good demonstration of just how general the type system of C#/.NET will allow you to go. Although that does not address the underlying question of: WHY? This started as a quick way to search for best paths on a 2D grid and worked quite nicely. Soon after, I needed to use a graph search algorithm for image unification. Instead of writing another implementation of A* (or any other graph-search algorithm), I decided to generalize the one I currently had. The ultimate reason why I want this to be as general as possible is because it is way easy to specialize a function for ease-of-use with wrapper functions, but almost impossible to generalize.
I do have a reason for every single type parameter!
TNode and TTransition
These are unavoidable type parameters. TNode is the type of nodes we are searching on and over, while TTransition is some transition which takes us from one TNode to another. There is no way to know what domain-specific types a user would want here.
TScore
This is the type of score value used in all cost calculations: it is the return type of a CostFunction<TNode, TScore> and HeuristicFunction<TNode, TScore>. Here's where my judgement gets questionable. Why would one need to do this? Aren't all scores just ints? Somebody might have ready that last statement an thought: What about float/double/long/MyOwnScoreType? The difference in effort of implementing one type of score and all types of scores (including those not yet made) was minimal. I do not care what type of score that you use, just that I can add it to another and tell if one is smaller than another (like concepts in C++).
TAdder
This is an IAdder<T> which takes two scores and adds them together. Why have the type parameter and not just pass an IAdder<T>? This allows the compiler to do some crazy optimizations for us. The contents of a IAdder<T>.Add probably look something like this:
public int Add(int x, int y)
{
return x + y;
}
This is an ideal candidate for inlining. However, if the compiler only knows that scoreAdder is an IAdder<int>, it must make a virtual call and, thus, cannot inline. Even if the compiler cannot inline the calls, we save one boxing conversion per call (which is good, because A* is something that is probably called a whole bunch of times).Why aren't nodeEqualityComparer and scoreComparer done like this? In 99% of cases, people are going to be using EqualityComparer<T>.Default and Comparer<T>.Default for these parameters, which will force the system to fall back to the worst-case of making the virtual calls. Perhaps I will change it in the future, but right now the advantages are very few.
Wow, all this talk and I've only managed to justify the function signature!
13 July 2010
Cloud Services and e-Commerce
A pretty big thing at work is the Payment Card Industry Data Security Standard, hereby referred to as PCI-DSS. It is a set of fairly strict security requirements that anybody wishing to do anything with processing credit cards must abide by. The standard can be summarized with simple rules like have a secure network, do not store things in plain text, use virus scanners and intrusion detection systems, etc.
Every year, the Payment Card Industry Security Standards Council (PCI-SSC) sends a Qualified Security Assessor (QSA) to assess the network for agreement lapses (ANAL). This costs the company millions of dollars on equipment like full-disk encryption, intrusion detection systems and tons of person-hours, but ultimately makes your credit card information safer. Aside from that, there is a fine on the order of $100,000 per month for not being compliant and there is a risk of losing the ability to run transactions at all (although given the volume of transactions that Fiserv does, I would imagine that number might be even larger).
The e-Commerice business has exploded in my lifetime, continues to do well in this economy and is not likely to ever stop growing. On a directly related note, more and more people are building web sites and selling things over the internet. Of these, very few meet PCI-DSS. It shows, too -- around 80% of unauthorized credit card transactions involve small merchants. Many small businesses do not bother with compliance and live with the fines because it is actually cheaper than trying to secure everything (and less effort).
And why should the bother trying to meet some ridiculous standard? It is so easy to hook up transaction processing to your little web server (violation), on the same network you give your employees WiFi with (at least 3 violations), store that information for future use (violation)...well, you get the idea. It is completely unreasonable to expect people to actually read the rules, much less understand them. Even if vendors made perfectly secure software (they don’t), you cannot expect every client to know how to set up an intrusion detection system or have in-depth knowledge of what a good security policy is. You can not even trust that the virus scanner is up-to-date.
Those are the kinds of e-Commerce businesses whose security would benefit the most to moving to a more secure infrastructure like Amazon EC2 or Google App Engine. Not only would the system be more secure, but there are tons of other benefits from maintainability to flexibility. If somebody had a little Python or Java module to drop into a Google App Engine web project, I can almost guarantee that the site would be more secure than if the developer had done the same thing on Bob's Server Farm. But, nobody writes generic cloud-based point-of-sale software. Why? Because it would be impossible for it to meet the PCI compliance standard.
The reason is section 12.8.2 of the PCI-DSS:
And 12.8.4:
In short, the cloud service provider must maintain their PCI stamp of approval and they must shoulder some of the responsibility. That rules out Amazon’s EC2: their service agreement specifies that they will take no responsibilities whatsoever. Google says the same thing about App Engine. Microsoft takes a similar stance with Windows Azure (I would link you, but they only offer the ToS in Word documents, which is completely brain-damaged). None of these cloud computing platforms is going to take on the liability of meeting the PCI specification and it is likely that they never will.
Does this mean that cloud computing and e-Commerce are destined to never meet? Not quite - there is always going to be Google Checkout and PayPal. Both of them have very customizable shopping cart implementations and are fully qualified to process credit card transactions. At that point, you are going to have to live with the fairly significant surcharge associated with those services.
Unfortunately, that appears to be the very limit of what is possible on any cloud system. The only possibility of moving away is for a developer to roll their own PayPal which resides on their own PCI-compliant infrastructure. The funny thing about doing something like that is that such a system would probably be less secure than running the same system on the public cloud. Essentially, one would be providing software as a service (SaaS) to a platform as a service (PaaS) on an infrastructure as a service (IaaS) (side note: aren't web acronyms fun?).
Another big issue with providing shopping cart functionality through any PayPal-like system is that it limits you to the web. This is a real shame because the internet has so much more potential. A piece of software like Steam could not exist on the cloud without some extremely clever single-sign on (SSO) hacking. Of course, once you are to the level of a desktop application, you are free to make multiple calls to places all over, but that is a really bad security practice.
My ultimate question is: Who will break, the PCI or a cloud service provider? I very much doubt that the PCI-SSC is going to quickly change their stance on anything, since, like any standards body, they are extremely slow to react (they do not address plain-old virtualization yet). Will one of the existing cloud service providers step up an become PCI-compliant? I highly doubt this as well.
My money is on the problems being solved by Google Checkout, PayPal or some new, but similar, service. I would love to see a web service-based alternative to those services. Combined with the emerging OAuth 2.0, developers could do whatever they want and have it all bundled up in a nice secure package. I really think there is a market for this -- it would open up these fun new elastic hosting solutions to all the Web 2.0 connectivity we have come to love. There is money to be made and it's all pretty exciting.
Every year, the Payment Card Industry Security Standards Council (PCI-SSC) sends a Qualified Security Assessor (QSA) to assess the network for agreement lapses (ANAL). This costs the company millions of dollars on equipment like full-disk encryption, intrusion detection systems and tons of person-hours, but ultimately makes your credit card information safer. Aside from that, there is a fine on the order of $100,000 per month for not being compliant and there is a risk of losing the ability to run transactions at all (although given the volume of transactions that Fiserv does, I would imagine that number might be even larger).
The e-Commerice business has exploded in my lifetime, continues to do well in this economy and is not likely to ever stop growing. On a directly related note, more and more people are building web sites and selling things over the internet. Of these, very few meet PCI-DSS. It shows, too -- around 80% of unauthorized credit card transactions involve small merchants. Many small businesses do not bother with compliance and live with the fines because it is actually cheaper than trying to secure everything (and less effort).
And why should the bother trying to meet some ridiculous standard? It is so easy to hook up transaction processing to your little web server (violation), on the same network you give your employees WiFi with (at least 3 violations), store that information for future use (violation)...well, you get the idea. It is completely unreasonable to expect people to actually read the rules, much less understand them. Even if vendors made perfectly secure software (they don’t), you cannot expect every client to know how to set up an intrusion detection system or have in-depth knowledge of what a good security policy is. You can not even trust that the virus scanner is up-to-date.
Those are the kinds of e-Commerce businesses whose security would benefit the most to moving to a more secure infrastructure like Amazon EC2 or Google App Engine. Not only would the system be more secure, but there are tons of other benefits from maintainability to flexibility. If somebody had a little Python or Java module to drop into a Google App Engine web project, I can almost guarantee that the site would be more secure than if the developer had done the same thing on Bob's Server Farm. But, nobody writes generic cloud-based point-of-sale software. Why? Because it would be impossible for it to meet the PCI compliance standard.
The reason is section 12.8.2 of the PCI-DSS:
Maintain a written agreement that includes an acknowledgement that the service providers are responsible for the security of cardholder data the service providers possess.
And 12.8.4:
Maintain a program to monitor service providers’ PCI-DSS compliance status.
In short, the cloud service provider must maintain their PCI stamp of approval and they must shoulder some of the responsibility. That rules out Amazon’s EC2: their service agreement specifies that they will take no responsibilities whatsoever. Google says the same thing about App Engine. Microsoft takes a similar stance with Windows Azure (I would link you, but they only offer the ToS in Word documents, which is completely brain-damaged). None of these cloud computing platforms is going to take on the liability of meeting the PCI specification and it is likely that they never will.
Does this mean that cloud computing and e-Commerce are destined to never meet? Not quite - there is always going to be Google Checkout and PayPal. Both of them have very customizable shopping cart implementations and are fully qualified to process credit card transactions. At that point, you are going to have to live with the fairly significant surcharge associated with those services.
Unfortunately, that appears to be the very limit of what is possible on any cloud system. The only possibility of moving away is for a developer to roll their own PayPal which resides on their own PCI-compliant infrastructure. The funny thing about doing something like that is that such a system would probably be less secure than running the same system on the public cloud. Essentially, one would be providing software as a service (SaaS) to a platform as a service (PaaS) on an infrastructure as a service (IaaS) (side note: aren't web acronyms fun?).
Another big issue with providing shopping cart functionality through any PayPal-like system is that it limits you to the web. This is a real shame because the internet has so much more potential. A piece of software like Steam could not exist on the cloud without some extremely clever single-sign on (SSO) hacking. Of course, once you are to the level of a desktop application, you are free to make multiple calls to places all over, but that is a really bad security practice.
My ultimate question is: Who will break, the PCI or a cloud service provider? I very much doubt that the PCI-SSC is going to quickly change their stance on anything, since, like any standards body, they are extremely slow to react (they do not address plain-old virtualization yet). Will one of the existing cloud service providers step up an become PCI-compliant? I highly doubt this as well.
My money is on the problems being solved by Google Checkout, PayPal or some new, but similar, service. I would love to see a web service-based alternative to those services. Combined with the emerging OAuth 2.0, developers could do whatever they want and have it all bundled up in a nice secure package. I really think there is a market for this -- it would open up these fun new elastic hosting solutions to all the Web 2.0 connectivity we have come to love. There is money to be made and it's all pretty exciting.
Subscribe to:
Comments (Atom)