LÖVE

Just because it's fun coding path finders

Easy to use, it will make you more attractive and you feel sensual doing so.
The module does not care how your map data is arranged, it simply asks you for the map position via a callback.

The path will be nil if no path was found, otherwise it contains a list of points that travel your path:
Now I'm going to find the shortest path to bed

Hey there!

Just a few questions. Which algorithm is used?

And is there a way to disable diagonal movement or introduce path cost?

erasio wrote: ↑Sat Dec 02, 2017 7:50 am Hey there!

Just a few questions. Which algorithm is used?

And is there a way to disable diagonal movement or introduce path cost?

The algorithm used is “Manhattan distance method”, as you can see in the references section: https://www.raywenderlich.com/4946/intr ... athfinding

To disable diagonal movement just comment 4 lines on the function getAdjacent(), just after the comment --include diagonal movements.

And to add path cost, that's beyond my knowledge right now. You can always tweak the code here and there, and see what happens.

P.S.: I've been looking at the code, and I guess that if you could pass a matrix of costs to the module:find() function, and pass it again to calculateScore(), then you could do this:

--- Return the score of a node.
-- G is the cost from START to this node.
-- H is a heuristic cost, in this case the distance from this node to the goal.
-- Returns F, the sum of G and H.
local function calculateScore(previous, node, goal, costs)

local G = previous.score + 1 + costs[node.x][node.y]
local H = distance(node.x, node.y, goal.x, goal.y)
return G + H, G, H

end

Hope it helps.

@OP, really good job! It's really easy to understand

P.P.S.:

@erasio it is very similar to A*, because I use distance as part of the cost, and because I sort the node list by cost priority, the algorithm tends to follow low-cost paths first. As you note I don't have user specified path costs.

@nyenye Thanks! I was thinking if you want to add path costs by way of the callback function. Instead of a bool indicating a walkable cell, return a number where 0 is a blocked cell, and any other value is the movement cost.

I can't vouch for the performance of this, I wrote it for a turn based game I'm making

This is another reference I used and forgot to mention https://www.redblobgames.com/pathfindin ... ction.html

FYI here is the git repo with some unit tests https://github.com/wesleywerner/lua-star

kbmonkey wrote: ↑Sat Dec 02, 2017 1:13 pm @nyenye Thanks! I was thinking if you want to add path costs by way of the callback function. Instead of a bool indicating a walkable cell, return a number where 0 is a blocked cell, and any other value is the movement cost.

So true. That makes so much sense. Really did a great job with this small lib.

That callback function is genius! I wish jumper implemented it the same way, would eliminate a lot of my problems.
So, uh, you wanna try your hand with JPS next?

I will make a note of JPS, I can't promise I will work on that yet, I am too infatuated with other projects. But JPS sounds like the way to optimize for speed