Luafinding - fast, efficient & easy A* pathfinding library

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

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

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?

[Xii]

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.

[GlorifiedPig]

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.

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 : )

[Gunroar:Cannon()]

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

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

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]

It looks good