I'm trying to manage a list of coordinates for a pathfinding script in a ordered way

Question

What i'm trying to do is cut out all of the unecessary indexes of the a list of points used during pathfinding and also put the used points in order. In the simulator I am running, creatures will only be able to walk left, right, up, and down so the pathfinding cant use diagonal movement. (Images are below to help with what i'm talking about.)

What I mean: I have access to the starting point when the pathfinding starts. I want a list with a clear in order path to the end point. for example: If I had the list going from point 0,0 to 3,4 it would look like [(0,0), (1,0), (1,1), (2,1), (2,2), (2,3), (3,3), (3,4)] if before it was all messed up like:

[(0,0), (2,2), (1,0), (1,1), (2,3), (3,3), (2,1), (2,3), (3,4), (3,5), (3,6), (2,4)]

Note: in the fixed one, all of the coordinates are adjacent to each-other.

I used random in the pathfinding so they are all different but here is an example of a list of points after running it through a repeat deleter.

[(6, 7), (6, 6), (5, 6), (2, 6), (1, 6), (3, 4), (1, 5), (2, 5), (3, 6), (4, 6), (0, 4), (0, 5), (0, 7), (0, 6), (1, 4), (2, 3), (1, 3), (2, 4), (0, 3), (4, 4), (4, 3), (4, 2), (4, 1), (3, 1), (3, 0), (2, 0), (1, 0), (0, 0)]

Here is a picture of my console: 1's represent the points used in an example of the pathfinding, the '-'s are nothing, and the target was 0,0. The green represents the points I want to keep, and the red circles the points that don't matter and should be destroyed. the gray represents the walls that the pathfinding has to maneuver around. the start was 7,7 or the bottom right corner.

I was trying to use this function that tells you if one coordinate is adjacent to another and I'm not ruling it out as useful. In the solution something like this will probably be used to kind of lego the correct points together.

def PointIsNextToPoint(point1, point2):
    x1 = point1[0]
    y1 = point1[1]
    x2 = point2[0]
    y2 = point2[1]
    return (abs(x1 - x2) == 1 and y1 == y2) or (abs(y1 - y2) == 1 and x1 == x2)

Answer 1

What you are looking for here is a "breadth-first search". You start from a starting point (I assume (0,0) here). For each point, you try all four directions. If that new point is in the list of valid points and is a point you haven't visited before, you push that on the queue of points to try next.

The nice thing about this algorithm is that you look at all the points that are 1 step away before you start looking at the points that are 2 steps away, etc. Thus, when you visit a point, you know that it's the shortest path to that point.

pts = [(6, 7), (6, 6), (5, 6), (2, 6), (1, 6), (3, 4), (1, 5), (2, 5), (3, 6), (4, 6), (0, 4), (0, 5), (0, 7), (0, 6), (1, 4), (2, 3), (1, 3), (2, 4), (0, 3), (4, 4), (4, 3), (4, 2), (4, 1), (3, 1), (3, 0), (2, 0), (1, 0), (0, 0)]

dirs = [(1,0),(0,1),(-1,0),(0,-1)]

# Choose a starting point.

seen = set()
start = pts.pop()
pending = [(start,[start])]
while pending:
    (x,y),path = pending.pop(0)
    seen.add( (x,y))
    if (x,y) == pts[0]:
        print( path )
        break

    for dx,dy in dirs:
        x0 = x+dx
        y0 = y+dy
        if (x0,y0) in pts and (x0,y0) not in seen:
            pending.append( ((x0,y0),path+[(x0,y0)]) )

Output:

[(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (2, 5), (2, 6), (3, 6), (4, 6), (5, 6), (6, 6), (6, 7)]