LÖVE

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

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.

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?

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.

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.

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

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

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

It looks good