Discussing pathfinding API

[AgostinoSturaro]

EDIT by davebaol

• Pathfinding TODO List
• Pathfinding wiki page (to be finished)

Hello, now that you have your own extension, maybe you can start considering an A* implementation to go together with that wonderful steering, right? :)

[davebaol]

Yeah, I'd just need 48-hours days. :)
But don't worry, I think pathfinding will be added after the next release.
For the next release I want to fix issue #2 and merge PR #4

[yigitest]

Hi,
Do you have anything in your mind about graph and data structures?
A-Star and other shortestpath algorithms are easy to implement if you have a good graph api :) I started to write one but this will take a lot of time before it’s nice and polished.

[davebaol]

@yessit
No, I have not had time to think about it. PR welcome :)

BTW, there are a few old PR in libgdx repo you might want to look into:

• Added GDX port of Slick2D's AStarPathFinder libgdx#575
• Pathfinding Implementation libgdx#1972
• Added pathfinding to AI extension libgdx#1977

[najmam]

@yessit seems like you don't have to !
https://code.google.com/p/aima-java/

The repo's description says "Java implementation of algorithms from Norvig and Russell's Artificial Intelligence - A Modern Approach 3rd Edition"... and it's released under the MIT license :)
I haven't tried the code yet but it comes with tests and lengthy documentation about data structures & procedures. And since the book is kind of a reference, I guess it has been reviewed a number of times.

I'll be integrating A* in my game soon, I'll send a PR if it's not too late by then.

[yigitest]

My idea was based on this and this. User is responsible for providing a way to access Node and Edges data. This makes the implementation a lot more simple while flexible to fit the needs of different applications.

A simple and ugly implementation to this: all the data inside Node classes

What do you think?

@pascience thanks for the heads up. They seem to have agreed on other implementations too.But they need one final push to this new extension.

[davebaol]

@pascience
aima-java API is really convoluted and doesn't use generics.

How about creating a new branch where we can discuss and share a common implementation?

[davebaol]

Ok, I'm currently working on it.
I think I'll push the new branch with pathfinding and path smoothing within the weekend.

[nooone]

Where is it? :)

[davebaol]

@nooone just pushed the new pathfinding branch 😄

Currently only A* and path smoothing are supported. Hierarchical pathfinding coming soon (hopefully).

@yessit @pascience @AgostinoSturaro
I'd like some feedback by you too. 😄

[davebaol]

TODO List

• Move RaycastCollisionDetector and ray-related classes to a common package because now they are used by steering behaviors and pathfinding.
• Add support for hierarchical pathfinding which is useful for large graphs.
• Add a scheduling API to support the feature below.
• Add support for deferred pathfinding requests by giving the pathfinder a time budget per frame. This allows us to time slice the whole process so as to cope with many requests at the same time through an asynchronous pathfinding queue which uses the message system to send the calculated path to the client.
• Extend deferred pathfinding requests to hierarchical pathfinding.

[nooone]

Looks pretty good in total. The smoothing using a RaycastCollisionDetector is pretty smart.

I have only small things to add.

• In IndexedGraph you have to remove that default constructor. It's not usable since it will result in NPEs.
• DefaultConnection looks like it's meant to be extended. Thus its fields (fromNode and toNode) should be protected.
• GraphPath looks pretty much exactly like a List or libgdx Array. I think it makes sense to have this interface, but I would add two things to it:
  • Make it Iterable, so one is able to use the result of the path finding in a simple for-loop.
  • Add a DefaultGraphPath implementation that uses an internal Array (just like TiledSmoothableGraphPath, kind of just code shifting).

[davebaol]

@nooone Thanks, all done :)

[davebaol]

Just added hierarchical pathfinding.
Updated TODO List

[AgostinoSturaro]

The class and function skeleton look fine to me. Very nice to see the way you guys work :)

[davebaol]

Thanks. Looks like hierarchical pathfinding is broken though. Working on a test to fix it.

[davebaol]

Ok, now hierarchical pathfinding is working properly. Also added a test using a hierarchical tiled map with 2 levels of nodes:

• level 0: 125x75 tiles
• level 1: 3x2 buildings

[davebaol]

• Added a scheduling API for interruptible tasks with time slice over multiple frames, see the wiki page.
• Added interruptible pathfinding with test, wiki page coming soon.

Let me know if you have any problem.

[gamemachine]

Random observer here. Been playing around with the pathfinding stuff, really like how it's well abstracted. It was really simple to just plug in an existing 3d navmesh and do pathfinding on it. I've spent hours searching for decent java pathfinding libraries, and this is absolutely the best designed one I've seen so far.

Do you anticipate the pathfinding api changing much before a release?

