Click here to Skip to main content
15,860,943 members
Articles / Artificial Intelligence

WPF: A* search

Rate me:
Please Sign up or sign in to vote.
4.98/5 (129 votes)
8 Nov 2009CPOL12 min read 288.5K   5.9K   245   109
An AI search application using the A* algorithm.

Contents

Introduction

I don't know how many of you know about my past, but I studied Artificial Intelligence and Computer Science (CSAI) for my degree. One of the assignments we had was to create a search over a cut down list of the London underground stations. At the time, I thought my textual search was ace, but I couldn't help but think it would be nice to have a go at that again using some nice UI code. Then low and behold, WPF came along, and I got into it and started writing articles in it, and forgot all about my CSAI days.

So time passes....zzzzzz

I went on holiday, happy days, holiday ends. Bummer, back to work.

So I thought I needed something fun to get myself back into work mode, and I thought, I know I'll have a go at the London underground tube agent again, this time making it highly graphical using WPF, of course.

Now I know, this is quite a niche article, and it is not that re-usable to anyone out there, but I can assure you if you want to learn some WPF, this is a good exemplar of what WPF can do, and how. So there is some merit in it.

Anyways, this article, as you can now probably imagine, is all about a London underground search algorithm. It is actually an A* like algorithm, where the search is guided by a known cost and a heuristic, which is some custom guidance factor.

There are some neat tricks in this article that I feel are good WPF practice, and also some XLINQ/LINQ snippets which you may or may not have used before.

So I hope there is enough interest in there for you, to carry on reading. I like it anyway.

What Does It Look Like Then, Eh?

Ah, now that is the nice part. I have to say, I, for one, am most pleased with how it looks. Here are a couple of screenshots. And here is the list of the highlights:

  • Panning
  • Zooming
  • Station connection tooltips
  • Hiding unwanted lines (to de-clutter the diagram)
  • Information bubble
  • Diagrammatic solution path visualization
  • Textual solution path description

When it first starts, the lines are drawn as shown here:

Image 1

When a solution path is found, it is also drawn on the diagram using a wider (hopefully) more visible brush, which you can see below. Also of note is that each station also has a nice tooltip which shows its own line connections.

Image 2

When a solution path is found, a new information button will be shown in the bottom right of the UI which the user can use.

Image 3

This information button allows the user to see a textual description of the solution path.

Image 4

When a solution path is found, it is also possible for the user to hide lines that are not part of the solution path, which is achieved by using a context menu (right click) which will show the lines popup (as seen below), from where the user can toggle the visibility of any line that is allowed to be toggled (basically not part of the solution path). The lines that are part of the solution path will be disabled, so the user will not be able to toggle them.

Image 5

What Does It Do And How Does It Do It?

In the next sections, I will cover how all the individual parts work together to form a whole app.

Loading Data

So obviously, one of the first things that needs to happen is that we need to load some data. The data is actually split into two parts:

  • Station geographical coordinates: which are stored in a CSV file called "StationLocations.csv". This information was found at http://www.doogal.co.uk/london_stations.php.
  • Line connections: which I pain stakingly hand crafted myself in an XML file called "StationConnections.xml".

In order to load this data, these two files are embedded as resources and read out using different techniques. The reading of the initial data is inside a new worker item in the ThreadPool, which allows the UI to remain responsive while the data is loading, even though there is not much the UI or user can do until the data is loaded. Still it's good practice.

So how is the data loaded? Well, we enqueue our worker like this, where this is happening in a specialized Canvas control called TubeStationsCanvas, which is located inside another called DiagramViewer, which in turn is inside the MainWindow which has a ViewModel called PlannerViewModel set as its DataContext. The PlannerViewModel is the central backbone object of the application. The PlannerViewModel stores a Dictionary<String,StationViewModel>. As such, most other controls within the app will need to interact with the PlannerViewModel at some stage. This is sometimes achieved using direct XAML Binding, or in some other cases, is realized as shown below, where we get the current Window and get its DataContext which is cast to a PlannerViewModel.

C#
if (System.ComponentModel.DesignerProperties.GetIsInDesignMode(this))
    return;

vm = (PlannerViewModel)Window.GetWindow(this).DataContext;

ThreadPool.QueueUserWorkItem((stateObject) =>
{
    #region Read in stations
    ......
    ......

    #endregion

    #region Setup start stations
    ......
    ......
    #endregion

    #region Setup connections
    ......
    ......
    #endregion

    #region Update UI
    ......
    ......
    #endregion


}, vm);

Where the state object being passed to the worker is an instance of the main PlannerViewModel that is being used by the MainWindow DataContext. The PlannerViewModel is the top level ViewModel that coordinates all user actions.

Anyway, getting back to how the data is loaded, the stations themselves are loaded by reading the embedded resource stream for the "StationLocations.csv" file. It can also be seen below that the read in coordinates are scaled against the TubeStationsCanvas width and height to allow the stations to be positioned correctly. Basically, what happens is that for each station read in from the CSV file, a new StationViewModel is added to the Dictionary<String,StationViewModel> in the PlannerViewModel. Then, a new StationControl is created and has its DataContext set to the StationViewModel which was added to the Dictionary<String,StationViewModel> in the PlannerViewModel. And then the StationControl is positioned within the TubeStationsCanvas using some DPs.

