Last active
January 22, 2025 20:46
-
-
Save EllieTheYeen/fbbf0e197fe652a6425c9baebcc03e48 to your computer and use it in GitHub Desktop.
A test where I implemented a pathfinding algorithm without actually looking up how to write one for the challenge and it works most of the time
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from PIL import Image, ImageDraw | |
| from IPython.display import Image as Im | |
| import random | |
| import io | |
| def manhattan(c1, c2): | |
| return abs(c1[0] - c2[0]) + abs(c1[1] - c2[1]) | |
| w, h = 100, 100 | |
| res = 400, 400 | |
| pw = int(res[0] // w) | |
| ph = int(res[1] // h) | |
| hw = int(pw // 2) | |
| hh = int(ph // 2) | |
| grid = dict() | |
| moves = set() | |
| fromto = dict() | |
| EMPTY = object() | |
| TAKEN = object() | |
| BLOCKED = object() | |
| POSSIBLE = object() | |
| g = (EMPTY,) * 2 + (BLOCKED,) | |
| for hi in range(h): | |
| for wi in range(w): | |
| grid[wi, hi] = random.choice(g) | |
| grid[w - 1, h - 1] = EMPTY | |
| imgs = [] | |
| start = 0, 0 | |
| target = w - 1, h - 1 | |
| s = start | |
| doend = False | |
| for it in range(1000): | |
| grid[s[0], s[1]] = TAKEN | |
| up = s[0], s[1] - 1 | |
| right = s[0] + 1, s[1] | |
| down = s[0], s[1] + 1 | |
| left = s[0] - 1, s[1] | |
| if up[1] >= 0 and grid[up] is EMPTY: | |
| grid[up] = POSSIBLE | |
| moves.add(up) | |
| fromto[up] = s | |
| if down[1] < h and grid[down] is EMPTY: | |
| grid[down] = POSSIBLE | |
| moves.add(down) | |
| fromto[down] = s | |
| if right[0] < w and grid[right] is EMPTY: | |
| grid[right] = POSSIBLE | |
| moves.add(right) | |
| fromto[right] = s | |
| if left[0] >= 0 and grid[left] is EMPTY: | |
| grid[left] = POSSIBLE | |
| moves.add(left) | |
| fromto[left] = s | |
| if s == target: | |
| doend = True | |
| im = Image.new('RGBA', res, (0, 0, 0)) | |
| d = ImageDraw.Draw(im) | |
| for (a, b), slot in grid.items(): | |
| col = "grey" | |
| if slot is BLOCKED: | |
| col = "blue" | |
| elif slot is TAKEN: | |
| col = "orange" | |
| elif slot is POSSIBLE: | |
| col = "brown" | |
| d.rectangle((a * pw, b * ph, a * pw + pw, b * ph + ph), fill=col) | |
| for from_, to in fromto.items(): | |
| d.line((from_[0] * pw + hw, from_[1] * ph + hh, to[0] * pw + hw, to[1] * ph + hh), | |
| width=hw, fill="white" if doend else "green") | |
| imgs.append(im) | |
| if not moves or doend: | |
| break | |
| closest = sorted(moves, key=lambda c: manhattan(target, c)) | |
| if not closest: | |
| break | |
| s = closest[0] | |
| moves.remove(s) | |
| imgs.insert(0, imgs[-1]) | |
| imgs = imgs + imgs[-2:] * 10 | |
| ii = io.BytesIO() | |
| imgs[0].save(ii, 'gif', loop=0, save_all=True, append_images=imgs[1:], duration=0.01) | |
| Im(ii.getvalue()) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment