Solving mazes using Python: Simple recursivity and A* search | Hacker News Reader

Solving mazes using Python: Simple recursivity and A* search

laurentluce.com

14 pointslaurentluce7 comments

Not to be pedantic, but where's the recursion?

Seems like an instance of a common metaphor:

    while queue.hasElements():
      element = queue.pop()
      explore element if we haven't already
      put element's successors into queue using some priority

A correct implementation of A* might look simple, and indeed it's not the most complicated algorithm out there, but I wouldn't dismiss it until you've read and understand the proof of its optimality.

Of course, I've dealt with many search problems using A* (in particular, in the context of machine translation). I understand the algorithm and the proof of optimality. And I agree, the algorithm is very simple (not much different than uniform-cost search)--the complex part (in more general applications) is the heuristic function.

I don't see where I dismissed A*.

Maybe I misunderstood this:

>Seems like an instance of a common metaphor

That gave me the impression that A) it was new to you (due to the "seems to be") and that B) you weren't impressed ("common").

There are two separate algorithms - the first one is recursive.

I wonder how the algorithm would be affected by weave mazes. http://weblog.jamisbuck.org/2011/3/4/maze-generation-weave-m...

Neither is.

Reply on news.ycombinator.com