C#
vm.IsBusy = true;
vm.IsBusyText = "Loading Stations";

Assembly assembly = Assembly.GetExecutingAssembly();
using (
    TextReader textReader =
        new StreamReader(assembly.GetManifestResourceStream
        ("TubePlanner.Data.StationLocations.csv")))
{
    String line = textReader.ReadLine();
    while (line != null)
    {
        String[] parts = line.Split(',');
        vm.Stations.Add(parts[0].Trim(), 
        new StationViewModel(parts[0].Trim(), 
        parts[1].Trim(),
            Int32.Parse(parts[2]), 
        Int32.Parse(parts[3]), 
        parts[4].Trim()));
        line = textReader.ReadLine();

    }
}

Decimal factorX = maxX - minX;
Decimal factorY = maxY - minY;

this.Dispatcher.InvokeIfRequired(() =>
{
    Double left;
    Double bottom;
    foreach (var station in vm.Stations.Values)
    {
        StationControl sc = new StationControl();
        left = this.Width * 
            (station.XPos - minX) / (maxX - minX); 

        bottom = this.Height * 
            (station.YPos - minY) / (maxY - minY);

        left = left > (this.Width - sc.Width)
                                  ? left - (sc.Width)
                                  : left;
        sc.SetValue(Canvas.LeftProperty, left);

        bottom = bottom > (this.Height - sc.Height)
                                  ? bottom - (sc.Height)
                                  : bottom;
        sc.SetValue(Canvas.BottomProperty, bottom);

        station.CentrePointOnDiagramPosition =
            new Point(left + sc.Width / 2,
                      (this.Height - bottom) - (sc.Height / 2));
        //set DataContext
        sc.DataContext = station;

        //add it to Canvas
        this.Children.Add(sc);
    }
});

And the station connections are read in as follows using some XLINQ over the embedded resource stream for the "StationConnections.xml" file. What happens is that the station read in from the XML file is retrieved from the Dictionary<String,StationViewModel> in the PlannerViewModel, and then the retrieved StationViewModel has its connections added to for the currently read line from the XML file. This is repeated for all read in lines and the stations on the read in lines.

C#
XElement xmlRoot = XElement.Load("Data/StationConnections.xml");
IEnumerable<XElement> lines = xmlRoot.Descendants("Line");

//For each Line get the connections
foreach (var line in lines)
{
    Line isOnLine = (Line)Enum.Parse(typeof(Line), 
        line.Attribute("Name").Value);

    //now fetch the Connections for all the Stations on the Line
    foreach (var lineStation in line.Elements())
    {
        //Fetch station based on it's name
        StationViewModel currentStation =
            vm.Stations[lineStation.Attribute("Name").Value];

        //Setup Line for station
        if (!currentStation.Lines.Contains(isOnLine))
            currentStation.Lines.Add(isOnLine);

        //Setup Connects to, by fetching the Connecting Station
        //and adding it to the currentStations connections
        StationViewModel connectingStation =
            vm.Stations[lineStation.Attribute("ConnectsTo").Value];

        if (!connectingStation.Lines.Contains(isOnLine))
            connectingStation.Lines.Add(isOnLine);

        currentStation.Connections.Add(
            new Connection(connectingStation, isOnLine));
    }
}

Drawing the Lines

As I just mentioned, there is a specialized Canvas control called TubeStationsCanvas whose job it is to render the station connections and the search solution path. We just covered how the stations are actually loaded in the first place, so how do the connections get drawn? Well, the trick is to know about what the start stations are. This is also done in the TubeStationsCanvas prior to attempting to render any connections. Let's consider one line as an example, say Jubilee, and look at how that works.

First, we set up a start station for the line in the TubeStationsCanvas as follows:

C#
List<StationViewModel> jublieeStarts = new List<StationViewModel>();
jublieeStarts.Add(vm.Stations["Stanmore"]);
startStationDict.Add(Line.Jubilee, jublieeStarts);

By doing this, it allows us to grab the start of a line, and from there, grab all the connections using a bit of LINQ.

Here is an example for the Jubilee line; again, this is all done in the TubeStationsCanvas. In this case, it is using an override of the void OnRender(DrawingContext dc), which exposes a DrawingContext parameter (think OnPaint() in WinForms) which allows us to well, er.., draw stuff.

C#
protected override void OnRender(DrawingContext dc)
{
    base.OnRender(dc);

    try
    {
        if (isDataReadyToBeRendered && vm != null)
        {
         .....
         .....
         .....

            //Jubilee line
            if (vm.JubileeRequestedVisibility)
            {
                var jublieeStartStations = startStationDict[Line.Jubilee];
                DrawLines(dc, Line.Jubilee, Brushes.Silver, jublieeStartStations);
            }
        
         .....
         .....
         .....

        }
    }
    catch (Exception ex)
    {
        messager.ShowError("There was a problem setting up the Stations / Lines");
    }
}

