Yet another path finding module

[kbmonkey]

Just because it's fun coding path finders

pathfinder.png (12.61 KiB) Viewed 6770 times

Easy to use, it will make you more attractive and you feel sensual doing so.

Code: Select all

local lib = require("lib")

function isPositionOpenfunc(x, y)
    -- should return true if the map position at x, y is open to walk
    return map[x][y]
end

-- find me a path
local mapwidth = 10
local mapheight = 10
local start = { 1, 10 }
local goal = { 10, 1 }
path = lib:find(mapwidth, mapheight, start, goal, isPositionOpenfunc)

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:

Code: Select all

    if path then
        for _, p in ipairs(path) do
            print(p.x, p.y)
        end
    end

Now I'm going to find the shortest path to bed

[erasio]

Hey there!

Just a few questions. Which algorithm is used?

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

[nyenye]

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.:

photo_2017-12-02_12-53-20.jpg (40.7 KiB) Viewed 6718 times

[kbmonkey]

@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

[kbmonkey]

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

[nyenye]

@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.

[KayleMaster]

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?

[kbmonkey]

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