15,177,588 members
Articles / Game Development
Article
Posted 6 Aug 2013

95.5K views
4.5K downloads
98 bookmarked

# EpPathFinding.cs- A Fast Path Finding Algorithm (Jump Point Search) in C# (grid-based)

Rate me:
4.82/5 (46 votes)
1 Jul 2015MIT5 min read
A jump point search algorithm for grid based games in C#

## Introduction

I was working on my grid-based game in C#, and I needed a fast path-find algorithm for my game AI. While I was searching for a good algorithm (since I was not satisfied with A* or Dijkstra), I've found a great article (jump point search) by D. Harabor and a JavaScript implementation by Xueqiao Xu. And I came up with an idea, "Why not for C#?" So here it is! EpPathFinding.cs!

EpPathFinding.cs works very similar to PathFinding.js.

(If you are interested in more detail of the jump point search algorithm and the original JavaScript implementation, please see D. Harabor's article and Xueqiao Xu's implementation.)

## Unity Integration Guide

Add `EpPathFinding.cs\PathFinder `folder to 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)

## Basic Usage

The usage and the demo have 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):

C#
`BaseGrid searchGrid = new StaticGrid(64, 32);   `

By default, every node 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):

C#
```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 `Static<code>Grid `class. It will initiate all the nodes in the grid with the walkability indicated by the array. (`true `for walkable otherwise not walkable):

C#
```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;
}
}

BaseGrid 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):

C#
```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):

C#
```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:

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

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

C#
```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 true as a default when the parameter is not specified.)

C#
`JumpPointParam jpParam = new JumpPointParam(searchGrid, true); `

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

C#
`JumpPointParam jpParam = new JumpPointParam(searchGrid, false); `

### Cross Corners

When instantiating the `JumpPointParam`, you may pass in additional parameters to make the search able to walk diagonally when one of the side is unwalkable grid:

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

C#
`JumpPointParam jpParam = new JumpPointParam(searchGrid,true,true);   `

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

C#
`JumpPointParam jpParam = new JumpPointParam(searchGrid,true,false);   `

### Cross Adjacent Point

When instantiating the `JumpPointParam`, you may pass in additional parameter to indicate specific strategies to use

(Note that this option will be ignored if the `CrossCorner `option is false.)

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

C#
`JumpPointParam jpParam = new JumpPointParam(searchGrid, true, true, true); `

To make it unable to walk diagonally across two diagonal unwalkable corners:

C#
`JumpPointParam jpParam = new JumpPointParam(searchGrid, true, true, false);   `

### Heuristic Functions

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

To use the `MANHATTAN` heuristic function:

C#
`JumpPointParam jpParam = new JumpPointParam(searchGrid,true,true,true, Heuristic.MANHATTAN); `

You can always change the heuristics later with `SetHeuristic `function:

C#
`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.)

C#
`BaseGrid seachGrid = new DynamicGrid();   `

You may also use a `List` of walkable `GridPos`, while instantiating the `Dynamic<code>Grid `class. It will initiate only the nodes in the grid where the walkability is `true`:

C#
```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.

C#
```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 `with/without `DynamicGridWPool`. Just give the `GridRect `which shows the portion of the grid you want to search within.

C#
```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.

### UseRecursive

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

(Note that the default is false, which uses loop function.)

C#
```// To use recursive function
JumpPointParam jpParam = new JumpPointParam(...);
jpParam.UseRecursive = true;  ```

To change back to loop function

C#
```// To change back to loop function
jpParam.UseRecursive = false; ```

## Conclusion

Most of functionality and work of EpPathFinding.cs project was originally from D. Harabor's article and PathFinding.js, so all the hard work and contribution should go to D. Harabor and Xueqiao Xu. The reason I am presenting this is in a hope of being helpful to someone who might need this algorithm in C#.

## History