It can be seen that this makes use of a method called DrawLines(), so let's continue our drawing journey.

C#
private void DrawLines(DrawingContext dc, Line theLine,
        SolidColorBrush brush, IEnumerable<StationViewModel> stations)
{
    foreach (var connectedStation in stations)
    {
        DrawConnectionsForLine(theLine, dc, brush, connectedStation);
    }
}

And this in turn calls the DrawConnectionsForLine() method, which is shown below:

C#
private void DrawConnectionsForLine(Line theLine, DrawingContext dc,
    SolidColorBrush brush, StationViewModel startStation)
{
    Pen pen = new Pen(brush, 25);
    pen.EndLineCap = PenLineCap.Round;
    pen.DashCap = PenLineCap.Round;
    pen.LineJoin = PenLineJoin.Round;
    pen.StartLineCap = PenLineCap.Round;
    pen.MiterLimit = 8;

    var connections = (from x in startStation.Connections
                       where x.Line == theLine
                       select x);

    foreach (var connection in connections)
    {
        dc.DrawLine(pen,
            startStation.CentrePointOnDiagramPosition,
            connection.Station.CentrePointOnDiagramPosition);
    }

    foreach (var connection in connections)
        DrawConnectionsForLine(theLine, dc, brush, connection.Station);

}

It can be seen that the DrawConnectionsForLine() method is called recursively, ensuring all connections are drawn.

That is how the connection drawing is done for all lines.

Panning the Diagram

As I stated at the start of the article, the diagramming component supports panning. This is realized much easier than one would think. It's basically all down to a specialized ScrollViewer called PanningScrollViewer, which contains the TubeStationsCanvas. The entire code for the PanningScrollViewer is as shown below:

C#
/// <summary>
/// A panning scrollviewer
/// </summary>
public class PanningScrollViewer : ScrollViewer
{
    #region Data
    // Used when manually scrolling
    private Point scrollStartPoint;
    private Point scrollStartOffset;

    #endregion

    #region Mouse Events
    protected override void OnPreviewMouseDown(MouseButtonEventArgs e)
    {
        if (IsMouseOver)
        {
            // Save starting point, used later when determining how much to scroll.
            scrollStartPoint = e.GetPosition(this);
            scrollStartOffset.X = HorizontalOffset;
            scrollStartOffset.Y = VerticalOffset;

            // Update the cursor if can scroll or not.
            this.Cursor = (ExtentWidth > ViewportWidth) ||
                (ExtentHeight > ViewportHeight) ?
                Cursors.ScrollAll : Cursors.Arrow;

            this.CaptureMouse();
        }

        base.OnPreviewMouseDown(e);
    }


    protected override void OnPreviewMouseMove(MouseEventArgs e)
    {
        if (this.IsMouseCaptured)
        {
            // Get the new scroll position.
            Point point = e.GetPosition(this);

            // Determine the new amount to scroll.
            Point delta = new Point(
                (point.X > this.scrollStartPoint.X) ?
                    -(point.X - this.scrollStartPoint.X) :
                    (this.scrollStartPoint.X - point.X),

                (point.Y > this.scrollStartPoint.Y) ?
                    -(point.Y - this.scrollStartPoint.Y) :
                    (this.scrollStartPoint.Y - point.Y));

            // Scroll to the new position.
            ScrollToHorizontalOffset(this.scrollStartOffset.X + delta.X);
            ScrollToVerticalOffset(this.scrollStartOffset.Y + delta.Y);
        }

        base.OnPreviewMouseMove(e);
    }



    protected override void OnPreviewMouseUp(MouseButtonEventArgs e)
    {
        if (this.IsMouseCaptured)
        {
            this.Cursor = Cursors.Arrow;
            this.ReleaseMouseCapture();
        }

        base.OnPreviewMouseUp(e);
    }
    #endregion
}

Where there is also a small XAML Style required, which is as follows:

XML
<!-- scroll viewer -->
<Style x:Key="ScrollViewerStyle"
       TargetType="{x:Type ScrollViewer}">
    <Setter Property="HorizontalScrollBarVisibility"
            Value="Hidden" />
    <Setter Property="VerticalScrollBarVisibility"
            Value="Hidden" />
</Style>

And here is the PanningScrollViewer hosting the TubeStationsCanvas:

XML
<local:PanningScrollViewer x:Name="svDiagram" Visibility="{Binding Path=IsBusy, 
    Converter={StaticResource BoolToVisibilityConv}, ConverterParameter=False}"
                         Style="{StaticResource ScrollViewerStyle}">
    <local:TubeStationsCanvas x:Name="canv" Margin="50"
            Background="Transparent"
            Width="7680"
            Height="6144">
    </local:TubeStationsCanvas>
</local:PanningScrollViewer>

Zooming the Diagram

Zooming, well, credit where credit is due, is more than likely sourced for all zooming WPF apps from Vertigo's sublime initial WPF exemplar, The Family Show, which was and still is one of the best uses of WPF I have seen.

Anyway, to cut a long story short, zooming is realized using a standard WPF Slider control (albeit I have jazzed it up a bit with a XAML Style) and a ScaleTransform.

