AAPathfinding_Nuget_Nomono 1.0.0

Supports any-angle pathfinding for C# projects based on SharpMath2. This is built with the NOT_MONOGAME flag and is thus incompatible with monogame.

Install-Package AAPathfinding_Nuget_Nomono -Version 1.0.0
dotnet add package AAPathfinding_Nuget_Nomono --version 1.0.0
<PackageReference Include="AAPathfinding_Nuget_Nomono" Version="1.0.0" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add AAPathfinding_Nuget_Nomono --version 1.0.0
The NuGet Team does not provide support for this client. Please contact its maintainers for support.

Any-Angle Pathfinding

This package is a lightweight any-angle pathfinding algoirthm that depends on
SharpMath2. This implementation
tends to have faster performance and a simpler implementation compared to Theta*
Pathfinding.

This package does not require a graph system and does not give optimal paths,
however it seems that for a 2D rts style game this is sufficiently fast and
gives sufficiently good paths. Importantly, the difficult of calculating the
path does not depend on the map size but rather the complexity of the path
produced. This ensures that even when the paths are slow it is intuitive why
the paths are slow and thus easier for level designers to avoid pathological
cases.

Videos

The following video demonstrates paths from this library. Click for higher
quality

Paths
example

Installation

Open either a git for windows terminal (windows)
or the standard terminal (linux, mac). Move into the solution folder (i.e., cd
into the folder containing the .sln folder for the project you want to use this
pathfinder in). Run the following:

mkdir SharpMath2
cd SharpMath2
git init
git remote add origin "git@github.com:Tjstretchalot/SharpMath2.git"
git pull origin master
cd ..
mkdir AnyAnglePathfinding
cd AnyAnglePathfinding
git init
git remote add origin "git@github.com:Tjstretchalot/AnyAnglePathfinding.git"
git pull origin master

Then open up your project, right click the solution, "Add existing project",
navigate to the sharpmath2.shproj file and add it. Repeat for the AnyAnglePathfinding
package.

Right click "References" inside your main project. Under shared projects (left),
check "SharpMath2" and "AnyAnglePathfinding".

Quickstart

var map = new SimpleAAMap<AACollidable>(200, 100);

var entity = new AACollidable()
{
    Position = new Vector2(50, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 10, segments: 7)
};
map.Register(entity);

var entity2 = new TSCollidable()
{
    Position = new Vector2(100, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 7, segments: 5)
};
map.Register(entity2);

var excludeIds = new HashSet<int>();
excludeIds.Add(entity.ID);

List<Vector2> path = new AAPathfinder(
        map, entity.Bounds, entity.Position,
        new Vector2(150, 70), excludeIds, 0
    ).CalculatePath();

Console.WriteLine($"entity 1 at {entity.Position}");
foreach(var loc in path)
{
    Console.WriteLine($"moved entity 1 to {loc}");
}

Usage

You will need a map class that implements AAMap&lt;T&gt;. This class will need to be
able to trace polygons as they move through your world. In general your
implementation can mirror the SimpleAAMap&lt;T&gt; class, except you should
incorporate some space partitioning system in order to prevent the n^2 collision
detection costs. Including several SimpleAAMap&lt;T&gt; which simply ignore the
Width/Height parameter is one ultra-simple approach to do this. Although not
required, leveraging the SharpMath2 raytraceables is a reasonably fast
implementation for doing these traces when combined with a space partitioning
system and will ensure that the map size you choose does not effect performance.

The most direct way to incorporate ThetaStarSharp into an existing project:

  • Have your entity class extend (or include) AACollidable
  • Have your map class implement AAMap&lt;T&gt; where T is your entity class
    • If you don't want to worry about space partitioning yet, have it just extend
      SimpleAAMap&lt;T&gt; and use SimpleAAMap&lt;T&gt;.Collidables as your entity list
  • Calculate paths via new AAPathfinder(map, bounds, start, end, excludeIds, excludeFlags).CalculatePath()

Comparison to other pathfinding algorithms

