Discussing pathfinding API

AgostinoSturaro commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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

najmam commented 9 years ago

@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 commented 9 years ago

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 commented 9 years ago

@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 commented 9 years ago

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

nooone commented 9 years ago

Where is it? :)

davebaol commented 9 years ago

@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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

@nooone Thanks, all done :)

davebaol commented 9 years ago

Just added hierarchical pathfinding. Updated TODO List

AgostinoSturaro commented 9 years ago

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

davebaol commented 9 years ago

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

davebaol commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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

gamemachine commented 9 years ago

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 commented 9 years ago

@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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

@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 commented 9 years ago

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 commented 9 years ago

@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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

@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 commented 9 years ago

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

davebaol commented 9 years ago

Maybe GoalController is a more appropriate name. Thoughts?

davebaol commented 9 years ago

@Nauktis It looks like there is a problem with the proposed API change and hierarchical pathfinding which needs the actual end node to convert nodes between levels, see https://github.com/libgdx/gdx-ai/blob/master/gdx-ai/src/com/badlogic/gdx/ai/pfa/HierarchicalPathFinder.java#L75

A possible (easy) solution could be to add a getActualEndNode to the GoalController interface that will be used by hierarchical pathfinding algorithm to switch between graph levels. However, this means that hierarchical pathfinder is limited to 1 node to change level.

Actually this is kinda a ugly hack that makes no sense in lots of situations because usually a goal represented by a set of nodes is based on quality criteria rather than neighborhood criteria. For example, in chess, the goal is to reach a state called “checkmate” where the opponent’s king is under attack and can’t escape. Obviously all these checkmate states are not neighbors in the graph (they are not directly connected).

This makes me hesitant.

Nauktis commented 9 years ago

@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 commented 9 years ago

@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 commented 9 years ago

Finally gdx-ai 1.5.0 has been just released :smile:

adam-law commented 8 years ago

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 commented 8 years ago

@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 commented 8 years ago

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 commented 8 years ago

@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 commented 8 years ago

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 https://github.com/libgdx/gdx-ai/issues/7#issuecomment-141370945.

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 commented 8 years ago

Great advice guys. I appreciate it. Cheers!

davebaol commented 8 years ago

Commit f5ef1a9b4601560d490ca74b26cc2ae532c6e185 should make the API slightly simpler

piotrekuczy commented 8 years ago

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 commented 8 years ago

@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 commented 8 years ago

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 commented 8 years ago

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

piotrekuczy commented 8 years ago

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 commented 8 years ago

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

piotrekuczy commented 8 years ago

i know, but why this line is good:

SmoothableGraphPath< MyNode, Vector2> smoothPath;

but this line isn't? :

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

davebaol commented 8 years ago

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

libgdx / gdx-ai

Discussing pathfinding API #7