Transcript slides

CSE 348 AI Game Programming
Project 2: Pathfinding in Games
DUE: WEDNESDAY, FEBRUARY 29
PRESENTED BY: JAMES AHLUM
The Framework
 Pac-Man
 Developed at UC Berkeley
 Very well tested and documented
 The instructions are excellent
 We will focus on the search application of the framework
The Project
 Search in Pac-Man
 5 Tasks
 Depth-first Search
 Breadth-first Search
 A* Search
 Transition Tables
 A* Food Search
Find a path to eat all dots in the map as fast as possible
 In-class competition to determine the winner

Setup
 Download the Pac-Man Framework
 You can get the zip file here or from the website
 Unpack the zip file and store it in your desired location
 Download Python
 You want Python version 2.7.2
 Download it for various OS here
 Select the desired installation location

Default for Windows is C:\Python27
Setup
 Add Python to your Path


Windows: Computer > Properties > Advanced System Settings >
Environment Variables (under Advanced Tab)
Find “Path” under System Variables > Edit it and *APPEND*
C:\Python27 (or the directory where you installed Python)

Note: Do not replace the Path variable with C:\Python27, just append it
using a semicolon
 You should now be able to invoke the Python interpreter
from the command line


Open a Command Prompt, switch to the “search” directory where you
unpacked the zip file
Type “python pacman.py” to test your setup

It should open a GUI where you can use arrow keys to control Pac-Man
Development
 Pseudocode for the algorithms will be presented in
the next lecture
 The only files you should need to edit are search.py
and searchAgents.py

They are well commented and make it very clear where your
code needs to go
 An important note from the project website:
 “Each algorithm is very similar. Algorithms for DFS, BFS, and
A* differ only in the details of how the fringe is managed. So,
concentrate on getting DFS right and the rest should be
relatively straightforward.”
Development
 I recommend using the data structures in util.py
 Stack will be useful for depth-first search
 Queue will be useful for breadth-first search
 Priority Queue will be useful for A*
 If you don’t know Python, learning it might take
some time


The Pac-Man projects has a tutorial that goes over the basics
and key things you’ll need to know for this project
There’s also an official Python tutorial and full documentation
Python
 Data Structures
 Lists: list = [2, ‘a’, “string”], list[0] == 2
 Tuples: pair = (1,2), pair[0] == 1
 Sets: mySet = set(), mySet.add(1), 1 in mySet == True
 Dictionaries (associative arrays): f = {}, f[state] = 1.0, where
state = (x,y)
 Finding the length of a structure
 len(“abc”) == 3, len(list) == 3
 Comments:
 #single line comment, “””multi line comment”””
Debugging
 Print to the command prompt
 print “message”
 for state in answer: print str(state)

Notice the str() method to print string representation
 Log to a file
 file = open(‘log.txt’, ‘w’)
 file.write(‘log message \n’)
 file.close()
Deliverables
 Code
 Email search.py and searchAgents.py to [email protected] by
midnight, Wednesday, February 29
 If you create any additional files (i.e. for your own data
structures) or modify any existing files, also send those along
with a detailed description of the additions/modifications
 Presentation & Report
 As explained in the project description, due Thursday, March 1
That’s All
 Questions?
 Email [email protected] with CSE348 in the subject, CC
[email protected]