5 ms·

There are about a zillion implementations of vanilla A* on the internet. What's particularly interesting about this one? Do you have some cool new heuristic fun

There are about a zillion implementations of vanilla A* on the internet. What's particularly interesting about this one? Do you have some cool new heuristic function or some nice insight into how the search works? The as-is version is pretty crappy. I mean, I can't even see the nodes expanded!

coderdude 15y ago
As far as I can tell there is nothing particularly interesting about this implementation. It's cool because it lets you play with it and because the code is pretty short which makes it easy for anyone unfamiliar with the algorithm to grok how it works. It also has some nice documentation: http://www.matthewtrost.org/projects/astar/documentation.html http://www.matthewtrost.org/projects/astar/documentation.htm... For the Python programmer here is a very short implementation of A* that someone on Stack Overflow posted: http://stackoverflow.com/questions/4159331/python-speed-up-an-a-star-pathfinding-algorithm http://stackoverflow.com/questions/4159331/python-speed-up-a...
- gradstudent 15y ago
  Actually, I found the documentation reasonably poor. It does a good job of explaining the API but does little to provide a would-be user with any insights into why the search works, how it works or how efficient it is. It doesn't even discuss why (or when) I might choose one of the three given heuristic functions over the others. i.e. despite its length, it's not actually a very useful document.
  - coderdude 15y ago
    While I agree that what you listed would be useful to include I think it's important to note that it is documentation of his implementation (what the various parameters are for) and not of how A* works. To that end he did a good job. I especially like the little ideas he throws in under "Extending astar.js." He links to the Wikipedia entry for those who want to know more about how A* works.
    - gradstudent 15y ago
      Suppose the C++ STL documentation, such as it is, linked you to CLRS. Would you regard it as adequate or would you demand more? I don't expect a rigorous academic treatment here but at least something to tell me (a) how efficient the implementation is and (b) why (or when) I might want to use X or Y provided feature over Z. For example: why is the Euclidean heuristic "slow"? Is it a shitty implementation? Is it because it's underestimating the goal distance too much? Another gripe: the author doesn't even tell me what kind of open and closed list implementations are in use! I don't mean to be a hater but this fails at contributing something novel (which it doesn't), it fails as a learning resource which teaches something interesting (which it doesn't) and it fails as a well documented programming hack (which it isn't).
  - deleted 15y ago
    [deleted]
StavrosK 15y ago
What sort of cool new heuristic function could one have? All you need is the three shown there.
- gradstudent 15y ago
  Excuse me? The study of better heuristics to guide search is a very active area of AI research. See, for example, Sturtevant et al's 2009 work on True Distance Heuristics or their 2011 work on compressed heuristic functions presented at AAAI last week.
  - StavrosK 15y ago
    Is this research focused on search on two-dimensional grids?
    - gradstudent 15y ago
      No, it's more general. The central idea is to identify "interesting" nodes in explicit graphs which can be used to improve heuristic accuracy. You might even be able to do this for implicit graphs though that extension is not straightforward. I suspect you'd need some kind of pattern database approach. Harabor and Grastien had a nice AAAI 2011 paper on speeding up heuristic search -- which is specific to 2D grids.
      - StavrosK 15y ago
        Exactly, my point was that you can't improve that much on heuristics for a 2D grid. The heuristics are already admissible and simple, pretty much all you can do is speed it up.
        marshray 15y ago
        Well, just to put in a hopeful word here, for hundreds of years mathematicians had figured that the most efficient way to multiply square matrices was O(n^3). Yet today it's significantly less than that, even in practice.
AlexC04 15y ago
Even if it's not the best implementation, it could be considered as scaffolding upon which to improve. While you clearly have enough experience with A* to tell the difference between a good and bad implementation, I've not got the same background (I've been reading about it, looking at flash implementations and trying to figure out how the heck I was going to do it in JS+Canvas). Maybe there's a short list of glaring inefficiencies or places where this implementation is behind the curve. What's it missing? I'm sure that for the OP this is a reasonably significant achievement, to me it's voodoo... and to John Carmack it's something else. I doubt Carmack would be so derisive of someone's professional development. Would you tell an 8 year old that their finger paintings were pretty crappy too? Criticism can be valid and encouraging if delivered in the right way.
- gradstudent 15y ago
  Perhaps we have different expectations of what we think should appear on Hacker News. I come here to find out about cool new stuff that hackers elsewhere in the world are working on. To me, an individual learning a fundamental AI algorithm isn't all that interesting. Particularly as the OP in this case has nothing to add to the discussion; he's just crowing to the world: "Look! I implemented someone else's idea!"
  - coderdude 15y ago
    That's retarded. 90% of the articles on the homepage at all times are garbage tech gossip. I don't see you insulting those authors. You're either a troll or just a jerk.
    - gradstudent 15y ago
      Wtf? This is a news site. How is somebody learning something fundamental news? Would you like to see a front-page story every time some kid completes an algorithms assignment? I don't. Not because the learning is unimportant, simply because it's most interesting to the person doing the learning. All I'm saying is this: if you've learned something cool, and you want to tell the world about it, you need to present it in a way such that your learning contributes something to the learning of others. For example: explaining a complicated idea in really simple terms that anyone can understand (such as this cute example of the Halting Problem proof: http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html). Another way to make your learning interesting to other people is to present an implementation that provides insight into the subject. The author tried to do this but I argue his execution is poor. I learned nothing from his app and nothing from his documentation. No implementation insights, no analysis, no beautiful code, nothing. Nada. Zip. Zilch. It's just a web-based A* implementation. Of which there are zillions.
MortenK 15y ago
Where is your A* implementation?

coderdude 15y ago

As far as I can tell there is nothing particularly interesting about this implementation. It's cool because it lets you play with it and because the code is pretty short which makes it easy for anyone unfamiliar with the algorithm to grok how it works. It also has some nice documentation: http://www.matthewtrost.org/projects/astar/documentation.html http://www.matthewtrost.org/projects/astar/documentation.htm... For the Python programmer here is a very short implementation of A* that someone on Stack Overflow posted: http://stackoverflow.com/questions/4159331/python-speed-up-an-a-star-pathfinding-algorithm http://stackoverflow.com/questions/4159331/python-speed-up-a...

gradstudent 15y ago
Actually, I found the documentation reasonably poor. It does a good job of explaining the API but does little to provide a would-be user with any insights into why the search works, how it works or how efficient it is. It doesn't even discuss why (or when) I might choose one of the three given heuristic functions over the others. i.e. despite its length, it's not actually a very useful document.
- coderdude 15y ago
  While I agree that what you listed would be useful to include I think it's important to note that it is documentation of his implementation (what the various parameters are for) and not of how A* works. To that end he did a good job. I especially like the little ideas he throws in under "Extending astar.js." He links to the Wikipedia entry for those who want to know more about how A* works.
  - gradstudent 15y ago
    Suppose the C++ STL documentation, such as it is, linked you to CLRS. Would you regard it as adequate or would you demand more? I don't expect a rigorous academic treatment here but at least something to tell me (a) how efficient the implementation is and (b) why (or when) I might want to use X or Y provided feature over Z. For example: why is the Euclidean heuristic "slow"? Is it a shitty implementation? Is it because it's underestimating the goal distance too much? Another gripe: the author doesn't even tell me what kind of open and closed list implementations are in use! I don't mean to be a hater but this fails at contributing something novel (which it doesn't), it fails as a learning resource which teaches something interesting (which it doesn't) and it fails as a well documented programming hack (which it isn't).
- deleted 15y ago
  [deleted]

StavrosK 15y ago

What sort of cool new heuristic function could one have? All you need is the three shown there.

gradstudent 15y ago
Excuse me? The study of better heuristics to guide search is a very active area of AI research. See, for example, Sturtevant et al's 2009 work on True Distance Heuristics or their 2011 work on compressed heuristic functions presented at AAAI last week.
- StavrosK 15y ago
  Is this research focused on search on two-dimensional grids?
  - gradstudent 15y ago
    No, it's more general. The central idea is to identify "interesting" nodes in explicit graphs which can be used to improve heuristic accuracy. You might even be able to do this for implicit graphs though that extension is not straightforward. I suspect you'd need some kind of pattern database approach. Harabor and Grastien had a nice AAAI 2011 paper on speeding up heuristic search -- which is specific to 2D grids.
    - StavrosK 15y ago
      Exactly, my point was that you can't improve that much on heuristics for a 2D grid. The heuristics are already admissible and simple, pretty much all you can do is speed it up.
      - marshray 15y ago
        Well, just to put in a hopeful word here, for hundreds of years mathematicians had figured that the most efficient way to multiply square matrices was O(n^3). Yet today it's significantly less than that, even in practice.

AlexC04 15y ago

Even if it's not the best implementation, it could be considered as scaffolding upon which to improve. While you clearly have enough experience with A* to tell the difference between a good and bad implementation, I've not got the same background (I've been reading about it, looking at flash implementations and trying to figure out how the heck I was going to do it in JS+Canvas). Maybe there's a short list of glaring inefficiencies or places where this implementation is behind the curve. What's it missing? I'm sure that for the OP this is a reasonably significant achievement, to me it's voodoo... and to John Carmack it's something else. I doubt Carmack would be so derisive of someone's professional development. Would you tell an 8 year old that their finger paintings were pretty crappy too? Criticism can be valid and encouraging if delivered in the right way.

gradstudent 15y ago
Perhaps we have different expectations of what we think should appear on Hacker News. I come here to find out about cool new stuff that hackers elsewhere in the world are working on. To me, an individual learning a fundamental AI algorithm isn't all that interesting. Particularly as the OP in this case has nothing to add to the discussion; he's just crowing to the world: "Look! I implemented someone else's idea!"
- coderdude 15y ago
  That's retarded. 90% of the articles on the homepage at all times are garbage tech gossip. I don't see you insulting those authors. You're either a troll or just a jerk.
  - gradstudent 15y ago
    Wtf? This is a news site. How is somebody learning something fundamental news? Would you like to see a front-page story every time some kid completes an algorithms assignment? I don't. Not because the learning is unimportant, simply because it's most interesting to the person doing the learning. All I'm saying is this: if you've learned something cool, and you want to tell the world about it, you need to present it in a way such that your learning contributes something to the learning of others. For example: explaining a complicated idea in really simple terms that anyone can understand (such as this cute example of the Halting Problem proof: http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html). Another way to make your learning interesting to other people is to present an implementation that provides insight into the subject. The author tried to do this but I argue his execution is poor. I learned nothing from his app and nothing from his documentation. No implementation insights, no analysis, no beautiful code, nothing. Nada. Zip. Zilch. It's just a web-based A* implementation. Of which there are zillions.

MortenK 15y ago

Where is your A* implementation?