CMPT 120 Assignment 4

1. In a file myrange.py, write a recursive version of the range function. Your function should be:
   def myrange(start, end, step): …

   You can assume that start<=end and that step>0. Under those conditions, your function should always return the same list as range(start, end, step).

2. In a file selectionsort.py, write a recursive version of the selection sort algorithm. Your function should be:
   def selection_sort(lst, start, end): …

   The recursive step should be to get the smallest item from lst[start:end+1] into lst[start]. Once this is done, you can recursively sort the list from start+1 to end.

3. In a file binary.py, write a recursive function bin_to_int that takes an unsigned binary value (as a string like "100101") and converts it to an integer (37 in the example).

   This can be done recursively for any length binary string. In the example ("100101"), notice that the first 5 characters of the string ("10010") convert to the integer 18, and the last character ("1") becomes 1. Therefore, the whole string converts to 37 = 2×18 + 1.

   So, you should first convert the first n-1 bits to a decimal value, double it, and add the last bit.

One common component of video games is non-player characters or NPCs. These are people or other entities in games that aren't controlled by the players. These range from the ghosts in Pac-Man to computer-controlled teammates in modern first-person shooters. (The term “NPC” is often reserved for non-opponents, but I'm using to refer to any computer-controlled entity in the game.)

NPCs seem to always receive the same criticism: they're stupid. Even Yahtzee thinks so (caution: he has quite the pottymouth). Most NPCs are prone to things like standing stupidly in a corner, and being generally useless. Basically, things don't seem to have progressed much since Pac-Man.

So, we're going to see what we can do about the problem. Working on a game like Halo 3 seems like a bit much, so we're going to start on the other end of the spectrum, with a Pac-Man-inspired game.

Your job in this assignment is to control the ghosts in a Pac-Man-like game. The game is quite different than the original Pac-Man. We will call our game CMPTman.

For this assignment, your job is to create an algorithm and program to control the ghosts. Name your program game.py.

Both CMPTman and the ghosts move around a grid of squares. CMPTman is trying to collect all of the dots; the ghosts are trying to catch CMPTman. Our game will eliminate many of the complications of Pac-Man: there will be no power pellets (so no eating ghosts), no bonus items, and no “lives” to lose (when CMPTman hits a ghost, the game is over). This is what the game will look like when played:

Our game will be turn-based instead of an action game. In the game, CMPTman will make two moves, and then each of the ghosts will take one.

You don't have to draw the board or worry about the gameplay: the provided module will do that for you. Your job is to design and implement an algorithm that will control the ghosts. The provided library will take care of CMPTman's moves. You simply have to provide the direction for each ghost to move for each turn.

The fundamental job of the ghosts is simple: get CMPTman!

Doing this well is quite hard and you aren't expected create a “perfect” solution (whatever that means). Start by getting the ghosts moving toward CMPTman and work up from there. Note that multiple ghosts can occupy the same square: they don't have to worry about running into each other.

Implementing

A module “cmptman” has been provided: you'll have to download the cmptman.pyc file. Save this file in the same directory as your program and you should be able to import it.

The module takes care of the actual game (except moving the ghosts, of course). When you get the game running, use the arrow keys to move CMPTman.

A collection of hints has been provided.

Your code should be easy to read and understand.

When you submit, include a text file about.txt that describes what your code is doing. You can use this to give whatever kind of description you think is appropriate for the markers. This will be a chance to describe anything you think is clever, or that we might not notice. You could also describe known problems (like “the ghosts always gets stuck if…”).

When you're done, submit your work in the Course Management System.

[Thanks to Deborah Lee for procrastinating by making nicer icons for the game.]