A Simple Pathfinding Laboratory

• Download source files - 85.9 KB

Introduction

In this article, we will take a look into a simple pathfinding laboratory--a web application where users can edit map and compare paths found by different pathfinding algorithms and heuristic functions. The project is built on the following frameworks and technologies:

• ASP.NET Core MVC and Web API - for general website functionalities
• Bootstrap, jQuery, TypeScript, HTML5 - for overall front-end presentation
• SVG DOM for map rendering and path animation
• LINQ to A* - for pathfinding algorithms behind Web API, the core part of the project

The source code can be downloaded from CodeProject and GitHub. 

Before we start, let us briefly understand the core part of the project, LINQ to A*.

What is LINQ to A*

LINQ to A* is an experimental library aimed to incorporate LINQ expressions into A* and other heuristic search algorithms. With the library, users can use LINQ as query expression to state conditions and fetch shortest path found by the algorithm. This makes the algorithms very easy and flexible to work with just like searching data from database via LINQ to SQL or LINQ to Entities.

The code snippet below searches the shortest path between start and goal on a 20 * 20 map:

var start = new Point(3, 13); 
var goal = new Point(15, 4); 
var boundary = new Rectangle(0, 0, 20, 20); // The 20 * 20 map
var queryable = HeuristicSearch.AStar(start, goal, (s, i) => s.GetFourDirections(unit));
var solution = from p in queryable.Except(GetMapObstacles()) 
               where boundary.Contains(p)
               orderby p.GetManhattanDistance(goal) 
               select p;

where:

1. The HeuristicSearch.AStar<TStep>() method creates a queryable instance with the callback that gets nearby four positions from the current one.
2. The Except() eliminates all obstacles on the map.
3. The where clause eliminates invalid positions. In this snippet, it is used to check whether the position is out of boundary.
4. The orderby clause states a heuristic function that evaluates the cost of position. In this snippet, we use Manhattan distance as our heuristic function.

The solution is an IEnumerable<Point> instance that enumerates each position of the path. If path is not found, the result is empty.

The stable version of LINQ to A* is available on NuGet. The project uses this library as its core part to calculate the path. Users are also able to see the equivalent LINQ expressions on the web application.

Playing with the Laboratory

Let us get started with the laboratory. The web application looks like this:

A green 20 * 20 tile map on the left is where we can place obstacles (left click) and find path (right click) using the algorithm and heuristic functions we choose. On the bottom-right, three equivalent LINQ expressions (SelectMany(), Except() and Where()) appear here as examples so users can try out on their own application.

Now let us place some obstacles and find a few paths with different settings:

Once a path is found, the road will be drawn on the map. Clicking its corresponding history button on bottom-right will toggle an animated overlay on the map as well as its algorithm settings and LINQ expressions on right side. Below is the path found by A* search algorithm along with Manhattan distance:

We can use this feature to compare multiple paths found by different algorithms. Following is the other path between same start and goal but using Best-first Search algorithm instead.

As you can see, the path found by Best-first Search (the red path) is clearly different from A*. And because of the algorithm's design, the former takes more steps than the latter.

While editing map, you can save, load or start over anytime. The application uses localStorage to store your progress.

Multiple Heuristic Functions

You may have noticed that more than one heuristic function can co-exist in the laboratory. This is one of the flexible features in LINQ to A* that is different from classical pathfinding implementations. When multiple heuristic functions are used, the subsequent one will only be called if previous one estimates two positions as equal. This is very useful for the following scenario:

var start = new Point(8, 14);
var goal = new Point(11, 8);
var boundary = new Rectangle(0, 0, 20, 20);
var queryable = HeuristicSearch.AStar(start, goal, (s, i) => s.GetFourDirections(unit)); 
var solution = from p in queryable 
               from obstacle in GetMapObstacles() 
               where boundary.Contains(p) && p != obstacle 
               orderby p.GetManhattanDistance(goal), p.GetEuclideanDistance(goal) 
               select p;

In this code snippet, GetEuclideanDistance() is the secondary heuristic function after GetManhattanDistance(). Because calculating Euclidean distance is expensive and is way slower than Manhattan distance, it is not needed all the time unless we want further comparison. The OrderBy() and ThenBy() clauses can help us out.

Theoretically, you can attach as many heuristic functions as you want in your expression.

Closing

This is merely a simple laboratory and has lots of potential of improvement. If you are interested in it, there are several ways of getting involved in the project:

• If you are experiencing issues, or have new idea about the web application, please file an issue to the repository at GitHub.
• If you are experiencing issues about the algorithm and LINQ expression, please file an issue to the repository of LINQ to A* at GitHub.
• If you have an awesome idea of pathfinding process and want to try it out in the project, LINQ to A* allows user-defined algorithm where you can implement your own algorithm and apply same LINQ expression to it.

All feedbacks are appreciated.

History

• 2018-07-01: Initial post
• 2018-07-15: Update layout, rewrite map in SVG (previously canvas), add path animation
• 2018-08-08: Update package reference to stable release