Category Archives: Uncategorized

Web API Unit Tests: Get HttpResponseMessage from IHttpActionResult

This is a quick post to share a pattern for unit testing Web API methods where async Task<IHttpActionResult> is being used as the return type.

Download the example project

During a recent code review of some unit tests for a Web API project, a stylistic issue was picked up that was pretty minor but appeared through most of our controller tests. Here’s the kind of thing we were seeing:

// Unit test excerpt...
var result = await controller.GetSomethingAsync(123);
Assert.IsNotNull(result); // Check the result isn’t null
var someResult = result as OkNegotiatedContentResult<SomeModel>; // Cast as Ok<SomeModel>
Assert.IsNotNull(someResult); // Check the cast worked

There’s nothing technically wrong with this since it verifies that we’re getting back an expected result when we call GetSomethingAsync with a value of 123. What is doesn’t do so well is express the semantics of what’s being tested. Here’s the above code as a list of pseudo-code steps:

  • Get the result of the method when called with “123”
  • Check it returned something
  • Try to cast the result to the type we’d expect if everything went okay
  • Check the cast worked

It’s those last two steps that we didn’t like. As test-driven developers, we prefer small, discrete steps in tests that help us to see precisely what’s failed when things break; as Web API developers, we prefer to view our APIs in terms of HTTP rather than abstractions. What we wanted to test might better be written as:

  • Get the response from calling the method with “123”
  • Check we have a response
  • Check that it’s an HTTP 200/OK response
  • Check that the content is as we expect

While we could have changed the return types in all our API methods from IHttpActionResult to HttpResponseMessage to achieve this, we really just wanted a way to treat the existing return types as HTTP responses. This turns out not to be trivial, though, as the HTTP response is built in a pipeline as part of an HTTP request, along with its headers, status, etc. A little digging around in the ASP.NET MVC unit tests yielded some examples of how to do just enough mocking around the ApiController to build the HttpResponseMessages in a unit test environment. Furthermore, by presenting it all as a single extension method, any additional complexity in the unit tests is kept to a minimum.

Here’s what the previous code excerpt looks like using the new approach:

HttpResponseMessage response =
    await controller.WithMockedHttpRequest(c => c.GetSomethingAsync(123));
Assert.IsNotNull(response); // Check we have a response
Assert.AreEqual(HttpStatusCode.OK, response.StatusCode); // Check the HTTP status
SomeModel someModel;
Assert.IsTrue(response.TryGetContentValue(out someModel)); // Check the content

The new method, WithMockedHttpRequest, is an extension method defined as follows:

public static class TestExtensions
{
  /// <summary>
  /// Runs the controller action within a mocked HTTP context
  /// </summary>
  /// <typeparam name="T">The controller type</typeparam>
  /// <typeparam name="TReturn">The controller action return type</typeparam>
  /// <param name="controller"></param>
  /// <param name="func">The controller code to execute within a mocked HTTP context</param>
  /// <returns>The HttpResponseMessage containing the action result</returns>
  public static async Task<HttpResponseMessage> WithMockedHttpRequest<T, TReturn>(
    this T controller, Func<T, Task<TReturn>> func) where T : ApiController
  {
    // Build a mocked JSON request/response configuration
    MediaTypeFormatter expectedFormatter = new StubMediaTypeFormatter();
    MediaTypeHeaderValue expectedMediaType = new MediaTypeHeaderValue("text/json");
    ContentNegotiationResult negotiationResult = new ContentNegotiationResult(expectedFormatter, expectedMediaType);
    Mock<IContentNegotiator> contentNegotiator = new Mock<IContentNegotiator>();
contentNegotiator
      .Setup(n => n.Negotiate(It.IsAny<Type>(), It.IsAny<HttpRequestMessage>(), It.IsAny<IEnumerable<MediaTypeFormatter>>()))
      .Returns(negotiationResult);
   using (HttpConfiguration configuration = CreateConfiguration(new StubMediaTypeFormatter(), contentNegotiator.Object))
    {
      controller.Configuration = configuration;
      // Build a mocked request context from which to build the response
      using (HttpRequestMessage request = new HttpRequestMessage())
      {
        controller.Request = request;
        var actionResult = await func.Invoke(controller);
        // Create the response from the action result
        if (typeof (IHttpActionResult).IsAssignableFrom(typeof (TReturn)))
        {
          return await ((IHttpActionResult) actionResult).ExecuteAsync(CancellationToken.None);
        }
        else
        {
          return await Task.FromResult(request.CreateResponse(actionResult));
        }
      }
    }
  }

