juhgiyo/eppathfinding.cs

A jump point search algorithm for grid based games in C#

EpPathFinding.cs

A jump point search algorithm for grid based games in C#

For 3D Environment

You may take a look at EpPathFinding3D.cs

Introduction

This project was started after I was inspired by PathFinding.js by Xueqiao Xu and the article by D. Harabor. It comes along with a demo to show how the agorithm execute as similar to Xueqiao Xu's Online Demo.

Unity Integration Guide

Copy EpPathFinding.cs\PathFinder folder intto your Unity Project's Assets folder. Then within the script file, you want to use the EpPathFinding.cs, just add using EpPathFinding.cs; namespace at the top of the file, and use it as the guide below.

(If you have a problem when compiling, please refer to Unity Forum)

Also EpPathFinding.cs depends on C5.

Pre-compiled C5.dll for Unity is included in EpPathFinding3D.cs\PathFinder\UnityC5 folder.

(Please refer to C5 on Unity3D, if you have any dependency issue with C5.)

Nuget Package

Nuget Package

Basic Usage

The usage and the demo has been made very similar to PathFinding.js for ease of usage.

You first need to build a grid-map. (For example: width 64 and height 32):

BaseGrid searchGrid = new StaticGrid(64, 32);

By default, every nodes in the grid will NOT allow to be walked through. To set whether a node at a given coordinate is walkable or not, use the SetWalkableAt function.

For example, in order to set the node at (10 , 20) to be walkable, where 10 is the x coordinate (from left to right), and 20 is the y coordinate (from top to bottom):

searchGrid.SetWalkableAt(10, 20, true);
 
// OR
 
searchGrid.SetWalkableAt(new GridPos(10,20),true);  

You may also use in a 2-d array while instantiating the StaticGrid class. It will initiate all the nodes in the grid with the walkability indicated by the array. (true for walkable otherwise not walkable):

bool [][] movableMatrix = new bool [width][];
for(int widthTrav=0; widthTrav< 64; widthTrav++)
{
   movableMatrix[widthTrav]=new bool[height];
   for(int heightTrav=0; heightTrav < 32;  heightTrav++)
   { 
      movableMatrix[widthTrav][heightTrav]=true; 
   }  
}

Grid searchGrid = new StaticGrid(64,32, movableMatrix);

In order to search the route from (10,10) to (20,10), you need to create JumpPointParam class with grid and start/end positions. (Note: both the start point and end point must be walkable):

GridPos startPos=new GridPos(10,10); 
GridPos endPos = new GridPos(20,10);  
JumpPointParam jpParam = new JumpPointParam(searchGrid,startPos,endPos ); 

You can also set/change the start and end positions later. (However the start and end positions must be set before the actual search):

JumpPoinParam jpParam = new JumpPointParam(searchGrid);
jpParam.Reset(new GridPos(10,10), new GridPos(20,10)); 

To find a path, simply run FindPath function with JumpPointParam object created above:

List<GridPos> resultPathList = JumpPointFinder.FindPath(jpParam); 

JumpPointParam class can be used as much as you want with different start/end positions unlike PathFinding.js:

jpParam.Reset(new GridPos(15,15), new GridPos(20,15));
resultPathList = JumpPointFinder.FindPath(jpParam); 

Advanced Usage

Find the path even the end node is unwalkable

When instantiating the JumpPointParam, you may pass in additional parameter to make the search able to find path even the end node is unwalkable grid:

Note that it automatically sets to ALLOW as a default when the parameter is not specified.

JumpPointParam jpParam = new JumpPointParam(searchGrid,EndNodeUnWalkableTreatment.ALLOW);

If iAllowEndNodeUnWalkable is DISALLOW the FindPath will return the empty path if the end node is unwalkable:

JumpPointParam jpParam = new JumpPointParam(searchGrid,EndNodeUnWalkableTreatment.DISALLOW);   

DiagonalMovement.Always (Cross Adjacent Point)

In order to make search able to walk diagonally across corner of two diagonal unwalkable nodes:

JumpPointParam jpParam = new JumpPointParam(searchGrid,EndNodeUnWalkableTreatment.ALLOW,DiagonalMovement.Always);   

DiagonalMovement.IfAtLeastOneWalkable (Cross Corner)

When instantiating the JumpPointParam, to make the search able to walk diagonally when one of the side is unwalkable grid:

JumpPointParam jpParam = new JumpPointParam(searchGrid,EndNodeUnWalkableTreatment.ALLOW,DiagonalMovement.IfAtLeastOneWalkable);   

DiagonalMovement.OnlyWhenNoObstacles

To make it unable to walk diagonally when one of the side is unwalkable and rather go around the corner:

