I've implemented this in my small little game and I noticed the bug. I then was able to replicate the bug on your test example application. On any row but the top if you try to go straight left/right the green guy goes up first then down then over. I didn't place any obstacles on the board so something is causing the green square to take paths that aren't the shortest. Really love this library and how easy it was to integrate (it actually threw me for a loop starting your map with index of 1 instead of 0 like how my map was defined but fixed that). Would love for this small bug fix!


Roland_Yonaba wrote Aug 2, 2011 at 5:26 PM

Thanks for trying this.
First, I'd like to point out something, Astar algorithm does not look for the best path, or the shortest path.For instance, Dijkstra algorithm does.
Astar just looks for a possible path, and returns it back.
This is very useful just because it doesn't require much memory, and it can give you quickly a reasonable answer.
Just wanted to point that out.
Well, i dind't know about that bug, thanks for tipping me by the way. I'll be looking at this just this evening, and then release a possible fix as soon as possible.

Roland Y.

rpiller wrote Aug 2, 2011 at 6:50 PM

Ah thanks, I didn't know that. I always thought A* also found the shortest path.

Looking forward to the fix. I'm using Leadwerks game engine which has a Lua bind so this is really cool. You might get more people from over there checking out this library once they see it in my little game.

rpiller wrote Aug 2, 2011 at 9:28 PM

Also, would you ever consider adding diagonal movement to the script?

Roland_Yonaba wrote Aug 4, 2011 at 10:14 AM

Hi, LuAstar now fixed.
I've added new extra stuff, such as depth area search, and diagonal movement.
Hope you like it.

Roland Y.

rpiller wrote Aug 4, 2011 at 11:10 AM

Without diagonal movement it looks like the bug was fixed. With diagonal movement enabled in your test app and you go straight left to right it looks like the bug is there now. The green square will go diagonally up then over then diagonally down instead of just straight over.

That search depth feature is cool btw!

Roland_Yonaba wrote Aug 4, 2011 at 2:16 PM

Thanks for the tip.
It was just a problem of straight/diagonal moves cost in distance heuristics. Now fixed!

rpiller wrote Aug 4, 2011 at 5:34 PM

Yep that fixed it!

I hate to be a bother with this but I noticed 1 other thing. If I move 2+ tiles the path table that comes back looks slightly different than if I move only 1 tile over. I've take a screenshot of a printout of the path table in a 2 tile movement and 1 tile movement. It seems in the 1 tile movement the 2nd item in the table is the same as the first where I would think it would be embedded in the parent of the first like in the 2+ movement.

What I do with my pathfinding is remove the first node (since it's the starting node) and start moving to the next node. This works great with 2+ tile movements but with only 1 tile movement since the starting location is actually in the table twice at the same level, my character walks in place before moving to the next node. I don't know if that's a bug somewhere that can be fixed? I can compare the first node with the 2nd and if the same remove both, but just thought I'd point this out in case it is a bug as I'm sure you want your pathfinding to be perfect :)

Moving 2 tiles - Notice the embedded table in the parent of the first node

Moving 1 tile - Notice there is no embedded table in the first parent node and the starting node is repeated twice

Roland_Yonaba wrote Aug 8, 2011 at 3:48 PM

This issue was fixed in LuAstar v3.
Thanks for the tip, one more time.

Roland Y.

wrote Feb 13, 2013 at 1:29 AM