Solving mazes using Python: Simple recursivity and A* search

http://www.laurentluce.com/?p=264

by laurentluce • 15 years ago

14 7 15 years ago

orijing2• 15 years ago

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

dminor• 15 years ago

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

endtime2• 15 years ago

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.

orijing2• 15 years ago

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

Kafka• 15 years ago

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

mukyu• 15 years ago

Neither is.

Solving mazes using Python: Simple recursivity and A* search

Related Stories