Courses/CS 491ab/Winter 2008/Spencer Perreault
From CSWiki
Contents |
[edit] Week 1 - January 4, 2008
This week we were introduced to the class, and to each other. I mentioned my interest in video games development and emulation.
[edit] Week 2 - January 11, 2008
[edit] SDL
[edit] What is SDL?
From its homepage:
"Simple DirectMedia Layer is a cross-platform multimedia library designed to provide low level access to audio, keyboard, mouse, joystick, 3D hardware via OpenGL, and 2D video framebuffer. It is used by MPEG playback software, emulators, and many popular games, including the award winning Linux port of "Civilization: Call To Power."
It's written in C, with bindings to numerous other languages, and released under the LGPL. It supports all major operating systems (Windows, Mac OS X, Linux, BSD variants, etc.) in addition to a number of more exotic platforms (like the Sega Dreamcast).
[edit] Where to get it
You can find the latest binaries and source code here: [1].
[edit] Example program
Note: You'll need to provide your own version of guy.bmp; my artistic works created with MS Paint fetch far too high a price to simply give them away for free.
#include <SDL.h>
int main(int argc, char *argv[])
{
SDL_Surface *screen, *guy, *background;
int running = 1;
SDL_Rect dstrect;
int playerX = 0, playerY = 0;
int x, y;
if (SDL_Init(SDL_INIT_VIDEO) < 0)
return 1;
screen = SDL_SetVideoMode(640, 480, 32, SDL_HWSURFACE);
guy = SDL_LoadBMP("guy.bmp");
SDL_SetColorKey(guy, SDL_SRCCOLORKEY, SDL_MapRGB(guy->format, 0, 0, 0));
background = SDL_CreateRGBSurface(SDL_HWSURFACE, 640, 480, 32, 0, 0, 0, 0);
SDL_LockSurface(background);
for (y = 0; y < 480; y++)
for (x = 0; x < 640; x++)
((Uint32 *)((Uint8 *)background->pixels + background->pitch * y))[x] =
SDL_MapRGB(background->format, x ^ y, x - y, x + y);
SDL_UnlockSurface(background);
while (running)
{
SDL_Event event;
Uint8 *keystate = SDL_GetKeyState(NULL);
while (SDL_PollEvent(&event) > 0)
{
switch (event.type)
{
case SDL_QUIT:
running = 0;
break;
case SDL_KEYDOWN:
if (event.key.keysym.sym == SDLK_ESCAPE)
running = 0;
break;
}
}
if (keystate[SDLK_LEFT])
playerX--;
if (keystate[SDLK_RIGHT])
playerX++;
if (keystate[SDLK_DOWN])
playerY++;
if (keystate[SDLK_UP])
playerY--;
SDL_BlitSurface(background, 0, screen, 0);
dstrect.x = playerX;
dstrect.y = playerY;
SDL_BlitSurface(guy, 0, screen, &dstrect);
SDL_UpdateRect(screen, 0, 0, 0, 0);
SDL_Delay(16);
}
SDL_Quit();
}
[edit] Week 3 - January 18, 2008
[edit] OpenGL
[edit] What is OpenGL?
From their website:
"OpenGL is the premier environment for developing portable, interactive 2D and 3D graphics applications. Since its introduction in 1992, OpenGL has become the industry's most widely used and supported 2D and 3D graphics application programming interface (API), bringing thousands of applications to a wide variety of computer platforms."
The main function of OpenGL is to provide uniform access to a wide variety of graphics cards. In this regard, its only competitor is Direct3D, which is restricted to Windows platforms. OpenGL, on the other hand, is supported by many operating systems.
Although SDL can do its own 2D drawing, due to the wide availability of graphics cards it is often advantageous to use them to offload the computational strain of drawing. Although OpenGL is used primarily for 3D applications, it is also suited to 2D as well.
[edit] SDL and OpenGL
SDL is designed to work hand-in-hand with OpenGL. By itself, OpenGL cannot handle such basic tasks as getting user input or even creating a window to draw in. There exist libraries that fulfill this need and actually require that you use OpenGL for rendering (like GLUT or GLFW). SDL can handle its own rendering if necessary, is more featured in most areas, and has been ported to many more platforms, so I'm going to stick with it for this example.
[edit] Example
#include <windows.h>
#include <GL/gl.h>
#include <SDL.h>
int main(int argc, char *argv[])
{
SDL_Surface *screen, *guy, *background, *converted;
int running = 1;
int playerX = 0, playerY = 0;
int x, y;
if (SDL_Init(SDL_INIT_VIDEO) < 0)
return 1;
screen = SDL_SetVideoMode(640, 480, 32, SDL_OPENGL);
guy = SDL_LoadBMP("guy.bmp");
background = SDL_CreateRGBSurface(SDL_SWSURFACE, 640, 480, 32, 0xFF, 0xFF << 8, 0xFF << 16, 0xFF << 24);
for (y = 0; y < 480; y++)
for (x = 0; x < 640; x++)
((Uint32 *)((Uint8 *)background->pixels + background->pitch * y))[x] =
SDL_MapRGB(background->format, x ^ y, x - y, x + y);
converted = SDL_ConvertSurface(guy, background->format, SDL_SWSURFACE);
for (y = 0; y < converted->h; y++)
{
for (x = 0; x < converted->w; x++)
{
Uint8 r, g, b;
Uint32 *pixel = (Uint32 *)((Uint8 *)converted->pixels + y * converted->pitch) + x;
SDL_GetRGB(*pixel, converted->format, &r, &g, &b);
*pixel = SDL_MapRGBA(converted->format, r, g, b, !r && !g && !b ? 0 : 255);
}
}
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, 128, 128, 0, GL_RGBA, GL_UNSIGNED_BYTE, converted->pixels);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0, 640, 480, 0, -1, 1);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE);
while (running)
{
SDL_Event event;
Uint8 *keystate = SDL_GetKeyState(NULL);
while (SDL_PollEvent(&event) > 0)
{
switch (event.type)
{
case SDL_QUIT:
running = 0;
break;
case SDL_KEYDOWN:
if (event.key.keysym.sym == SDLK_ESCAPE)
running = 0;
break;
}
}
if (keystate[SDLK_LEFT])
playerX--;
if (keystate[SDLK_RIGHT])
playerX++;
if (keystate[SDLK_DOWN])
playerY++;
if (keystate[SDLK_UP])
playerY--;
glClear(GL_COLOR_BUFFER_BIT);
glDrawPixels(640, 480, GL_RGBA, GL_UNSIGNED_BYTE, background->pixels);
glEnable(GL_TEXTURE_2D);
glBegin(GL_QUADS);
glTexCoord2i(0, 0); glVertex3i(playerX, playerY, 0);
glTexCoord2i(1, 0); glVertex3i(playerX + guy->w, playerY, 0);
glTexCoord2i(1, 1); glVertex3i(playerX + guy->w, playerY + guy->h, 0);
glTexCoord2i(0, 1); glVertex3i(playerX, playerY + guy->h, 0);
glEnd();
glDisable(GL_TEXTURE_2D);
SDL_GL_SwapBuffers();
SDL_Delay(16);
}
SDL_FreeSurface(converted);
SDL_FreeSurface(background);
SDL_FreeSurface(guy);
SDL_Quit();
return 0;
}
[edit] Week 4 - January 25, 2008
[edit] Physics engines
[edit] Physics for games
Nowadays, many games support physical interactions far more complicated and accurate than before. Since Half-Life 2, a game renowned for its impressive simulation of the physical world, it has become a common feature in most games. The widespread demand has created a market for fast (and less technically precise) physics engines. HL2 and many other games use the Havok engine. A company named AGEIA even attempted to create and market the first dedicated "physics card", with limited success.
The demands for a game physics engine are fairly limited; they deal almost exclusively with rigid body dynamics and collision detection - the movement and interactions of solid, non-deformable objects. Soft body dynamics and fluid dynamics, along with the rest of physics, have largely be ignored at this point due to prohibitive computational complexity for real-time use. For now, developers have found ways that these things can be reasonably faked (using separate models/animations for deformable objects, and limiting the kinds of interactions players can have with liquids).
[edit] List of engines
There exist a number of released physics engines, some open source, some closed, some free, and some that require licensing for commercial use. Here I will try to provide a quick overview of some of the more prominent ones.
[edit] Open Dynamics Engine (ODE)
A fairly well known and widely-used physics engine. It is free software, released under the BSD license and the LGPL, and supports rigid body dynamics and collision detection between basic geometric objects, triangle meshes, and height maps, and various joints and constraints. People have written code to simplify the use of ODE in conjunction with graphics engines (for example, OgreODE for use with OGRE).
[edit] Newton Game Dynamics
A free, but closed source physics engine. Unlike many engines designed with games in mind, it puts more emphasis on accuracy at the cost of speed. Feature-wise, it is on par with ODE.
[edit] Bullet
Written by a Havok ex-employee, this engine is free, open source, and released under the very liberal zlib license. It supports many of the same features as the above two, and also allows you to import physics information from COLLADA files (an open 3D model file format).
[edit] PhysX
A physics SDK created by AGEIA for use with their PhysX card, it also contains an implementation in software. It is freely available for download, but its source is closed and there are licensing restrictions. It is a very featured engine, and has been used in a number of commercial games. It is considered to be a competitor to Havok (although Havok still dominates the market).
[edit] Physics Abstraction Layer (PAL)
PAL is not a physics engine, but a wrapper.
From their website:
"The Physics Abstraction Layer (PAL) provides a unified interface to a number of different physics engines. This enables the use of multiple physics engines within one application. It is not just a simple physics wrapper, but provides an extensible plug-in architecture for the physics system, as well as extended functionality for common simulation components."
[edit] Week 5 - February 1, 2008
[edit] Programming games in C#
[edit] Introduction
Until now, I thought I'd be coordinating my senior project with a game I was working on for another project. A requirement of this project was that it must be completely cross-platform, which is why I avoided C# and XNA until now.
[edit] Continuing in the same vein with Tao
If I so chose, I could use all of the same libraries in C# that I would be using in C++. Tao, a subproject of the Mono project (an effort led by Novell to create an open-source set of tools and libraries compatible with the CLR and .Net), has bindings for SDL, OpenGL, and ODE, among other libraries. Using this, my code could remain largely platform-indepenent even when using C#.
[edit] Finally, we arrive at XNA
Until now, I had avoided mention of XNA because I did not believe I would be able to use it. It is the successor to Managed DirectX, which was originally a C# wrapper for DirectX. XNA has been actively developed over the last couple years into something much more: a powerful set of libraries and tools for game development. Version 2.0 has just been released, including some of the long-missing features of the 1.0 release including networking support (over LANs and through Xbox Live) and full integration into the Visual Studio 2005 toolchain (previously only offered for the Express version).
XNA is cross-platform, but not in the usual sense of the term. It is closed source, but is freely available for download and is in fact being marketed at hobbiests as well as developers as a solution for simultaneous development of games for Windows and the Xbox 360. Games developed with XNA will run on both platforms at remarkable speeds (for managed code), allowing for the creation of fully 3D games that utilize the latest graphics techniques (namely, pixel shaders).
[edit] Where I'm going from here
Whether I will choose to write a game in C++ or C# using SDL/OpenGL or XNA is mostly irrelevant at this point. In the next week I will have decide what I want to put these technologies to use, whichever ones I end up using.
[edit] Week 6 - February 8, 2008
[edit] Emulation
[edit] Introduction
Many of you may be familiar with the idea of emulation, though under a different name: virtualization, as it often referred to in the business world. In recent years, virtualization of hardware has become an important tool for easy deployment and testing of systems, as well as for the support of legacy code that only runs on old hardware or in a certain environment. In this context, the devices being emulated are collectively referred to as a virtual machine.
Consumers, and not just server administrators, have now become familiar with this technology. It has appeared in a number of forms, some of the most popular being those that allow Mac OSX users to run older Mac OS applications or newer Windows ones, the latter being easier now that Macs now run on Intel x86 CPUs. Intel has in fact introduced new features into its processors that are specifically designed to speed up virtualization.
However, emulators have long been utilized by regular computer users, in a specific form: console and portable game system emulators. These programs are designed to allow PC users to play games designed for systems other than their computers, provided that they have a ROM or CD-ROM image of the game data. This has raised a number of issues involving piracy, and the illegal distribution of games (collectively and from here on referred to simply as "roms"). The legality of emulators has also been called into question, a Playstation emulator called "bleem!" being a famous example because its creators were taken to court by Sony. Ultimately, the court ruled in favor of the emulator's authors, but they were forced out of business by legal fees. Since, there have not been many legal cases involving emulators, primarily because this incident revealed the danger of releasing an emulator commercially without the blessing of the console manufacturer.
However, many emulators have since been released for free, written by programmers and sometimes teams in their free time, and their legality is undisputed provided that official console documentation (provided only to people who have signed NDAs) was not used in their development.
[edit] From a technical perspective
Any self-contained emulator must be able to simulate the behavior of all the subsystems and devices in the target hardware. These can be broadly subdivided into three categories: processors, memory, and input/output devices. Often, for the purposes of an emulator it is not required that the software implementation of any of these reflects the internal hardware, as long as it produces the same results for the same input. Communication between subsystems can also be simplified, to some extent. This raises other issues, though, particularly that of synchronization. On the machine running the hardware, it will rarely be possible to truly emulate each in parallel. This is an issue I have not yet had to confront, but at some point I may.
[edit] Processor emulation
Software emulation of a single processor is straightforward, but also requires a signficant deal of code, depending on the architecture and instruction set. Conceptually, at the heart of a CPU emulator is the instruction cycle, also known as the fetch-and-execute cycle or fetch-decode-execute cycle. The emulator must pull the next instruction from memory at the address of the program counter, decode it and execute the corresponding code that emulations the functionality of the operation, then advance the program counter and begin again.
Of course, there are other elements that come into play in emulation of real CPUs, such as interrupts. Also, this method in particular can be refered to as an interpreter. There also exist significantly faster methods, such as dynamic recompilation, in which machine code is translated in blocks, on the fly, into machine code native to the platform on which the emulator is being run. This recompiled code is cached so that it can be reused again and again.
[edit] Chip8
I have read that perhaps an ideal starting point for an aspiring emulator author would be to take on the Chip8, a very simple system with a limited instruction set. In fact, it is technically a virtual machine, since it never had a physical implementation in hardware. However, the principles are the same, and the simplified architecture makes it easy to understand and implement. Indeed, the Wikipedia page (linked to above) provides almost all the information necessary to write an emulator for the system.
Last weekend, I wrote a Chip8 emulator using C and SDL.
[edit] Week 7 - February 15, 2008
Note: Due to my recent workload, I have not had a chance to update my weekly notes. Progress, however, has been made, and I will report on it during class.
[edit] Week 8 - February 22, 2008
[edit] Week 9 - February 29, 2008
[edit] Progress
I have begun collecting documentation on the Intel 8080 CPU. It was used in a number of arcade machines from the late 70s and early 80s, including the rather famous "Space Invaders". I have also started writing an 8080 CPU core in C#. Here are the most useful links with information that I have found so far.
Intel 8080 - Wikipedia
DatasheetArchive - Search results for "8080"
Space Invaders - Wikipedia
Space Invaders - Hardware map
Because of the 8080's age and the fact that it was supplanted by the Z80 years ago, Intel doesn't even offer any documentation for it on their website. I have had to look for documentation in various locations like the website DatasheetArchive, which collects digitized versions of various hardware documentation. There seem to be only two real official documents on the CPU with useful information: the Intel 8080 Microcomputer Systems User's Manual and Intel 8080 Assembly Language Programming Manual.
The page I located with the Space Invaders hardware map seems to cover most of the specific hardware of Space Invaders. I would like to use this game to test my 8080 core once it is completed.
[edit] Week 10 - March 7, 2008
[edit] Final Report
[edit] Brief project description
The goal of this project is to develop framework for writing emulation software for various devices and hardware used in video game systems as well as arcade cabinets. If users can provide the original game ROM data, they will be able to play video games made for supported game systems. My intent is to explore various methods of emulation: dynamic recompilation and on-the-fly generation of bytecode for virtual machines. The framework should enforce a modular design on emulated components, allowing them to be reused to add support for new systems with similar hardware.
[edit] Anticipated users
The users will be video game players with fond memories of old games or younger players who are curious about the history of games. In addition, users may also be individuals or groups interested in the preservation of games that are increasingly harder to find and play on their original hardware. This technology could also be licensed for use by companies who own the rights to old games and are interested in republishing them for modern hardware.
[edit] Main conceptual (i.e., user-level) objects
Objects relevant to the user will be the main application itself (which will come packaged with emulation modules), game ROMs, persistent machine data, snapshots of the emulator state, and possibly video/audio/input plugins, which can be written by third parties and may provide various levels of speed and compatibility on different operating systems.
[edit] Primary conceptual (i.e., user-level) operations
When users run the main application, they will be able to load game ROM images and save and load emulator snapshots (also known as savestates) as well as persistent machine data. Video, audio, and input plugins (encompassing all forms of I/O) should be swappable at runtime, and should allow some level of configuration by the user. There should be an integrated debugger that allows the user to control and observe the state of the emulator. Finally, users should be able to schedule self-updates consisting of the downloading and installation of new modules and bugfixes (adding support for new systems and enhancing compatiblity with existing ones) from a main server as they are made available.
[edit] Why I am interested in this project
I have always wondered about how things work, all the way down to the lowest level. This, combined with an interest in games, has led to a great interest in video game hardware and emulators for video game systems. I also see an opportunity to try something that has seldom been attempted: writing emulation software in managed code.
[edit] Status
I have done a little work on existing emulators and written a very small CHIP8 emulator of my own. I have begun writing an Intel 8080 CPU core for a Space Invaders emulator. I believe that Space Invaders a good arcade game for testing because it utilized very little hardware besides the 8080, and I have been able to find good documentation on what little extra hardware there was. I have also begun to look into the topics of dynamic recompilation and generating bytecode for virtual machines.
