xaguzman / pathfinding Goto Github PK

Java pathfinding framework.

License: Apache License 2.0

Java 100.00%

pathfinding-library gamedev-tool libgdx java

pathfinding's Introduction

pathfinding - APACHE LICENSE 2.0

A java pathfinding library meant to be used for games. It is generic enough to be used in different kind of graphs (though, right now it only has implementation for grid graphs).

It was heavily inspired by this javascript library. Code initially was adapted, then some modifications were made.

This library works with Libgdx's html5 backend, it was even used in my #1GAM january entry.

Current versions:

0.2.6

Installing

The library has been uploaded to sonatype oss repository. If you are using libgdx you can install it via graddle adding this dependency to your core project:

compile "com.github.xaguzman:pathfinding:0.2.6"

There's also the gdx-bridge extension to easily get pathfinding features in your game directly from your tmx maps.

Intro

The library works on a bunch of interfaces:

NavigationNode: this basically just represents a node of a graph. contains some getters and setters meant for navigation. Right now, only implementation is GridCell
NavigationGrap: a group of navigation nodes. Right now, only implementation is NavigationGrid
PathFinder: the implementation for the pathfinding algorithm, current options are:
- AStarFinder
- AStarGridFinder
- JumpPointFinder
- ThetaStarFinder
- ThetaStarGridFinder

Finders are fed with so called PathFinderOptions, which determine how the pathfinding will work (allowing diagonal movement, for example).

How to use

You need to create a graph. Be aware the the NavigationGrid class, expects a bidimensional array of GridCell stored as [x][y]

//these should be stored as [x][y]
GridCell[][] cells = new GridCell[5][5];
	
//create your cells with whatever data you need
cells = createCells();
	
//create a navigation grid with the cells you just created
NavigationGrid<GridCell> navGrid = new NavigationGrid(cells);

Now, you need a finder which can work on your graph.

//create a finder either using the default options
AStarGridFinder<GridCell> finder = new AStarGridFinder(GridCell.class);
	
//or create your own pathfinder options:
GridFinderOptions opt = new GridFinderOptions();
opt.allowDiagonal = false;
	
AStarGridFinder<GridCell> finder = new AStarGridFinder(GridCell.class, opt);

Once you have both, a graph and a finder, you can find paths within your graph at any time.

List<GridCell> pathToEnd = finder.findPath(0, 0, 4, 3, navGrid);

That's pretty much all there is to using the library.

pathfinding's People

Contributors

Stargazers

Watchers

pathfinding's Issues

add clearance support for grid-based pathfinding

Clearance is the way to deal with agents bigger than one grid cell.

Here is a good article, in case of : https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/

Load larger maps (700k)

Hello,

First, great job! I'm using it for a while not and its awesome. Thanks!

Using a 172k map file, with some layers, works fine.

Now i have a bigger map (700~k), and i need to load it, but it crashes due to out of memory.

com.badlogic.gdx.utils.GdxRuntimeException: com.badlogic.gdx.utils.GdxRuntimeException: Couldn't load asset: maps/mapFloors.tmx
at com.badlogic.gdx.assets.AssetManager.handleTaskError(AssetManager.java:576)
at com.badlogic.gdx.assets.AssetManager.update(AssetManager.java:377)
Caused by: com.badlogic.gdx.utils.GdxRuntimeException: Couldn't load asset: maps/mapFloors.tmx
at com.badlogic.gdx.assets.AssetLoadingTask.handleAsyncLoader(AssetLoadingTask.java:139)
at com.badlogic.gdx.assets.AssetLoadingTask.update(AssetLoadingTask.java:90)
at com.badlogic.gdx.assets.AssetManager.updateTask(AssetManager.java:501)
at com.badlogic.gdx.assets.AssetManager.update(AssetManager.java:375)
at com.riot.game.RiotGame.render(RiotGame.java:65)
at com.badlogic.gdx.backends.android.AndroidGraphics.onDrawFrame(AndroidGraphics.java:459)
at android.opengl.GLSurfaceView$GLThread.guardedRun(GLSurfaceView.java:1527)
at android.opengl.GLSurfaceView$GLThread.run(GLSurfaceView.java:1244)
Caused by: com.badlogic.gdx.utils.GdxRuntimeException: java.lang.OutOfMemoryError
at com.badlogic.gdx.utils.async.AsyncResult.get(AsyncResult.java:46)
at com.badlogic.gdx.assets.AssetLoadingTask.handleAsyncLoader(AssetLoadingTask.java:137)
Caused by: java.lang.OutOfMemoryError
at org.xguzm.pathfinding.util.ObjectIntMap.(ObjectIntMap.java:80)
at org.xguzm.pathfinding.util.ObjectIntMap.(ObjectIntMap.java:54)
at org.xguzm.pathfinding.grid.GridCell.(GridCell.java:20)
at org.xguzm.pathfinding.gdxbridge.NavTmxMapLoader.loadNavigationLayer(NavTmxMapLoader.java:62)
at org.xguzm.pathfinding.gdxbridge.NavTmxMapLoader.loadTileLayer(NavTmxMapLoader.java:43)
at com.badlogic.gdx.maps.tiled.TmxMapLoader.loadTilemap(TmxMapLoader.java:213)
at com.badlogic.gdx.maps.tiled.TmxMapLoader.loadAsync(TmxMapLoader.java:110)
at com.badlogic.gdx.maps.tiled.TmxMapLoader.loadAsync(TmxMapLoader.java:42)
at com.badlogic.gdx.assets.AssetLoadingTask.call(AssetLoadingTask.java:74)
at com.badlogic.gdx.assets.AssetLoadingTask.call(AssetLoadingTask.java:34)
at com.badlogic.gdx.utils.async.AsyncExecutor$2.call(AsyncExecutor.java:58)

