COMP521 - Modern Computer Games

Winter 2008

• Preamble
• Assignment 1
  • PNFG
  • Inform
• Assignment 2
  • Bounding areas
  • Perlin Noise
• Assignment 3
  • GBA Emulator
• Assignment 4
  • Client/Servers

Your friendly neighbourhood TA here. If you haven't noticed, this page is pretty much in a constant state of flux. Generally speaking though, I'll try to make sure everything you see/hear on this page is true -- if not always complete.

Given this state of affairs, it may some day happen that you can't find what you're looking for here -- or that what you do find doesn't make much sense. On such occasions, feel free to send off a quick email to...

Nicholas.Rudzicz <AT> mail.mcgill.ca

Sadly, 70% of my waking hours are spent jacked in to the "Internets," so I'll probably get your email right away.

Go forth, young hobbits...

UPDATE: I've uploaded my own class notes from when I took the course. They can be found here. I MAKE NO CLAIMS AS TO THEIR ACCURACY; however, they can hopefully help you get a better grasp or a new perspective on a given problem.

UPDATE #2: I've uploaded the class presentation I gave regarding procedural content generation in video games. (Link)

UPDATE #3: (if anyone still visits this site) I enjoyed TA'ing the course, and I hope you each took something away from it as well. I'm not sure if TA assessments have been disabled/delayed because of the TA strike (or if anyone bothers filling them out), but if there are any lingering issues, complaints, questions, or anything else, I can be reached at my McGill email, above, or otherwise at nrudzicz <AT> hotmail. It was a pleasure, and I hope to see you kids around campus.

% java -cp pnfg.jar pnfg.Main -nfg foo.pnfg > foo.nfg

% java -cp nfg.jar nfg.Main foo.nfg

Troubleshooting

• I compiled these .jar files with JDK 1.5. Check that any errors you might have do not arise from an incompatible JVM.
• Java heap size is sometimes a problem. If you encounter an 'Out of memory' error, or something similar, you can try adding the '-Xmx1000M' flag to the command line, just after 'java'
• UPDATE: It seems that PNFG is indeed affected by the newline characters in your .pnfg source files: it expects Unix newlines as opposed to Windows ones. If you're writing/compiling your .pnfg file in Windows, you'd be well-advised to either:
  • Copy your .pnfg file to your McGill CS account, and use the "dos2unix" command on the file there (i.e., "% dos2unix foo.pnfg").
  • Download Cygwin to your Windows machine, install dos2unix.exe through Cygwin's interface, and run the program on your local source file, as above.

Example(s)

• As a zero'th order step, set aside a directory for your Inform install. We'll pretend it's in /home/nick/Inform. I'll refer to that directory as $INFROOT.


