Skip to content
master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

A 2D A* (A Star) algorithm for C#

Travis (.com) branch NuGet

The world is represented by a WorldGrid that is essentially a matrix of the C# short data type. A value of 0 indicates the cell is closed / blocked. Any other number indicates the cell is open and traversable. It is recommended to use 1 for open cells as numbers greater and less than 0 may be used to apply penalty or priority to movement through those nodes in the future.

The WorldGrid can be indexed via either:

  1. The provided Position struct where a row represents the vertical axis and column the horizontal axis (Similar to indexing into a matrix Prc).

  2. The C# Point struct that operates like a cartesian co-ordinate system where X represents the horizontal axis and Y represents the vertical axis (Pxy).

Paths can be found using either Positions (matrix indexing) or Points (cartesian indexing).

Example usage

PathingExample

   var pathfinderOptions = new PathFinderOptions { 
      PunishChangeDirection = true,
      UseDiagonals = false, 
   };

   var tiles = new short[,] {
      { 1, 0, 1 },
      { 1, 0, 1 },
      { 1, 1, 1 },
   };

    var worldGrid = new WorldGrid(tiles);
    var pathfinder = new PathFinder(worldGrids, pathfinderOptions);
    
    // The following are equivalent:
    
    // matrix indexing
    Position[] path = pathfinder.FindPath(new Position(0, 0), new Position(0, 2));
    
    // point indexing
    Point[] path = pathfinder.FindPath(new Point(0, 0), new Point(2, 0));

Options

  • Allowing / restricting diagonal movement
  • A choice of heuristic (Manhattan, MaxDxDy, Euclidean, Diagonal shortcut)
  • The option to punish direction changes.
  • A search limit to short circuit the search

Changes from 0.1.x to 1.0.0

  • The world is now represented by a WorldGrid that uses shorts internally instead of bytes
  • If no path is found, the algorithm now reports an empty array instead of null
  • Moved out of the AStar.Core namespace into simply AStar
  • Replaced former Point class with the new Position class that uses Row / Column instead of X / Y to avoid confusion with cartesian co-ordinates
  • Implemented support for Point class indexing and pathing which represent a traditional cartesian co-ordinate system
  • Changed path from List to Array and changed type from PathFinderNode to Position or Point
  • Reversed the order of the returned path to start at the start node
  • Rationalised and dropped buggy options (heavy diagonals)

About

A 2D A Star (A*) pathfinding implementation in C# focused on ease of use

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages