I'll try to be brief here. I'm trying to implement A Star on Python, but obviously I'm doing something wrong, because when I test it, it doesn't return the list of steps to get to the destination.
Basically, the context is: I have a map, represented as a graph, formed by nodes. I have a Player class, a Node class, and a Graph class. That doens't matter much, but might be necessary. The player has to get to the nearest node with a Coin in it, which is also a Class.
My implementation is based on the Wikipedia pseudocode, but for some reason it won't work. I'm almost completely sure that my mistake is on A* Star, but i can't find it. Here, i'll put the two functions that i made regarding A Star. Hope it's not too messy, i'm just starting with programming and i like commenting a lot.
I would really appreciate any help to find the problem :)
Note: I'm not an english speaker, so i'm sorry for my mistakes. Wish, in a few years, i'll be able to comunicate better.
def A_Star(player,graph,array_of_available_coins):
# Define the initial position and the last position, where the coin is
initial_position=player.position # Player is a class. Position is of type Node
final_position=closest_cpin(player,graph,array_of_available_coins)
# Define the open_set, closed_set, and work with a Heap.
open_set=[initial_position] # Open_set will be initialized with the current position of the player
closed_set=[]
heapq.heapify(open_set) # Converts the open_set into a Python Heap (or Priority Queue)
came_from={} # It's a dictionary where each key is the a node, and the value is the previous node in the path
# Modify G and H, and therefore F, of the initial position. G of the inicial position is 0.
#And H of the initial position is the pitagoric distance.
initial_position.modify_g_and_h(0,initial_position.distance(final_position))
while open_set!=[]:
square=heapq.heappop(open_set) # Gets the least value of the open_set
if square.is_wall(): # If it's a Wall, the player can't move over it.
continue
if square==final_position:
movements=[] # Creates a empty array to save the movements
rebuild_path(came_from,square,movements) # Calls the function to rebuild the path
player.add_movements_array(movements) # Copies the movements into the movements array of the player
return
# In this point, the square is not a wall and it's not the final_position
closed_set.append(square) # Add the square into the closed_set
neighbours=graph.see_neighbours(square) # Checks all the neighbours of the current square
for neigh in neighbours:
if neigh.is_wall()==True:
continue
if neigh in closed_set:
continue
# Calculates the new G, H and F values
g_aux=square.see_g()+square.get_cost(neigh) # Current g + the cost to get from current to neighbour
h_aux=neigh.distance(final_position) # Pitagoric distance between the neighbour and the last position
f_aux=g_aux+h_aux # F=G+H
if neigh not in open_set:
heapq.heappush(open_set,neigh) # Adds the neigh into the open_set
is_better=True
elif f_aux<neigh.see_f():
is_better=True
else:
is_better=False
if is_better==True:
came_from[neigh]=square # The actual neigh came from the actual square
neigh.modify_g_and_h(g_aux,h_aux) #Modifies the g and h values of the actual neighbour
return None
def rebuild_path(came_from,square,array_of_movements):
array_of_movements.insert(0,square) # Adds, in the first position of the array, the square it gets by parameter
if not square in came_from: # if there is no key "square" in the came_from dictionary, then it's the first position
array_of_movements.remove(array_of_movements[0]) # Gets the first element of the array out (because i need it to be that way later)
return array_of_movements
rebuild_path(came_from,came_from[square],array_of_movements)
return
The thing is, i have to implement the algorithm, because it's part of an Excercise (much larger, with Pygame and everything), and this is the only thing that's making me nervous. If i use a library, it'll count as if i didn't do it, so i'll have to deliver it again :(
I would recommend networkx
import networkx
this can do this kind of stuff:
#!/usr/bin/env python
# encoding: utf-8
"""
Example of creating a block model using the blockmodel function in NX. Data used is the Hartford, CT drug users network:
@article{,
title = {Social Networks of Drug Users in {High-Risk} Sites: Finding the Connections},
volume = {6},
shorttitle = {Social Networks of Drug Users in {High-Risk} Sites},
url = {http://dx.doi.org/10.1023/A:1015457400897},
doi = {10.1023/A:1015457400897},
number = {2},
journal = {{AIDS} and Behavior},
author = {Margaret R. Weeks and Scott Clair and Stephen P. Borgatti and Kim Radda and Jean J. Schensul},
month = jun,
year = {2002},
pages = {193--206}
}
"""
__author__ = """\n""".join(['Drew Conway <drew.conway@nyu.edu>',
'Aric Hagberg <hagberg@lanl.gov>'])
from collections import defaultdict
import networkx as nx
import numpy
from scipy.cluster import hierarchy
from scipy.spatial import distance
import matplotlib.pyplot as plt
def create_hc(G):
"""Creates hierarchical cluster of graph G from distance matrix"""
path_length=nx.all_pairs_shortest_path_length(G)
distances=numpy.zeros((len(G),len(G)))
for u,p in path_length.items():
for v,d in p.items():
distances[u][v]=d
# Create hierarchical cluster
Y=distance.squareform(distances)
Z=hierarchy.complete(Y) # Creates HC using farthest point linkage
# This partition selection is arbitrary, for illustrive purposes
membership=list(hierarchy.fcluster(Z,t=1.15))
# Create collection of lists for blockmodel
partition=defaultdict(list)
for n,p in zip(list(range(len(G))),membership):
partition[p].append(n)
return list(partition.values())
if __name__ == '__main__':
G=nx.read_edgelist("hartford_drug.edgelist")
# Extract largest connected component into graph H
H=nx.connected_component_subgraphs(G)[0]
# Makes life easier to have consecutively labeled integer nodes
H=nx.convert_node_labels_to_integers(H)
# Create parititions with hierarchical clustering
partitions=create_hc(H)
# Build blockmodel graph
BM=nx.blockmodel(H,partitions)
# Draw original graph
pos=nx.spring_layout(H,iterations=100)
fig=plt.figure(1,figsize=(6,10))
ax=fig.add_subplot(211)
nx.draw(H,pos,with_labels=False,node_size=10)
plt.xlim(0,1)
plt.ylim(0,1)
# Draw block model with weighted edges and nodes sized by number of internal nodes
node_size=[BM.node[x]['nnodes']*10 for x in BM.nodes()]
edge_width=[(2*d['weight']) for (u,v,d) in BM.edges(data=True)]
# Set positions to mean of positions of internal nodes from original graph
posBM={}
for n in BM:
xy=numpy.array([pos[u] for u in BM.node[n]['graph']])
posBM[n]=xy.mean(axis=0)
ax=fig.add_subplot(212)
nx.draw(BM,posBM,node_size=node_size,width=edge_width,with_labels=False)
plt.xlim(0,1)
plt.ylim(0,1)
plt.axis('off')
plt.savefig('hartford_drug_block_model.png')