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

[apicici]

• pathfun: git repository, download
• pathfun-editor: git repository, download

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

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]

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'

[apicici]

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]

Nice. A path finder that is not tile based.

[ReFreezed]

Let me know how it goes!

Ok, now it works.

[darkfrei]

Nice. A path finder that is not tile based.

Vertex-based

[Jasoco]

I'm intrigued. How well does it perform when you have multiple entities all calculating paths at once?

[apicici]

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.

[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.

[dusoft]

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.