Skip to content
Sample Recipe for A* algorithm
Python
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
mazes
output
#README#
.gitignore
README
main.py

README

Author: Yohei YASUKAWA
Date: 01/31/2011
Mail: yasulab@gmail.com

A* Search Algorithm
============================

Description
-----------
This program implements the idea of A* algorithm
with following three heuristic functions:

- 1. Zero heuristic
- 2. Manhattan heuristic
- 3. Euclidean heuristic

In Zero heuristic, each space in a maze is equally cost,
so the next-exploring space totally depends on how spaces
are put into the queue. In this program, the spaces are
put into the queue in the way from top left to bottom right.
For example, if the program seeks the 3x3 map, it should put
as follows:

1 2 3
4 5 6
7 8 9


Manhattan heuristic calculates costs with Manhattan distance.
For example, in the following state, where the '*' is goal,
'x' is current location, and 'o' is the start, the cost
should be 4.

    * . .
    . x .
    . . o
    
In addition, if some elements in the queue has
same cost, the queue sorts them according to the sort of
Queue.PriorityQueue in Python library.

In particular, the priority queue sorts elements in the queue
by the ascend order of number x if given element's costs are
all same. Also, it sorts them by the ascend order of number y
if given element's costs and number of x are all same.


Euclidean heuristic calculates costs with Euclidean distance.
For example, in the following state, the cost should be 10.

f(x) = h(x) + g(x)
     = sqrt(3^2+4^2) + sqrt(4^2+3^2)
     = 5 + 5
     = 10

    * . . . . . . . .
    . . . . . . . . .
    . . . . . . . . .
    . . . . o . . . .
    . . . . . . . . .
    . . . . . . . . .
    . . . . . . . . x

So, using these heuristics, this program shows how A* algorithm
works step by step.



How To Run
----------
1. Get python 2.6 or higher

2. Type following command in your terminal.

  $ python main.py [options]

Options are not needed to run the program. But,
if you want to specify input files, heuristic
function, or make program display much information,
the following options will be useful.

  -h, --help            show this help message and exit
  -f FILE, --file=FILE  choose a formatted text file for creating a maze. This
                        program uses 'mazes/sample' by default.
  -H HEURISTICS         choose a heuristic function for A* algorithm from
     			'zero', 'manhattan', 'euclidean' (or it's abbreviations:
			'z', 'm', and 'e'). This option sets'zero' by default.
  -v, --verbose         display information verbosely.
  -d, --diagonal        switch to the program that allows diagonal travel for
                        a cost of 3, and horizontal/vertical motion costs 2.


Get Latest Code
---------------
If you would like to see/run the latest code,
type following command to clone it with Git.

  $ git clone git://github.com/yasulab/a-star-algorithm.git

Or, visit the following repository.

  https://github.com/yasulab/a-star-algorithm

To clone the code, you need to install Git.

   Git - Fast Version Control System
   http://git-scm.com/

You can’t perform that action at this time.