Luafinding - fast, efficient & easy A* pathfinding library

Showcase your libraries, tools and other projects that help your fellow love users.
Post Reply
GlorifiedPig
Prole
Posts: 15
Joined: Sat Feb 11, 2017 4:39 pm

Luafinding - fast, efficient & easy A* pathfinding library

Post by GlorifiedPig »

Luafinding
Luafinding is an A* module written in Lua with the main purposes being ease of use & optimization. Feel free to open any issues you find and make pull requests.

https://github.com/GlorifiedPig/Luafinding

Performance Tests
To run a performance test yourself, see "performance/performance.lua". Move "luafinding.lua", "vector.lua" and "heap.lua" to that folder and run "performance.lua" in your console. Here are my performance results:

Code: Select all

> luajit performance.lua
Using seed 1614795006
Building 100 x 100 sized map.
Generating 2000 random start/finish positions.
Finding 1000 paths.
Done in 0.309 seconds.
Average of 0.000309 per path.
To compare, "lua-star" runs at an average of 0.0017 seconds per path on my machine for a 100x100 map; that's an 81.8% improvement from one of the mainstream Love2D pathfinding methods.

Not to mention that a lot of Love2D implementations also feature a lot of O(n) for tables instead of indexing. When testing "lua-star" in Love2D, it ran at about 2 seconds per path - whereas Luafinding, on my machine, runs at 0.00034 seconds per path. That's an entire 99.98% decrease in computing time.

Love2D Implementation
To see an example of how this is implemented in Love2D, navigate to the "love2d-example" folder in the GitHub repo.

Image
User avatar
Xii
Party member
Posts: 137
Joined: Thu Aug 13, 2020 9:09 pm
Contact:

Re: Luafinding - fast, efficient & easy A* pathfinding library

Post by Xii »

You've locked into using a 2-dimensional regular grid. My maps aren't regular grids, so I can't use this. A generic pathfinding library wouldn't care about the topology of the game world, and would instead implement callbacks to get neighboring cells, etc. which is topology-agnostic.
GlorifiedPig
Prole
Posts: 15
Joined: Sat Feb 11, 2017 4:39 pm

Re: Luafinding - fast, efficient & easy A* pathfinding library

Post by GlorifiedPig »

Xii wrote: Wed Mar 03, 2021 6:56 pm You've locked into using a 2-dimensional regular grid. My maps aren't regular grids, so I can't use this. A generic pathfinding library wouldn't care about the topology of the game world, and would instead implement callbacks to get neighboring cells, etc. which is topology-agnostic.
You should be able to modify the Vector class and add support for 3 dimensions super easily, just make sure the :ID() function generates a unique number for each Vector, or am I misunderstanding you?
User avatar
Xii
Party member
Posts: 137
Joined: Thu Aug 13, 2020 9:09 pm
Contact:

Re: Luafinding - fast, efficient & easy A* pathfinding library

Post by Xii »

GlorifiedPig wrote: Wed Mar 03, 2021 7:30 pm You should be able to modify the Vector class and add support for 3 dimensions super easily, just make sure the :ID() function generates a unique number for each Vector, or am I misunderstanding you?
Well sure I could modify everything around the A* algorithm to adapt it to other topologies, but I'd expect an "A* library" to provide a generic, topology-agnostic implementation to begin with. Such libraries usually have a callback function to get the neighbours of a node, the heuristic distance to the goal, etc.. Here you've assumed a regular 2D grid with 8 cardinal directions.

And hey, that's ok for games taking place on regular 2D grids. I personally think such grids are supremely ugly and have woved to never use them. My grids are irregular. :awesome:

Image
GlorifiedPig
Prole
Posts: 15
Joined: Sat Feb 11, 2017 4:39 pm

Re: Luafinding - fast, efficient & easy A* pathfinding library

Post by GlorifiedPig »

Xii wrote: Wed Mar 03, 2021 10:47 pm
GlorifiedPig wrote: Wed Mar 03, 2021 7:30 pm You should be able to modify the Vector class and add support for 3 dimensions super easily, just make sure the :ID() function generates a unique number for each Vector, or am I misunderstanding you?
Well sure I could modify everything around the A* algorithm to adapt it to other topologies, but I'd expect an "A* library" to provide a generic, topology-agnostic implementation to begin with. Such libraries usually have a callback function to get the neighbours of a node, the heuristic distance to the goal, etc.. Here you've assumed a regular 2D grid with 8 cardinal directions.

And hey, that's ok for games taking place on regular 2D grids. I personally think such grids are supremely ugly and have woved to never use them. My grids are irregular. :awesome:

Image
This A* library was mainly made for myself in future tile games, I didn't think at all to add support for other nodes since it'd be an immensely extra amount of time for something that was designed to be simple, short & sweet to begin with - it's open source after all, so if you want something added you can : )
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Luafinding - fast, efficient & easy A* pathfinding library

Post by Gunroar:Cannon() »

GlorifiedPig wrote: Wed Mar 03, 2021 6:31 pm Luafinding
Luafinding is an A* module written in Lua with the main purposes being ease of use & optimization. Feel free to open any issues you find and make pull requests.
Is it faster than Jumper? https://www.love2d.org/wiki/Jumper
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
GlorifiedPig
Prole
Posts: 15
Joined: Sat Feb 11, 2017 4:39 pm

Re: Luafinding - fast, efficient & easy A* pathfinding library

Post by GlorifiedPig »

Gunroar:Cannon() wrote: Sat Mar 06, 2021 6:11 pm
GlorifiedPig wrote: Wed Mar 03, 2021 6:31 pm Luafinding
Luafinding is an A* module written in Lua with the main purposes being ease of use & optimization. Feel free to open any issues you find and make pull requests.
Is it faster than Jumper? https://www.love2d.org/wiki/Jumper
Nope, Jumper takes the cake for being the most optimized - I will keep working on it as time goes by & implement similar methods in hopes of getting an even higher speed
monolifed
Party member
Posts: 188
Joined: Sat Feb 06, 2016 9:42 pm

Re: Luafinding - fast, efficient & easy A* pathfinding library

Post by monolifed »

It looks good
Post Reply

Who is online

Users browsing this forum: No registered users and 15 guests