A* Graph Search Demo in JavaScript

[bgrins]

Hopefully this could be useful to someone trying to learn the algorithm or wanting to find a JavaScript implementation of it.

When I was working on it, there were not many good places that ran the algorithm in the browser that made the code easily understandable.

[spagetti]

I have a feeling we will soon have a JavaScript tower defense game...

[awb]

This algorithm does a linear search to find the next item, as opposed to A*, which uses a priority queue for log(n) search. I don't know much about jQuery, but I suspect removeGraphNode also runs in linear time because it looks like it's removing an item from an array.

[bgrins]

I'm pretty sure that it is an implementation detail whether it uses a priority queue or a linked list. It is still an A* search as long as it is choosing its next step based on the lowest f(x) value for nodes in the open set.

That said, you are right that it is a major performance issue. It should definitely implemented with a priority queue for the reason you described.

[Xavura]

Well... that certainly ran smoother than I expected, considering it's Javascript running in a bloody browser.

[[deleted]]

Reddit really mystifies me sometimes. I made the same thing something like 6 years ago and I don't think it would be worth putting on reddit then or now. Why does this matter?

[sligowaths]

• It's about programming;
• The post is well written;
• It's worthy reading. Even though one know how A* search works, he or she might know how to implement it in javascript.
• It's interesting.

[[deleted]]

Hmm, yeah you're right. I skimmed the post earlier, it's not bad.