Simplifying straight line movements in a list of step by step (x,y) coordinates

Question

In my game, I have a list of tuples (x,y) :

solution = [(36, 37), (36, 36), (36, 35), (37, 35), (38, 35),  (38, 34),  (38, 33), (38, 32)]

This list describes the movements the player should do to move from point (36, 37) to point (38, 32).

I want to simplify this list to the following :

opti = [(36, 37), (36, 35), (38, 35), (38, 32)]

This means I want to reduce any series of steps where x is fixed (or y is fixed) to only the first and the last step.

I'm struggling to figure out an algorithm to do this. I've been trying for more than two hours and here is what I'm currently trying to work on:

solution = [(36, 37), (36, 36), (36, 35), (37, 35), (38, 35),  (38, 34),  (38, 33), (38, 32)]
opti = [solution[0]]
for i in range(len(solution)):
    if opti[-1][0] == solution[i][0]:
        pass
    elif opti[-1][1] == solution[i][1]:
        pass
    else:
        opti.append(solution[i])

In the end opti is equal to [(36, 37), (37, 35), (38, 34)] which is not what I want.. Can someone point me to the right way to do this?

Answer 1

You can try this: compare the previous and next location with the current location when iterating over the list(solution) to check if all the points are in the same line, pass if they are in the same line else append to the final (opti) list.

solution = [(36, 37), (36, 36), (36, 35), (37, 35), (38, 35),  (38, 34),  (38, 33), (38, 32)]
opti = [solution[0]]
for i in range(1, len(solution) -1 ):
    if solution[i-1][0] == solution[i][0] and solution[i][0] == solution[i+1][0]:
        pass
    elif solution[i-1][1] == solution[i][1] and solution[i][1] == solution[i+1][1]:
        pass
    else:
        opti.append(solution[i])
opti.append(solution[-1])

print(opti)

output:

[(36, 37), (36, 35), (38, 35), (38, 32)]

I hope this helps, feel free to reach out in case of any doubt.

Answer 2

Keep points if they're not on a straight line.

pad = [(None, None)]
opti = [(x, y)
        for (x0, y0), (x, y), (x1, y1)
            in zip(pad + solution, solution, solution[1:] + pad)
        if not (x0 == x == x1 or y0 == y == y1)]