Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm an amateur game developer and somewhat amateur Java developer as well. I'm trying to find a way to have path finding for my game(s). I've first Googled for some existing Java libraries that have various path-finding implementations, but I've failed to find any. It seems to me that the only way to get pathfinding code is to use it via a game engine (like Unity). But I'd just like to have a library that I can use and make the game loop and other stuff on my own.

Failing to find such a library I've tried implementing some algorithms myself. I've managed to make a running A* in Java, but for fancier stuff like D* I find it hard to do it by hand.

So then, my question is, are there any Java libraries that contain at least some basic pathfinding algorithms implementations?

share|improve this question
    
D* is obsolete, use D*-Lite (which does the same thing, only faster and easier to implement) –  BlueRaja - Danny Pflughoeft Aug 30 '12 at 18:57
add comment

3 Answers

up vote 8 down vote accepted

Path finding libraries are not too common for general use. This is because the algorithm interacts directly with your world. The algorithm can't know in advance how you'll lay out your data structures for holding your world data. The amount of user required implementation for these algorithms would likely override the usefulness of providing the algorithm in library form. The more complex the algorithm, the more work it would be to make a generalized version for a library form. So you're less likely to really get what you want, the harder-to-implement algorithms won't be in library form. There are some libraries available, though I haven't used them, so I can't say how much work they are to use. Personally I would rather implement them myself so I can learn how they work and ensure they're properly integrated.

It may be useful to look at the libraries to get some implementation tips, but I don't think these will be implemented in the same way you would implement them. Since they need to overcome the issues I mentioned earlier, they might have some strange implementations.

For 2D, Slick2D has some built-in path finding for tile based games. StackFrame implements some simple pathfinding algorithms with PathFinder.

share|improve this answer
    
Thanks, Slick looks promising, and not just for the path-finding stuff. –  Shivan Dragon Aug 30 '12 at 15:17
add comment

Here are three places where you can see A* code in Java:

share|improve this answer
    
Any time I see A* I think of your great page :) theory.stanford.edu/~amitp/GameProgramming –  monkey May 26 '13 at 4:51
add comment

You may want to have a look at jKılavuz.

Taken from the definition on official site:

jKılavuz consists of an extensible set of tools for collecting pathfind data and finding and executing paths. Despite the complexness of subject it is designed for ease of use.

jKılavuz can work on almost arbitrary geometry. To collect pathfind data, it flood fills over surface starting from a set of points on ground. This way a kind of 2d grid in 3d space is created which can take us up or down slopes, across bridges and over and under overpasses. The process also takes care of jumping over obstacles and gaps. The default implementation uses jPCT's collision detection system but a custom implementation may be plugged. Later this massive information is collapsed into sectors and portals which are then converted into a very compact form to use in runtime. All the process is automized although users can intervene. Custom portals can be defined for elevators, teleporters etc.

Pathfinding is performed among sectors and hence can be considered as a hierarchical approach. This makes it quite fast and efficient even for very large maps.

jKılavuz provides the necessary methods to actually execute the found path. It provides a clean and uniform interface to iterate over paths over time. The iterator is suitable for both fixed and delta time approaches. Paths can be merged and customized in certain ways. Users can still create their own executable paths by using Lego like path segments.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.