Pathfinding class

I noticed that jMonkeyEngine does not have it’s own pathfinding utilities. Especially for beginners it is helpful to have some available, so here’s a small contribution. I have implemented the popular A* pathfinding and the code should work on any graph. Because in most cases the graph is simply a 2d grid, I have added a helper class for this that accepts a 2d array with values. These values represent the cost to be at a certain point. This allows for easy terrain costs: mountains cost more than nice paved roads, etc.



If you don’t want to use the helper class, and want to use your nodes from the scene graph, that’s possible. Just implement (and probably rename first) the Node interface and define your own graph.



In the future I will add support for some other useful pathfinding algorithms, for example one that support negative cost values. Another interesting algorithm is the closely related Simplified Memory Bounded A*, which is A* only, well, memory bounded. This is especially interesting for mobile devices.



Here’s the source code:

8 Likes

Cool. Theres multiple A* implementations on the forum already though. Also the SDK contains a navigation mesh generator which will be extended by a pathfinding api similar to the one in MonkeyZone at some point (that one has been adapted already and is in some local repos).

@normen said:
Also the SDK contains a navigation mesh generator which will be extended by a pathfinding api similar to the one in MonkeyZone at some point (that one has been adapted already and is in some local repos).

Ok, that's nice. :) If there is need for some other algorithm or something, just let me know and I'll see if I can contribute.
1 Like

hehe nice :slight_smile: will have a look through it properly later. I had to refactor it a bit to run on my JDK 6, as you used the diamond operators and Integer.Compare (I replaced with Double.Compare). Thanks for sharing!

Well if you are interested in improving and cleaning it up maybe we can add it rather sooner than later so you can have a whack… Otherwise that pathfinding code is also here in this little game I started:

http://normenhansen.de/PowerMonkey.zip

@wezrule said:
hehe nice :) will have a look through it properly later. I had to refactor it a bit to run on my JDK 6, as you used the diamond operators and Integer.Compare (I replaced with Double.Compare). Thanks for sharing!

Ah, yes. I have JDK 7 as default now. I'll change the code to JDK 6 soon.

@ normen said:
Well if you are interested in improving and cleaning it up maybe we can add it rather sooner than later so you can have a whack..

Sure, I'll see what I can do. Btw, I had a quick look at your code and saw that you use custom heaps. Java has a built-in PriorityQueue which does the same (but probably is more efficient).
1 Like

i made something before :slight_smile:



http://code.google.com/p/easyfinding/



it is not efficient but give easy to make ability of “climbing” or other.



it is not graph! it’s other less efficient way.

@benruijl said:
Sure, I'll see what I can do. Btw, I had a quick look at your code and saw that you use custom heaps. Java has a built-in PriorityQueue which does the same (but probably is more efficient).

Yes, the implementation was adapted from the example implementation for the mesh generator library and its unfinished state is why its not in core yet :) Java 5 is baseline for jME3 btw.

I’ve updated the code to be Java 5 compliant (no more <> and helpful @Override tags :frowning: ), changed from ints to doubles and fixed an indexing bug.

@Override is in java 5

It is, but you can’t use @Override on interfaces. In Java 6 you can, which is useful to prevent errors.

Hi,
As for me, I am testing the related java barcode generator these days. Do you have any ideas about it? Or any good suggestion? I am totally a green hand on barcode generating field. Any suggestion will be appreciated.

Thanks in advance.

Best regards,
Arron

@arronlee

Why don’t you use GitHub - zxing/zxing: ZXing ("Zebra Crossing") barcode scanning library for Java, Android ?

Because arronlee is a spambot 8)

You can use my navmesh code, which I’ve taken and modified for my upcoming game, 4089. Works decently, but it isn’t rock-solid…