[davebaol]

@gamemachine
I think the API won't change much.

[gamemachine]

So I've been playing around with some approaches to path smoothing on grids. I'm using the pathfinding outside of a libgdx app on the server, so the raycasting approach wasn't really an option. I did something very similar using supercover lines as my rays.

One thing I found is that since neither approach looks ahead, you will get a decent number of paths that are not straight. A trick that fixes this for fairly minimal cost is to take the smoothed path and start raycasting from the end to the origin. Each successive raycast is end - 1 until you get a raycast that connects. The node you connect with becomes the new origin, and you start raycasting again from the end. Normally the originally smoothed path is going to be fairly short, so this extra smoothing is cheap.

[davebaol]

@gamemachine
Not sure to fully understand your reasoning. Are you saying that your approach is general enough to be part of the framework? If so, can you show the algorithm with some (pseudo)code. Of course, a pool request is welcome too. 😄

[gamemachine]

I'm working on a more refined version that takes a divide and conquer approach. I'll be using it in my own open source project so I can submit a pull request once it's done.

As for the reasoning. A* especially on a grid will often go around an obstacle even when you can draw a straight line in pixels from start to end that completely avoids the obstacle. Raycasting back while following the line forward 2 nodes at a time can't straighten this case.

Say you have a path the start is 0,0 and the end is 100,100. At 20,20 there is a straight pixel path to the end where all intersecting cells are walkable, but not at any other coordinate after that. A* didn't pick the straight path from 20,20 to the end because it wasn't the shortest path if you go by movement from node to node. The only way to straighten that path is to raycast from 20,20 to the end.

[AgostinoSturaro]

The wiki page for basic A* search seems to be absent.
Is there a work in progress somewhere?

Some small code examples would be very appreciated.
Thanks.

[davebaol]

@AgostinoSturaro
Yeah the A* page is missing and I'm not planning to write it in next few days because I'm really busy with real life at the moment (just bought a new house 🚧 👷 🔨 ). Hopefully the next month I'll have some spare time to complete the wiki.
In the meantime you can look at pathfinding tests, especially the FlatXXXX ones.
If you need help feel free to ask here, on the forum or on the libgdx irc channel.

[Nauktis]

I am using the Pathfinding api in my current project.
I'm facing a challenge and don't know if it is possible with the current api.
My target node is a non walkable node but I want to find a path to any of its connected node.
How should I go about this?

[davebaol]

@Nauktis
Hmmm... so your target node is actually a set whose nodes are specified by a certain criteria, right?
Probably the neatest way to support your requirement is to change the API in order to pass a GoalTest instance to the PathFinder.search methods in place of the endNode.
I'll look into it deeper soon (hopefully).
Ideas, alternative approaches and PR (why not?) are welcome of course. 😄

[davebaol]

Just to clarify what I mean

public interface GoalHandler<N> {

    /** Checks the given node to see if it is a goal node.
     * @param node the node to test
     * @return {@code true} if the given node is a goal node; {@code false} otherwise */
    public boolean isGoal (N node);

    /** Calculates the estimated cost to reach the goal from the given node.
     * <p>
     * This method is the heuristic function that pathfinding algorithms use to choose the node that is most likely to lead to the
     * optimal path. The notion of "most likely" depends on the heuristic implementation. If the heuristic is accurate, then the
     * algorithm will be efficient. If the heuristic is terrible, then it can perform even worse than other algorithms that don't
     * use any heuristic function such as Dijkstra.
     * @param node the node to estimate the cost for
     * @return the estimated cost */
    public float estimateCost (N node);
}

What do you think?

PS:
Any idea of a better name for the GoalHandler class? I'm not fully convinced by the Handler part. 😑

[Nauktis]

Thanks for the amazingly fast response davebaol :)
Your idea seems to allow for a lot of flexibility and is definitely addressing my need.
Any reason to have moved the heuristic in?
If you leave the heuristic out you can probably call it GoalPredicate (?)

[Nauktis]

@davebaol
I fully understand your concern. Maybe the goal should always be a node like it is the case for the moment. But the API could take an optional GoalController that would only have one method isGoodEnough(currentNode). If this method returns true, that would say the current path is good enough even though the destination node hasn't been reached. And the pathfinding would stop with the current path. Would that be a less obstructive approach?

[davebaol]

@Nauktis
Just created a new issue to keep track of the enhancement.

I think it will be postponed after 1.5.0 that should come out soon.

[davebaol]

Finally gdx-ai 1.5.0 has been just released 😄

[adam-law]

Hi,