JumpPointParam jpParam = new JumpPointParam(searchGrid,EndNodeUnWalkableTreatment.ALLOW,DiagonalMovement.OnlyWhenNoObstacles);   

DiagonalMovement.Never

To make it unable to walk diagonally:

// Special thanks to Nil Amar for the idea!
JumpPointParam jpParam = new JumpPointParam(searchGrid,EndNodeUnWalkableTreatment.ALLOW,DiagonalMovement.Never);   

Heuristic Functions

The predefined heuristics are Heuristic.EUCLIDEAN (default), Heuristic.MANHATTAN, and Heuristic.CHEBYSHEV.

To use the MANHATTAN heuristic:

JumpPointParam jpParam = new JumpPointParam(searchGrid,EndNodeUnWalkableTreatment.ALLOW, DiagonalMovement.Always, Heuristic.MANHATTAN); 

You can always change the heuristics later with SetHeuristic function:

jpParam.SetHeuristic(Heuristic.MANHATTAN);

Dynamic Grid

For my grid-based game, I had much less walkable grid nodes than un-walkable grid nodes. So above StaticGrid was wasting too much memory to hold un-walkable grid nodes. To avoid the memory waste, I have created DynamicGrid, which allocates the memory for only walkable grid nodes.

(Please note that there is trade off of memory and performance. This degrades the performance to improve memory usage.)

BaseGrid seachGrid = new DynamicGrid();  

You may also use a List of walkable GridPos, while instantiating the DynamicGrid class. It will initiate only the nodes in the grid where the walkability is true:

List<GridPos> walkableGridPosList= new List<GridPos>();
for(int widthTrav=0; widthTrav< 64; widthTrav++)
{
   movableMatrix[widthTrav]=new bool[height];
   for(int heightTrav=0; heightTrav < 32;  heightTrav++)
   {
      walkableGridPosList.Add(new GridPos(widthTrav, heightTrav));
   }
}

BaseGrid searchGrid = new DynamicGrid(walkableGridPosList);  

Rest of the functionality like SetWalkableAt, Reset, etc. are same as StaticGrid.

Dynamic Grid With Pool

In many cases, you might want to reuse the same grid for next search. And this can be extremely useful when used with PartialGridWPool, since you don't have to allocate the grid again.

NodePool nodePool = new NodePool();
BaseGrid seachGrid = new DynamicGridWPool(nodePool);  

Rest of the functionality like SetWalkableAt, Reset, etc. are same as DynamicGrid.

Partial Grid With Pool

As mentioned above, if you want to search only partial of the grid for performance reason, you can use PartialGridWPool. Just give the GridRect which shows the portion of the grid you want to search within.

