Page 1 of 1

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

Posted: Tue Jul 27, 2021 1:51 pm
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.

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

Posted: Tue Jul 27, 2021 6:19 pm
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'

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

Posted: Tue Jul 27, 2021 7:46 pm
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!

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

Posted: Tue Jul 27, 2021 10:54 pm
by togFox
Nice. A path finder that is not tile based. :)

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

Posted: Wed Jul 28, 2021 12:16 am
by ReFreezed
apicici wrote: Tue Jul 27, 2021 7:46 pm Let me know how it goes!
Ok, now it works. :)

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

Posted: Wed Jul 28, 2021 8:14 am
by darkfrei
togFox wrote: Tue Jul 27, 2021 10:54 pm Nice. A path finder that is not tile based. :)
Vertex-based :)

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

Posted: Sun Aug 01, 2021 3:42 am
by Jasoco
I'm intrigued. How well does it perform when you have multiple entities all calculating paths at once?

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

Posted: Tue Aug 03, 2021 8:24 pm
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.

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

Posted: Tue Aug 03, 2021 9:18 pm
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.

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

Posted: Tue Aug 17, 2021 7:23 pm
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.