The Importance of Reliable Algorithms

The study and usage of computer algorithms is one of the most important concepts for any computer programmer, and having a collection of well-written algorithms is essential for his toolkit. Modern algorithms are used to solve a wide variety of common problems, and their order of growths are all very well understood. Understanding and using algorithms can often be the difference between solving a problem and not solving it.

I recently took the time to put my common C# algorithms onto Github. This collection of algorithms is still growing, but each one of the algorithms in there has proven vital for me in a few projects. They are all based on algorithms in the book Algorithms, 4th Edition by Bob Sedgewick, ported to my software langauge of choice C#.

Inside this collection I have a few algorithms that I have made use of in recent game projects, structured in such a way to be extremely reusable.

    • AStar is an implementation of the well known A* algorithm for finding a path between two nodes on a network. To use it, have your nodes implement the IAStarNode interface and define the needed functions:
      • GetNeighbors() - returns an IEnumerable<AStarNode> of all neighbors accessible from this node.
      • EstimateDistance(IAStarNode end) - returns an estimated distance from this node to a target node. This is used for the A* best-case heuristic to find the end.
      • Distance(IAStarNode destination) - returns an actual distance from this node to the target node. Target node must be a neighbor.
    • PriorityQueue<TValue> is a generic PriorityQueue. Just make sure whatever TValue you use with it extends IComparable<TValue> so the comparer can work.
    • FordFulkerson, FlowNetwork and FlowEdge are all tools to run a Ford-Fulkerson algorithm on a network to identify the max-flow and min-cut. It's an odd algorithm, but when you need it, you need it. To use it, create a flow network with the number of nodes that your network will contain, add capacities to the flow network, and then pass the FlowNetwork into a new FordFulkerson.

I suppose it is obvious looking at these 3 algorithms that I first implemented that I have something in the works involving networks and pathing. It is a game idea that I've been kicking around lately but don't plan to get fully involved in for at least a few months. I came up with the idea while sitting onboard the M/V Klahowya in the Salish Sea on my honeymoon in October. The game revolves around how people and goods move from city to city, and these algorithms were very valuable in developing it.

The bonus is that I now have these algorithms written in a generic enough manner to be reused anytime I need. And that is the power of a well written algorithm.