Currently I am working on the pathfinding for my project and i thought it could
be useful to share my work and experience and get some feedback.
I decided to use a grid for my RTS because it is the most common way for pathfinding in this genre.
As you can see in the picture i split the map into 4 submaps and each of the submap can have a different
count of cells in the grid. This is useful because a ground map need to be more detailed than a map for buildings.
This Submaps have a grid and (planed for the future) a quad tree with obstacles for the steering behaviours.
Steering behaaviours are important because with my pathfinding I only find a way arround trees, cliffs and buildings but
I ignore other units. Therefore the steering behaviours have the task to find a way thorugh the units which
stands on the way the pathfinding found. Because of this the steering behaviours need information where
obstacles block the way. I thought of a QuadTree because it alows me to abstract the obstacles
instead of creating one obstacle for every blocked cell in my grid.
(Like in this picture: http://img6.imagebanana.com/img/8ittl6ep/pathing3.png)
The Grid and different unit sizes
In my grid i need to solve two problems:
-to handle different unit sizes
-to handle different pathing layer
To handle the unit sizes I give the non blocked fields a value between 1 and 5.
1 means that a unit with a size of 1 field can pass the way and a 5 that a unit with a diameter of 5
can path this way.
Every field gets the value by checking how large we could expand the rectangle:
(explained here: http://aigamedev.com/open/tutorial/clearance-based-pathfinding/)
This is useful because it is easy to change blocking fields and to recalculate the size for the units.
I can simply start at the bottom right position I want to change and than always determine the new value by
looking at the right/bottom/diagonal neighbour of this field. (if it exists)
The pathingmap has the feature to calculate all unitsize values for the fields and than to activate a mode in which
all changes in the pathingmap directly affect the stored unit sizes. This could speed up the work with the pathingmap in an editor.
To deal with different pathing layers i use negative values like -1,-2,-4,-8 which each
represent an own layer. So a value like -3 shows that a cell is blocked by two layers.
This is important, for example a building blocks some cells, later a trigger says that no one should be
allowed to build in the whole area and after this the building is destroyed. If we would only use one
layer you could build at the same position after the construction was removed.
Jump Point Search
I read about JPS, a way to improve the performance of an A* search.
Short explanation: You search for special points in your grid (called Jump Points).
This points are mostly the edges of obstacles and the special thing is that you are able
to ignore all the other points in the map. To detect jump points there exists the so called prunning rules.
Here is an image how the jump points look like:
For detailed information read: http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/#3JumpPointSearch
Here are some screenshots of my current work: (The Jump Point Search and normal A* are a little bit buggy atm)
Look how the algorithm finds another way because the new unit is to fat to pass through the walls.
If someone want to help me to improve the maps/algorithm I can upload my source code but I want to make
clear that it is not the finished code.
Interresting read, thanks for sharing!
Looks like nice work. The A* jump points sounds very much like using a node graph on top of the grid.
@zarch said:
The A* jump points sounds very much like using a node graph on top of the grid.
The "grid" should technically also always be a node graph and ideally you don't really keep nodes in memory that have no special data / generate them from data on the fly.
Good post!
@normen said:
The "grid" should technically also always be a node graph ..
Yes, this. I have something similar. Basically I start out with a large potential grid, then sample each unit point. The points are sampled against the navmesh that is generated for the level, and then a grid (built of nodes) is created. All at startup.
Grids are nice for RTS because often the grid will change when buildings are built, and it is faster to block cells (by removing nodes) than it is to regenerate the navmesh.
i done grid based pathfind here for a 3d grid:
http://hub.jmonkeyengine.org/groups/user-code-projects/forum/topic/easyfinding-pathfinding-class/
you can look at source. Its still not done, but it works.
i do not have Jump Point Search here, only grid system
maybe something from this code could help 
Hasn’t everybody done some a* at some time? 
http://hub.jmonkeyengine.org/groups/user-code-projects/forum/topic/pathfinding-system-with-test-environment/
Okay, I actualy used a graph only for the Jump Point search :roll:
But for me it doesnt sound like a huge improvement to generate the nodes at the beginning.
This would mean that creating Objects which will not be needed in the future is slow/needs to much memory…
I think about data structures like lists which use tons of objects in the background…
Or am I confused?
Hm,
Atm I dont find the bug in the A* (wtf?) and I dont know how I could improve the speed of the JPS.
Because of this it doesnt look like I will make any progress in the next days so here is my code:
http://www.file-upload.net/download-4312632/JMonkey-RTS-Pathfinding-0.01.rar.html
It would be nice if some take a look at it.
(Controls:
Set the start and end point via right and left mouse click, change the unit size with the number keys and to switch between the way of the A* and JPS press the hotkeys A and J)
Maybe here again my question: isn’t a graph component an fundamental element of a game framework and shouldn’t JME include some basic graph datastructure plus some common algorithms for path finding etc? Im not sure if I missed something here?
<cite>@simon.heinen said:</cite> Maybe here again my question: isn't a graph component an fundamental element of a game framework and shouldn't JME include some basic graph datastructure plus some common algorithms for path finding etc? Im not sure if I missed something here?
jME3 is used for everything from business apps and university research projects to android. Tetris games, skateboarding games, first person shooters, MMOs, TCGs, Block Worlds, etc.
Graph components are only relevant to some of those games, and even for those games their requirements can be widely different.
Where is the gain from integrating a graph component into jme when people can use a 3rd party graphing library (or write their own graphing) that best suits their needs?
All data is technically a graph. A generic graph data structure is only rarely necessary… and in 99% of those cases, an adjacency function would have worked just fine.
I’m probably one of the biggest “graph” guys you will meet and I still don’t see it as a necessary part of a game engine.
And by the way, if you choose to go the adjacency function route you can look at my fstep package:
http://fgraph.org/
…which is essentially a traversal framework based on formalized adjacency functions. I keep meaning to check in an AStar traverser but the priority-based traversers are only one step away or so.