As i can see, the AssetManger can load the map, but at some point it cant handle all layers and tiles.

After some research, i didnt find any topic about big map files in Libgdx or here. Do you know any method for handling bigger maps? Do i need to break it? (My problem is that this current map has only the top layer (floor), and its gonna have several floors.

TiledMapTileLayer cannot be cast to NavigationTiledMapLayer

Hello, and thank you for your project !

I have an issue using your astar algorithm with my TiledMap. I basically used the code you give in your exemple :

TiledMap map = new NavTmxMapLoader().load(level.file);

AStarGridFinder<GridCell> finder = new AStarGridFinder<GridCell>(GridCell.class);

NavigationTiledMapLayer nav = (NavigationTiledMapLayer)map.getLayers().get("meta");

List<GridCell> path = finder.findPath(this.getPosX(), this.getPosY(), player.getPosX(), player.getPosY(), nav);

for(GridCell c : path){
    Gdx.app.log("Map Loading Test - path: ", c.toString());
}

Wich give me this error :

Exception in thread "LWJGL Application" java.lang.ClassCastException: com.badlogic.gdx.maps.tiled.TiledMapTileLayer cannot be cast to org.xguzm.pathfinding.gdxbridge.NavigationTiledMapLayer

Do you have any clue ?

Thank you for your help !
Thomeuxe

dontCrossCorners/diagonale and obstacle

Greetings,

I use you algorithm to make a shortcut in my software.
The option “opt.dontCrossCorners = false;” allows me to manage the diagonals in the corners without any issues (cf. picture 1 & 2)

On the other hand when I add an obstacle inside of a corner on the way of the diagonal has to go, the path is not best anymore (cf. picture 3).
Would you have a solution for this issue ?

Thanks a lot.
Kind Regards,

Gradle issue

Hello, Im a bit new to gradle, Im trying to use your gdx-bridge, adding the following lines to my build.gradle:

project(":core") {
    apply plugin: "java"


    dependencies {
        compile "com.badlogicgames.gdx:gdx:$gdxVersion"
        compile "com.badlogicgames.gdx:gdx-box2d:$gdxVersion"
        compile "com.github.xaguzman:pathfinding:0.2.6"
        compile "com.github.xaguzman:pathfinding-gdx-bridge:0.2.6"
    }
}

However, I got the following error at build time:

Error:Gradle: Could not resolve all dependencies for configuration ':core:compile'.
> Could not find pathfinding:pathfinding:unspecified.
  Searched in the following locations:
      https://repo1.maven.org/maven2/pathfinding/pathfinding/unspecified/pathfinding-unspecified.pom
      https://repo1.maven.org/maven2/pathfinding/pathfinding/unspecified/pathfinding-unspecified.jar
      https://oss.sonatype.org/content/repositories/snapshots/pathfinding/pathfinding/unspecified/pathfinding-unspecified.pom
      https://oss.sonatype.org/content/repositories/snapshots/pathfinding/pathfinding/unspecified/pathfinding-unspecified.jar
      https://oss.sonatype.org/content/repositories/releases/pathfinding/pathfinding/unspecified/pathfinding-unspecified.pom
      https://oss.sonatype.org/content/repositories/releases/pathfinding/pathfinding/unspecified/pathfinding-unspecified.jar
  Required by:
      TestsTiles:core:1.0 > com.github.xaguzman:pathfinding-gdx-bridge:0.2.6

Am I doing something wrong?

Staggered isometric maps

Hi,

this is more of a question, not a bug. I'm using libgdx with staggered isometric map, where the tiles are stored like so:

0/4   1/4   2/4   3/4   4/4   ...
   0/3   1/3   2/3   3/3   4/3   ...
0/2   1/2   2/2   3/2   4/2   ...
   0/1   1/1   2/1   3/1   4/1   ...
0/0   1/0   2/0   3/0   4/0   ...

This is a bit hard to map onto the GridCell array and I was hoping if I could just override the neighbour resolving:

new NavigationGrid<GridCell>(createCells()) {
            @Override
            public List<GridCell> getNeighbors(GridCell cell) {
                int x = cell.getX();
                int y = cell.getY();
                List<GridCell> neighbours = new ArrayList<GridCell>();
                for (StaggeredDirection dir : StaggeredDirection.PATH_AROUND) {
                    int x1 = x + dir.getX(y % 2 == 1);
                    int y1 = y + dir.getY();
                    neighbours.add(new GridCell(x1, y1, layer.getCell(x1, y1) == null));
                }
                return neighbours;
            }

            @Override
            public List<GridCell> getNeighbors(GridCell node, PathFinderOptions opt) {
                return this.getNeighbors(node);
            }
        };

However this method seems to never be called in the first place. Would you have any recommendations how to approach my problem?

How can i add this library to a libgdx gwt html project?

I tried countless posibilities, but I can't make it compile properly.
It works on desktop but not html.

Licensing

Hi,

I just wanted to confirm that this library is under Apache License 2.0. I noticed there isn't a NOTICE or LICENSE file so I just wanted to make sure.
I'm looking to use your library in an app but not make any modifications.

GridCell reuse

Hi, im creating GridCell on touchDown() as

        GridCell[][] cells = new GridCell[mapHeight][mapWidth];
        for (int x = 0 ; x < mapHeight; x++){
            for (int y = 0 ; y < mapWidth; y++){
                cells[x][y] = new GridCell(x, y, gridObj.getBoolean(x,y));
            }
        }
        GridFinderOptions opt = new GridFinderOptions();
        opt.allowDiagonal = false;
        AStarGridFinder<GridCell> finder = new AStarGridFinder(GridCell.class, opt);

        NavigationGrid<GridCell> navGrid = new NavigationGrid(cells);

        pathToEnd = finder.findPath(playerClass.getPositionX()/32, playerClass.getPositionY()/32, (int) coords.y/32, (int) coords.x/32, navGrid);

Problem with it is that i cant reuse GridCell[][] cells, so i am creating new GridCell[][] cells every time on new search.
So am i missing something or is there way to fill GridCell[][] cells on show() and the use old data every time new search is needed on touchDown()?

Automatically assign x, y to GridCell

As suggested in #3 :
passing an array of GridCells to a NavigationGrid should automatically set the x and y of GridCells

Is it possible to use this library to create an android app?

I need to create an android app from an internal map with internal navigation, using QR Codes to find the user's current location, and find the best path to the chosen destination in the application. Then show the map with the path and guide the user to the destination, like a GPS. I was looking for a library to help me create this app. Can yours be useful to me? And could you give me a handout on how I could use your library to develop this project for my college?

[Question] Is this library support still alive?

Allow multiple finders to run in parallel

Right now, finders keep a track of their own jobId, which is then set on the nodes.
If you want to alternately use finders on a graph it could generate incorrect paths (or not find them at all) due to skipping some nodes, assuming they were already evaluated.

Node's job should be store per type / category, meaning each node should be able to have more than one jobId at the same time.

TiledMapTileLayer cannot be cast to NavigationTiledMapLayer

I did exactly what the guide said:

map = new NavTmxMapLoader().load("res/battlefield001.tmx",params);
navLayer = (NavigationTiledMapLayer) map.getLayers().get("navigation");

But then I get Exception in thread "LWJGL Application" java.lang.ClassCastException: com.badlogic.gdx.maps.tiled.TiledMapTileLayer cannot be cast to org.xguzm.pathfinding.gdxbridge.NavigationTiledMapLayer

I have used a navigation layer in Tiled etc.
What can I do?
Newest libgdx and tiled version.

Can't import from Gradle, but .jar works

Hey,

Recently had an issue where I couldn't get the library to import successfully. Changing the version number to an invalid version 404'd, so it's some kind of configuration issue by the looks of it. Anyway, adding the jar worked.

New tiled version

Hello,

Once again, thanks for your project, its working like a charm.

I try to upgrade my libgdx version to 1.9.8, but i couldn't use like before. This libgdx version comes with a GroupMapLayer, to handle Groups in tiled (Also new versions).
When your try to create a new NavigationTileMapLayer, i use as ((NavigationTiledMapLayer) layer).getNodes(), it fails to cast.
Specific message is: com.badlogic.gdx.maps.tiled.TiledMapTileLayer cannot be cast to org.xguzm.pathfinding.gdxbridge.NavigationTiledMapLayer

I have seen some previous issue where the name "navigation" is mandatory, so its not about that, my layer name is "navigation". If you just update libgdx version, it already fails to cast.

I can give more details if you need.

Dont know if im using it wrong or if something needs to be upgraded, just like to report it.
Thanks!

Fix compatibility with libgdx 1.5.3 for gdx-bridge

TmxMapHelper seems to be removed from version 1.5.3.
Needs to work again!

See #7

finder = new AStarGridFinder(GridCell.class) ERROR

Hello, I am trying to use this library for a personal project of mine. Problem is that the line
AStarGridFinder finder = new AStarGridFinder(GridCell.class);
makes the following exception
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Lorg.xguzm.pathfinding.BHeapNode;
Is there something I might be doing wrong?
Thank you.

JumpPointFinder crashing when allowDiagonal is true

JumpPointFinder is crashing when allowDiagonal is true.
I tried disabling diagonals and seems to work

Enhance Javadoc

There are some javadocs that are missleading, and some others were not updated when code was, thus they hint to previous versions of the library. Some other have typos

Null Pointer Exception

Hi, I really like your library, I've been able to load a tmx map but when I try to find a path, I get this:

Exception in thread "LWJGL Application" java.lang.NullPointerException
    at org.xguzm.pathfinding.finders.AStarFinder.findPath(AStarFinder.java:56)
    at org.xguzm.pathfinding.grid.finders.AStarGridFinder.findPath(AStarGridFinder.java:32)
    at com.route7.td.ai.Grid.getPath(Grid.java:32)
    at com.route7.td.map.Map.findPath(Map.java:187)
    at com.route7.td.sprites.Enemy.setDestination(Enemy.java:74)
    at com.route7.td.map.Level.show(Level.java:90)
    at com.badlogic.gdx.Game.setScreen(Game.java:61)
    at com.route7.td.screens.LevelSelect$2.changed(LevelSelect.java:158)
    at com.badlogic.gdx.scenes.scene2d.utils.ChangeListener.handle(ChangeListener.java:28)
    at com.badlogic.gdx.scenes.scene2d.Actor.notify(Actor.java:181)
    at com.badlogic.gdx.scenes.scene2d.Actor.fire(Actor.java:146)
    at com.badlogic.gdx.scenes.scene2d.ui.Button.setChecked(Button.java:116)
    at com.badlogic.gdx.scenes.scene2d.ui.Button$1.clicked(Button.java:90)
    at com.badlogic.gdx.scenes.scene2d.utils.ClickListener.touchUp(ClickListener.java:89)
    at com.badlogic.gdx.scenes.scene2d.InputListener.handle(InputListener.java:57)
    at com.badlogic.gdx.scenes.scene2d.Stage.touchUp(Stage.java:348)
    at com.badlogic.gdx.backends.lwjgl.LwjglInput.processEvents(LwjglInput.java:306)
    at com.badlogic.gdx.backends.lwjgl.LwjglApplication.mainLoop(LwjglApplication.java:206)
    at com.badlogic.gdx.backends.lwjgl.LwjglApplication$1.run(LwjglApplication.java:120)

Here is my code:

import org.xguzm.pathfinding.gdxbridge.NavigationTiledMapLayer;
import org.xguzm.pathfinding.grid.GridCell;
import org.xguzm.pathfinding.grid.finders.AStarGridFinder;
import org.xguzm.pathfinding.grid.finders.GridFinderOptions;

import com.badlogic.gdx.maps.tiled.TiledMap;
import com.badlogic.gdx.math.Rectangle;
import com.route7.td.map.Map;

public class Grid {

    public AStarGridFinder<GridCell> finder;

    public NavigationTiledMapLayer pathLayer;
    public TiledMap map;

    public Grid(Map tmxMap) {
        TiledMap map = new NavTmxMapLoader().load(tmxMap.tmxFile);
        pathLayer = (NavigationTiledMapLayer) map.getLayers().get("navigation");

        GridFinderOptions opt = new GridFinderOptions();
        opt.allowDiagonal = false;

        finder = new AStarGridFinder<GridCell>(GridCell.class, opt);
    }

    public List<GridCell> getPath(Rectangle start, Rectangle end) {
        return finder.findPath((int)start.x, (int)start.y, (int)end.x, (int)end.y, pathLayer);
    }
}

Any help would greatly be appreciated 👍

weights

The library is good and useable but currently there is no possibility to provide weights if I have not overseen sth?

Diagonal fixtures

Hi,

I used the original DIagonalNavigationLayer but i found some issues. I cant tell you specific what it was because it was a some time ago, i would like to share my version, maybe you could use it in your original project or base on it to fix:


package com.riot.pathfinding;

import org.xguzm.pathfinding.PathFinderOptions;
import org.xguzm.pathfinding.grid.GridCell;
import org.xguzm.pathfinding.grid.NavigationGrid;
import org.xguzm.pathfinding.grid.NavigationGridGraphNode;
import org.xguzm.pathfinding.grid.finders.GridFinderOptions;

import java.util.ArrayList;
import java.util.List;

public class DiagonalNavigationGrid<T extends NavigationGridGraphNode> extends NavigationGrid {
    private List neighbors = new ArrayList();

    public DiagonalNavigationGrid(GridCell[][] nodes) {
        super(nodes, false);
    }


    @Override
    public List getNeighbors(NavigationGridGraphNode cell) {
        return super.getNeighbors(cell);
    }

    @Override
    public List getNeighbors(NavigationGridGraphNode node, PathFinderOptions opt) {
        GridFinderOptions options = (GridFinderOptions) opt;
        boolean allowDiagonal = options.allowDiagonal;
        boolean dontCrossCorners = options.dontCrossCorners;
        int yDir = options.isYDown ? -1 : 1;
        int x = node.getX(), y = node.getY();
        neighbors.clear();
        boolean s0 = false, d0 = false, s1 = false, d1 = false,
                s2 = false, d2 = false, s3 = false, d3 = false;

        // up
        if (isWalkable(x, y + yDir)) {
            neighbors.add(nodes[x][y + yDir]);
            s0 = true;
        }
        // right
        if (isWalkable(x + 1, y)) {
            neighbors.add(nodes[x + 1][y]);
            s1 = true;
        }
        // down
        if (isWalkable(x, y - yDir)) {
            neighbors.add(nodes[x][y - yDir]);
            s2 = true;
        }
        // left
        if (isWalkable(x - 1, y)) {
            neighbors.add(nodes[x - 1][y]);
            s3 = true;
        }

        if (!allowDiagonal) {
            return neighbors;
        }

        if (dontCrossCorners) {
            d0 = s3 && s0;
            d1 = s0 && s1;
            d2 = s1 && s2;
            d3 = s2 && s3;
        } else {
            d0 = true;//s3 || s0;
            d1 = true;//s0 || s1;
            d2 = true;//s1 || s2;
            d3 = true;//s2 || s3;
        }

        // up left
        if (d0 && this.isWalkable(x - 1, y + yDir)) {
            neighbors.add(nodes[x - 1][y + yDir]);
        }
        // up right
        if (d1 && this.isWalkable(x + 1, y + yDir)) {
            neighbors.add(nodes[x + 1][y + yDir]);
        }
        // down right
        if (d2 && this.isWalkable(x + 1, y - yDir)) {
            neighbors.add(nodes[x + 1][y - yDir]);
        }
        // down left
        if (d3 && this.isWalkable(x - 1, y - yDir)) {
            neighbors.add(nodes[x - 1][y - yDir]);
        }

        return neighbors;
    }
}

I end up using a new DiagonalNavigationTileMapLayer also, just to reference the above class.

Hope it helps someone.
Thanks!