# How to implement pathfinding in this situation

So I'm creating a game for android using the libgdx library. I render the map from a tmx file and in it all the water tiles have the property of blocked. My player(a sprite) moves to where I clicked/tapped.

My problem is that I am unsure as to how to implement pathfinding. I can get in the layer with the tiles that which have the blocked property but I'm not sure as to how to stop my player from moving through them. I am using the tweenengine to move the player.

I was thinking that perhaps the code would create waypoints for the tween movement from a path finding code but again I'm not sure as to how to implement it.

I looked at A* and all the examples I was looking at were using rectangles and my player doesnt move in a uniform way(1 tile per move). So I cant really assign it values (10 for vertical/horizontal, 14 for diagonal).

If I have said anything that is not true then please correct me

• Is there a set of rules for how your player moves? Also, what kind of a game is it? – sparks Sep 5 '13 at 19:53
• @sparks: well in the end the game is supposed to be a MOBA. As for how the player moves, I just tap on the screen and the player tweens to the x,y coordinates – Exikle Sep 5 '13 at 19:57

I'm going to assume even if you're not moving by squares on the map that you still have them.

With this in mind the solution becomes the same as if your character did move along the squares. Use a pathfinding algorithm to find where the character needs to head. Then find the nodes where the slope of the path changes and these nodes become waypoints. You can then tween between the waypoints.

For instance, say your character is at (0,0) on the map and your pathfinding algorithm starts with a slope of 3/4 (move 3 blocks up and 4 to the right) to point (4,3) then changes to a slope of 0 to point (4,13) then changes again to slope 1/6 to point (10, 14).

You then go through and find the points listed since the slopes change and then tween as so:

(0,0) to (4,3)
(4,3) to (4,13)
(4,13) to (10,14)

• so make the code find the closest tile the character is at and then from that tile do a pathfinding algo? – Exikle Sep 5 '13 at 20:27
• That sounds like it should work. I honestly didn't think "What if the character is currently tweening?" but yeah, finding the tile the character is most "on" and starting from there should work. – sparks Sep 5 '13 at 20:32

Although it is written in C#, Eric Lippert presented an excellent introduction to the A* algorithm here. Implementing A* in any other C-like language should be straightforward from Eric's description and analysis.

Eric's algorithm is for a square grid, and illustrates usage of the .NET framework for understandable reasons.

An ALT bidirectional implementation of A* (also in C#) is available in my Open Source (MIT) hex-grid library here for any who require a more efficient implementation. (It calculates shortest paths on a 750 x 460 hexgrid terrain map in under 5ms on my i7 laptop.)

• codeproject.com/Articles/15307/A-algorithm-implementation-in-C has a great A* implementation. – Arconath Sep 6 '13 at 0:13
• Care for a path-off against my implementation? ;-) – Pieter Geerkens Sep 6 '13 at 0:27
• @Arconath: No offence to both of you but I'm doing it in java. I'll still look at both for my understanding but it wont be written in c#, itll be written in java – Exikle Sep 6 '13 at 6:03
• @Exikle: No offence taken; of course you will use your own language of choice. – Pieter Geerkens Sep 8 '13 at 17:08