LoveAStar: A* Search in Lua/Love

[Roland_Yonaba]

No, lol.

Huh...I said it because of the very last lines of your first post.

[MarekkPie]

A few lines above that link:

Links to pathfinding optimization articles (who found the article will be noted in parentheses):

[Roland_Yonaba]

Sorry, I missed that.
Well, I am actually trying to have Jump Point Search working. I read the papers, and I think I go the general idea (how it works, in the outline).
But some parts remains a bit unclear...Pruning rules, for instance...
Well, I do have something working, yet the are are some odds. With diagonal moves.
I'll be looking to it. In the meantime, if one have extra information that might help, please post.

[MarekkPie]

http://aigamedev.com/open/tutorial/symm ... thfinding/
Here's the same article of AIGameDev, with a surprise appearance by our very own kikito.

From what I understand, pruning is just using logic that A* doesn't take into account. Keep in mind that JPS (or at least the JPS described in this article) relies on uniform edge costs throughout the graph, otherwise, some of the assumptions made are not necessarily true.



For orthogonal movement, it's pretty simple. If my move is 4->X, then all of the grayed-out boxes either:

• Have no path that could be shorter when going through X than what was available when going directly from 4 (vertexes 1, 2, 6, 7);
• Have a symmetrically equal path through a different node (vertexes 3, 8).

Diagonal movement follows the first rule, but doesn't seem to follow the second. The only reason I can think for this is when searching for the next jump point successor, diagonal movements give more available options.



When a non-uniform neighbor set appears (meaning a wall or other obstacle is in your set of neighbors), or for diagonal movement when one of its branches reaches a wall, standard pruning doesn't work, and at that point you need to actually call A* to figure out your next move.




(ignore the transparent tile)

The other thing is (which is something I didn't quite understand until now) you only actually call A* when you reach a jump point successor. So it all hinges on the speed of the pruning to find the next successor, which is clearly going to be faster than an A* call for orthogonal movement, and likely faster than a call for diagonal movement (which must make multiple orthogonal calls during each step).

[Roland_Yonaba]

Right,

Well, after lot of reading, headaches and coffee, I think I succeeded in it.
I'll be posting as soon as I get the code clean, with a graphical demo.

[LumoBlaze]

Hey I'm really new to LUA and Love2d, and I've been trying to implement this into my little test project, and can't seem to figure out how to get the pathfinding to start. Is there any sort of tutorial on like, how to use move a cube from Point A to Player?
Thanks in advance

[BoundSyco]

There is a minor error in the code which causes incorrect (for A*) path generation.

Wrong (Existing Implementation)

Correct


The error is a very minor one (and unfortunately quite common). You will notice that the path returned in the existing implementation is not optimal.

An exaggeration of this problem is demonstrated in the following image. Those two inward dips towards the goal are the result of an incorrect path recreation.

Very Bad


This kind of path generation is a partial "Best First" implementation with lots of overhead. (Best First requires exponentially fewer calculations than A* and the paths generated here are marginally better than best first).

The fix exists in the astar.lua file, lines 39-40 (two lines).
Existing:

Code: Select all

39: while path[#path].pathLoc ~= startPos do
40:	table.insert(path, closedSet[path[#path].pCloseLoc])
41: end

Should be:

Code: Select all

39: while path[#path].parent ~= path[#path] do
40:	table.insert(path, path[#path].parent)
41: end

I have attached a corrected version.