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

Showcase your libraries, tools and other projects that help your fellow love users.
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:
• Add code to load the background image into the editor
• 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: 323
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'
navigation/polygons.lua:6: in main chunk
[C]: in function 'require'
navigation/editor.lua:8: in main chunk
[C]: in function 'require'
navigation/init.lua:3: in main chunk
[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'
main.lua:11: in function 'load'
[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: 451
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

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

Nice. A path finder that is not tile based.
ReFreezed
Party member
Posts: 323
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: 439
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: 3676
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
(10.62 KiB) Downloaded 153 times
pgimeno
Party member
Posts: 2870
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: 174
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 7 guests