NodePool nodePool = new NodePool();
...
BaseGrid seachGrid = new PartialGridWPool(nodePool, new GridRect(1,3,15,30);  

Rest of the functionality like SetWalkableAt, Reset, etc. are same as DynamicGridWPool.

IterationType

You may use recursive function or loop function to find the path. This can be simply done by setting IterationType flag in JumpPointParam:

Note that the default is IterationType.LOOP, which uses loop function.

// To use recursive function
JumpPointParam jpParam = new JumpPointParam(...);
jpParam.IterationType = IterationType.RECURSIVE;  

To change back to loop function

// To change back to loop function 
jpParam.IterationType = IterationType.LOOP; 

Extendability

You can also create a sub-class of BaseGrid to create your own way of Grid class to best support your situation.

License

The MIT License

Copyright (c) 2013 Woong Gyu La <[email protected]>

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

eppathfinding.cs's Issues

Suggestion: add weights to each position

For pathfinding over uneven surfaces (swamp vs tiled roads) it would be useful to assign weights to positions, where 0 = blocked, and any number higher= easier to traverse.
e.g. wall: 0, swamp=0.3f, road=1.0f

Similar to https://github.com/RonenNess/Unity-2d-pathfinding that supposed boolean (passable/non-passable) or weighed (float)

AStarFinder on serialized foreach is faster than parallel.foreach

i used a stopwatch and i saw that.any explanation ?

A horizontal path with a hole in the middle is not blocked

Hi, I believe I found a bug.
The scenario is simple: a horizontal walking path with a hole in the middle ([0,0],[1.0].[2.0].[4.0] when trying to get from [0,0] to [4,0]).
I expect the algorithm to reach [2,0] and then get stuck, but that's not what happens.
It gets to [2,0], and then in JumpPointFinder.jumpLoop under line 524, since dy is 0 the second condition passes (it checks the current position) and then it junps to [3,0] even though it's not walkable.
I haven't checked but I'm guessing a vertical line would have the same issue (only with the first condition and not the second).

Here's an Nunit test that reproduces the issue:

    [TestCase(5,5, 0,0, 4,0,    0,0, 1,0, 2,0, 4,0, Result = false)]
    public bool FailedPathTest(int width, int height, int fromX, int fromY, int toX, int toY, params int[] walkablePoints)
    {
        bool[][] matrix = getGrid(width, height, walkablePoints);

        StaticGrid grid = new StaticGrid (width, height, matrix);
        JumpPointParam input = new JumpPointParam (grid, new GridPos(fromX, fromY), new GridPos(toX, toY), false, true, false);
        var cells = JumpPointFinder.FindPath (input);
        return cells.Count > 0;
    }

    private bool[][] getGrid(int width, int height, params int[] walkablePoints)
    {
        bool[][] array = new bool[width][];

        for (int x = 0; x < width; x++)
        {
            array[x] = new bool[height];
        }

        for (int pointIndex = 0; pointIndex < walkablePoints.Length; pointIndex += 2)
        {
            int x = walkablePoints[pointIndex];
            int y = walkablePoints[pointIndex + 1];
            array[x][y] = true;
        }
        return array;
    }

AStarFinder in Unity (not contains System.Threading.Tasks;)

AStarFinder line78 (Parallel.ForEach(neighbors, neighbor =>)

Parallel is not exist

[not an issue]

Hey mate.i would like to present to you our Thesis ,based on your algorithm.take a shot ;)
https://github.com/k-aGv/industrial
1 to 5 vehicles must move all the loads to one unique exit.play with it and tell me your opinion

thanks for your algorithms!seems really fast!

disallow diagonal movement

how to implement only horizontal and vertical movement?

OutOfMemory / StackOverflow when using DiagonalMovement.Never

Trying to find a path from green box to red box causes OutOfMemoryException for Loop implementation or StackOverflowException for Recursive implementation and JumpPointSearchParam.DiagonalMovement = DiagonalMovement.Never

Grid size is 7 columns and 11 rows.

Returning Failed Path

Hey I found that the AStarFinder was returning paths the lead to... nowhere in particular. I'm assuming what happened was the finder found no suitable paths, and simply returned the path back from the most recently searched node.

My solution to this problem was to change this:

if (openList.Count == 0) return Node.Backtrace(node);

...to...

if (openList.Count == 0 && node == endNode) return Node.Backtrace(node);

Not sure if that fits what you were aiming for, but it makes it infinitely more useful to me.

I would like to change the size of the node to a number other than 1.

I would like to change the size of the node to a number other than 1.

Now, 1 node finding the paths.
but i want to finding 4 size of the node finding path

JumpPointFinder.GetFullPath(...) is broken.

Instead of returning a full path, as of the latest version from Nuget JumpPointFinder.GetFullPath(...) only returns the jump points. This was tested thoroughly in my project, and copying the code from the following older commit directly into my project fixed the problem:
a40f199

Direct link to the problem function here:
https://github.com/juhgiyo/EpPathFinding.cs/blob/master/EpPathFinding.cs/EpPathFinding.cs/PathFinder/JumpPointFinder.cs#L157

GetFullPath returns a list with the first node wrong and jumps corners and changes input list

BaseGrid searchGrid = new StaticGrid(myWidth, myHeight);

for (int x = 0; x < myWidth; x++)
    for (int z = 0; z < myHeight; z++)
        searchGrid.SetWalkableAt(x, z, true);

var staticlyCachedJpParam = new JumpPointParam(searchGrid, false, false);

GridPos from = new GridPos(61, 73);
GridPos to = new GridPos(67, 98);
staticlyCachedJpParam.Reset(from, to);

List<GridPos> pathTurns = JumpPointFinder.FindPath(staticlyCachedJpParam);
List<GridPos> fullPath = JumpPointFinder.GetFullPath(pathTurns);

fullPath now has the following elements (67,79) (62, 74) (63,75) (64,76)... and then etc in "correct order", which has three problems:

1. The first node is wrong
2. It didnt take in consideration iCrossCorner = false
3. It also changes the input list routeFound, which is kinda wierd!

Other than that thanks for the algorithm. : )

Split library from demo and publish nuget package

It would be really great if you could:

1. Separate the path finding code from the demo so the project for the library can easily be included in other solutions as a library.
2. Publish a nuget package.

Thanks for the project!

change from struct to class

@juhgiyo Do you remember why you changed GridPos and GridRect from struct to class? Back then the commit said something about iOS compliance. Have you ever checked the performance impact?

Or was it because struct is not nullable and you wanted to use GridPos??

a40f199

GetFullPath merging old array with fullpath array and return redundant elements.

DEaDA@9750114