Path-finding for an Android TD - A* in JNI?

[DeanMSands3]

I’m looking to make a Tower Defense on Android for a university class final project. For this, I will need to use a Path-Finding algorithm (A*, D*, D*-lite, etc.). Path-finding tends to be time-consuming, and I want this to work on 2.3.3 era phones. Also, one of the requirements for the project is I need to use OpenGL. That means more time-consumption.
So I’m thinking… Native Code for the path-finding. I’m really a C/C++ dev anyway. And it would NOT be my first multiple code-language or multiple-architecture project (embedded firmware development makes me cry, but it also makes me money; I spend a lot of time crying.)

I’m looking at a blog post on JNI here: http://www.integratingstuff.com/2010/12/12/calling-native-c-code-through-jni-in-android-applications/ and it seems straight-forward enough.

Anyone have input on their JNI experiences?

BTW, first post, glad to be here, etc., etc.
-DeanMSands3

[sproingie]

The overhead of JNI on Android is pretty damn gigantic, so whatever you do should be staying in native code for a while and not crossing back and forth with java willy-nilly. Consider also that the constrained display of a phone is not likely to present a large field to be pathfinding over, and it isn’t really that clear whether the native code approach will actually pay off.

Obviously it depends on how complex your pathfinding actually is, and more obviously the only real answer is the one you actually measure.

[princec]

Android’s easily fast enough to run A* in Dalvik.

Cas

[pitbuller]

@sproingie

The overhead of JNI on Android is pretty damn gigantic, so whatever you do should be staying in native code for a while and not crossing back and forth with java willy-nilly. Consider also that the constrained display of a phone is not likely to present a large field to be pathfinding over, and it isn’t really that clear whether the native code approach will actually pay off.

Obviously it depends on how complex your pathfinding actually is, and more obviously the only real answer is the one you actually measure.

Quite not true. Libgdx use JNI at many places and many those are really small things like Matrix math and such. The overhead are there but older android versions dalvik is such crap that JNI version is usually much faster.

I still recommend first make pure java A* version and profile it. JNI can be such a hassle that make sure it’s worth it.

[DrHalfway]

Surely for a TD game you wouldn’t need to run the A* algorithm every frame iteration or even on a set update, could improvise and pre-calculate the path on a wave-wave basis?

And just because something is written in native code dos not make it better or faster than java/dalvik code. Profile first, and if its too slow, then think about going native. You’ll find most optimization can be done at an algorithm/design level.

[DeanMSands3]

OK, so the forum consensus is “No, but maybe.” (I still think I’ll try it.;)) Duly noted. But that does leave me curious. Supposing I get started with libGDX and decide to work on a game. Are there any instances where JNI would be worthwhile?

[EgonOlsen]

@DeanMSands3

Supposing I get started with libGDX and decide to work on a game. Are there any instances where JNI would be worthwhile?

Depends on the game, but you can do pretty complex stuff in Java/on Dalvik if you aren’t scared of doing some micro optimization of your most performance critical code sections.
For example, this uses pure Java and runs fine on an older Galaxy S class device: http://www.youtube.com/watch?v=olxPQ6zjNEA. But it required some optimizations to get there. Without them, it would run at maybe 60% the speed.