• 07.01.2015: - Advanced usage updated again.
• 02.18.2014: - Advanced usage updated
• 08.21.2013: - Re-distributed under MIT License
• 08.20.2013: - Article updated with "DynamicGrid"
• 08.19.2013: - Source updated with a bug fix. (Thanks to Jacek Gajek)
• 08.18.2013: - Source updated with a bug fix. (Thanks to  Ted Goulden and sam.hill
• 08.07.2013: - Source updated
• 08.06.2013: - Submitted the article

## License

This article, along with any associated source code and files, is licensed under The MIT License

## About the Author

 Software Developer United States
Woong Gyu La had been working as a software developer for over 8 years.
His personal interests are improving his personal projects,

EpLibrary (Visual C++ Utility Library)
https://github.com/juhgiyo/EpLibrary[^]

EpOraLibrary (Oracle OCI Wrapper Library for Visual C++)
https://github.com/juhgiyo/EpOraLibrary[^]

EpServerEngine (Visual C++ WinSock Server/Client Engine)
https://github.com/juhgiyo/EpServerEngine[^]

And other projects can be found at
https://github.com/juhgiyo?tab=repositories[^]

Finally, my other articles can be found at
http://www.codeproject.com/Articles/juhgiyo#articles[^]

You can contact me at juhgiyo@gmail.com[^]

## Comments and Discussions

 First Prev Next
 No diagonal path Member 1451579125-Dec-19 3:16 Member 14515791 25-Dec-19 3:16
 Clean and ready to upgrade for the needs of your project Tkangal8-Mar-17 6:35 Tkangal 8-Mar-17 6:35
 Result path reverso1322-Sep-16 1:57 reverso13 22-Sep-16 1:57
 Re: Result path Chris La22-Sep-16 3:13 Chris La 22-Sep-16 3:13
 uploading map Member 1093836210-Dec-14 21:16 Member 10938362 10-Dec-14 21:16
 Full path list Member 1067978827-Mar-14 11:03 Member 10679788 27-Mar-14 11:03
 Re: Full path list Chris La29-Mar-14 7:05 Chris La 29-Mar-14 7:05
 Hi, You can simply get full path by adding and calling below function with the route(cue points), you found. C#Copy Code ```... m_routeList = JumpPointFinder.FindPath(jpParam); m_fullRouteList= GetFullPath(m_routeList); ... List GetFullPath(List routeList) { List consecutiveGridList=new List(); if(routeList.Count>1) consecutiveGridList.Add(routeList[0]); for(int routeTrav=0; routeTrav < routeList.Count-1;routeTrav++) { GridPos fromGrid=routeList[routeTrav]; GridPos toGrid=routeList[routeTrav+1]; int dX = toGrid.x-fromGrid.x; int dY = toGrid.y-fromGrid.y; if(dX!=0 && dY!=0) // diagonal move { while(fromGrid!=toGrid) { fromGrid.x+=(dX/Math.Abs(dX)); fromGrid.y+=(dY/Math.Abs(dY)); consecutiveGridList.Add(new GridPos(fromGrid.x,fromGrid.y)); } } else if(dX==0) // horizontal move { while(fromGrid!=toGrid) { fromGrid.y+=(dY/Math.Abs(dY)); consecutiveGridList.Add(new GridPos(fromGrid.x,fromGrid.y)); } } else // vertical move { while(fromGrid!=toGrid) { fromGrid.x+=(dX/Math.Abs(dX)); consecutiveGridList.Add(new GridPos(fromGrid.x,fromGrid.y)); } } consecutiveGridList.Add(new GridPos(toGrid)); } return consecutiveGridList; }```
 My vote of 5 Athari10-Sep-13 22:53 Athari 10-Sep-13 22:53
 GPL License --> nobody will use? [Edit: now MIT, yay!] JaredThirsk19-Aug-13 20:39 JaredThirsk 19-Aug-13 20:39
 Re: GPL License --> nobody will use? Chris La20-Aug-13 5:52 Chris La 20-Aug-13 5:52
 Re: GPL License --> nobody will use? JaredThirsk20-Aug-13 12:04 JaredThirsk 20-Aug-13 12:04
 Re: GPL License --> nobody will use? David Jeske26-Oct-14 0:25 David Jeske 26-Oct-14 0:25
 My vote of 4 sam.hill8-Aug-13 7:40 sam.hill 8-Aug-13 7:40
 Re: My vote of 4 Chris La8-Aug-13 13:54 Chris La 8-Aug-13 13:54
 Re: My vote of 4 sam.hill8-Aug-13 20:34 sam.hill 8-Aug-13 20:34
 Re: My vote of 4 Ted Goulden15-Aug-13 11:08 Ted Goulden 15-Aug-13 11:08
 Re: My vote of 4 Chris La15-Aug-13 12:22 Chris La 15-Aug-13 12:22
 Re: My vote of 4 Ted Goulden17-Aug-13 13:14 Ted Goulden 17-Aug-13 13:14
 Re: My vote of 4 Chris La17-Aug-13 15:19 Chris La 17-Aug-13 15:19
 Last Visit: 31-Dec-99 19:00     Last Update: 26-Jan-22 2:18 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.