C#
public Double Zoom
{
    get { return ZoomSlider.Value; }
    set
    {
        if (value >= ZoomSlider.Minimum && value <= ZoomSlider.Maximum)
        {
            canv.LayoutTransform = new ScaleTransform(value, value);
            canv.InvalidateVisual();

            ZoomSlider.Value = value;
            UpdateScrollSize();
            this.InvalidateVisual();
        }
    }
}

The user can zoom using the Slider as shown in the app:

Image 6

Station Line Tooltips

I thought it may be nice to have each StationControl render a tooltip which only shows the lines that the StationControl is on. This is done using standard Binding, where the StationControl's ToolTip binds to the StationViewModel which is the DataContext for the StationControl. The StationViewModel contains a IList<Line> which represents the lines the station is on. So from there, it is just a question of making the tooltip look cool. Luckily, this is what WPF is good at. Here is how:

First, the StationControl.ToolTip, which is defined as shown below:

XML
<UserControl.ToolTip>

    <Border HorizontalAlignment="Stretch"
                        SnapsToDevicePixels="True"
                        BorderBrush="Black"
                        Background="White"
                        VerticalAlignment="Stretch"
                        Height="Auto"
                        BorderThickness="3"
                        CornerRadius="5">
        <Grid Margin="0" Width="300">
            <Grid.RowDefinitions>
                <RowDefinition Height="40"/>
                <RowDefinition Height="Auto"/>
            </Grid.RowDefinitions>
            
            <Border CornerRadius="2,2,0,0" Grid.Row="0" 
                    BorderBrush="Black" BorderThickness="2"
                    Background="Black">
                <StackPanel Orientation="Horizontal" >
                    <Image Source="../Images/tubeIconNormal.png"
                               Width="30"
                               Height="30" 
                               VerticalAlignment="Center" 
                               HorizontalAlignment="Left" 
                               Margin="2"/>
                    <Label Content="{Binding DisplayName}"
                               FontSize="14"
                               FontWeight="Bold"
                               Foreground="White"
                               VerticalContentAlignment="Center"
                               Margin="5,0,0,0" />

                </StackPanel>

            </Border>

            <StackPanel Orientation="Vertical" Grid.Row="1">

            <!-- Bakerloo -->
            <StackPanel Orientation="Horizontal" HorizontalAlignment="Stretch"
                        Visibility="{Binding RelativeSource={RelativeSource Self}, 
                        Path=DataContext, Converter={StaticResource OnLineToVisibilityConv}, 
                            ConverterParameter='Bakerloo'}">

                
               <Border BorderBrush="Black" BorderThickness="2" 
                       CornerRadius="5"
                       Background="Brown" Height="30" Width="30" 
                       Margin="10,2,10,2">
                    <Image Source="../Images/tubeIcon.png" Width="20" 
                           Height="20" HorizontalAlignment="Center"
                           VerticalAlignment="Center"/>
                </Border>

                <Label Content="Bakerloo" 
                       Padding="2"
                       Foreground="Black"
                       FontSize="10"
                       FontWeight="Bold"
                       HorizontalAlignment="Center"
                       VerticalAlignment="Center" 
                       VerticalContentAlignment="Center"
                       HorizontalContentAlignment="Center"/>


            </StackPanel>

        <!-- Other lines done the same as Bakerloo -->
        <!-- Other lines done the same as Bakerloo -->
        <!-- Other lines done the same as Bakerloo -->
        <!-- Other lines done the same as Bakerloo -->
        <!-- Other lines done the same as Bakerloo -->
        <!-- Other lines done the same as Bakerloo -->

            <Label Content="{Binding ZoneInfo}"
                FontSize="10"
                Foreground="Black"
                FontWeight="Bold"
                VerticalContentAlignment="Center"
                Margin="5" />

            </StackPanel>
        </Grid>
    </Border>
</UserControl.ToolTip>

And there is a Style in the /Resources/AppStyles.xaml ResourceDictionary which dictates what ToolTips should look like. Here is that XAML:

XML
<!-- Tooltip-->
<Style TargetType="{x:Type ToolTip}">
    <Setter Property="Template">
        <Setter.Value>
            <ControlTemplate TargetType="{x:Type ToolTip}">
                <Border BorderBrush="Black" CornerRadius="3" 
                        Margin="10,2,10,2"
                        Background="White" BorderThickness="1"
                        HorizontalAlignment="Center" 
                        VerticalAlignment="Center">

                    <Label Content="{TemplateBinding Content}" 
                       Padding="2"
                       Foreground="Black"
                       FontSize="10"
                       FontWeight="Bold"
                       HorizontalAlignment="Center"
                       VerticalAlignment="Center" 
                       VerticalContentAlignment="Center"
                       HorizontalContentAlignment="Center"/>

                </Border>
            </ControlTemplate>
        </Setter.Value>
    </Setter>
</Style>

This looks quite cool when you hover over a StationControl; it will look like the following, which is quite useful when you are mousing over various stations on the diagram. Oh, also, the actual StationControl grows and shrinks when you mouse over it; this also aids in showing the user which station the ToolTip is for.

