cookertron

A Star Pygame

Jan 1st, 2020
394
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import math, random, sys
  2. import pygame
  3. from pygame.locals import *
  4.  
  5. # exit the program
  6. def events():
  7.     for event in pygame.event.get():
  8.         if event.type == QUIT or (event.type == KEYDOWN and event.key == K_ESCAPE):
  9.             pygame.quit()
  10.             sys.exit()
  11.  
  12. # define display surface           
  13. W, H = 1920, 1080
  14. HW, HH = W / 2, H / 2
  15. AREA = W * H
  16.  
  17. # initialise display
  18. pygame.init()
  19. pygame.font.init()
  20. CLOCK = pygame.time.Clock()
  21. FONT_SMALL = pygame.font.Font(None, 26)
  22. FONT_LARGE = pygame.font.Font(None, 50)
  23. DS = pygame.display.set_mode((W, H))
  24. pygame.display.set_caption("code.Pylet - Template")
  25. FPS = 1
  26.  
  27. # define some colors
  28. BLACK = (0, 0, 0, 255)
  29. WHITE = (255, 255, 255, 255)
  30. RED = (255, 0, 0, 255)
  31. GREEN = (0, 128, 0, 255)
  32. BLUE = (0, 0, 255, 255)
  33. PURPLE = (255, 255, 0, 255)
  34.  
  35. # define node class
  36. class node:
  37.     def __init__(self, x, y, obstacle):
  38.         self.x = x
  39.         self.y = y
  40.         self.pos = (x, y)
  41.         self.h = 0
  42.         self.g = 0
  43.         self.f = 0
  44.         self.obstacle = obstacle
  45.         self.other = None
  46.         self.parent = None
  47.    
  48.     def neighbourPos(self, offset):
  49.         return (self.x + offset[0], self.y + offset[1])
  50.    
  51.     def draw(self, size, color = None, id = None, surface = None):
  52.         global text, FONT_SMALL, FONT_LARGE
  53.         if not surface: surface = pygame.display.get_surface()
  54.         pos = (self.x * size[0], self.y * size[1])
  55.         if not color:
  56.             if not self.obstacle:
  57.                 if not self.other: pygame.draw.rect(surface, BLACK, pos + size, 0)
  58.                 else: pygame.draw.rect(surface, BLUE, pos + size, 0)
  59.             else:
  60.                 pygame.draw.rect(surface, WHITE, pos + size, 0)
  61.         else:
  62.             pygame.draw.rect(surface, color, pos + size, 0)
  63.         pygame.draw.rect(surface, WHITE, pos + size, 1)
  64.         if self.f:
  65.             text(FONT_SMALL, "G:{0}".format(self.g), pos[0] + 5, pos[1] + 5, 0, 0, surface)
  66.             text(FONT_SMALL, "H:{0}".format(self.h), pos[0] + size[0] - 5, pos[1] + 5, 1, 0, surface)
  67.             text(FONT_LARGE, "F:{0}".format(self.f),  pos[0] + size[0] / 2, pos[1] + size[1] / 2 , 2, 2, surface)
  68.             if not id == None:
  69.                 text(FONT_SMALL, "{0}".format(id), pos[0] + 5, pos[1] + size[1] - 5, 0, 1, surface)
  70.                
  71.            
  72. def drawNodes(n, ms, cs):
  73.     for x in range(ms[0]):
  74.         for y in range(ms[1]):
  75.             n[x][y].draw(cs)
  76.  
  77. def drawNodeList(node_list, cs, color):
  78.     id = 0
  79.     for n in node_list:
  80.         n.draw(cs, color, id)
  81.         id += 1
  82.        
  83. def heuristics(pos1, pos2):
  84.     return int(math.hypot(pos1[0] - pos2[0], pos1[1] - pos2[1]) * 10)
  85.  
  86. def text(font, string, x, y, xJustify = None, yJustify = None, surface = None):
  87.     global WHITE
  88.     if not surface: surface = pygame.display.get_surface()
  89.     textSurface = font.render(string, 1, WHITE)
  90.     textRect = textSurface.get_rect()
  91.     if xJustify == 1:
  92.         x -= textRect.width
  93.     elif xJustify == 2:
  94.         x -= textRect.center[0]
  95.     if yJustify == 1:
  96.         y -= textRect.height
  97.     elif yJustify == 2:
  98.         y -= textRect.center[1]
  99.     surface.blit(textSurface, (x, y))
  100.    
  101. map = pygame.image.load("test.png").convert()
  102. map_size = map_width, map_height = map.get_rect().size
  103. cell_size = (W / map_width, H / map_height)
  104.  
  105. #create list of nodes
  106. nodes = list([])
  107. for x in range(map_width):
  108.     nodes.append(list([]))
  109.     for y in range(map_height):
  110.         color = map.get_at((x, y))
  111.         if color != WHITE:
  112.             nodes[x].append(node(x, y, False))
  113.             if color == BLUE:
  114.                 start = nodes[x][y]
  115.                 start.other = True
  116.             elif color == RED:
  117.                 end = nodes[x][y]
  118.                 end.other = True
  119.         else:
  120.             nodes[x].append(node(x, y, True))
  121.  
  122.  
  123. # This list contains relative x & y positions to reference a node's neighbour
  124. NEIGHBOURS = list([(-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0)])          
  125.  
  126.  
  127.  
  128.  
  129. # the closed list contains all the nodes that have been considered economical viable.
  130. # By that I mean a node that has been closer to the end node than any other in the open list at one time
  131. closed = list([])
  132.  
  133. # The open list contains all the closed list's neighbours that haven't been identified as being economically sound node yet
  134. open = list([])
  135. open.append(start) # add the start node so that we can then add it's neighbours
  136.  
  137.  
  138.  
  139. # if the algorithm finds the end node then pathFound will be true otherwise it's false.
  140. # Once it becomes true there's no more calculations to do so the path finding script will be skipped over
  141. pathFound = False
  142. completedPath = list([]) #
  143.  
  144. # main loop
  145. while True:
  146.     DS.fill(BLACK) 
  147.     drawNodes(nodes, map_size, cell_size)
  148.     drawNodeList(open, cell_size, GREEN)
  149.     drawNodeList(closed, cell_size, RED)
  150.     if pathFound: drawNodeList(completedPath, cell_size, PURPLE)
  151.     pygame.display.update()
  152.    
  153.     # wait for user to press mouse button
  154.     while not pygame.mouse.get_pressed()[0]:
  155.         events()
  156.     while pygame.mouse.get_pressed()[0]:
  157.         events()
  158.    
  159.     # if we've found the quickest path from start node to end node then just draw, no need continue path finding
  160.     if pathFound: continue
  161.     if not open: continue
  162.    
  163.    
  164.     # get lowest f from the open list, the node with the lowest f is the most economical in terms of the path towards the end node
  165.     openNodeWithlowestF = open[0]
  166.     for o in open:
  167.         if  o.f < openNodeWithlowestF.f: openNodeWithlowestF = o
  168.  
  169.     mostEconomicalNodeSoFar = openNodeWithlowestF # let's make this more readable! Economical means the best path to the end given the choices but not definitive.
  170.    
  171.     # remove the mostEconomicalNodeSoFar from the open list
  172.     open.remove(mostEconomicalNodeSoFar)
  173.     # add mostEconomicalNodeSoFar to the closed list
  174.     closed.append(mostEconomicalNodeSoFar)
  175.    
  176.     # if the mostEconomicalNodeSoFar is equal to the end node then we've reach our target
  177.     if mostEconomicalNodeSoFar == end:
  178.         temp = end
  179.         while temp.parent:
  180.             completedPath.append(temp)
  181.             temp = temp.parent
  182.         completedPath.append(start)
  183.         pathFound = True
  184.         # get the path etc
  185.        
  186.     # iterate through the list of neighbours belonging to the mostEconomicalNodeSoFar. Why?
  187.     for neighbourOffset in NEIGHBOURS:
  188.         nx, ny = mostEconomicalNodeSoFar.neighbourPos(neighbourOffset)
  189.  
  190.         if nx < 0 or nx >= map_width or ny < 0 or ny >= map_height: continue
  191.         neighbour = nodes[nx][ny] # create a variable to represent the mostEconomicalNodeSoFar's neighbour
  192.         if neighbour.obstacle: continue # if the mostEconomicalNodeSoFar's neighbouring node is an obstacle then we can't ...?
  193.         if neighbour in closed: continue # if the mostEconomicalNodeSoFar's neighbouring node is in the closed list then we can't ...?
  194.  
  195.         # now we need to see if the mostEconomicalNodeSoFar's neighbour is more economical ...?
  196.         hypotheticalFScore = mostEconomicalNodeSoFar.g + heuristics(neighbour.pos, mostEconomicalNodeSoFar.pos)
  197.         NeighbourIsBetterThanMostEconomicalNodeSoFar = False # Yes it's a long variable name but it describes what it is so all is good!
  198.        
  199.         # is this neighbour already in open list? if it is then we don't want to be adding it again. to chec
  200.         if not neighbour in open:
  201.             NeighbourIsBetterThanMostEconomicalNodeSoFar = True
  202.             neighbour.h = heuristics(neighbour.pos, end.pos)
  203.             open.append(neighbour)
  204.         elif hypotheticalFScore < neighbour.g:
  205.             NeighbourIsBetterThanMostEconomicalNodeSoFar = True
  206.  
  207.         if NeighbourIsBetterThanMostEconomicalNodeSoFar:
  208.             neighbour.parent = mostEconomicalNodeSoFar
  209.             neighbour.g = hypotheticalFScore
  210.             neighbour.f = neighbour.g + neighbour.h
  211.     #sys.exit()
RAW Paste Data