This is not a grid-based pathfinding algorithm. Furthermore, tracing polygons
across arbitrary distances requires polygon collision detection which is not
trivial to implement on your own. By incorporating this project you get the
flexibility of any-angle pathfinding on a plane in just a few lines of code.
Furthermore you no longer have to worry about grid size as a hyperparameter in
your pathfinding performance, which improves generalizability.

This package is not suitable if any of the following apply:

  • Movement is not identical on a plane (i.e. sidescrollers cannot use this
    package)
  • Your entities can only move in a limited number of directions (i.e. cardinal
    directions)
  • It is more expensive to move over some parts of the map then others, and you
    want this taken into account during pathfinding
  • Optimal pathing is more important than quickly finding paths
  • There are relatively few paths that will get you to the destination. In other
    words, the world is not relatively open.
    • Navigating through a maze will work but is not going to be fast using this
      algorithm

This package is meant for you (and you should submit issues to address any
problems) if:

  • Your entities can move in any angle (i.e. an RTS)
  • Collidables are relatively sparse
  • You prefer human-looking paths to optimal paths
  • Paths will tend to have only a few nodes or be impossible
  • Some classes of objects do not collide with other classes of objects
    • For example, you want to move to attack a building and ignore any enemy
      that is in the way
  • Some paths will not collide with a small set of objects
    • For example a door that only one unit can walk through

Flags example

// define your flags by incrementing the number on the right.
// this gives you up to 63 flags. You can use an enum with [Flags]
// which subtypes long as well
long TEAM_1 = 1 << 0; // 2^0
long TEAM_2 = 1 << 1; // 2^1

var entity = new AACollidable()
{
    Position = new Vector2(50, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 10, segments: 7),
    Flags = TEAM_1
};
map.Register(entity);

var entity2 = new AACollidable()
{
    Position = new Vector2(100, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 7, segments: 5),
    FLAGS = TEAM_2
};
map.Register(entity2);

var excludeIds = new HashSet<int>();
excludeIds.Add(entity.ID);

List<Vector2> path = new AAPathfinder(
        map, entity.Bounds, entity.Position,
        new Vector2(150, 70), excludeIds, TEAM_2 // ignores team 2 (i.e., entity2) -> direct path
    ).CalculatePath();

Console.WriteLine($"entity 1 at {entity.Position}");
foreach(var loc in path)
{
    Console.WriteLine($"moved entity 1 to {loc}");
}

Any-Angle Pathfinding

This package is a lightweight any-angle pathfinding algoirthm that depends on
SharpMath2. This implementation
tends to have faster performance and a simpler implementation compared to Theta*
Pathfinding.

This package does not require a graph system and does not give optimal paths,
however it seems that for a 2D rts style game this is sufficiently fast and
gives sufficiently good paths. Importantly, the difficult of calculating the
path does not depend on the map size but rather the complexity of the path
produced. This ensures that even when the paths are slow it is intuitive why
the paths are slow and thus easier for level designers to avoid pathological
cases.

Videos

The following video demonstrates paths from this library. Click for higher
quality

Paths
example

Installation

Open either a git for windows terminal (windows)
or the standard terminal (linux, mac). Move into the solution folder (i.e., cd
into the folder containing the .sln folder for the project you want to use this
pathfinder in). Run the following:

mkdir SharpMath2
cd SharpMath2
git init
git remote add origin "git@github.com:Tjstretchalot/SharpMath2.git"
git pull origin master
cd ..
mkdir AnyAnglePathfinding
cd AnyAnglePathfinding
git init
git remote add origin "git@github.com:Tjstretchalot/AnyAnglePathfinding.git"
git pull origin master

Then open up your project, right click the solution, "Add existing project",
navigate to the sharpmath2.shproj file and add it. Repeat for the AnyAnglePathfinding
package.

Right click "References" inside your main project. Under shared projects (left),
check "SharpMath2" and "AnyAnglePathfinding".

Quickstart

var map = new SimpleAAMap<AACollidable>(200, 100);

var entity = new AACollidable()
{
    Position = new Vector2(50, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 10, segments: 7)
};
map.Register(entity);

var entity2 = new TSCollidable()
{
    Position = new Vector2(100, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 7, segments: 5)
};
map.Register(entity2);

var excludeIds = new HashSet<int>();
excludeIds.Add(entity.ID);

