RoyT.AStar 2.0.1

There is a newer version of this package available.
See the version list below for details.
dotnet add package RoyT.AStar --version 2.0.1
NuGet\Install-Package RoyT.AStar -Version 2.0.1
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="RoyT.AStar" Version="2.0.1" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add RoyT.AStar --version 2.0.1
#r "nuget: RoyT.AStar, 2.0.1"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package.
// Install RoyT.AStar as a Cake Addin
#addin nuget:?package=RoyT.AStar&version=2.0.1

// Install RoyT.AStar as a Cake Tool
#tool nuget:?package=RoyT.AStar&version=2.0.1

Roy-T.AStar

A fast 2D path finding library based on the A* algorithm for .NETStandard 1.0 and .Net 4.5 and higher. This library has no external dependencies. The library is licensed under the MIT license, see the LICENSE file for more details.

For more information about the A* path finding algorithm and this library, please visit my blog.

For more information about this library visit github.

Why choose this library?

  • Its very fast
  • It generates lowest cost, visually appealing, paths using the A* algorithm
  • Its flexible, you can define how your agent moves and this library will accomodate these restrictions
  • Its easy to use, you can generate a path with two lines of code
  • It has zero (0) external dependencies
  • It works on both .Net Core and .Net 4.5 and higher by targetting .Net standard 1.0

Tutorial

Below I give short code-first example. If you are more interested in textual explanation you can find it right after the next section.

Usage example in code

You can easily search for the lowest cost path for an agent that can move in all directions.

using RoyT.AStar;

// Create a new grid and let each cell have a default traversal cost of 1.0
var grid = new Grid(100, 100, 1.0f);

// Block some cells (for example walls)
grid.BlockCell(new Position(5, 5))

// Make other cells harder to traverse (for example water)
grid.SetCellCost(new Position(6, 5), 3.0f);

// And finally start the search for the shortest path form start to end
Position[] path = grid.GetPath(new Position(0, 0), new Position(99, 99));

It is also posssible to define the agent's movement pattern.

// Use one of the built-in ranges of motion
var path = grid.GetPath(new Position(0, 0), new Position(99, 99), MovementPatterns.DiagonalOnly);

// Or define the movement pattern of an agent yourself
// For example, here is an agent that can only move left and up
var movementPattern = new[] {new Offset(-1, 0), new Offset(0, -1)};
var path = grid.GetPath(new Position(0, 0), new Position(99, 99), movementPattern);

Usage in text

Your agent might be able to move fluently through a world with hills and water but that representation is too complex for the A* algorithm. So the first thing you need to do is to is to create an abstract representation of your world that is simple enough for the path finding algorithm to understand. In this library we use a grid to represent the traversable, and intraversable, space in your world.

You can instantiate a grid using the Grid class. If you have a world that is a 100 by a 100 meters large, and you create a grid of 100x100, each cell will represent a patch of land of 1x1 meters.

Experiment with the size of the grid, a larger grid will give you more fine grained control but it will also make the path finding algorithm slower.

Once you have a grid you need to configure which cells represent obstacles. Some obstacles, like a high wall, are intraversable. Use the BlockCell method on your grid to prevent the path finding algorithm from planning paths through that cell. Other obstacles, like dense shrubbery, take more time to traverse. In that case give the cell a higher cost using the SetCellCost method.

Once you've configured your grid its time to start planning paths. Using the GetPath method you can immidately search for a path between two cells for an agent that can move in all directions. You can also plan paths for agents that are more limited in their movent using the overload of GetPath that takes a movementPattern parameter. In that case you can either select one of the predefined ranges of motion from the MovementPatterns class or you can configure yourself what kind of steps an agent can make.

You can define your own patterns for your agents. Below I have defined the movement pattern for an agent that can only move diagonally. (This movement pattern is included in the library as MovementPatterns.DiagonalOnly).