Great work on this library. I've been able to implement it for use in my square and hex grids, where it computes the path of an object the size of a grid cell. My question is, what is the correct approach for objects larger than a grid cell (e.g. 2x2, 3x3)? Right now, larger objects "pass through" "tunnels" that are 1x1 wide, because the computation only figures in the 1x1 starting cell to the end node.

Off the top of my head, I was (naively) thinking that I would need to create different graphs based on the "master" graph, accounting for the possible entity sizes. For example, a graph for 2x2 sized entities would start from master graph's 0, 0 cell and encompass cells (0, 1), (1, 0), and (1, 1). If one of these cells is of a "blocking" type, the 2x2 graph's 0,0 node, would then be marked as "blocked". Any extraneous nodes of the 1x1 graph that don't fit into the 2x2 one, will be declared untraversable as well.

I'm hesitant to implement the (naive) idea, thinking that you might have a better one, or there is already an existing solution here that I missed.

Any advice would be appreciated :)

[davebaol]

@adam-law
You might work at the heuristic level with just one graph. If the heuristic function is somehow aware of the size of the character you're calculating the path for, you can simply return Float.POSITIVE_INFINITE when the cell cannot be traversed.
This should do the trick.

[adam-law]

Thanks for the quick reply :)

I guess you're saying that, in the heuristic, I should do the checking of the entity size, versus some information regarding size on that node? Something like the clearance algorithm? Or were you pertaining to something else? Sorry for the questions, I'm still very new to game development XD

[davebaol]

@adam-law
Yeah that's what I meant.
Keep in mind that the heuristic should be as fast as possible. So it would be advisable to precalculate the size of the passage for each node in the graph.

[entangledloops]

https://github.com/adam-law
It's quite common to perform search on a coarse grid of a larger size, and
if you find no path then refine the search to a smaller space. As for grid
alignment, that's a parameter that will never be "generally correct" for
all maps or positions, so it doesn't matter so much. You can try
re-aligning and searching again.
On Fri, Sep 18, 2015 at 9:36 AM davebaol notifications@github.com wrote:

@adam-law https://github.com/adam-law
Yeah that's what I meant.
Keep in mind that the heuristic should be as fast as possible. So it would
be advisable to precalculate the size of the passage for each node in the
graph.

—
Reply to this email directly or view it on GitHub
#7 (comment).

Stephen Dunn
http://www.entangledloops.com

Setem Technologies
http://www.setemtech.com
12 Kent Way, Suite 210
Newbury, MA 01922
ph: +1 (617) 997.0000
fx: +1 (617) 995.0890

[adam-law]

Great advice guys. I appreciate it. Cheers!

[davebaol]

Commit f5ef1a9 should make the API slightly simpler

[piotrekuczy]

Hello,

Could somebody help me how to use Path Smoothing?

( https://github.com/libgdx/gdx-ai/wiki/Path-Smoothing )

I need some code example.

[davebaol]

@piotrekuczy
Sure, you can look at this

Basically, you have to create the pathSmoother once, then call pathSmoother.smoothPath(path);
To create the pathSmoother you need an implementation of RaycastCollisionDetector which performs line of sight between nodes.

[piotrekuczy]

ok, i have this:

SmoothableGraphPath< MyNode, Vector2> smoothPath;
PathSmoother< MyNode, Vector2> pathSmoother;

and i have cannot instantiate error with this line:

smoothPath = new SmoothableGraphPath< MyNode, Vector2 >();

what is wrong?

[davebaol]

Well, my crystal ball is broken... What about showing your code and stack trace? 😃

[piotrekuczy]

my code:

SmoothableGraphPath< MyNode, Vector2> smoothPath;
PathSmoother< MyNode, Vector2> pathSmoother;
smoothPath = new SmoothableGraphPath< MyNode, Vector2 >();

console errors for line with smoothPath= new ..... :

Exception in thread "LWJGL Application" com.badlogic.gdx.utils.GdxRuntimeException: java.lang.Error: Unresolved compilation problem: 
    Cannot instantiate the type SmoothableGraphPath<MyNode,Vector2>
    at com.badlogic.gdx.backends.lwjgl.LwjglApplication$1.run(LwjglApplication.java:131)
Caused by: java.lang.Error: Unresolved compilation problem: 
    Cannot instantiate the type SmoothableGraphPath<MyNode,Vector2>
    at com.postpunkgames.SceneEditor.create(SceneEditor.java:169)
    at com.badlogic.gdx.backends.lwjgl.LwjglApplication.mainLoop(LwjglApplication.java:147)
    at com.badlogic.gdx.backends.lwjgl.LwjglApplication$1.run(LwjglApplication.java:124)

[davebaol]

Hmmm.... "Unresolved compilation problem" means that your code does not even compile correctly. You should first fix compile errors in source code.

[piotrekuczy]

i know, but why this line is good:

SmoothableGraphPath< MyNode, Vector2> smoothPath;

but this line isn't? :

smoothPath = new SmoothableGraphPath< MyNode, Vector2 >();

[davebaol]

Because SmoothableGraphPath is an interface, so you cannot instantiate it.
You have to create a concrete class which implements that interface.

[piotrekuczy]

Thank you. Now i have a problem because my graph is no grid based (like yours examples) - my nodes are a polygon vertices.
Could you help me how to implement MyRaycastCollisionDetector and MySmoothPath in my code?

This is my classes:

main game class

// pathfinding

    MyGraph mGraph;
    IndexedAStarPathFinder<MyNode> mPathFinder;
    DefaultGraphPath<MyNode> mPath;
    ManhattanDistanceHeuristic mHeuristic;

// pathsmoothing

    MyRaycastCollisionDetector raycastCollisionDetector;
    MySmoothPath smoothedPath;
    PathSmoother<MyNode, Vector2> pathSmoother;

    ...


// pathfinding

    nodes = new Array<MyNode>();
    mPath = new DefaultGraphPath<MyNode>();
    mHeuristic = new ManhattanDistanceHeuristic();

// smooth path

    smoothedPath = new MySmoothPath();
    raycastCollisionDetector = new MyRaycastCollisionDetector();
    pathSmoother = new PathSmoother<MyNode, Vector2>(raycastCollisionDetector);

MySmoothPath class

import java.util.Iterator;
import com.badlogic.gdx.ai.pfa.SmoothableGraphPath;
import com.badlogic.gdx.math.Vector2;

public class MySmoothPath implements SmoothableGraphPath<MyNode, Vector2> {

    public MySmoothPath() {
        // TODO Auto-generated constructor stub
    }

    @Override
    public int getCount() {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public MyNode get(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void add(MyNode node) {
        // TODO Auto-generated method stub

    }

    @Override
    public void clear() {
        // TODO Auto-generated method stub

    }

    @Override
    public void reverse() {
        // TODO Auto-generated method stub

    }

    @Override
    public Iterator<MyNode> iterator() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public Vector2 getNodePosition(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void swapNodes(int index1, int index2) {
        // TODO Auto-generated method stub

    }

    @Override
    public void truncatePath(int newLength) {
        // TODO Auto-generated method stub

    }

}

MyRaycastCollisionDetector class:

import com.badlogic.gdx.ai.utils.Collision;
import com.badlogic.gdx.ai.utils.Ray;
import com.badlogic.gdx.ai.utils.RaycastCollisionDetector;
import com.badlogic.gdx.math.Vector2;

public class MyRaycastCollisionDetector implements RaycastCollisionDetector<Vector2> {

    public MyRaycastCollisionDetector() {
        // TODO Auto-generated constructor stub
    }

    @Override
    public boolean collides(Ray<Vector2> ray) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean findCollision(Collision<Vector2> outputCollision, Ray<Vector2> inputRay) {
        // TODO Auto-generated method stub
        return false;
    }

}

ManhattanDistanceHeuristic class

import com.badlogic.gdx.ai.pfa.Heuristic;

public class ManhattanDistanceHeuristic implements Heuristic<MyNode> {

    public ManhattanDistanceHeuristic() {
    }

    @Override
    public float estimate(MyNode node, MyNode endNode) {
        return Math.abs(endNode.mX - node.mX) + Math.abs(endNode.mY - node.mY);
    }

}

[davebaol]

Oh for navmesh pathfinding with gdx-ai you might want to look at the open source project GdxDemo3D.

[piotrekuczy]

in this project there is no PathSmoother

[davebaol]

Well, there's no PathSmoother because that project performs path smoothing through the simple stupid funnel algorithm.

See the method calculateEdgePoints in NavMeshPointPath.java

[piotrekuczy]

I will read this, thanks. So there is no working example of PathSmoother with navmesh?

[davebaol]

Not that I know of

[implicit-invocation]

@davebaol
I used the precompiled Java code from hxDaedalus and wrote a very thin layer on top of it to provide an easy to setup 2D polygonal pathfinding.

https://github.com/implicit-invocation/jwalkable

Any chance for merging?

[assofohdz]

Polygonal pathfinding would make gdx-ai a go-to library! 👍

[dushechka]

@davebaol
I used the precompiled Java code from hxDaedalus and wrote a very thin layer on top of it to provide an easy to setup 2D polygonal pathfinding.

https://github.com/implicit-invocation/jwalkable

Any chance for merging?

So, what's up with merging? I couldn't find it in the GDX.