  private class StubMediaTypeFormatter : MediaTypeFormatter
  {
    public override bool CanReadType(Type type)
    {
      return true;
    }
    public override bool CanWriteType(Type type)
    {
      return true;
    }
  }

  private static HttpConfiguration CreateConfiguration(MediaTypeFormatter formatter, IContentNegotiator contentNegotiator)
  {
    HttpConfiguration configuration = new HttpConfiguration();
    configuration.Formatters.Clear();
    configuration.Formatters.Add(formatter);
    configuration.Services.Replace(typeof(IContentNegotiator), contentNegotiator);
    return configuration;
  }
}

The example is based in part on the ASP.NET MVC unit tests for ContentNegotiatedResult. Those tests are a good place to start if you want to get a feel for how the HTTP responses are built.

– Mike Clift

A Simple A* Path-Finding Example in C#

A few weeks back, I needed a path-finding solution for a little home project of mine, a game in which a character must move from location to location without walking through walls or other obstacles. A bit of research showed that an algorithm called A* (pronounced “A Star”) underpins most solutions to this problem—not just in games but also in other applications such as satellite navigation devices.

Browse or download the example project

Header Image

There must be thousands of pages on the Internet discussing this topic. The write-up I’ve used most frequently for guidance is Patrick Lester’s article, A* Pathfinding for Beginners. I’d recommend that article as a good place to get to grips with the fundamentals. The Wikipedia article, A* search algorithm, is also a helpful resource.

Before I start, take note that this is a really dumb, stripped-back, bare-bones implementation that won’t always give the best result. It’s very much a learning exercise for me, so it’s likely to be wrong in places. What I hope it will do is provide a working example that’s easy to follow and extend. There are much better example implementations around and I’ll include links to a couple of them at the bottom of the page.

First Steps

I’ll start with a grid of booleans, where false means the location is blocked (e.g. a wall) and true means it’s clear. Then I’ll identify two points on the grid: a start location and a finish location.

Here’s a representation of my sample grid. It’s 7×5 and includes an L-shaped wall with a one-node-wide gap along the bottom.

A simple grid with a start and end location
Figure 1: A simple grid with a start and end location

The above information will be used to initialise the path-finding class. I create a class called SearchParameters to be the container for this information.

public class SearchParameters
{
    public Point StartLocation { get; set; }
    public Point EndLocation { get; set; }
    public bool[,] Map { get; set; }
    ...
}
Note: I’m using the Point structure from the System.Drawing assembly to store grid coordinates.

Internally, the algorithm needs to hold a little more information about each node. It needs to keep a record of a few things as it goes along:

G: The length of the path from the start node to this node.
H: The straight-line distance from this node to the end node.
F: An estimate of the total distance if taking this route. It’s calculated simply using F = G + H.

Figure 2 gives a visual representation of how these values are calculated for the node immediately to the right of the start node. The distance along the path so far (G) is 1 step. Using Pythagoras’ theorem, the estimated distance from here to the end node (H) is 3 steps. Adding these two together gives the total estimated ‘cost’ in taking this path (F) of 4 steps.

Calculating G, H and F
Figure 2: Calculating F, G and H

The calculations are repeated for each adjacent node.

The 'total estimated cost' (F) is calculated for each adjacent node
Figure 3: The ‘total estimated cost’ (F) is calculated for each adjacent node

Now that the F-value for each node is known, it can be used to work out which path to try out first by putting all the options in a list and sorting them by F. Clearly, the node at grid location 2,2 with F=4 is the best bet.

Adjacent nodes sorted by F-value
Figure 4: The adjacent nodes are sorted in ascending order of F-value

This seems like a good place to introduce the Search(...) method that’s core to the implementation. The code listing below is incomplete but I’ll build upon it later. It shows the method taking currentNode as its starting point, getting a list of any adjacent nodes that are walkable, and then sorting the list by F-value before iterating over its contents.

private bool Search(Node currentNode)
{
    ...
    List<Node> nextNodes = GetAdjacentWalkableNodes(currentNode);
    nextNodes.Sort((node1, node2) => node1.F.CompareTo(node2.F));
    foreach (var nextNode in nextNodes)
    {
        ...
    }
    ...
}

So now the process is repeated using the node at location 2,2. However, there’s some more information that needs to be recorded about each node before moving on much further.

Any nodes that have been added to an ‘adjacent nodes’ list like the one above are marked as ‘Open’, i.e. they’re considered an open option for the search. However, as soon as a node becomes part of a path, it’s marked as ‘Closed’ and it remains closed even if that path ends up being discarded. Marking a node as closed means it won’t be considered again.