• Download the Inform executable into your $INFROOT directory (you may have to right-click and select "Save as"). Unzip the package (if you're not prompted with a GUI to do so) with:
  

  % gunzip inform630_linux.gz



• Download the Inform library, and unzip the contents into the same $INFROOT directory. You can now give the compiler a shot, using any of the examples found here, as follows:
  

  % ./inform630_linux Advent.inf

  This will generate a .z5 file (in this case, "Advent.z5")


• Finally, download the Frotz Z-machine compiler, here. Once again, save it to your $INFROOT directory. To unzip and compile it:
  
  • Unzip/untar it with:
    

    % tar xzvf frotz-2.43.tar.gz

  • Then, to compile:
    

    % cd frotz-2.43
    % make

  • Then, to run your compiled z5 program:
    

    % ./frotz ../Advent.z5

• WINDOWS USERS: If you really must use Windows, you can use the following links:
  • First, get the Inform executable here. Unzip the .exe into your $INFROOT directory.
  • Download the Inform library from the same link as above. Unzip those files into your $INFROOT directory as well.
  • You can now compile an Inform game file (*.inf), examples of which are shown in the link above. Compile them with:

    > inform-631.exe Advent.inf

  • Download the Windows-specific Frotz interpreter from here, and extract everything into a new directory, say $INFROOT\frotz
  • You can now use the Frotz interpreter to run your game files as follows:

    > WinFrotz.exe ..\Advent.z5

Troubleshooting

• If you have trouble connecting to the if-archive servers (which seems to happen more frequently than I'd like), try connecting to any one of the dozen or so mirrors. Hopefully, one will be available.
• If you just connect to the mirror at its head, or if the particular versions of Inform executables/libraries/interpreters to which I've linked don't work for you, you can navigate to different versions of each.
  • Try one of the mirrors listed above. Once you find an active one, follow the links listed below for each type of file...
  • Executables: $INF-MIRROR -> infocom -> compilers -> inform6 -> executables
  • Library: The library is the same for all platforms.
  • Interpreter: $INF-MIRROR -> infocom -> interpreters -> frotz

• The random points you generate can be within arbitrary limits (up to the maximum and minimum representable numbers in your language of choice, of course). However, I suggest two things:
  • Do not restrict yourself to one quadrant of Cartesian space. Allow both negative and positive values on both the x and y axes.
  • Since you'll be comparing the effectiveness of two algorithms, having larger clusters will make the comparisons more obvious -- that is, the difference in resulting areas will be more apparent.
• With these two points in mind, my own suggestion would be to generate random points anywhere between no less than -1,000 and 1,000 on both axes, scaling those limits outwards if you feel so inclined.
• However, I spoke with Prof. Verbrugge, and he expressed his own opinion that the points would be best chosen from around the origin. His explanation is that, since floating-point values in any language have a fixed number of bits, larger values have a larger number of bits devoted merely to generating the offset from the origin, which results in fewer bits devoted to absolute precision. Conversely, values close to the origin can devote more bits to precision. Thus, it's argued that picking your random points from around the origin will result in more precise values.
• All this to say that picking ranges for your random points is up to you. Picking them on a larger scale (-1000 to 1000, say) will result in larger (by magnitude) differences in area; picking the points on a smaller scale will result in much more precise answers. Since we're mainly interested simply in the comparison (e.g., "Ritter's algorithm gives bounding circles 1.25 times as big as Welzl's"), the choice is up to you.
• See my class notes (up in the preamble) for my own interpretations of some of these algorithms.
• Ritter notes:
  • Nothing yet...
• Welzl notes:
  • The question came up as to whether the "base case" of three points defining a circle was really a trivial calculation. It is indeed trivial, although not necessarily obvious. The procedure can be found here: http://windowseat.ca/circles/ (click on "learn about circles"). There's a lot of graphical fluff, but it's probably the best explanation you'll find.

• There are obviously a number of ways to go about this problem; however, in the end, you should all have something that looks fairly similar.
• Personally, I tried implementing something myself following the instructions on this site (also linked to on the main course website). It took me three or four hours to get some good-looking noise.
• Note that Zucker's approach says nothing about octaves! We have to take his algorithm and iterate it n times (where n is our number of octaves).
• At each iteration -- that is, for each octave -- we have to calculate the frequency and amplitude associated with that octave. We then use x*freq and y*freq as the "inputs" for this iteration, perform the calculation as explained on Zucker's website, and multiply the result by our amplitude. This final result is then added to our running total of the noise generated at the original x,y co-ordinates.
• New: I received an email based on Zucker's approach to Perlin noise, and the response I wrote was typical of me, in that it was long and overly wordy. There might be some useful information in it however, so I reproduce it here.

Troubleshooting

• I had the problem (and apparently wasn't the only one) getting the Assig2.java applet to load in my browser. I'm in Ubuntu, and after googling the symptoms I traced the problem to issues with the libXp library. In my repositories, I found that I already had libxp6 installed, but not libxp-dev. I installed the latter and had no more problems. If you're having similar issues, check if you have (in whatever distro you use) libxp and libxp-dev installed (I don't think this is a problem in Windows).

• HALT! Before doing anything else, please visit this site if you haven't already. It was created by the person who wrote the original Ship code, and it's a wealth of information (the link appears in the readme file posted on the course website, but you may not have seen it beforehand).
• Simply put, getting the actual debugger to work with devkitARM is a pain. When I took the course, most if not all students gave up on the debugger and just printed debug messages to the terminal -- not as elegant a solution perhaps, but it is simple and it works. To do so, search the above website for "agbprint". You'll see the function prototype ("extern void..."); just include this in a header file in your project. Then, when you want to print something, use a character string:
  

  char foo[100];
  sprintf(foo, "Counter value is %d\n", count);
  agbprint(foo);

• The website claims that the agbprint function doesn't work for versions of VBA later than 1.7.1 -- however, I'm using 1.7.2-6 in Ubuntu, and it works just fine.
• WINDOWS USERS: I know some Windows users are having trouble getting either the Unix tools, the compiler, the emulator, etc. working. I managed to get it up and running (after a few headaches) on the WinXP partition on my laptop.
  • The bulk of the instructions are available here. I'll refer to this as The Guide <dramatic music>.
  • Note that I'm using Eclipse v3.3 (Europa) with the latest CDT plugin.
  • You will also need the Windows versions of a few Unix tools. Cygwin is your best bet. Follow the installation instructions on the site, and make sure you use the installation wizard to install, at a very minimum, the "make" and "gcc" utilities.
  • You must add the Cygwin binaries to your PATH environment variable. For this, go to Control Panel -> System -> Advanced tab -> Environment variables -> In "System Variables", edit the one named PATH. Just add the absolute path of the Cygwin binaries, which will be something like "C:\cygwin\bin"
  • In step 3) in the above guide, it asks you to install devkitARM. The version I used is available here.
  • The version of VisualBoyAdvance that I used is available here. I used the first one labeled "Windows - Development".
  • Create the C project in Eclipse, as shown in the Guide. Skip the parts in step 6) that talk about source files and make files. Just take the "ship" source code and unzip it into your project, makefile and all
  • Then do the steps in step 6) of the guide that talk about adding make/build targets
  • Et voila. Follow the rest of the guide and you should be on your way. Or, you'll get a ton of errors. That's what I'm here for.
