Click here to Skip to main content
Click here to Skip to main content

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

By , 18 Feb 2014
Rate this:
Please Sign up or sign in to vote.

Table of Contents

  1. Introduction 
  2. Basic Usage
  3. Advanced Usage
  4. Conclusion
  5. Reference

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.)

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

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

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; 
   }  
}
 
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):

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

JumpPointParam jpParam = new JumpPointParam(searchGrid, true); 

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

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.) 

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:

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:

JumpPointParam jpParam = new JumpPointParam(searchGrid, true, true, true); 

 

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

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: 

JumpPointParam jpParam = new JumpPointParam(searchGrid,true,true,true, 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.

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 SetWalkableAtReset, etc. are same as StaticGrid.  

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.) 

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

To change back to loop function

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

Extendability 

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

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

Reference

History

  • 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

Woong Gyu La
Software Developer
Korea (Republic Of) Korea (Republic Of)
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[^]
 
EpWinService (Windows Service Management Solution)
https://github.com/juhgiyo/EpWinService[^]
 
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[^]
Follow on   Twitter   Google+   LinkedIn

Comments and Discussions

 
QuestionFull path list PinmemberMember 1067978827-Mar-14 10:03 
AnswerRe: Full path list PinpremiumWoong Gyu La29-Mar-14 6:05 
GeneralMy vote of 5 PinprofessionalAthari10-Sep-13 21:53 
QuestionGPL License --> nobody will use? [Edit: now MIT, yay!] [modified] PinmemberJaredThirsk19-Aug-13 19:39 
AnswerRe: GPL License --> nobody will use? PinmemberWoong Gyu La20-Aug-13 4:52 
GeneralRe: GPL License --> nobody will use? PinmemberJaredThirsk20-Aug-13 11:04 
GeneralMy vote of 4 Pinmembersam.hill8-Aug-13 6:40 
GeneralRe: My vote of 4 PinmemberWoong Gyu La8-Aug-13 12:54 
GeneralRe: My vote of 4 Pinmembersam.hill8-Aug-13 19:34 
GeneralRe: My vote of 4 PinmemberTed Goulden15-Aug-13 10:08 
GeneralRe: My vote of 4 [modified] PinmemberWoong Gyu La15-Aug-13 11:22 
GeneralRe: My vote of 4 PinmemberTed Goulden17-Aug-13 12:14 
GeneralRe: My vote of 4 PinmemberWoong Gyu La17-Aug-13 14:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140415.2 | Last Updated 18 Feb 2014
Article Copyright 2013 by Woong Gyu La
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid