domino path connecting two coordinates in Python

Question

Context

I'm trying to create a maze resolver.

Question

Is it possible to sort & filter a list of [x, y] coordinates, more or less like dominoes, connecting 2 known coordinates ?

Input

# [2, 2] is start
# [6, 2] is end
[[2, 2], [4, 2], [5, 2], [2, 3], [4, 3], [2, 4], [3, 4], [4, 4], [2, 5], [4, 5], [5, 5], [6, 2]]

Wanted output

# Shortest path from Start to End
[[2, 2], [2, 3], [2, 4], [3, 4], [4, 4], [4, 3], [4, 2], [5, 2], [6, 2]]

Yes, it is possible. What was the problem when you tried to do it? — mkrieger1, Jan 16 '20 at 14:49
@mkrieger1 I wrote the output by hand. I don't know how to code it. — Lbh, Jan 16 '20 at 15:00
@mkrieger1 My maze is grid based. I simply transcribed the cells coordinates. Should i add a picture of the maze for more clarity ? — Lbh, Jan 16 '20 at 15:07

score 0 · Accepted Answer · answered Jan 23 '20 at 14:35

For now, the best way to resolve my issue was found on this post : Get shortest path to a cell in a 2d array python

Here is the way i used the given code. It works perfectly :

import collections

start = (2, 2)
end = (6, 2)
grid = [(2, 2), (4, 2), (5, 2), (2, 3), (4, 3), (2, 4), (3, 4), (4, 4), (2, 5), (4, 5), (5, 5), (6, 2)]

queue = collections.deque([[start]])
seen = set(start)

while queue:
    path = queue.popleft()
        (x, y) = path[-1]
        if (x, y) == end:
            return path
        for x2, y2 in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
            if (x2, y2) not in seen and (x2, y2) in grid:
                queue.append(path + [(x2, y2)])
                seen.add((x2, y2)) 
print(path)
# path is [(2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (4, 3), (4, 2), (5, 2), (6, 2)]

domino path connecting two coordinates in Python

Context

Question

Input

Wanted output

1 Answers1