pathfinding/main.py at main · makkuz2013/pathfinding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import pygame

pygame.init()

screen = pygame.display.set_mode((800, 600))
clock = pygame.time.Clock()
running = True

pygame.display.set_caption('Pathfinding Demo')

grid_width = int(screen.get_width() / 50)
grid_height = int(screen.get_height() / 50)
grid = []

font = pygame.font.Font(None, 22)

start_point = None
end_point = None

class Tile:
    def __init__(self, color):
        self.color = color
        self.searched = False
        self.prev = None

for i in range(grid_width * grid_height):
    grid.append(Tile('white'))

pathfinddirs = {
    "up": -1,
    "down": 1,
    "left": -grid_height,
    "right": grid_height,
    "upleft": -grid_height - 1,
    "upright": grid_height - 1,
    "downleft": -grid_height + 1,
    "downright": grid_height +1
}

queue = []

def trace(tile: int):
    reached_target = False
    index = tile
    while not reached_target:
        if grid[index].color == 'green':
            reached_target = True
            break
        grid[index].color = 'purple'
        index = grid[index].prev

def branchout(tile: int):
    for dir, add in pathfinddirs.items():
        column = tile // grid_height
        row = tile % grid_height
        index = tile + add
        if 'left' in dir and column == 0:
            continue
        if 'right' in dir and column == grid_width-1:
            continue
        if 'up' in dir and row == 0:
            continue
        if 'down' in dir and row == grid_height-1:
            continue
        if grid[index].color == 'red':
            grid[index].prev = tile
            trace(index)
            return
        if not grid[index].searched and grid[index].color == 'white':
            grid[index].searched = True
            grid[index].prev = tile
            queue.append(index)

tick = 0

def reset():
    for tile in grid:
        tile.searched = False
        if tile.color == 'purple':
            tile.color = 'white'

while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    screen.fill('white')

    while queue:
        branchout(queue.pop(0))

    for i in range(int(screen.get_width() / 50)):
        for j in range(int(screen.get_height() / 50)):
            rect = pygame.Rect(i*50, j*50, 50, 50)
            index = j + i * grid_height
            column = index // grid_height
            row = index % grid_height
            color = grid[index].color
            if index == end_point:
                color = 'red'
            pygame.draw.rect(screen, color, rect)
            pygame.draw.rect(screen, 'black', rect, 1)
            if rect.collidepoint(pygame.mouse.get_pos()):
                if pygame.mouse.get_pressed()[0]:
                    if not start_point:
                        grid[index].color = 'green'
                        start_point = index
                    elif index != start_point:
                        if end_point:
                            grid[end_point].color = 'white'
                        if end_point != index:
                            end_point = index
                            grid[index].color = 'red'
                            reset()
                            branchout(start_point)
                elif pygame.mouse.get_pressed()[2]:
                    grid[index].color = 'black'

    pygame.display.flip()

    clock.tick(60)

    tick += 1

pygame.quit()