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:

• https://github.com/libgdx/libgdx/pull/575
• https://github.com/libgdx/libgdx/pull/1972
• https://github.com/libgdx/libgdx/pull/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 :smile:

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

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

[davebaol]

TODO List

• [x] Move RaycastCollisionDetector and ray-related classes to a common package because now they are used by steering behaviors and pathfinding.
• [x] Add support for hierarchical pathfinding which is useful for large graphs.
• [x] Add a scheduling API to support the feature below.
• [x] 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.
• [x] 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. :smile:

[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 :construction: :construction_worker: :hammer: ). 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. :smile:

[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. :expressionless:

[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 (?)

[davebaol]

@Nauktis Yeah I moved the heuristic there because it heavily depends on the goal. I mean, each time you need to calculate a new path you have to specify the new goal. Both the heuristic and the test must know it. For example, a very simple implementation might be like that

public class MyGoalHandler implements GoalHandler<TiledNode> {
    private TiledNode endNode;

    public MyGoalHandler() {
    }

    public void setEndNode (TiledNode node) {
        this.endNode = endNode;
    }

    @Override    
    public boolean isGoal (TiledNode node) {
        return node == endNode;
    }

    @Override    
    public float estimateCost (TiledNode node) {
        return Math.abs(endNode.x - node.x) + Math.abs(endNode.y - node.y);
    }
}

Typical usage

    myGoalHandler.setEndNode(endNode);
    pathFinder.search(startNode, myGoalHandler, outPath);

[Nauktis]

Makes a lot of sense indeed. Can't wait to have it included and play with it (pathfinding to an area, get close enough to something, etc.).