LoveAStar: A* Search in Lua/Love

[ishkabible]

Wouldn't this be an issue of graph construction and not the algorithm? You would have to construct the graph so that there wasn't an edge going diagonal there; It has nothing to do with the A* algorithm. IMO graph construction should be up to the user how to construct the graph. Particularly when it comes to irregular maps you would want to be able to construct your own graph.

The squares graph should just be a helper function if you ask me. The main interface should deal with edge and node construction. you could even add helpers for both behaviors.

Always strive to make code more flexible; arguing over which semantics you like better is a bad idea when you can have the best both

edit:
also, you could allow the specification of a prediction function(predicts the lengths of edges) so that it behaves more optimally with irregular graphs.

[MarekkPie]

My A* function is completely abstract. It already does follow everything you've said. The DEMO follows a certain rule, because how am I supposed to demo every map type?

There is absolutely nothing that is stopping Jasoco from making his own flattenMap function, which prunes out nodes of his graph that follow that specification. The flattenMap function I have provided does not, because it is FAR easier to do it this way.

Every single piece of information used in my A* is user provided: from the start/end functions to the list of neighbors, to the distance between each node (edit: even the heuristic used is up to the user). The only requirements I have is that you put this information into a "node" class, which I provide in my source code, so that it better interfaces with the algorithm.

This is the entire point of my second revision of the algorithm, as it clearly states on the original post of this thread:

Even more optimization, and a "final" release. It's also completely abstracted from any particular map, so you can make square maps, rectangular maps, hexagonal maps, circular maps, atlases, possibly even 3D space. Since I require you to shrink everything into a 1D array before use, the rigidity of the map doesn't really matter.

The demo is simply that. A demo. It is not A*.

[xjermx]

Will this be updated to 0.8.0?

Nevermind,

Changed the following lines in a copy of the code and it works great. thanks, MarekkPie.

51 local fb = love.graphics.newCanvas()
52 love.graphics.setCanvas(fb)
65 love.graphics.setCanvas()

[Roland_Yonaba]

Will this be updated to 0.8.0?

It doesn't need to.
The algorithm itself is not relevant to any version of love.
If you want to disable the warning screen when loading the demo application with love 0.8.0, just open the configuration file (conf.lua)
look for the line t.version (or add it) with "0.8.0" as its value.

Code: Select all

t.version = "0.8.0"

it should work fine.
If your video card supports framebuffers and Canvas, though.

[MarekkPie]

I don't use LOVE/Lua much anymore, but I made some fixes for the obvious compatibility issues. Here's the new file. I'll update the original post to link to the new version as well.

Roland is right, though. The code for the actual A* is LOVE independent; it's only the demo that was incompatible.

[coffee]

I don't use LOVE/Lua much anymore

So you trade us for Haxe... you a punk!
The best for you Marekk! Keep visiting us!

[Roland_Yonaba]

I took a closer look at the code, MarekkPie..This is awful. Well done!
Indeed, using binary heap makes Aster run faster.
Did you wrote the binary heap prototype by yourself ? Did you use some documentation for the algorithms (the heap:pop method, especially).
I noticied your implementation can be used as min-heap or max-heap, depending on a custom comparison function which can be easily written.
Nice.

[MarekkPie]

Update: updated the Github repo to reflect the current version. The repo should also be more sane than it was before. Only text files are in the code section; the demo is found in the Downloads section.

This is awful. Well done!

Que? Wie bitte? What?

Indeed, using binary heap makes Aster run faster.
Did you wrote the binary heap prototype by yourself ? Did you use some documentation for the algorithms (the heap:pop method, especially).
I noticied your implementation can be used as min-heap or max-heap, depending on a custom comparison function which can be easily written.
Nice.

Most of the info I got from the links you can find in the original post. I initially wrote it very naively, and was getting enormously crapping run times. So I rewrote it, and in the process tried to optimize it with other things I had learned.

The binary heap is not mine. I think the contact/licensing information for it can be found in the source file. I've finally taken a formal course in data structures and algorithms now, though, so I'm sure if I ran back through the code I could optimize it some more and make it nicer, but I've got other things on my docket at the moment.

One thing I wish I was able to figure out was a way to get this to run in a separate thread, but the 0.7.2 documentation for threads was severely lacking. Lemme refresh the main Github repo with the new version, and if anyone wants to take a swing at that, by all means, fork it and go.

[Roland_Yonaba]

Just to mention that I tried to write another implentation of binary-heaps.
You can find it here.

@MarekkPie : Out of topic, are you the original author of Using Binary Heaps in A* Pathfinding ?

[MarekkPie]

No, lol. Binary heaps and shortest path algorithms have been used together for a long, long time.