PacMan鬼运动

Question

所以我一直在尝试重现PacMan游戏，我一直被困在如何接近幽灵在迷宫中移动的想法上，我听说过A*和Dijkstra的算法，但是有更简单的方法来实现鬼魂在迷宫中移动吗？除了找出不同的模式，他们可以进入，害怕，大通，和分散，我只是想能够理解什么是最好的方式，让他们在迷宫中随机移动与墙壁检测功能到位。

import pygame
import time
#import random
import pickle
import math

pygame.init()
pygame.mixer.init()
pygame.display.set_caption("Pac-Man")

# Sets the size of the screen via (WIDTH, HEIGHT)
SCREEN_WIDTH = 478
SCREEN_HEIGHT = 608
# Speed of Characters
SPEED = 1
# Frames per second, how fast the game runs
FPS = 50
# Colors (RED,GREEN,BLUE)
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
YELLOW = (255, 255, 0)
BLUE = (0, 0, 255)

# Sets the WIDTH and HEIGHT of the window
WINDOW = (SCREEN_WIDTH, SCREEN_HEIGHT)
# Displays the screen
SCREEN = pygame.display.set_mode(WINDOW)
CLOCK = pygame.time.Clock()

PacManStartSurface = pygame.transform.scale(pygame.image.load 
                                           ("PacManStart.png"), (23, 23))
PacManStartSurface.convert()
PacManStartRect = PacManStartSurface.get_rect(topleft = 
                                             (((SCREEN_WIDTH - 25) // 2),
                                             (SCREEN_HEIGHT + 144) // 2))

PacManSurface = pygame.transform.scale(pygame.image.load 
                                      ("PacManRight.png"), (23, 23))
PacManSurface.convert()
PacManRect = PacManStartSurface.get_rect(topleft = 
                                        (((SCREEN_WIDTH - 125) // 2),
                                        (SCREEN_HEIGHT + 144) // 2))

CurrentSurface = PacManStartSurface
CurrentRect = PacManStartRect 

BackgroundSurface = pygame.image.load("Background.png").convert()

PinkGhostSurface = pygame.transform.scale(pygame.image.load("PinkGhost.png")
                                           .convert(), (23, 23))
PinkGhostRect = PinkGhostSurface.get_rect()
YellowGhostSurface = pygame.transform.scale(pygame.image.load
                                           ("YellowGhost.png")
                                           .convert(), (23, 23))
YellowGhostRect = YellowGhostSurface.get_rect()
RedGhostSurface = pygame.transform.scale(pygame.image.load("RedGhost.png")
                                         .convert(), (23, 23))
RedGhostRect = RedGhostSurface.get_rect()
BlueGhostSurface = pygame.transform.scale(pygame.image.load("BlueGhost.png")
                                          .convert(), (23, 23))
BlueGhostRect = BlueGhostSurface.get_rect()

pygame.mixer.music.load('power_pellet.wav')

Font = pygame.font.Font("emulogic.ttf", 15)

class PacMan():
    def __init__(self):
        self.LIVES = 3
        
class Maze():
    def __init__(self):
        self.DOTS = []
        self.WALLS = []
        self.ENERGIZER = []
        self.GHOSTS = []
        self.DECISION_NODES = []
        self.BLOCK_WIDTH = 25
        self.BLOCK_HEIGHT = 25
        self.MAZE_OFFSET_X = 0
        self.MAZE_OFFSET_Y = 50
        self.MARGIN = 3
        # 0 - Dots
        # 1 - Walls
        # 2 - Energizers
        # 3 - Empty Spaces
        # 4 - Ghosts
        # 5 - Decision Nodes & will be added for intersections in maze
        self.MATRIX = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], \
                      [1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1], \
                      [1,2,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,2,1], \
                      [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1], \
                      [1,0,1,1,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1], \
                      [1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,1], \
                      [1,1,1,1,0,1,1,1,3,1,3,1,1,1,0,1,1,1,1], \
                      [3,3,3,1,0,1,3,3,5,4,5,3,3,1,0,1,3,3,3], \
                      [1,1,1,1,0,1,3,1,1,1,1,1,3,1,0,1,1,1,1], \
                      [0,0,0,0,0,3,5,1,4,4,4,1,5,3,0,0,0,0,0], \
                      [1,1,1,1,0,1,3,1,1,1,1,1,3,1,0,1,1,1,1], \
                      [3,3,3,1,0,1,5,3,3,3,3,3,5,1,0,1,3,3,3], \
                      [1,1,1,1,0,1,3,1,1,1,1,1,3,1,0,1,1,1,1], \
                      [1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1], \
                      [1,2,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,2,1], \
                      [1,0,0,1,0,0,0,0,0,3,0,0,0,0,0,1,0,0,1], \
                      [1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1], \
                      [1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,1], \
                      [1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1], \
                      [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1], \
                      [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
                      
        # BackgroundImage(X, Y, WIDTH, HEIGHT)
        self.MAZE_X = self.BLOCK_WIDTH * (len(self.MATRIX[0]) 
                      + self.MAZE_OFFSET_X)
        self.MAZE_Y = self.BLOCK_HEIGHT * (len(self.MATRIX)
                      + self.MAZE_OFFSET_Y)
        self.MAZE_WIDTH = self.BLOCK_WIDTH * len(self.MATRIX[0])
        self.MAZE_HEIGHT = self.BLOCK_HEIGHT * len(self.MATRIX) 

    def DrawMaze(self, MazeSurface):
        for ROW in range(len(self.MATRIX)):
            for COLUMN in range(len(self.MATRIX[0])):
                # Only saves the position of each dot
                if self.MATRIX[ROW][COLUMN] == 0:
                    self.DOTS.append([(self.BLOCK_WIDTH * COLUMN),
                                    (self.BLOCK_HEIGHT * ROW), 4, 4])
                if self.MATRIX[ROW][COLUMN] == 1:
                    self.WALLS.append(pygame.draw.rect(MazeSurface, WHITE,
                                     [((self.BLOCK_WIDTH) * COLUMN),
                                     ((self.BLOCK_HEIGHT) * ROW), 
                                     self.BLOCK_WIDTH, self.BLOCK_HEIGHT]))
                if self.MATRIX[ROW][COLUMN] == 2:
                    self.ENERGIZER.append([(self.BLOCK_WIDTH * COLUMN),
                                         (self.BLOCK_HEIGHT * ROW), 14, 14])
                if self.MATRIX[ROW][COLUMN] == 4:
                    self.GHOSTS.append([(self.BLOCK_WIDTH * COLUMN), 
                                      (self.BLOCK_HEIGHT * ROW), 23, 23])
                if self.MATRIX[ROW][COLUMN] == 5:
                    self.DECISION_NODES.append([(self.BLOCK_WIDTH * COLUMN), 
                                              (self.BLOCK_HEIGHT * ROW), 4, 4])  
         
class Main(Maze):
    def __init__(self):
        # Inherits Maze class
        Maze.__init__(self)
        self.TimeBetweenBites = 0.1
        self.LastBiteTime = time.time()
        self.MouthOpen = False
        self.PacManDirection = ""
        self.GhostDirection = ""
        self.PreviousGhostDirection = ""
        self.SCORE = 0
        self.HIGH_SCORE = 0
        
    def PacManMovement(self):
        key = pygame.key.get_pressed()
        if key[pygame.K_LEFT] and not key[pygame.K_UP] \
                              and not key[pygame.K_DOWN]:
            self.PacManDirection = "LEFT"
        elif key[pygame.K_RIGHT] and not key[pygame.K_UP] \
                               and not key[pygame.K_DOWN]:
            self.PacManDirection = "RIGHT"
        elif key[pygame.K_UP] and not key[pygame.K_LEFT] \
                            and not key[pygame.K_RIGHT]:
            self.PacManDirection = "UP"
        elif key[pygame.K_DOWN] and not key[pygame.K_LEFT] \
                              and not key[pygame.K_RIGHT]:
            self.PacManDirection = "DOWN"
        
    def ContinuePacManMovement(self):
        if self.PacManDirection == "LEFT":
            CurrentRect.x -= SPEED
            self.PacManWallDetection(-1, 0, CurrentRect)
        if self.PacManDirection == "RIGHT":
            CurrentRect.x += SPEED
            self.PacManWallDetection(1, 0, CurrentRect)
        if self.PacManDirection == "UP":
            CurrentRect.y -= SPEED
            self.PacManWallDetection(0, -1, CurrentRect)
        if self.PacManDirection == "DOWN":
            CurrentRect.y += SPEED
            self.PacManWallDetection(0, 1, CurrentRect)
            
    def PacManTeleport(self):
        if CurrentRect.right < 0:
            CurrentRect.right = SCREEN_WIDTH + 20
        if CurrentRect.left > SCREEN_WIDTH:
            CurrentRect.right = 0
    
    def GhostTeleport(self):
        if PinkGhostRect.right < 0:
            PinkGhostRect.right = SCREEN_WIDTH + 20
        if PinkGhostRect.left > SCREEN_WIDTH:
            PinkGhostRect.right = 0
            
    def PacManWallDetection(self, x, y, CurrentRect):
        CurrentRect.right += x
        for WALL in self.WALLS:
            COLLIDE = CurrentRect.colliderect(WALL)
            if COLLIDE:
                if x < 0: 
                    CurrentRect.left = WALL.right
                    CurrentSurface = pygame.transform.rotate(PacManSurface, 180)
                    MazeSurface.blit(CurrentSurface, CurrentRect)
                if x > 0:
                    CurrentRect.right = WALL.left
                break
        
        CurrentRect.top += y
        for WALL in self.WALLS:
            COLLIDE = CurrentRect.colliderect(WALL)
            if COLLIDE:
                if y < 0:
                    CurrentRect.top = WALL.bottom
                if y > 0:
                    CurrentRect.bottom = WALL.top
                break
            
    def GhostWallDetection(self, x, y, PinkGhostRect):
        PinkGhostRect.right += x
        for WALL in self.WALLS:
            COLLIDE = PinkGhostRect.colliderect(WALL)
            if COLLIDE:
                if x < 0:
                    PinkGhostRect.left = WALL.right
                if x > 0:
                    PinkGhostRect.right = WALL.left
                break
        
        PinkGhostRect.top += y
        for WALL in self.WALLS:
            COLLIDE = PinkGhostRect.colliderect(WALL)
            if COLLIDE:
                if y < 0:
                    PinkGhostRect.top = WALL.bottom
                if y > 0:
                    PinkGhostRect.bottom = WALL.top 
                break
            
    def EatDots(self):
        for ROW in range(len(self.MATRIX)):
            for COLUMN in range(len(self.MATRIX[0])):
                for DOT in self.DOTS:
                    CHOMP = CurrentRect.colliderect(DOT)
                    if CHOMP:
                        Main.PlaySound(self, 0)
                        self.DOTS.remove(DOT)
                        self.MATRIX[ROW][COLUMN] = 3
                        self.SCORE += 10
        if self.SCORE > self.HIGH_SCORE:
            self.HIGH_SCORE = self.SCORE
        return str(self.SCORE), str(self.HIGH_SCORE)
    
    def EatEnergizer(self):
        for ROW in range(len(self.MATRIX)):
            for COLUMN in range(len(self.MATRIX[0])):
                for POWERUP in self.ENERGIZER:
                    CHOMP = CurrentRect.colliderect(POWERUP)
                    if CHOMP:
                        self.ENERGIZER.remove(POWERUP)
                        self.MATRIX[ROW][COLUMN] = 3
                        self.SCORE += 50
                        Main.PlaySound(self, 1)
        if self.SCORE > self.HIGH_SCORE:
            self.HIGH_SCORE = self.SCORE
        return str(self.SCORE), str(self.HIGH_SCORE)
    
    def EatGhosts(self):
        pass
                
    def DrawDots(self):
        for POSITION in self.DOTS:
            X = POSITION[0] + 13
            Y = POSITION[1] + 13
            WIDTH = POSITION[2]
            HEIGHT = POSITION[3]
            pygame.draw.circle(MazeSurface, YELLOW, (X, Y), 
                               WIDTH // 2, HEIGHT // 2)
            
    def DrawEnergizer(self):
        for POSITION in self.ENERGIZER:
            X = POSITION[0] + 13
            Y = POSITION[1] + 13
            WIDTH = POSITION[2] 
            HEIGHT = POSITION[3] 
            pygame.draw.circle(MazeSurface, YELLOW, (X, Y), 
                               WIDTH // 2, HEIGHT // 2)

    def DrawGhosts(self):        
        MazeSurface.blit(PinkGhostSurface, PinkGhostRect) 
        MazeSurface.blit(YellowGhostSurface, YellowGhostRect) 
        MazeSurface.blit(RedGhostSurface, RedGhostRect) 
        MazeSurface.blit(BlueGhostSurface, BlueGhostRect) 
        
    def GhostPosition(self):
        X, Y, WIDTH, HEIGHT = self.GHOSTS[0]
        PinkGhostRect.x = X
        PinkGhostRect.y = Y
        PinkGhostRect.width = WIDTH
        PinkGhostRect.height = HEIGHT
        
        X, Y, WIDTH, HEIGHT = self.GHOSTS[1]
        YellowGhostRect.x = X
        YellowGhostRect.y = Y
        YellowGhostRect.width = WIDTH
        YellowGhostRect.height = HEIGHT
        
        X, Y, WIDTH, HEIGHT = self.GHOSTS[2]
        RedGhostRect.x = X
        RedGhostRect.y = Y
        RedGhostRect.width = WIDTH
        RedGhostRect.height = HEIGHT
        
        X, Y, WIDTH, HEIGHT = self.GHOSTS[3]
        BlueGhostRect.x = X
        BlueGhostRect.y = Y
        BlueGhostRect.width = WIDTH
        BlueGhostRect.height = HEIGHT
    
    def ChaseMode(self):
        self.GhostDirection = "LEFT"
        self.GhostWallDetection(-1, 0, PinkGhostRect)
        if PinkGhostRect.x < CurrentRect.x:
            self.GhostDirection = "RIGHT"
            self.GhostWallDetection(1, 0, PinkGhostRect)
        if PinkGhostRect.y > CurrentRect.y:
            self.GhostDirection = "UP"
            self.GhostWallDetection(0, -1, PinkGhostRect)
        if PinkGhostRect.y < CurrentRect.y:
            self.GhostDirection = "DOWN"
            self.GhostWallDetection(0, 1, PinkGhostRect)
    
    def ScatterMode(self):
        pass
    
    def FrightenedMode(self):
        pass
        
    def PlaySound(self, Track):
        if Track == 0:
            Eat = pygame.mixer.Sound("pacman_chomp.wav")
            Eat.play()
            pygame.mixer.fadeout(400)
        if Track == 1:
            EatPellet = pygame.mixer.Sound("pacman_eatghost.wav")
            EatPellet.play()
            pygame.mixer.music.play(7)
            pygame.mixer.fadeout(400)
                
    def ShowScore(self):
        global Font
        OneUpText = Font.render("1UP", True, WHITE)
        OneUpTextRect = OneUpText.get_rect(center = (70, 10))
        # Displays current score
        OneUpScoreText = Font.render(str(self.SCORE), True, WHITE)
        OneUpScoreRect = OneUpScoreText.get_rect(center =
                                                ((SCREEN_WIDTH - 290) 
                                                // 2, 26))
        HighScoreText = Font.render("High Score", True, WHITE)
        HighScoreTextRect = HighScoreText.get_rect(center = 
                                                  (SCREEN_WIDTH // 2, 10))
        # Displays High Score
        HighScoreNumber = Font.render(str(self.HIGH_SCORE), True, WHITE)
        HighScoreNumberRect = HighScoreNumber.get_rect(center = 
                                                      ((SCREEN_WIDTH + 90) 
                                                      // 2, 26))
        SCREEN.blit(OneUpText, OneUpTextRect)
        SCREEN.blit(OneUpScoreText, OneUpScoreRect)
        SCREEN.blit(HighScoreText, HighScoreTextRect)
        SCREEN.blit(HighScoreNumber, HighScoreNumberRect)
        
    def PacManBite(self):
        global CurrentSurface
        CurrentTime = time.time()
        if CurrentTime - self.LastBiteTime >= self.TimeBetweenBites:
            self.LastBiteTime = CurrentTime
            if self.MouthOpen:
                CurrentSurface = PacManStartSurface
            else:
                CurrentSurface = PacManSurface
            self.MouthOpen = not self.MouthOpen
            if self.PacManDirection == "LEFT":
                CurrentSurface = pygame.transform.rotate(CurrentSurface, 180)
            if self.PacManDirection == "RIGHT":
                CurrentSurface = CurrentSurface
            if self.PacManDirection == "UP":
                CurrentSurface = pygame.transform.rotate(CurrentSurface, 90)
            if self.PacManDirection == "DOWN":
                CurrentSurface = pygame.transform.rotate(CurrentSurface, 270)
    
    def PacManLives(self):
        pass
        
Player = Main()

BackgroundSurface = pygame.transform.scale(BackgroundSurface, 
                                          (Player.MAZE_WIDTH, 
                                           Player.MAZE_HEIGHT))
BackgroundRect = BackgroundSurface.get_rect()

MazeSurface = pygame.Surface((Player.MAZE_WIDTH, Player.MAZE_HEIGHT))
MazeRect = MazeSurface.get_rect(topleft = (Player.MAZE_OFFSET_X, 
                                           Player.MAZE_OFFSET_Y))
Player.DrawMaze(MazeSurface)
Player.GhostPosition()
#Player.GhostMovement()

'''
Before the game starts ...
pregame = True
while pregame:
    if key button pressed:
        pregame = False
    run = True
'''

run = True
while run:
    SCREEN.fill(BLACK)
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False
        if event.type == pygame.KEYDOWN:
            Player.PacManMovement()
            Player.PacManTeleport()   
            
    Player.ContinuePacManMovement()
    MazeSurface.blit(BackgroundSurface, BackgroundRect) 
    Player.DrawDots()
    Player.DrawEnergizer()
    Player.DrawGhosts()
    Player.GhostTeleport()
    Player.EatDots()
    Player.EatEnergizer()
    Player.ChaseMode()
    MazeSurface.blit(CurrentSurface, CurrentRect)
    Player.PacManBite()
    SCREEN.blit(MazeSurface, MazeRect)
    Player.ShowScore()
    pygame.display.update()
    CLOCK.tick(FPS)
    
pygame.quit()

Answer 1

一个简单的移动算法就是简单地查看这个位置的可用出口并选择去哪里。

观察帕克曼几分钟会引出一些运动规则：

• 方向只在精确的地图网格边界上改变(对所有实体都是如此)。
• 鬼魂不会停下来
• 鬼怪不会倒转方向
• ..。除非成为可食用的(暂时超出范围)

所以我用一个简单的启发实现了这一点：

• 除非是在死胡同，否则不要倒车。
• 总是向前走，但如果我们可以转身，仍然更喜欢向前(60%的时间)。

要对此进行编码，GhostSprite只需记住它在self.direction中的当前方向，这是一个指南针，方位为North、East、South、West。北面是窗口的顶部(-Y)，西面是左边(-X)。

这使得幽灵的方向控制简化为一个单一的算法：

• 通过查阅地图，列出可用的出口。
• 是唯一可用的反向方向吗？
  • 是的:转过身来
  • No：
    • 60%的时间继续前进
    • 在40%的时间里，选择一个随机的方向

在我的实现中，幽灵跳过整个网格协调。在每像素移动的版本中，幽灵只需要在一个精确的网格边界上检查它，然后再麻烦地检查方向的变化。像self.rect.x % GRID_SIZE == 0这样的东西很快就能实现。

​

​

**守则**

import pygame
import random

# Window size
WINDOW_WIDTH      = 420
WINDOW_HEIGHT     = 465

GRID_SIZE = WINDOW_HEIGHT // 21

MAP_WIDTH  = 19
MAP_HEIGHT = 21
MAP = [ "###################", 
        "#        #        #",
        "# ## ### # ### ## #",
        "#                 #",
        "# ## # ##### # ## #",
        "#    #   #   #    #",
        "#### ### # ### ####",
        "#### #       # ####",
        "#### # ## ## # ####",
        "<      #   #      >",
        "#### # ##### # ####",
        "#### #   c   # ####",
        "#### # ##### # ####",
        "#        #        #",
        "# ## ### # ### ## #",
        "#  #           #  #",
        "## # # ##### # # ##",
        "#    #   #   #    #",
        "# ###### # ###### #",
        "#                 #",
        "###################" ]

BLACK    = (  0,   0,   0)
YELLOW   = (255, 255,   0)
BLUE     = (  0,   0, 254)
RED      = (255,   0,   0)
LIGHTBLUE= (161, 255, 254)
PINK     = (255, 192, 203)
ORANGE   = (255, 165,   0)


def pixelPosToGridPos( pixel_x, pixel_y ):
    """ Map a window-pixel position to a map-grid position """
    return ( pixel_x // GRID_SIZE, pixel_y // GRID_SIZE )

def gridPosToPixelPos( grid_x, grid_y ):
    """ Map a grid position to a window-position position """
    return ( grid_x * GRID_SIZE, grid_y * GRID_SIZE )
    
def getMapColour( x, y ):
    """ Convert map symbols into colours """
    symbol = MAP[y][x]
    if ( symbol == '#' ):
        return BLUE
    elif ( symbol == 'c' ):
        return YELLOW
    elif ( symbol == 'b' ):   # "Shadow" / "Blinky"
        return RED
    elif ( symbol == 'p' ):   # "Speedy" / "Pinky"
        return PINK
    elif ( symbol == 'i' ):   # "Bashful" / "Inky"
        return LIGHTBLUE
    elif ( symbol == 'o' ):   # "Pokey" / "Clyde"
        return ORANGE
    return BLACK


class GhostSprite( pygame.sprite.Sprite ):
    """ A pacman-like ghost sprite """

    def __init__( self, grid_x, grid_y, colour ):
        super().__init__()
        self.image = pygame.Surface( ( GRID_SIZE, GRID_SIZE), pygame.SRCALPHA )
        self.image.fill( colour )
        self.rect = self.image.get_rect()
        self.rect.topleft = gridPosToPixelPos( grid_x, grid_y )
        self.direction = random.choice( [ 'N', 'S', 'E', 'W' ] ) 


    def moveToGrid( self, grid_x, grid_y ):
        """ Allow position to be reset """
        self.rect.topleft = gridPosToPixelPos( grid_x, grid_y )

    def availableMoves( self ):
        """ Consult the map to see where is good to go from here.
            We only consider walls, not other NPCs """
        map_x, map_y = pixelPosToGridPos( self.rect.x, self.rect.y )
        exits = []
        # handle wrap-around, where it's possible to go "off grid"
        if ( map_x <= 0 or map_x >= MAP_WIDTH-1 ):
            exits = [ 'E', 'W' ]
        else:
            # otherwise consult the map
            if ( MAP[ map_y-1 ][ map_x ] != '#' ):
                exits.append( 'N' )
            if ( MAP[ map_y ][ map_x+1 ] != '#' ):
                exits.append( 'E' )
            if ( MAP[ map_y+1 ][ map_x ] != '#' ):
                exits.append( 'S' )
            if ( MAP[ map_y ][ map_x-1 ] != '#' ):
                exits.append( 'W' )
        return exits

    def getOppositeDirection( self ):
        """ Return the compass-opposite of our current movement direction """
        opposites = { 'N':'S', 'S':'N', 'E':'W', 'W':'E' };
        return opposites[ self.direction ]

    def moveForward( self ):
        """ Move in the current direction.  Generally we use the map
            to keep us in-bounds, but on the wrap-around we can get
            close to the edge of the map, so use special handling for
            warping """
        # handle wrap-around avenue
        map_x, map_y = pixelPosToGridPos( self.rect.x, self.rect.y )
        if ( MAP[ map_y ][ map_x ] == '<' ):
            self.direction = 'W'
            self.rect.x = (MAP_WIDTH-1) * GRID_SIZE
        elif ( MAP[ map_y ][ map_x ] == '>' ):
            self.direction = 'E'
            self.rect.x = 0
            
        # Whichever direction we're moving in, go forward
        if ( self.direction == 'N' ):
            self.rect.y -= GRID_SIZE
        elif ( self.direction == 'E' ):
            self.rect.x += GRID_SIZE
        elif ( self.direction == 'S' ):
            self.rect.y += GRID_SIZE
        else:  # W
            self.rect.x -= GRID_SIZE


    def update( self ):
        """ Move the ghost, mostly forward, never backwards (unless dead-end)
            At an intersection, possibly turn """
        exits = self.availableMoves()
        # Generally: Keep moving in current direction, never u-turn 
        opposite = self.getOppositeDirection()
        # 60% change of continuing forward at an intersection
        if ( self.direction in exits and ( len( exits ) == 1 or random.randrange( 0,100 ) <= 60 ) ):
            pass
        elif ( self.direction not in exits and len( exits ) == 1 ):
            self.direction = exits[0]   # maybe u-turn
        else:  # more than 1 exit
            if ( opposite in exits ):
                exits.remove( opposite )
            self.direction = random.choice( exits )
        # Move-it- Move-it
        self.moveForward()



###
### MAIN
###
pygame.init()
window  = pygame.display.set_mode( ( WINDOW_WIDTH, WINDOW_HEIGHT ), pygame.HWSURFACE )
pygame.display.set_caption("Pac Algorithm")

# Make background image of map
background = pygame.Surface( ( WINDOW_WIDTH, WINDOW_HEIGHT ), pygame.SRCALPHA )
for y in range( MAP_HEIGHT ):
    for x in range( MAP_WIDTH ):
        rect = pygame.Rect( x * GRID_SIZE, y * GRID_SIZE, GRID_SIZE, GRID_SIZE )
        pygame.draw.rect( background, getMapColour( x, y ), rect )

# Make the Ghosts
blinky = GhostSprite( 9, 7, RED )
inky   = GhostSprite( 8, 9, LIGHTBLUE )
pinky  = GhostSprite( 9, 9, PINK )
pokey  = GhostSprite(10, 9, ORANGE )
ghosts = pygame.sprite.Group() 
ghosts.add( [ blinky, inky, pinky, pokey ] )

# Ghosts move periodically
next_ghost_movement = pygame.time.get_ticks() + 1000

# Main loop
clock = pygame.time.Clock()
running = True
while running:
    time_now = pygame.time.get_ticks()
    # Handle user-input
    for event in pygame.event.get():
        if ( event.type == pygame.QUIT ):
            running = False

    # Movement keys
    keys = pygame.key.get_pressed()
    if ( keys[pygame.K_UP] ):
        print("up")
    elif ( keys[pygame.K_DOWN] ):
        print("down")
    elif ( keys[pygame.K_LEFT] ):
        print("left")
    elif ( keys[pygame.K_RIGHT] ):
        print("right")
    elif ( keys[pygame.K_ESCAPE] ):
        # Reset the ghosts home
        blinky.moveToGrid( 9, 7 )
        inky.moveToGrid( 8, 9 )
        pinky.moveToGrid( 9, 9 )
        pokey.moveToGrid( 10, 9 )
        next_ghost_movement = time_now + 1000 

    # move the ghosts
    if ( time_now > next_ghost_movement ):
        ghosts.update()
        next_ghost_movement = time_now + 100 

    # Update the window, but not more than 60fps
    window.blit( background, ( 0, 0 ) )
    ghosts.draw( window )
    pygame.display.flip()

    # Clamp FPS
    clock.tick(30)

pygame.quit()