List<Vector2> path = new AAPathfinder(
        map, entity.Bounds, entity.Position,
        new Vector2(150, 70), excludeIds, 0
    ).CalculatePath();

Console.WriteLine($"entity 1 at {entity.Position}");
foreach(var loc in path)
{
    Console.WriteLine($"moved entity 1 to {loc}");
}

Usage

You will need a map class that implements AAMap&lt;T&gt;. This class will need to be
able to trace polygons as they move through your world. In general your
implementation can mirror the SimpleAAMap&lt;T&gt; class, except you should
incorporate some space partitioning system in order to prevent the n^2 collision
detection costs. Including several SimpleAAMap&lt;T&gt; which simply ignore the
Width/Height parameter is one ultra-simple approach to do this. Although not
required, leveraging the SharpMath2 raytraceables is a reasonably fast
implementation for doing these traces when combined with a space partitioning
system and will ensure that the map size you choose does not effect performance.

The most direct way to incorporate ThetaStarSharp into an existing project:

  • Have your entity class extend (or include) AACollidable
  • Have your map class implement AAMap&lt;T&gt; where T is your entity class
    • If you don't want to worry about space partitioning yet, have it just extend
      SimpleAAMap&lt;T&gt; and use SimpleAAMap&lt;T&gt;.Collidables as your entity list
  • Calculate paths via new AAPathfinder(map, bounds, start, end, excludeIds, excludeFlags).CalculatePath()

Comparison to other pathfinding algorithms

This is not a grid-based pathfinding algorithm. Furthermore, tracing polygons
across arbitrary distances requires polygon collision detection which is not
trivial to implement on your own. By incorporating this project you get the
flexibility of any-angle pathfinding on a plane in just a few lines of code.
Furthermore you no longer have to worry about grid size as a hyperparameter in
your pathfinding performance, which improves generalizability.

This package is not suitable if any of the following apply:

  • Movement is not identical on a plane (i.e. sidescrollers cannot use this
    package)
  • Your entities can only move in a limited number of directions (i.e. cardinal
    directions)
  • It is more expensive to move over some parts of the map then others, and you
    want this taken into account during pathfinding
  • Optimal pathing is more important than quickly finding paths
  • There are relatively few paths that will get you to the destination. In other
    words, the world is not relatively open.
    • Navigating through a maze will work but is not going to be fast using this
      algorithm

This package is meant for you (and you should submit issues to address any
problems) if:

  • Your entities can move in any angle (i.e. an RTS)
  • Collidables are relatively sparse
  • You prefer human-looking paths to optimal paths
  • Paths will tend to have only a few nodes or be impossible
  • Some classes of objects do not collide with other classes of objects
    • For example, you want to move to attack a building and ignore any enemy
      that is in the way
  • Some paths will not collide with a small set of objects
    • For example a door that only one unit can walk through

Flags example

// define your flags by incrementing the number on the right.
// this gives you up to 63 flags. You can use an enum with [Flags]
// which subtypes long as well
long TEAM_1 = 1 << 0; // 2^0
long TEAM_2 = 1 << 1; // 2^1

var entity = new AACollidable()
{
    Position = new Vector2(50, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 10, segments: 7),
    Flags = TEAM_1
};
map.Register(entity);

var entity2 = new AACollidable()
{
    Position = new Vector2(100, 70),
    Bounds = ShapeUtils.CreateCircle(radius: 7, segments: 5),
    FLAGS = TEAM_2
};
map.Register(entity2);

var excludeIds = new HashSet<int>();
excludeIds.Add(entity.ID);

List<Vector2> path = new AAPathfinder(
        map, entity.Bounds, entity.Position,
        new Vector2(150, 70), excludeIds, TEAM_2 // ignores team 2 (i.e., entity2) -> direct path
    ).CalculatePath();

Console.WriteLine($"entity 1 at {entity.Position}");
foreach(var loc in path)
{
    Console.WriteLine($"moved entity 1 to {loc}");
}

  • .NETStandard 2.0

    • No dependencies.

This package is not used by any popular GitHub repositories.

Version History

Version Downloads Last updated
1.0.0 136 4/14/2019