## Yet another path finding module

kbmonkey
Party member
Posts: 127
Joined: Tue Sep 01, 2015 12:19 pm

### Yet another path finding module

Just because it's fun coding path finders
pathfinder.png (12.61 KiB) Viewed 1445 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

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

### Re: Yet another path finding module

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

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.:
photo_2017-12-02_12-53-20.jpg (40.7 KiB) Viewed 1393 times

kbmonkey
Party member
Posts: 127
Joined: Tue Sep 01, 2015 12:19 pm

### Re: Yet another path finding module

@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
Party member
Posts: 127
Joined: Tue Sep 01, 2015 12:19 pm

### Re: Yet another path finding module

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

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: 191
Joined: Mon Aug 29, 2016 8:51 am

### Re: Yet another path finding module

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
Party member
Posts: 127
Joined: Tue Sep 01, 2015 12:19 pm

### Re: Yet another path finding module

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

### Who is online

Users browsing this forum: Exabot [Bot], Google [Bot] and 1 guest