Jump to content
  • Advertisement
Sign in to follow this  
daniel_i_l

Python problem

This topic is 3989 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I just learned python and wanted to practice by implementing the A* algorithm and using it to solve the 8-puzzle. So I made a node class that looks like this:
class Node:
    def  __init__(self, data):
        self.data = data
    parent = 0
    f,g,h=0,0,0


where data is a 1D representation of the 2D board (so that data[x+3*y] is the (x,y) square) where the emty square has the value 0. I also have a function called GenerateNeighbors(node) which takes a node as input and returns a list of neighboring nodes. Now, just to check that everything was working I made a function that shuffles a board using the GenerateNeighbors function:
def Shuffle(node, depth):
    if depth==0:
        return node.data, depth
    print node.data , depth
    Shuffle(GenerateNeighbors(node)[0],depth-1)


I know that it's not random at all but I did it just to see if it would work. So then I did:
start = [1,2,3,4,5,6,7,8,0]
print Shuffle(Node(start),10)


and got: [1, 2, 3, 4, 5, 6, 7, 8, 0] 10 [1, 2, 3, 4, 5, 0, 7, 8, 6] 9 [1, 2, 0, 4, 5, 3, 7, 8, 6] 8 [1, 2, 3, 4, 5, 0, 7, 8, 6] 7 [1, 2, 0, 4, 5, 3, 7, 8, 6] 6 [1, 2, 3, 4, 5, 0, 7, 8, 6] 5 [1, 2, 0, 4, 5, 3, 7, 8, 6] 4 [1, 2, 3, 4, 5, 0, 7, 8, 6] 3 [1, 2, 0, 4, 5, 3, 7, 8, 6] 2 [1, 2, 3, 4, 5, 0, 7, 8, 6] 1 None So I know that the functions are working but why did I get None at the end? Thanks.

Share this post


Link to post
Share on other sites
Advertisement

print Shuffle(Node(start),10)

This prints only the return value of the first or outermost call to Shuffle. Shuffle only returns (node.data, depth) if depth == 0. But depth == 10, and since there is no return statement in the remaining part of the function, it returns None. A function that doesn't specify a return value returns None. It's similar to void in C++.

The rest of the printed lines come from the print statement within the Shuffle function. Since this is being called recursively, the first call returns last, hence the None is printed last rather than first.

Share this post


Link to post
Share on other sites
You would have to return it all the way back down the call stack.

def Shuffle(node, depth):
if depth==0:
return node.data, depth
return Shuffle(GenerateNeighbors(node)[0],depth-1)


Returning depth is redundant though. It will always == 0 at the point it is returned.
Recursion seems unnecessary in this case. Consider an iterative approach:

def Shuffle(node, depth):
for i in xrange(depth):
node = GenerateNeighbors(node)[0]
return node.data


As far as I can tell, this is equivelent to the recursive version.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!