For a matrix without obstacles

a-star-search.py

'''
1 1 1 1
1 1 1 1
1 1 1 1  
1 1 1 1
'''
import heapq
from math import sqrt
from math import pow

class Cell():
	
	def __init__(self, x, y):
		self.x = x
		self.y = y
		self.g = 0
		self.h = 0
		self.f = 0
		self.parent = None
	def __repr__(self):
		return str((int(self.x), int(self.y)))

class A_Star_Search(object):
	def __init__(self):
		self.opened = []
		heapq.heapify(self.opened)
		self.closed = set()
		self.cells = []
		self.grid_height = 4
		self.grid_width = 4

	def init_grid(self):
		for x in range(self.grid_width):
			for y in range(self.grid_height):
				self.cells.append(Cell(x,y))
		self.start = self.get_cell(0,0)
		self.end = self.get_cell(2,2)

	def get_heuristic(self, cell):
		return 10*(abs(cell.x - self.end.x) + abs(cell.y - self.end.y))

	def get_cell(self, x, y):
		return self.cells[x * self.grid_height + y]

	def get_adjecent_cells(self, cell):
		cells = []
		if cell.x < self.grid_width-1:
			cells.append(self.get_cell(cell.x+1, cell.y))
		if cell.y > 0:
			cells.append(self.get_cell(cell.x, cell.y-1))
		if cell.x > 0:
			cells.append(self.get_cell(cell.x-1, cell.y))
		if cell.y < self.grid_height-1:
			cells.append(self.get_cell(cell.x, cell.y+1))
		return cells

	def update_cell(self, adj, cell):
		adj.g = cell.g+10
		adj.h = self.get_heuristic(adj)
		adj.parent = cell
		adj.f = adj.g + adj.h

	def display_path(self):
		cell = self.end
		print 'path: cell: %d,%d' %(cell.x, cell.y)
		while cell.parent is not self.start:
			cell = cell.parent
			print 'path: cell: %d,%d' % (cell.x, cell.y)
		cell = cell.parent
		print 'path: cell: %d,%d' % (cell.x, cell.y)

	def process(self):
		heapq.heappush(self.opened, (self.start.f, self.start))
		while len(self.opened):
			f,cell = heapq.heappop(self.opened)
			self.closed.add(cell)
			if cell is self.end:
				self.display_path()
				break
			adj_cells = self.get_adjecent_cells(cell)
			for adj_cell in adj_cells:
				if adj_cell not in self.closed:
					if (adj_cell.f, adj_cell) not in self.opened:
						if adj_cell.g > cell.g+10:
							self.update_cell(adj_cell, cell)
						else:
							self.update_cell(adj_cell, cell)
							heapq.heappush(self.opened, (adj_cell.f, adj_cell))

if __name__ == '__main__':
	problem = A_Star_Search()
	problem.init_grid()
	problem.process()