• A long-time listener, first-time caller pointed out that there are also instructions on how to use devkitARM in MS Visual Studio 6. Feel free to make the attempt if you're more comfortable in MSVS6, though I won't be able to offer as much assistance with it.
• NEW: A student noted that their implementation of A* for the computer-controlled ship was somewhat time-consuming, and they asked how this would affect the mark for this question. This was my response:
  • Yup, that's indeed a tough question. Obviously the strict hardware limitations of the GBA make full/quick searches time consuming. I've spoken with Prof. Verbrugge, and we agreed that the ideal program would be real-time (no slowing down) and dynamic -- that is, if the black ship is moving toward its target, and the white ship moves, the black ship should be able recalculate a new trajectory, instead of following the original one all the way to the end.
    Clearly, that's very, *very* hard to implement on this system. As mentioned in the assignment handout, you can experiment with different search depths. This should give you a nice hard limit to the amount of "exploration" your algorithm does, reducing time and memory usage. Also, finding quantitatively "better" heuristics will have some effect (though generally a bit smaller) by more accurately directing your search, and thus finding a correct path more quickly.
    All this to say that there is an "ideal" program which is dynamic and real-time. Since this is very hard to implement, I will try to give the majority of points for the question based on having a sound version of A* -- so if your program is slow, or if it does not recalculate a path to the (moving) white ship on the fly, you should still get a good mark. (A good mark being anything north of 60%. I realise the marks for A2 were a bit...scary, but this is university after all -- and the marks do get averaged out in the end).

• NOTE: Question 2 builds on work done in Question 1; so much so that it's pretty pointless to create two separate executables. Feel free to combine the two questions into one executable. However, please have some sort of notification in both the server and clients that indicates when the initial connection is complete:
  

  SERVER: Question 1 -- n connections complete
  ...
  CLIENT: Abracadabra -- Question 1 connection complete

• It also seems that some people, starting at Question 2, are assigning completely random movement vectors to each client's shapes at every game loop. This is incorrect. If your client is implementing the "move in a random straight line forever" behaviour, then the client generates a random vector on creation, and uses this movement vector until the client itself is destroyed. The client does not create a new random movement vector at each game loop. Thus, the clients move their shapes in straight lines, but the direction of these lines is determined randomly when the client is created.