CSCI 171: Lab exercise 3

In the first three parts of this lab you will read through the descriptions of how to set up a map tiling system and a pair of AI movement/exploration algorithms.

You will then complete two exercises in revising the maps and the exploration algorithms as the 'marked' portion of the lab, worth 5% of your total course mark, and to be submitted by the start of the lecture session on Thursday April 8th.

A compact version of the exercise portion is available for printing here.

The initial setup involves copying python and image from the instructor's account to your own, and making each of the programs executable.

Turn in the (paper) copy of your work by the deadline noted above.

Initial setup

First, as always, move into your csci171 directory, create a directory for this week's lab, and move into that. E.g. 

   cd csci171
   mkdir lab10
   cd lab10
Next, copy across some files for this week's lab (from Dave's account to your current directory): 

   cp  ~wesselsd/labfiles/lab10/*  .

Run the chmod command to make any python scripts executable:
chmod u+x *.py

This completes the setup, you can now proceed to the actual lab exercises below

Part 1: storing map information as a grid

As discussed in lectures, one way to simplify map handling is to divide the game map into a collection of rows and columns, and identify a terrain type for each square on the map.

When drawing the map we draw the squares, or tiles, individually - picking a small image appropriate for the terrain in that square.

In today's example, we will use a grid of text characters to store the terrain types for a map divided into 15 rows and 15 columns.

Each tile will be 32 pixels by 32 pixels, making the overall map 480 x 480.

We will have a handful of different terrain types, each represented by a different alphabetic character:

To look up the kind of terrain in any map square we could use the row and column, e.g. something like: 

print "looking up row 3, column 7"
t = defaultMap[r][c]
if (t == 'w'): print "it is a wall"
elif (t == 'g'): print "it is grass"
elif (t == 'l'): print "it is a lake"
elif (t == 'f'): print "it is the finishing flag"
else: print "oops, there is a bad character in the map data"
Note: remember that indexing in Python starts at 0, so when there are 15 rows they are numbered 0..14, and that the 15 columns are similarly numbered 0..14.

Part 2: tiling

Part 1 showed how we'll store information about the map internally, but we also need to create a set of terrain objects, the images to draw on the screen as the background (i.e. the pieces of wall, lake, grassland, etc).

We'll create an extension of the Sprite class to represent terrain objects, we'll make sure the setup routine reads through our map description from part 1 and creates the needed terrain objects for the display, and we'll make sure the main routine updates them the same way it updated other game objects in our previous labs.

The class for the terrain objects might look something like this:

Our gameSetup routine needs to read our defaultMap and create a seperate object for each map square, keeping them all in a global list, e.g.:

Finally, our main routine needs to create a group for the terrain objects and update them, just as we would do for character objects in our game, e.g.:

Part 3: AI exploration of the map

Our AI characters will now keep track of which map square they are in, and will try to explore the map by looking at the grid we created and seeing if they can move into adjacent squares on the map. Here we'll assume the characters can only move around on grass squares.

When we create a character, we'll specify the image for it, the starting map row and column, the direction they face initially (north, south, east, or west), a movement style (random or clockwise, described a little later), and a unique integer id.

E.g. in the main routine the list of created AI might look like:

The AI exploration code itself is a little more extensive, so it has been divided into a handful of smaller routines:

Code for the complete character class, with all the setup and movement routines, is given below.

Complete code version 
#! /usr/bin/python
import sys, os, pygame, random

# =====================================================================
# GLOBAL VARIABLES
gameScreen = None   # the main display screen
scrRefreshRate = 250 # the pause (in milliseconds) between updates
keepPlaying = True  # flag to identify if the game should continue
backImage = None
terrainList = []

# define the size of the pygame display window
scrSize = scrWidth, scrHeight = 480,480
mapRows, mapCols = 15, 15 # the size of the map in rows by columns
tilePixels = 32
defaultMap = [
      ['w','w','w','w','w','w','w','w','w','w','w','w','w','w','w'],
      ['w','g','g','g','g','g','g','g','g','g','w','g','g','g','w'],
      ['w','g','w','g','g','w','w','w','w','g','w','g','w','f','w'],
      ['w','g','w','g','g','w','g','g','g','g','w','g','w','w','w'],
      ['w','g','w','w','w','w','g','w','w','w','w','g','g','g','w'],
      ['w','g','g','w','g','g','g','g','g','g','w','g','g','g','w'],
      ['w','g','g','w','g','g','g','g','l','g','w','w','w','g','w'],
      ['w','g','g','w','g','g','l','l','l','g','g','g','g','g','w'],
      ['w','g','w','w','w','w','l','l','l','l','g','g','g','g','w'],
      ['w','g','w','g','g','g','g','l','w','g','g','w','w','w','w'],
      ['w','g','w','g','g','g','g','g','w','g','g','w','g','g','w'],
      ['w','g','w','w','w','w','w','g','w','g','w','w','g','g','w'],
      ['w','g','g','g','g','w','g','g','w','g','w','w','g','w','w'],
      ['w','g','w','g','g','g','g','g','w','g','g','g','g','g','w'],
      ['w','w','w','w','w','w','w','w','w','w','w','w','w','w','w']
   ]

# =====================================================================
# SETUP ROUTINE    
#    - initializes the pygame display screen and background image

def gameSetup():

   # specify the global variables the setup routine needs to access
   global gameScreen, scrSize, backImage, terrainList, mapRows, mapCols

   # initialize the randon number generator
   random.seed()

   # initialize the display screen
   pygame.init()
   gameScreen = pygame.display.set_mode(scrSize)
   backImage = pygame.image.load('backdrop.gif')
   gameScreen.blit(backImage, (0,0))

   # now build the terrain objects from the text map,
   # a seperate object is created for each tile on the map
   r = 0
   while r < mapRows:
      c = 0
      while c < mapCols:
         terrainList.append(Terrain(defaultMap[r][c], r, c))
         c += 1
      r += 1

# ====================================================================
# TERRAIN OBJECT
#    terrain constitutes the background of the game map,
#        e.g. grass, walls, water, etc
#
#    each terrain object has several properties:
#        - the image loaded for that terrain object
#        - the terrain object's pixel position on the display
#        - the terrain object's map square (row, column)
#        - the terrain type (grass, lake, wall)
class Terrain(pygame.sprite.Sprite):

   # the constructor (initialization routine) 
   def __init__(self, terrainType, r, c):

      # initialize a pygame sprite for the object
      pygame.sprite.Sprite.__init__(self)

      # establish the terrain attributes
      global tilePixels
      self.terrainType = terrainType
      self.row = r
      self.col = c
      self.position = self.x, self.y = r*tilePixels, c*tilePixels
      if terrainType == 'g':
         self.image = pygame.image.load('grass.gif')
      elif terrainType == 'w':
         self.image = pygame.image.load('wall.gif')
      elif terrainType == 'f':
         self.image = pygame.image.load('finish.gif')
      else:
         self.image = pygame.image.load('lake.gif')
      self.rect = self.image.get_rect()

      # draw the terrain
      global gameScreen
      gameScreen.blit(self.image, (self.x, self.y))

   def update(self):
      # redraws the terrain item
      self.rect.topleft = self.x,self.y

# =====================================================================
# CHARACTER OBJECT

class Character(pygame.sprite.Sprite):

   # the constructor (initialization routine) 
   def __init__(self, image, r, c, mdir, moveAlg, cid):

      # initialize a pygame sprite for the character
      pygame.sprite.Sprite.__init__(self)

      # record the character's unique id
      self.characterID = cid

      # load an image for the character
      self.image = pygame.image.load(image)
      self.rect = self.image.get_rect()

      # set up the initial position for the character,
      #    both as a map square (row,col) 
      #     and as a display (pixel) position (x,y)
      global tilePixels
      self.mapLocation = self.row, self.col = r, c
      self.position = self.x, self.y = r*tilePixels, c*tilePixels

      # set up the initial direction for the character
      self.movingDir = mdir

      # record the movement plotting algorithm the character should use
      #   (e.g. 'random' movement, 'clockwise' movement, etc)
      self.plotting = moveAlg


   # check for a winner (adj to finish flag)
   def checkForWin(self):
      global keepPlaying
      win = False
      if (defaultMap[self.row+1][self.col] == 'f'):
         win = True
      elif (defaultMap[self.row-1][self.col] == 'f'):
         win = True
      elif (defaultMap[self.row][self.col-1] == 'f'):
         win = True
      elif (defaultMap[self.row][self.col+1] == 'f'):
         win = True
      if win:
         print "***************************"
         print "!!!!! AI number", self.characterID, "won !!!!!"
         print "***************************"
         pygame.time.delay(2000)
         keepPlaying = False
         return True
      else:
         return False

   # the update routine adjusts the character's current position 
   #     and image based on its direction and the local terrain
   def update(self):

      # calculate the object's new position based on its old position, 
      #    its current direction, and the local map terrain
      global defaultMap, tilePixels
      
      # end the game if a character has found the flag   
      if self.checkForWin():
         return
         
      # figure out where the character should move next,
      #    based on their plotting algorithm
      if (self.plotting == 'clockwise'):
         # characters attempting to follow the walls around the maze
	 #    should always run their plotting algorithm
         self.plotDirection()

      elif (self.plotting == 'random'):
         # characters using random plotting have roughly a 1/3 chance
	 #    of replotting their direction (i.e. randomly changing
	 #    which direction they're going)
         if (random.randint(0,100) < 34):
            self.plotDirection()

	 # otherwise, characters using random plotting will try to
	 #    keep going in the same direction if possible
	 # if their way turns out to be blocked then they'll
	 #    randomly plot a new direction
         elif not self.checkAndMove(self.movingDir):
               self.plotDirection()

      # position the image correctly
      self.rect = self.image.get_rect()
      self.rect.topleft = self.x,self.y = self.row*tilePixels, self.col*tilePixels


   # check to see if you are able to move in the specified direction (n,s,e,w)
   #    if it is possible, i.e. if the target tile is grass,
   #       then move, set your direction movement, and return true
   #    otherwise return false
   def checkAndMove(self, d):
      global defaultMap
      if (d == 'n'):
         if (defaultMap[self.row-1][self.col] == 'g'):
            self.row -= 1
            self.movingDir = 'n'
            return True
      elif (d == 's'):
         if (defaultMap[self.row+1][self.col] == 'g'):
            self.row += 1
            self.movingDir = 's'
            return True
      elif (d == 'e'):
         if (defaultMap[self.row][self.col+1] == 'g'):
            self.col += 1
            self.movingDir = 'e'
            return True
      elif (d == 'w'):
         if (defaultMap[self.row][self.col-1] == 'g'):
            self.col -= 1
            self.movingDir = 'w'
            return True
      return False

   # plotDirection calculates a new facing for an AI based on
   #     both the surrounding terrain and the AI's destination
   def plotDirection(self):
      global defaultMap

      # in random movement, there is an equal chance of the AI
      #    attempting to move in each of the four directions
      if (self.plotting == 'random'):
         choice = random.randint(0,100)
         if (choice < 25):
            self.checkAndMove('n')
         elif (choice < 50):
            self.checkAndMove('e')
         elif (choice < 75):
            self.checkAndMove('w')
         elif (defaultMap[self.row+1][self.col] == 'g'):
            self.checkAndMove('s')
            
      # in clockwise movement the AI basically tries to hug the wall:
      #    the AI tries to turn clockwise from its current facing,
      #    but if that is blocked the AI tries to keep moving
      #        in its old direction
      #    if that is also blocked,
      #       then the AI tries to turn still further
      #    and if that is also blocked then the AI goes in
      #       the one direction left 
      elif (self.plotting == 'clockwise'):
         if (self.movingDir == 'n'):
            # was moving north, see if we can turn east
            if self.checkAndMove('e'): return
            # otherwise see if we can go north
            elif self.checkAndMove('n'): return
            # otherwise see if we can go west
            elif self.checkAndMove('w'): return
            # otherwise go south
            else: self.checkAndMove('s')
         
         elif (self.movingDir == 'e'):
            # was moving east, see if we can turn south
            if self.checkAndMove('s'):  return
            # otherwise see if we can go east
            elif self.checkAndMove('e'):  return
            # otherwise see if we can go north
            elif self.checkAndMove('n'): return
            # otherwise go west
            else: self.checkAndMove('w')
               
         elif (self.movingDir == 's'):
            # was moving south, see if we can turn west
            if self.checkAndMove('w'): return
            # otherwise see if we can go south
            elif self.checkAndMove('s'): return
            # otherwise see if we can go east
            elif self.checkAndMove('e'): return
            # otherwise go north
            else: self.checkAndMove('n')
               
         else:
            # was moving west, see if we can turn north
            if self.checkAndMove('n'): return
            # otherwise see if we can go west
            elif self.checkAndMove('w'): return
            # otherwise see if we can go south
            elif self.checkAndMove('s'): return
            # otherwise go east
            else: self.checkAndMove('e')


# =====================================================================
# EVENT HANDLING ROUTINE
#    - processes any pending in-game events

def processEvents():

   # specify which global variables the routine needs access to
   global keepPlaying

   # process each pending event
   for event in pygame.event.get():

      # if the user closed the window set keepPlaying to False
      #    to tell the game to quit playing
      if event.type == pygame.QUIT:
         keepPlaying = False

      # check if the user has pressed a key
      elif event.type == pygame.KEYDOWN:

         # the escape and q keys quit the game
         if event.key == pygame.K_ESCAPE:
            keepPlaying = False
         elif event.key == pygame.K_q:
            keepPlaying = False


# =====================================================================
# MAIN GAME CONTROL ROUTINE
#    - sets up the game and runs the main game update loop
#      until instructed to quit

def main():

   # identify any global variables the main routine needs to access
   global gameScreen, backImage, scrRefreshRate, keepPlaying

   # initialize pygame and the game's display screen
   gameSetup()

   # create a list of characters to add to the display,
   # giving each of them an image, map row, map column, 
   #    facing direction, movement plotting style, and unique id
   characterList = [ 
               Character('ghost1.gif', 1, 1, 'e', 'random', 0),
               Character('ghost2.gif', mapCols - 2, 1, 'n', 'clockwise', 1),
          ]

   # create a group out of the list of character objects
   characterGroup = pygame.sprite.RenderUpdates(*characterList)

   # create a group out of the list of terrain objects (map tiles)   
   terrainGroup = pygame.sprite.RenderUpdates(*terrainList)

   # run the main game loop
   keepPlaying = True
   while keepPlaying:

      # handle any pending events
      processEvents()

      # clear both the character group and the terrain group
      # update both groups
      # get a list of changed sections of the screen
      #     as a result of changes to the characters and tiles
      # and redraw the display
      characterGroup.clear(gameScreen, backImage)
      terrainGroup.clear(gameScreen, backImage)
      characterGroup.update()
      terrainGroup.update()
      updateSections = terrainGroup.draw(gameScreen)
      updateSections += characterGroup.draw(gameScreen)
      pygame.display.update(updateSections)
      pygame.display.flip()

      # pause before initiating the next loop cycle
      pygame.time.delay(scrRefreshRate)

   # shut down the game
   pygame.display.quit()
   sys.exit()


# =====================================================================
# INITIATE THE GAME
#    - calls the main() routine
if __name__ == "__main__":
   main()

Part 4: Lab exercises

There are two parts to the actual exercise portion of the lab
(i) changing the code to use a new, smaller, map
(ii) changing the code to use a new wall-hugging algorithm

(i) replacing the map

The code that determines the map size and content in this lab is this section:

The first exercise is to replace the map with a map that is 5 rows by 5 columns, with walls around the outside, the finish flag in the center, and grass everywhere else. (This should result in 10 lines of code.)

(ii) replacing the wall hugging algorithm

The code that controls the 'wall-hugging' algorithm for the AI contained in a portion of the plotDirection routine (shown below with the comments removed).

The second portion of the lab exercise is to provide an alternate version of the code that causes the AI to hug the wall in the opposite direction - i.e. counter clockwise instead of clockwise.