The search moves first to the node with the lowest F-value
Figure 5: The search moves first to the node with the lowest F-value

In addition, every ‘Open’ node is given a reference to its ‘Parent’ node so that the path to get there can be traced back to the start. The starting node doesn’t have a parent.

So now the node needs to store the following information:

G: The length of the path from the start node to this node.
H: The straight-line distance from this node to the end node.
F: Estimated total distance/cost.
Open/closed state: Can be one of three states: not tested yet; open; closed.
Parent node: The previous node in this path. Always null for the starting node.
Is walkable: Boolean value indicating whether the node can be used.
Location: Keep a record of this node’s location in order to calculate distance to other locations.

In code, it looks something like this:

public class Node
{
    public Point Location { get; private set; }
    public bool IsWalkable { get; set; }
    public float G { get; private set; }
    public float H { get; private set; }
    public float F { get { return this.G + this.H; } }
    public NodeState State { get; set; }
    public Node ParentNode { get { ... } set { ... } }
    ...
}

public enum NodeState { Untested, Open, Closed }

The next part shows where the ‘Open’ and ‘Closed’ node states comes into play. Just as before, the algorithm needs to calculate the G-, H- and F-values of each adjacent node. This time, though, the ‘Closed’ node at 1,2 is ignored, along with the non-walkable nodes to the right. This leaves four ‘Open’ nodes that have already had their G-, H- and F-values calculated on the basis that the node at 1,2 was their direct parent.

This seems like a reasonable point to show the implementation of GetAdjacentWalkableNodes(...). For each adjacent node, it filters out the ones that are outside the grid’s boundaries, that aren’t walkable, that are ‘Closed’, and that are already on an ‘Open’ list and can’t be reached more efficiently via the current route. The complete listing is as follows:

private List<Node> GetAdjacentWalkableNodes(Node fromNode)
{
    List<Node> walkableNodes = new List<Node>();
    IEnumerable<Point> nextLocations = GetAdjacentLocations(fromNode.Location);

    foreach (var location in nextLocations)
    {
        int x = location.X;
        int y = location.Y;

        // Stay within the grid's boundaries
        if (x < 0 || x >= this.width || y < 0 || y >= this.height)
            continue;

        Node node = this.nodes[x, y];
        // Ignore non-walkable nodes
        if (!node.IsWalkable)
            continue;

        // Ignore already-closed nodes
        if (node.State == NodeState.Closed)
            continue;

        // Already-open nodes are only added to the list if their G-value is lower going via this route.
        if (node.State == NodeState.Open)
        {
            float traversalCost = Node.GetTraversalCost(node.Location, node.ParentNode.Location);
            float gTemp = fromNode.G + traversalCost;
            if (gTemp < node.G)
            {
                node.ParentNode = fromNode;
                walkableNodes.Add(node);
            }
        }
        else
        {
            // If it's untested, set the parent and flag it as 'Open' for consideration
            node.ParentNode = fromNode;
            node.State = NodeState.Open;
            walkableNodes.Add(node);
        }
    }

    return walkableNodes;
}

Applying the above code to the example scenario, it performs a ‘what-if’ calculation to determine whether it’s more efficient to reach any of the adjacent nodes via location 2,2 than via their existing parent. Note that H doesn’t need to be recalculated.

The adjacent nodes can be reached more efficiently via a different route
Figure 6: The adjacent nodes can be reached more efficiently via a different route

It’s clear from these ‘what-if’ F-values that it’s less efficient to go via this node than via the starting node to reach any of the four locations accessible from 2,2.

Note: If it turns out to be more efficient to reach an Open node via the current node, the Open node’s parent is changed to the current node and the ‘what-if’ G- and F- values are applied to it. Unfortunately, this situation isn’t encountered in this walkthrough.

A dead end has been reached, so what now?

Searching Beyond the First Node

In the sample code, I’ve used a recursive Search(...) method. A dead end situation is identified by the absence of any nodes to move to from the current location. To put it another way, the search will only continue along a given path if there’s somewhere to go next. I’ll expand on the earlier code listing for Search(...).

private bool Search(Node currentNode)
{
    currentNode.State = NodeState.Closed;
    List<Node> nextNodes = GetAdjacentWalkableNodes(currentNode);
    nextNodes.Sort((node1, node2) => node1.F.CompareTo(node2.F));
    foreach (var nextNode in nextNodes)
    {
        ...
        if (Search(nextNode)) // Note: Recurses back into Search(Node)
            return true;
    }
    return false;
}