Image 7

The Guided Search

As I previously mentioned, the search is an A* type of search, where we have a known cost and an unknown cost. Wikipedia has this to say about the A* algorithm:

In Computer Science: A* (pronounced "A star") is a best-first graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).

It uses a distance-plus-cost heuristic function (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The distance-plus-cost heuristic is a sum of two functions:

  • the path-cost function, which is the cost from the starting node to the current node (usually denoted g(x)).
  • and an admissible "heuristic estimate" of the distance to the goal (usually denoted h(x)).

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Besides, h(x) must be such that f(x) cannot decrease when a new step is taken. Thus, for an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points (or nodes for that matter).

--http://en.wikipedia.org/wiki/A*_search_algorithm

The search algorithm, as used in the app, is described by the figure shown below. The search is initiated from a ICommand in the PlannerViewModel which is triggered from the user clicking the button on the UI.

Image 8

Where the actual code looks like this:

C#
public SearchPath DoSearch()
{
    pathsSolutionsFound = new List<SearchPath>();
    pathsAgenda = new List<SearchPath>();

    SearchPath pathStart = new SearchPath();
    pathStart.AddStation(vm.CurrentStartStation);
    pathsAgenda.Add(pathStart);

    while (pathsAgenda.Count() > 0)
    {
        SearchPath currPath = pathsAgenda[0];
        pathsAgenda.RemoveAt(0);
        if (currPath.StationsOnPath.Count(
            x => x.Name.Equals(vm.CurrentEndStation.Name)) > 0)
        {
            pathsSolutionsFound.Add(currPath);
            break;
        }
        else
        {
            StationViewModel currStation = currPath.StationsOnPath.Last();
            List<StationViewModel> successorStations = 
                GetSuccessorsForStation(currStation);

            foreach (StationViewModel successorStation in successorStations)
            {
                if (!currPath.StationsOnPath.Contains(successorStation) &&
                    !(ExistsInSearchPath(pathsSolutionsFound, successorStation)))
                {
                    SearchPath newPath = new SearchPath();
                    foreach (StationViewModel station in currPath.StationsOnPath)
                        newPath.StationsOnPath.Add(station);

                    newPath.AddStation(successorStation);
                    pathsAgenda.Add(newPath);
                    pathsAgenda.Sort();
                }
            }
        }
    }

    //Finally, get the best Path, this should be the 1st one found due
    //to the heuristic evaluation performed by the search
    if (pathsSolutionsFound.Count() > 0)
    {
        return pathsSolutionsFound[0];
    }
    return null;

}

It can be seen that the search returns a SearchPath object. It is in the SearchPath objects that the costs are stored. There are several costs associated with the search algorithm.

HCost

An admissible "heuristic estimate" of the distance to the goal (usually denoted h(x)).

In terms of the attached application, this is simply the difference between two objects, which is coded as follows:

C#
public static Double GetHCost(StationViewModel currentStation, 
                              StationViewModel endStation)
{
    return Math.Abs(
        Math.Abs(currentStation.CentrePointOnDiagramPosition.X - 
            endStation.CentrePointOnDiagramPosition.X) +
        Math.Abs(currentStation.CentrePointOnDiagramPosition.Y - 
            endStation.CentrePointOnDiagramPosition.Y));
}

GCost

The path-cost function, which is the cost from the starting node to the current node (usually denoted g(x)).

In terms of the attached application, this is calculated using the number of line changes to get to the current station * SOME_CONSTANT.

C#
public Double GCost
{
    get { return gCost + (changesSoFar * LINE_CHANGE_PENALTY); }
}

FCost

This is the magic figure that guides the search when the SearchPaths in the Agenda are sorted. FCost is nothing more than GCost + FCost. So by sorting the Agenda SearchPaths on this value, the supposed best route is picked.

Drawing the Solution Path

Drawing the solution path is similar to what we saw in drawing the actual lines, except this time, we are only looping through the StationViewModels of the SolutionFound SearchPath object and drawing the connections in the StationViewModels in the solution path.

C#
private void DrawSolutionPath(DrawingContext dc, SearchPath solutionPath)
{
    for (int i = 0; i < solutionPath.StationsOnPath.Count() - 1; i++)
    {
        StationViewModel station1 = solutionPath.StationsOnPath[i];
        StationViewModel station2 = solutionPath.StationsOnPath[i + 1];
        SolidColorBrush brush = new SolidColorBrush(Colors.Orange);
        brush.Opacity = 0.6;

        Pen pen = new Pen(brush, 70);
        pen.EndLineCap = PenLineCap.Round;
        pen.DashCap = PenLineCap.Round;
        pen.LineJoin = PenLineJoin.Round;
        pen.StartLineCap = PenLineCap.Round;
        pen.MiterLimit = 10.0;
        dc.DrawLine(pen,
            station1.CentrePointOnDiagramPosition,
            station2.CentrePointOnDiagramPosition);
    }
}

This then looks like this on the diagram; note the orange path drawn, that is the Solution path:

Image 9

Hiding Unwanted Lines

Whilst it is nice to see all the lines in the diagram, there is a lot to display, and it would be nice if we could hide unwanted lines that are not part of the SolutionFound SearchPath. To this end, the attached demo code hosts a popup window with a checkbox per line, where the checkbox for a given line is only enabled if the SolutionFound SearchPath does not contain the line the checkbox is for.

Assuming that the SolutionFound SearchPath does not contain a given line, the user is able to toggle the lines Visibility using the checkbox.

Here is a screenshot of the line visibility popup and the effect of unchecking one of the checkboxes:

Image 10

As an added bonus, I have also included an attached behaviour that allows the user to drag the popup around using an embedded Thumb control. That attached behaviour is shown below:

C#
/// <summary>
/// Allows moving of Popup using a Thumb
/// </summary>
public class PopupBehaviours
{
    #region IsMoveEnabled DP
    public static Boolean GetIsMoveEnabledProperty(DependencyObject obj)
    {
        return (Boolean)obj.GetValue(IsMoveEnabledPropertyProperty);
    }

    public static void SetIsMoveEnabledProperty(DependencyObject obj, 
                                                Boolean value)
    {
        obj.SetValue(IsMoveEnabledPropertyProperty, value);
    }

    // Using a DependencyProperty as the backing store for 
    //IsMoveEnabledProperty. 
    public static readonly DependencyProperty IsMoveEnabledPropertyProperty =
        DependencyProperty.RegisterAttached("IsMoveEnabledProperty",
        typeof(Boolean), typeof(PopupBehaviours), 
        new UIPropertyMetadata(false,OnIsMoveStatedChanged));


    private static void OnIsMoveStatedChanged(DependencyObject sender, 
        DependencyPropertyChangedEventArgs e)
    {
        Thumb thumb = (Thumb)sender;

        if (thumb == null) return;

        thumb.DragStarted -= Thumb_DragStarted;
        thumb.DragDelta -= Thumb_DragDelta;
        thumb.DragCompleted -= Thumb_DragCompleted;

        if (e.NewValue != null && e.NewValue.GetType() == typeof(Boolean))
        {
            thumb.DragStarted += Thumb_DragStarted;
            thumb.DragDelta += Thumb_DragDelta;
            thumb.DragCompleted += Thumb_DragCompleted;
        }

    }
    #endregion

    #region Private Methods
    private static void Thumb_DragCompleted(object sender, 
        DragCompletedEventArgs e)
    {
        Thumb thumb = (Thumb)sender;
        thumb.Cursor = null;
    }

    private static void Thumb_DragDelta(object sender, 
    DragDeltaEventArgs e)
    {
        Thumb thumb = (Thumb)sender;
        Popup popup = thumb.Tag as Popup;

        if (popup != null)
        {
            popup.HorizontalOffset += e.HorizontalChange;
            popup.VerticalOffset += e.VerticalChange;
        }
    }

    private static void Thumb_DragStarted(object sender, 
    DragStartedEventArgs e)
    {
        Thumb thumb = (Thumb)sender;
        thumb.Cursor = Cursors.Hand;
    }
    #endregion

}

To use this attached behaviour, the popup itself must use a particular Style; this is shown below:

XML
<Popup x:Name="popLines"  
       PlacementTarget="{Binding ElementName=mainGrid}"
       Placement="Relative"
       IsOpen="False"
       Width="400" Height="225"
       AllowsTransparency="True"
       StaysOpen="False"
       PopupAnimation="Scroll"
       HorizontalAlignment="Right"
       HorizontalOffset="30" VerticalOffset="30" >

    <Border Background="Transparent" HorizontalAlignment="Stretch"
            VerticalAlignment="Stretch"
            BorderBrush="#FF000000" 
            BorderThickness="3" 
            CornerRadius="5,5,5,5">

        <Grid Background="White">

            <Grid.RowDefinitions>
                <RowDefinition Height="40"/>
                <RowDefinition Height="*"/>
            </Grid.RowDefinitions>

            <Thumb Grid.Row="0" Width="Auto" Height="40" 
                   Tag="{Binding ElementName=popLines}"
                   local:PopupBehaviours.IsMoveEnabledProperty="true">
                <Thumb.Template>
                    <ControlTemplate>
                        <Border  Width="Auto" Height="40" 
                 BorderBrush="#FF000000" 
                                 Background="Black" VerticalAlignment="Top" 
                                 CornerRadius="5,5,0,0" Margin="-2,-2,-2,0">

                            <Label Content="Lines"
                               FontSize="18"
                               FontWeight="Bold"
                               Foreground="White"
                               VerticalContentAlignment="Center"
                               Margin="5,0,0,0" />
                        </Border>
                    </ControlTemplate>
                </Thumb.Template>
            </Thumb>

            <!-- Actual Content Grid-->
            <Grid Grid.Row="1" Background="White"
                      Width="Auto"  Height="Auto" Margin="0,0,0,10">
                <ScrollViewer HorizontalScrollBarVisibility="Hidden"
                    VerticalScrollBarVisibility="Visible">
                </ScrollViewer> 
            </Grid>
        </Grid>
    </Border>
</Popup>

Textual Results

All along, I knew I wanted to create a jazzy popup window that would hold the textual description of the solution path found, that would allow the user to read the description in English. The idea is simple for each StationViewModel on the SolutionFound SearchPath: iterate through and build up a text description of the route, and display it to the user. This is done in the actual SearchPath object as follows:

C#
private String GetPathDescription()
{
    StringBuilder thePath = new StringBuilder(1000);
    StationViewModel currentStation;

    for (int i = 0; i < this.StationsOnPath.Count - 1; i++)
    {
        IList<Line> otherLines = this.StationsOnPath[i + 1].Lines;
        List<Line> linesInCommon = 
            this.StationsOnPath[i].Lines.Intersect(otherLines).ToList();
        if (i == 0)
        {
            currentStation = this.StationsOnPath[0];
            thePath.Append("Start at " + currentStation.Name +
                " station, which is on the " + 
                NormaliseLineName(linesInCommon[0]) + " line, ");
        }
        else
        {
            currentStation = this.StationsOnPath[i];
            thePath.Append("\r\nThen from " + currentStation.Name +
                " station, which is on the " + 
                NormaliseLineName(linesInCommon[0]) + " line, ");

        }

        thePath.Append("take the " + NormaliseLineName(linesInCommon[0]) +
            " line to " + this.StationsOnPath[i + 1] + " station\r\n");
    }

    //return the path description
    return thePath.ToString();
}

So after that, all that is left to do is display it. I talked about how I do that on my blog the other day: http://sachabarber.net/?p=580. The basic idea is that you use a popup and get it to support transparency, and then draw a callout graphic Path, and show the SearchPath text.

Here is it in action. I think it looks pretty cool:

Image 11

This is all done using the following XAML:

XML
<Popup x:Name="popInformation"  
       PlacementTarget="{Binding ElementName=imgInformation}"
       Placement="Top"
       IsOpen="False"
       Width="400" Height="250"
       AllowsTransparency="True"
       StaysOpen="True"
       PopupAnimation="Scroll"
       HorizontalAlignment="Right"
       VerticalAlignment="Top"
       HorizontalOffset="-190" VerticalOffset="-10" >
    <Grid Margin="10">
        <Path Fill="LightYellow" Stretch="Fill" 
              Stroke="LightGoldenrodYellow" 
                StrokeThickness="3" StrokeLineJoin="Round"
                Margin="0" Data="M130,154 L427.5,154 427.5,
              240.5 299.5,240.5 287.5,245.5 275.5,240.5 130,240.5 z">
            <Path.Effect>
                <DropShadowEffect BlurRadius="12" Color="Black" 
                                  Direction="315" Opacity="0.8"/>
            </Path.Effect>
        </Path>

        <Grid Height="225" Margin="10,5,10,5"
              HorizontalAlignment="Stretch" VerticalAlignment="Top">
            <Grid.RowDefinitions>
                <RowDefinition Height="Auto"/>
                <RowDefinition Height="*"/>
            </Grid.RowDefinitions>
            
            
            <Label Grid.Row="0" FontSize="16" 
                   FontWeight="Bold" Content="Your Route" 
                   HorizontalAlignment="Left" Margin="0,5,5,5"
                   VerticalAlignment="Center"/>
            
            
            <Button Grid.Row="0" HorizontalAlignment="Right"
                    Width="25" Click="Button_Click"
                    Height="25" VerticalAlignment="Top" Margin="2">
                <Button.Template>
                    <ControlTemplate TargetType="{x:Type Button}">
                        <Border x:Name="bord" CornerRadius="3" 
                                BorderBrush="Transparent" 
                                BorderThickness="2"
                                Background="Transparent" 
                                HorizontalAlignment="Center"
                                VerticalAlignment="Center" 
                                Margin="0" Width="25" Height="25">
                            <Label x:Name="lbl" Foreground="Black" 
                                   FontWeight="Bold" 
                                   HorizontalAlignment="Center"
                                   VerticalAlignment="Center"
                                   FontFamily="Wingdings 2" Content="O"  
                                   FontSize="14"/>
                        </Border>
                        <ControlTemplate.Triggers>
                            <Trigger Property="IsMouseOver" 
                            Value="True">
                                <Setter TargetName="bord" 
                                        Property="BorderBrush" 
                                        Value="Black"/>
                                <Setter TargetName="bord" 
                                        Property="Background"
                                         Value="Black"/>
                                <Setter TargetName="lbl" 
                                        Property="Foreground" 
                                        Value="LightGoldenrodYellow"/>
                            </Trigger>
                        </ControlTemplate.Triggers>
                    </ControlTemplate>
                </Button.Template>
                
            </Button>

            <ScrollViewer Grid.Row="1" Margin="0,5,0,30"
                          HorizontalScrollBarVisibility="Disabled" 
                          VerticalScrollBarVisibility="Auto">
                <TextBlock  TextWrapping="Wrap"  FontSize="10" Margin="5"
                       VerticalAlignment="Stretch" HorizontalAlignment="Stretch" 
                Text="{Binding Path=SearchPathDescription}"/>
            </ScrollViewer>

        </Grid>

    </Grid>
</Popup>

That's It. Hope You Liked It.

Anyway, there you go. Hope you liked it. Even if you don't have a use for a London tube planner, I think there is still lots of good WPF learning material in this one.

Thanks

As always, votes / comments are welcome.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
United Kingdom United Kingdom
I currently hold the following qualifications (amongst others, I also studied Music Technology and Electronics, for my sins)

- MSc (Passed with distinctions), in Information Technology for E-Commerce
- BSc Hons (1st class) in Computer Science & Artificial Intelligence

Both of these at Sussex University UK.

Award(s)

I am lucky enough to have won a few awards for Zany Crazy code articles over the years

  • Microsoft C# MVP 2016
  • Codeproject MVP 2016
  • Microsoft C# MVP 2015
  • Codeproject MVP 2015
  • Microsoft C# MVP 2014
  • Codeproject MVP 2014
  • Microsoft C# MVP 2013
  • Codeproject MVP 2013
  • Microsoft C# MVP 2012
  • Codeproject MVP 2012
  • Microsoft C# MVP 2011
  • Codeproject MVP 2011
  • Microsoft C# MVP 2010
  • Codeproject MVP 2010
  • Microsoft C# MVP 2009
  • Codeproject MVP 2009
  • Microsoft C# MVP 2008
  • Codeproject MVP 2008
  • And numerous codeproject awards which you can see over at my blog

Comments and Discussions

 
Questionquestion Pin
Member 1133408825-Apr-19 10:14
Member 1133408825-Apr-19 10:14 
PraiseThanks! Pin
BlancmangeForBrains12-Apr-16 7:23
BlancmangeForBrains12-Apr-16 7:23 
GeneralRe: Thanks! Pin
Sacha Barber12-Apr-16 8:08
Sacha Barber12-Apr-16 8:08 
PraiseVote of 5 Pin
Beginner Luck2-Feb-16 19:02
professionalBeginner Luck2-Feb-16 19:02 
QuestionCongratulations for wonderful job Pin
kiquenet.com15-Oct-15 3:47
professionalkiquenet.com15-Oct-15 3:47 
AnswerRe: Congratulations for wonderful job Pin
Sacha Barber15-Oct-15 6:29
Sacha Barber15-Oct-15 6:29 
GeneralMy vote of 5 Pin
leiyangge17-Jul-13 22:34
leiyangge17-Jul-13 22:34 
Questionhow come your answer is so different from other websites ? Pin
kailun9216-Apr-13 22:04
kailun9216-Apr-13 22:04 
QuestionIs your result the same as WWW.TUBEPLANNER.COM ? Pin
kailun9216-Apr-13 21:10
kailun9216-Apr-13 21:10 
GeneralMy vote of 5 Pin
Kenneth Haugland6-Oct-12 4:48
mvaKenneth Haugland6-Oct-12 4:48 
GeneralRe: My vote of 5 Pin
Sacha Barber6-Oct-12 4:57
Sacha Barber6-Oct-12 4:57 
GeneralRe: My vote of 5 Pin
Kenneth Haugland6-Oct-12 5:24
mvaKenneth Haugland6-Oct-12 5:24 
GeneralRe: My vote of 5 Pin
Sacha Barber6-Oct-12 20:43
Sacha Barber6-Oct-12 20:43 
QuestionMy Vote of 5! Pin
El_Codero3-Oct-12 9:41
El_Codero3-Oct-12 9:41 
Thanks for this (and all other articles you've published), great to expand my brain Smile | :)
Best Regards
AnswerRe: My Vote of 5! Pin
Sacha Barber3-Oct-12 10:26
Sacha Barber3-Oct-12 10:26 
Questionnice :) Pin
vasim sajad23-Sep-12 23:45
vasim sajad23-Sep-12 23:45 
GeneralMy vote of 5 Pin
vasim sajad23-Sep-12 23:44
vasim sajad23-Sep-12 23:44 
GeneralMy vote of 5 Pin
curt243230-Jul-12 14:11
curt243230-Jul-12 14:11 
QuestionPopupBehaviours - most helpful Pin
AndrewAngell21-May-12 5:09
AndrewAngell21-May-12 5:09 
AnswerRe: PopupBehaviours - most helpful Pin
Sacha Barber21-May-12 10:05
Sacha Barber21-May-12 10:05 
QuestionGreat, just great!!! Pin
Dominic_7720-Feb-12 21:24
Dominic_7720-Feb-12 21:24 
AnswerRe: Great, just great!!! Pin
Sacha Barber20-Feb-12 23:13
Sacha Barber20-Feb-12 23:13 
GeneralMy vote of 5 Pin
Barry Lapthorn15-Feb-12 0:29
protectorBarry Lapthorn15-Feb-12 0:29 
GeneralRe: My vote of 5 Pin
Sacha Barber20-Feb-12 23:12
Sacha Barber20-Feb-12 23:12 
QuestionGood Article! Pin
Sanjay K. Gupta15-Jan-12 2:59
professionalSanjay K. Gupta15-Jan-12 2:59 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.