A* algorithm implemented in Python.

a_star.py

import math
import random
from random import randint
from types import SimpleNamespace as Record
import pygame
from pygame.locals import *

SIZE = WIDTH, HEIGHT = 640, 360
HALFWIDTH, HALFHEIGHT = WIDTH // 2, HEIGHT // 2
BLOCS = BLOCW, BLOCH = 20, 20
BLOCHW, BLOCHH = BLOCW // 2, BLOCH // 2

BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
BLUE = (0, 0, 255)

pygame.init()

font = pygame.font.SysFont('Consolas', 18)

class Node(pygame.sprite.Sprite):
    """A node in the network."""

    name: str = ''
    connections: dict = {}

    @property
    def pos(self):
        return self.rect.center
    @pos.setter
    def pos(self, value):
        self.rect.center = value

    @property
    def x(self):
        return self.rect.centerx
    @x.setter
    def x(self, value):
        self.rect.centerx = value

    @property
    def y(self):
        return self.rect.centery
    @y.setter
    def y(self, value):
        self.rect.centery = value

    def __init__(self, name, pos):
        super().__init__()
        self.name = name
        self.reset_image()
        self.rect = self.image.get_rect()
        self.connections = {}
        self.pos = pos

    def reset_image(self, end=False):
        self.image = pygame.Surface(BLOCS)
        pygame.draw.circle(self.image, WHITE, (BLOCHW, BLOCHH), BLOCHW, 1)
        if end:
            pygame.draw.rect(self.image, (127, 127, 255),
                             (0, 0, BLOCW, BLOCH), 2)
        text = font.render(self.name, True, WHITE)
        self.image.blit(text, (BLOCHW - text.get_width() // 2,
                               BLOCHH - text.get_height() // 2))

    def connect(self, node, weight=1):
        if node.name not in self.connections:
            self.connections[node.name] = (node, weight)
            node.connections[self.name] = (self, weight)

    def distance(self, other):
        if not isinstance(other, type(self)):
            return NotImplemented
        return math.hypot(
            self.x - other.x,
            self.y - other.y
        )

    __sub__ = distance

    def __iadd__(self, value):
        if isinstance(value, tuple):
            self.connect(value[0], value[1])
        else:
            self.connect(value)
        return self

    def __repr__(self):
        return 'node ' + self.name

    def __eq__(self, other):
        if not isinstance(other, type(self)):
            return NotImplemented
        return self.name == other.name

    def __hash__(self):
        return hash(self.name)

    dragging = False
    drawing = False

    def update(self):
        if not a_done:
            return
        if pygame.mouse.get_pressed()[0]:
            if self.dragging:
                self.pos = pygame.mouse.get_pos()
            elif self.rect.collidepoint(pygame.mouse.get_pos()):
                for i in nodds:
                    if i.dragging:
                        return
                self.dragging = True
                reset()
            return
        else:
            self.dragging = False
        if pygame.mouse.get_pressed()[2]:
            if self.drawing:
                pass
            elif self.rect.collidepoint(pygame.mouse.get_pos()):
                self.drawing = True
                reset()
        elif self.drawing:
            self.drawing = False
            for i in nodds:
                if i.rect.collidepoint(pygame.mouse.get_pos()):
                    self.connect(i)
                    break

nodes = {}
def nod(name, x, y):
    nodes[name] = Node(name, (round(x * BLOCW * 2), round(y * BLOCH * 2)))
"""char = 64
for i in range(randint(3, 10)):
    char += 1
    nod(chr(char), randint(1, 12), randint(1, 9))
for nod in nodes.values():
    for i in range(randint(1, 3)):
        nod += random.choice(list(nodes.values())), randint(1, 7)

"""
nod('S', 2, 2)
nod('A', 1, 3)
nod('B', 2, 3)
nod('C', 5, 2)
nod('D', 1, 4)
nod('F', 1.5, 5)
nod('G', 3, 5)
nod('H', 2, 4)
nod('I', 5, 4)
nod('J', 7, 4)
nod('K', 6, 5)
nod('L', 6, 3)
nod('E', 6, 4)
def con(name1, name2, weight):
    nodes[name1].connect(nodes[name2], weight)
con('S', 'A', 7)
con('S', 'B', 2)
con('S', 'C', 3)
con('A', 'B', 3)
con('A', 'D', 4)
con('B', 'D', 4)
con('B', 'H', 1)
con('C', 'L', 2)
con('D', 'F', 5)
con('F', 'H', 3)
con('G', 'H', 2)
con('G', 'E', 2)
con('I', 'L', 4)
con('I', 'K', 4)
con('I', 'J', 6)
con('J', 'K', 4)
con('J', 'L', 4)
con('K', 'E', 5)
#"""
nods = nodes
def reset():
    for i in nodds[:-1]:
        i.reset_image()
    nodds[-1].reset_image(True)

SCREEN = pygame.display.set_mode(SIZE)

nodes = pygame.sprite.Group(*nodes.values())

class Record(Record):
    def __repr__(s):
        return '{} -{}-> {} ({})'.format(
            s.via, s.weight, s.node, s.value
        )

def astar(start, end):
    path = []
    stack = [Record(
        node=start, weight=0, via=None,
        value=start - end
    )]
    while 1:
        record = stack[0]
        if record.via in path[:-1]:
            stack.pop(0)
            continue
        node = record.node
        for nod, weight in node.connections.values():
            if nod in path:
                continue
            for i in stack:
                if i.node == nod and record.weight + weight < i.weight:
                    i.weight = record.weight + weight
                    i.value = i.weight + (i.node - end)
                    i.via = node
                    break
            else:
                stack.append(Record(
                    node=nod, weight=record.weight + weight, via=node,
                    value=record.weight + weight + (nod - end)
                ))
        path.append(node)
        stack.pop(0)
        stack.sort(key=lambda i: i.value)
        print(stack, path)
        if path[-1] == end:
            return iter(path)

frames = 0
a_done = True
nodds = list(nods.values())
nodds[-1].reset_image(end=True)

while 1:
    for event in pygame.event.get():
        if event.type == QUIT or getattr(event, 'key', None) == K_ESCAPE:
            pygame.quit()
            raise SystemExit()
        if event.type == KEYDOWN and event.key == K_SPACE:
            reset()
            gen = astar(nodds[0], nodds[-1])
            a_done = False
    if not a_done and frames % 30 == 0:
        nod = next(gen, None)
        if nod is not None:
            pygame.draw.circle(nod.image, (0, 255, 0),
                               (BLOCHW, BLOCHH), BLOCHW, 2)
        else:
            a_done = True
    nodes.update()
    SCREEN.fill(BLACK)
    # ALL DRAWING MUST GO UNDER THIS LINE #
    for node1 in nodes.sprites():
        for node2, weight in node1.connections.values():
            pygame.draw.line(SCREEN, (round(weight * 255 / 7) % 256,)*3,
                             node1.pos, node2.pos, (8 - weight) % 8)
    for node in nodds:
        if node.drawing:
            pygame.draw.line(SCREEN, (round(1 * 255 / 7) % 256,) * 3,
                             node.pos, pygame.mouse.get_pos(), (8 - 1) % 8)
    nodes.draw(SCREEN)
    pygame.display.flip()
    pygame.time.delay(30)
    frames += 1