If a dead end is detected, Search(...) simply returns false so that control is returned to the next level up in the call stack, and that’s exactly what happens here.

Returning to the search from the starting node, the next choice could be either at location 2,1 or at location 2,3 since they both have the same F-value and share #2 position in the list of adjacent nodes. For brevity’s sake, let’s assume the algorithm chooses the node at 2,1 next.

Try the next-best option
Figure 7: Try the next-best option

The Open node at 1,1 is left alone since there’s no advantage going via this route. That leaves three possibilities, with the node at 3,0 achieving the lowest F-value.

Crossing the corner to location 3,0
Figure 8: Crossing the corner to location 3,0

Note: This implementation permits the corners of obstacles to be crossed as shown in Figure 8. While it’s arguably valid in this situation, it probably wouldn’t be considered valid if there were an obstacle at location 2,0 (to the lower-left of the blue line). It’s worth considering how to deal with corners and diagonal obstacles if implementing A*.

From 3,0 there’s only one possible next node: the one at 4,0.

Crossing to location 4,0
Figure 9: Crossing to location 4,0

Of the two next options, crossing the corner to 5,1 is the best.

Crossing the corner to location 5,1
Figure 10: Crossing the corner to location 5,1

There are now five options. Unsurprisingly, the node with the lowest F-value is also the finish node.

Reaching the finish node
Figure 11: Reaching the finish node

I’ll expand upon Search(...) one last time. The additional code checks whether the last node has been reached and returns true if it has. GetAdjacentWalkableNodes(...) has already set the parent node on the finish node, so nothing else needs to happen inside this method.

private bool Search(Node currentNode)
{
    currentNode.State = NodeState.Closed;
    List<Node> nextNodes = GetAdjacentWalkableNodes(currentNode);
    nextNodes.Sort((node1, node2) => node1.F.CompareTo(node2.F));
    foreach (var nextNode in nextNodes)
    {
        if (nextNode.Location == this.endNode.Location)
        {
            return true;
        }
        else
        {
            if (Search(nextNode)) // Note: Recurses back into Search(Node)
                return true;
        }
    }
    return false;
}

Back to the example scenario: the new condition is hit, so the method returns true. This brings the application all the way back up the call stack to where Search(...) was first called. Returning true lets the caller know that a path was found.

Compiling the Path

Building a list of the nodes that comprise the path is simple: starting at the finish node, follow the line of ancestors, adding the location of each to a new list, until a null parent is reached (i.e. the start node has been reached).

Follow successive parent nodes to build the list of locations along the path
Figure 12: Follow successive parent nodes to build the list of locations along the path

The result is a list of locations running backwards from the finish location to the start location. The list is reversed so that they can be returned in the correct order. It can all be wrapped up in a public method along these lines:

public List<Point> FindPath()
{
    List<Point> path = new List<Point>();
    bool success = Search(startNode);
    if (success)
    {
        Node node = this.endNode;
        while (node.ParentNode != null)
        {
            path.Add(node.Location);
            node = node.ParentNode;
        }
        path.Reverse();
    }
    return path;
}

If a path isn’t found, it just returns an empty list, otherwise it returns a list of locations starting with the first adjacent location to the starting point and ending with the finish point.

The sample project includes a console application that shows the algorithm being run across three different grids: one that’s completely open; one with the L-shaped obstacle used in this walkthrough, and; one in which a wall prevents a path from being found.

Screenshot of the sample application
Figure 13: Screenshot of the sample application

Final Notes

The goal of this blog post is to show the fundamentals of A* through a really simple C# implementation. As a result of trying to keep the code short and easy to follow, it’s a bit inefficient and it doesn’t produce particularly good routes. Improving its efficiency shouldn’t be too hard: use lazy instantiation when building the Node grid; use fields rather than properties (although, of course, this goes against general .NET design guidelines—see MSDN article Properties (C# Programming Guide)); the other articles linked from this page highlight other optimisations.

As for ways to find better routes, there are plenty of C# examples around that are far better and richer than this one. CastorTiu has a really nice demo solution on CodeProject, A* algorithm implementation in C#, that animates the search algorithm and allows the user to tweak a few settings.

I also spent a while examining Woong Gyu La‘s solution on CodeProject, EpPathFinding.cs- A Fast Path Finding Algorithm (Jump Point Search) in C# (grid-based). It has a nice, clear GUI and allows a few settings to be tweaked. I’d recommend taking at look.

– Mike Clift

t: @mclift