0

I learn python just about one month. This is a recursive function I worte for my Pygame to find the correct way in a polygon without retreat. It's just a Pentagon here, (0,1,2,3,4) are vertices' number.

However, this code works with two global variables: 

last_poses = {}
route_all = []

This means I have to initialize those two variables every time I call it. And I also try to return the all the available route lines, but it didn't work properly.

This result comes from the global variable, it's correct:

[{0: 0, 1: 4, 2: 3, 3: 2, 4: 1, 5: 0}, {0: 0, 1: 4, 2: 3, 3: 2, 4: 1, 5: 0}]

This result comes from return value: 

[{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 0}]

My question is to return the correct value without global variables. Anyone who can help me resolve this, I really appreciate that. 

legal_action = ((4,1),(0,2),(1,3),(2,4),(0,3))

def route_cal(start_pos, steps):
    global last_poses,route_all
    last_poses[steps] = start_pos
    steps -= 1
    dest_all = list(legal_action[start_pos])

    if len(last_poses) >= 2:
        for i in dest_all:
            if i == last_poses[steps+2]:
                dest_all.remove(i)
    if steps > 0:
        for pos in dest_all:
            # route_cal(pos,steps)
            return route_cal(pos,steps)
    elif steps == 0:
        last_poses[steps] = dest_all[0]
        route_all.append(last_poses)
        return route_all
    # return route_all

last_poses = {}
route_all = []
# route_cal(0, 5)
# print route_all

routelines = route_cal(0,5)
print routelines

Circuit of my game

M. Chen
  • 135
  • 6
  • I'd love to help, but I'm having a little trouble following the logic. First of all, why the overkill of a recursive routine? If all you have to do is find your way around a polygon, simply traverse the legal_action list in any one order: the only other possible path is the reverse of the first. Second, the given code does not return both routes. Can you clarify, please? – Prune Feb 02 '16 at 20:46
  • Prune, thanks. My pygame looks like a "#" shape circuit, and the Pentagon is just one corner of the full circuit. So I want my function works under any given legal actions for any steps at any position. The legal actions list created for dealing with the movement on circuit is all I can get so far. If you have any better way to control the movement on such a circuit, please tell me. – M. Chen Feb 03 '16 at 00:09
  • Second, the function only can return one of the path, which cannot return the last two paths list. If I write the path to a global variable, the result is right. I appreciate any help from you. – M. Chen Feb 03 '16 at 00:15
  • Please update the question itself with these clarifications. I need more details to help you properly. What you're trying to do is find all Hamiltonian circuits of a particular graph. I'm a bit confused here, because an octothorpe (#) doesn't have any such circuit: the eight points are isolated once we reach them. – Prune Feb 03 '16 at 00:26
  • In the meantime, you might check more rigorous algorithms for finding such circuits. [Here](http://www.dharwadker.org/hamilton/) are [two](https://en.wikipedia.org/wiki/Hamiltonian_path_problem) references. – Prune Feb 03 '16 at 00:27
  • Prune, thank you for your help, I upload the screenshot of my game. This may help you understand my description. – M. Chen Feb 03 '16 at 01:40
  • I see: points on the inner square have 4 neighbors. However, we still have only the two Hamilton circuits for the graph as a whole, or for any sub-graph that has a circuit. For those purposes, you can remove all interior edges. – Prune Feb 03 '16 at 01:54

3 Answers3

1

The easiest answer is to use nonlocal instead of global. It's the same deal, but the variable is in a parent scope instead of the global one.

For your example, however, it looks like the parent scope of that function is the global one, so it won't change anything.

The more correct, but more difficult answer is if you want to get rid of external variable use, you're going to have to either pass the values into your function as parameters or return a tuple containing both of your currently global variables and your original return variable.

This question may help get you started.

Community
  • 1
  • 1
John Kossa
  • 459
  • 2
  • 8
0

You have a few options.One of them is using an optional parameter. It looks like you can use route_all as an optional parameters.

e.g.

def route_cal(start_pos, steps, route_all = {}):

Remember that optional parameters get initialized once (the first time the function is called).

Another way is to get rid of dest_all and last_poses, and only use one variable, route_all, and append to it everyone you reach a point in your polygon, and only return that point. 

return [route_all] + [recursive_call_here]

You can also look into not using your legal_actions variables and create the "neighbors" value as needed depending on the step number you are in.

There are other ways to minimize your problem and I recommend moving this question to the Code Review section to gain more insight about your code. For example, I would try to avoid using so many loops and instead use a formula that will calculate the "neighbors" when recursing through each step. Also, prevent reaching the Index out of range exception and/or the KeyError exception by making sure you don't access something it doesn't exists.

Community
  • 1
  • 1
mugabits
  • 1,015
  • 1
  • 12
  • 22
  • JM, thanks for your advice, and you offer me a good way to resolve my problem. My game is in a "#" shape, the lines crossed each other. I also want a better way to describe the relationship of those vertices for more complicated circuit. I thought neighbors cannot work in points of crossed lines, right? And JM, where is the error that I cannot get expected return value, it seems the return value get overrided by the last path it had found. Any help is appreciated. – M. Chen Feb 03 '16 at 01:34
0

In keeping with my earlier comment, here is a simple iterative way to traverse the polygon. It seems to give what you specified, without using a global variable or even recursion. Is this all you need?

def route_cal(start_node, move_list):
    # For each step in the circuit
    here = start_node
    path = [here]
    for step in range(len(move_list)):
        # Find any legal move to an adjacent vertex
        dest = move_list[here]
        for here in dest:
            if here not in path:    # Don't repeat a vertex
                path.append(here)
                break
    path.append(start_node)

    # Now that we've found the full circuit, build a dictionary in each direction
    path_len = len(path)
    forward = {n: path[n] for n in range(path_len)}
    reverse = {n: path[path_len-n-1] for n in range(path_len)}
    return [forward, reverse]


legal_action = ((4,1), (0,2), (1,3), (2,4), (0,3))
print route_cal(0, legal_action)
Prune
  • 76,765
  • 14
  • 60
  • 81