erasio wrote: ↑
Sat Dec 02, 2017 7:50 am
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
Hope it helps.
@OP, really good job! It's really easy to understand