var diagonalOnlyMovementPattern = new[] {
    new Offset(-1, -1), new Offset(1, -1), , new Offset(1, 1), , new Offset(-1, 1)
};

Viewer

If you just want to try this package out, without having to integrate it into your code base, there is a viewer you can use to fool around. For more information visit the github page.

Implementation details

While making this library I was mostly concerned with performance (how long does it take to find a path) and ease of use. I use a custom MinHeap data structure to keep track of the best candidates for the shortest path. I've experimented with other data structures, like the standard SortedSet but they were consistently slower. Inside the A* algorithm itself I use flat arrays to store the path and cost information. I use the Manhattan distance heuristic because its cheap to compute and is an admissible heuristic for all predefined movement patterns.

While micro-optimizing the code I've used the handy BenchMark.Net library to see if my changes had any effect. The benchmark suite is included in the source code here. So if you would like to try to make this implemention faster you can use the same benchmark and performance metrics I did.

Product Compatible and additional computed target framework versions.
.NET net5.0 was computed.  net5.0-windows was computed.  net6.0 was computed.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 was computed.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed.  net8.0 was computed.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed. 
.NET Core netcoreapp1.0 was computed.  netcoreapp1.1 was computed.  netcoreapp2.0 was computed.  netcoreapp2.1 was computed.  netcoreapp2.2 was computed.  netcoreapp3.0 was computed.  netcoreapp3.1 was computed. 
.NET Standard netstandard1.0 is compatible.  netstandard1.1 was computed.  netstandard1.2 was computed.  netstandard1.3 was computed.  netstandard1.4 was computed.  netstandard1.5 was computed.  netstandard1.6 was computed.  netstandard2.0 was computed.  netstandard2.1 was computed. 
.NET Framework net45 was computed.  net451 was computed.  net452 was computed.  net46 was computed.  net461 was computed.  net462 was computed.  net463 was computed.  net47 was computed.  net471 was computed.  net472 was computed.  net48 was computed.  net481 was computed. 
MonoAndroid monoandroid was computed. 
MonoMac monomac was computed. 
MonoTouch monotouch was computed. 
Tizen tizen30 was computed.  tizen40 was computed.  tizen60 was computed. 
Universal Windows Platform uap was computed.  uap10.0 was computed. 
Windows Phone wp8 was computed.  wp81 was computed.  wpa81 was computed. 
Windows Store netcore was computed.  netcore45 was computed.  netcore451 was computed. 
Xamarin.iOS xamarinios was computed. 
Xamarin.Mac xamarinmac was computed. 
Xamarin.TVOS xamarintvos was computed. 
Xamarin.WatchOS xamarinwatchos was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.

NuGet packages (3)

Showing the top 3 NuGet packages that depend on RoyT.AStar:

Package Downloads
OpenFTTH.RouteNetwork.Business

Package Description

SettlementSimulation.AreaGenerator

C# library for simulation the development of human settlement

Sharky

The Sharky Framework. A StarCraft 2 API framework for creating StarCraft 2 bots

GitHub repositories (4)

Showing the top 4 popular GitHub repositories that depend on RoyT.AStar:

Repository Stars
LeagueSandbox/GameServer
League Sandbox's Game Server
Chris3606/GoRogue
.NET Standard roguelike library in C#. Features many algorithms and data structures pertinent to roguelike/2D game developers, specifically designed to be minimally intrusive upon the developer's architecture.
TBye101/MagicalLife
A 2d game that aspires to be similar to Rimworld, with more depth, magic, and RPG concepts.
roy-t/MiniRTS
A game engine to learn about game engine development
Version Downloads Last updated
3.0.2 29,677 8/5/2020
3.0.1 15,785 2/28/2020
3.0.0 597 2/19/2020
2.1.0 17,430 4/5/2018
2.0.1 954 4/2/2018
2.0.0 1,125 3/31/2018
1.2.0 1,168 9/3/2017
1.1.0 888 8/4/2017
1.0.0 1,030 8/1/2017