Yet another path finding module

Showcase your libraries, tools and other projects that help your fellow love users.
Post Reply
User avatar
kbmonkey
Party member
Posts: 124
Joined: Tue Sep 01, 2015 12:19 pm

Yet another path finding module

Post by kbmonkey » Fri Dec 01, 2017 10:43 pm

Just because it's fun coding path finders :joker:
pathfinder.png
pathfinder.png (12.61 KiB) Viewed 1267 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
Attachments
pathfinder.love
(3.3 KiB) Downloaded 45 times

User avatar
erasio
Party member
Posts: 118
Joined: Wed Mar 15, 2017 8:52 am
Location: Germany

Re: Yet another path finding module

Post by erasio » 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?

nyenye
Citizen
Posts: 62
Joined: Fri Dec 02, 2016 1:44 pm

Re: Yet another path finding module

Post by nyenye » Sat Dec 02, 2017 10:29 am

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

P.P.S.:
photo_2017-12-02_12-53-20.jpg
photo_2017-12-02_12-53-20.jpg (40.7 KiB) Viewed 1215 times

User avatar
kbmonkey
Party member
Posts: 124
Joined: Tue Sep 01, 2015 12:19 pm

Re: Yet another path finding module

Post by kbmonkey » Sat Dec 02, 2017 1:13 pm

@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

User avatar
kbmonkey
Party member
Posts: 124
Joined: Tue Sep 01, 2015 12:19 pm

Re: Yet another path finding module

Post by kbmonkey » Sat Dec 02, 2017 1:20 pm

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

nyenye
Citizen
Posts: 62
Joined: Fri Dec 02, 2016 1:44 pm

Re: Yet another path finding module

Post by nyenye » Sat Dec 02, 2017 3:23 pm

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.

KayleMaster
Party member
Posts: 190
Joined: Mon Aug 29, 2016 8:51 am

Re: Yet another path finding module

Post by KayleMaster » Sun Dec 03, 2017 11:23 am

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? :D

User avatar
kbmonkey
Party member
Posts: 124
Joined: Tue Sep 01, 2015 12:19 pm

Re: Yet another path finding module

Post by kbmonkey » Thu Dec 07, 2017 8:04 pm

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

Post Reply

Who is online

Users browsing this forum: No registered users and 3 guests