0

I am creating an A* algorithm in python, and I am trying to figure out how to save the locations that my algorithm has previously visited within a binary array such as the one below. 

nmap = np.array([
    [0,0,0,0],
    [1,1,1,0],
    [0,0,0,0],
    [1,0,1,1],
    [0,0,0,0]
    ])

The only way I can think of is to save the location of the previously visited binary numbers via coordinates. For instance,

nmap[0][0]

would save the first binary number in a list or dictionary, and thus would not be revisited. The problem is I am not sure how to achieve this. Please keep in mind that I want to save the coordinates as the algorithm is running instead of previously writing out the coordinates. My reasoning for this is if I have an array with thousands of integers, previously writing this code could be quite cumbersome. Anyone know how I can accomplish this?

bnicholl
  • 306
  • 2
  • 13
  • Think about it. How did you know there is a wall, or an obstacle, on the map? You can think the nodes in the close list is equivalent to a wall. – Yang Yang May 22 '17 at 18:44
  • @EvenYoung I was going to incorporate obstacles in my algorithm by not allowing movement where there is a 1. My main issue if figuring out how to hold state on previously visited nodes without having a specific key assigned to each node. – bnicholl May 22 '17 at 21:04
  • My previous question is a hint. Just set the node to 1 on the map when you visit it the first time, then treat it as an obstacle. – Yang Yang May 22 '17 at 21:37

2 Answers2

1

The most obvious choice is a Set. It gives amortized O(1) lookup performance. You can add visited nodes to the visitedSet by using the add method, and you can check if a node is in your visitedSet using the in operator:

>>> from sets import Set
>>> visitedSet = Set()
>>> visitedSet.add( (1,2) )
>>> print( (0,0) in visitedSet )
False
>>> print( (1,2) in visitedSet)
True
Austin
  • 8,018
  • 2
  • 31
  • 37
0

You can easily save the indexes to the coordinates in a list of tuples for that:

visited = [(0,0), (2,0)...]
Netwave
  • 40,134
  • 6
  • 50
  • 93
  • I want them to save the coordinates as the algorithm is running instead of previously writing out the coordinates. My reasoning for this is if I have an array with thousands of integers, previously writing this code out could be quite cumbersome. – bnicholl May 22 '17 at 16:29
  • @bnicholl, i cant understand what you try to achieve then, could you expand your example? – Netwave May 22 '17 at 17:43