## pathfun: a pure Lua library for 2D pathfinding, with editor

apicici
Prole
Posts: 5
Joined: Wed Dec 18, 2019 9:25 pm

### pathfun: a pure Lua library for 2D pathfinding, with editor

--------------------------------------------------

Hi everyone,

I wanted to share pathfun, a 2d pathfinding library I've been working on. I made it as part of a LÖVE point & click adventure game engine I've been working on, and since it's self-contained I decided to release it on its own.

The pathfinding algorithm is a Lua translation of the one from the Godot Engine, which uses the funnel algorithm. The rest is my own work.

Features
• Pure Lua library
• Navigation area described by one or more polygonal maps
• Supports navigation areas made up of disjoint pieces and/or with holes
• Supports dynamically hiding/unhiding parts of the navigation area to add/ remove obstacles or disconnect/connect regions
• Uses integer coordinates to make calculations exact and avoid problems with floating point precision
• Comes with html documentation
See the animation below for an example of the pathfinding algorithm in action:

Editor

The navigation area data read by the library is a list of polygon maps consisting of convex polygons decompositions (see the documentation for more information), looking like this:

Code: Select all

polygon_maps = {
{
{{520,441},{456,429},{454,342},{658,370},{666,436}},
{{520,441},{666,436},{549,498}},
{{822,391},{880,372},{868,446},{747,431}},
{{822,391},{747,431},{754,360},{796,346}}
},
{
{{747,431},{666,436},{658,370},{754,360}},
hidden = true,
name = "bridge"
}
}

To avoid having to create these manually I created pathfun-editor, a navigation area editor for pathfun. The editor is done with LÖVE and uses cimgui-love for the interface, clipper for polygon operations, and polypartition to partition into convex polygons.

Features:
• Pre-built binaries available for Linux, Windows, and macos (cimgui and clipper need to be compiled otherwise)
• Visual editing the navigation area by adding or subtracting polygons in an intuitive way
• Testing mode to test pathfinding on the navigation area using pathfun
• Help window with instructions on how to use the editor
• Exports a .lua file that returns the navigation data expected from pathfun when required from Lua
The following animation provides a quick overview of the main features of the editor:

Editing the editor

You will probably need to make some changes to the source code of pathfun-editor to use it in your project, as you will want to draw the polygons on top of your background image.

In the simplest case you will need to:
• Draw the image at the very beginning of love.draw in the draw.lua file
• You may also want to save the location of the background image as a field in the exported Lua table and that read it when the file is loaded
Feel free to ask if you need help with this.
ReFreezed
Party member
Posts: 304
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

Looks cool, but I get an error at start-up for the editor (Windows, both 32 and 64-bit versions).

Code: Select all

Error: clipper.lua:297: cannot resolve symbol 'ClipperLib_Clipper__new': Det går inte att hitta den angivna proceduren.

stack traceback:
[string "boot.lua"]:777: in function <[string "boot.lua"]:773>
[C]: in function '__index'
clipper.lua:297: in function 'Clipper'
[C]: in function 'require'
[C]: in function 'require'
[C]: in function 'require'
serialization/init.lua:3: in main chunk
[C]: in function 'require'
input.lua:3: in main chunk
[C]: in function 'require'
[string "boot.lua"]:586: in function <[string "boot.lua"]:585>
[C]: in function 'xpcall'
[string "boot.lua"]:793: in function <[string "boot.lua"]:780>
[C]: in function 'xpcall'
Error: [string "boot.lua"]:714: UTF-8 decoding error: Invalid UTF-8
stack traceback:
[string "boot.lua"]:777: in function <[string "boot.lua"]:773>
[C]: in function 'printf'
[string "boot.lua"]:714: in function 'draw'
[string "boot.lua"]:756: in function <[string "boot.lua"]:730>
[C]: in function 'xpcall'

Tools: Hot Particles, LuaPreprocess, (more) Games: Momento Temporis: Light from the Deep, Energize!
"If each mistake being made is a new one, then progress is being made."
apicici
Prole
Posts: 5
Joined: Wed Dec 18, 2019 9:25 pm

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

ReFreezed wrote: Tue Jul 27, 2021 6:19 pm Looks cool, but I get an error at start-up for the editor (Windows, both 32 and 64-bit versions).
Thanks for noticing that! I had forgotten to set up the wrapper for the clipper library to export symbols on windows before I compiled it.

This version should work: https://github.com/apicici/pathfun-edit ... 4-v1.0.zip

Let me know how it goes!
togFox
Party member
Posts: 388
Joined: Sat Jan 30, 2021 9:46 am

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

Nice. A path finder that is not tile based.
ReFreezed
Party member
Posts: 304
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

apicici wrote: Tue Jul 27, 2021 7:46 pm Let me know how it goes!
Ok, now it works.
Tools: Hot Particles, LuaPreprocess, (more) Games: Momento Temporis: Light from the Deep, Energize!
"If each mistake being made is a new one, then progress is being made."
darkfrei
Party member
Posts: 418
Joined: Sat Feb 08, 2020 11:09 pm

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

togFox wrote: Tue Jul 27, 2021 10:54 pm Nice. A path finder that is not tile based.
Vertex-based
Falling in LÖVE
I Löve Lua and Love2D
Jasoco
Inner party member
Posts: 3668
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

I'm intrigued. How well does it perform when you have multiple entities all calculating paths at once?
apicici
Prole
Posts: 5
Joined: Wed Dec 18, 2019 9:25 pm

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

Jasoco wrote: Sun Aug 01, 2021 3:42 am I'm intrigued. How well does it perform when you have multiple entities all calculating paths at once?
I put together a quick test to check. On my systems it works fine with 100 entities, and some lag during the frame at which paths are calculated becomes noticeable with ~400 entities.
Attachments
pathfun_multiple_entities.love
pgimeno
Party member
Posts: 2821
Joined: Sun Oct 18, 2015 2:58 pm

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

The demo alone is fun to play with! It reminds me of Lemmings or Pikmin. I can only begin to imagine how fun it would be if it supported boids or some other similar group moving algorithm.
dusoft
Party member
Posts: 171
Joined: Fri Nov 08, 2013 12:07 am

### Re: pathfun: a pure Lua library for 2D pathfinding, with editor

apicici wrote: Tue Aug 03, 2021 8:24 pm
Jasoco wrote: Sun Aug 01, 2021 3:42 am I'm intrigued. How well does it perform when you have multiple entities all calculating paths at once?
I put together a quick test to check. On my systems it works fine with 100 entities, and some lag during the frame at which paths are calculated becomes noticeable with ~400 entities.
Cool. I tried 700+ and the lag is only during the first calculation. And this could be further calculated in smaller batches, so there wouldn't be any lag.

### Who is online

Users browsing this forum: No registered users and 10 guests