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: 23
Joined: Wed Dec 18, 2019 9:25 pm

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

Post by apicici »

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

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:

Image

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:

Image

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.
Last edited by apicici on Sat Dec 09, 2023 10:45 pm, edited 1 time in total.
User avatar
ReFreezed
Party member
Posts: 612
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

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

Post by ReFreezed »

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, InputField, (more) Games: Momento Temporis
"If each mistake being made is a new one, then progress is being made."
apicici
Prole
Posts: 23
Joined: Wed Dec 18, 2019 9:25 pm

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

Post by apicici »

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!
User avatar
togFox
Party member
Posts: 764
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

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

Post by togFox »

Nice. A path finder that is not tile based. :)
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
ReFreezed
Party member
Posts: 612
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

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

Post by ReFreezed »

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

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

Post by darkfrei »

togFox wrote: Tue Jul 27, 2021 10:54 pm Nice. A path finder that is not tile based. :)
Vertex-based :)
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
Jasoco
Inner party member
Posts: 3725
Joined: Mon Jun 22, 2009 9:35 am
Location: Pennsylvania, USA
Contact:

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

Post by Jasoco »

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

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

Post by apicici »

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 388 times
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

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

Post by pgimeno »

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.
User avatar
dusoft
Party member
Posts: 482
Joined: Fri Nov 08, 2013 12:07 am
Location: Europe usually
Contact:

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

Post by dusoft »

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.
Post Reply

Who is online

Users browsing this forum: No registered users and 17 guests