*** How To Write a Pacman Game in JavaScript ***
A tutorial for advanced JavaScript techniques. This file is related to scripts to be found at
PrefaceThe game described here differs from the original "Pac-Man"™ by Namco™ <http://www.namco.com/> in some ways: The original game uses only one layout populated by four ghosts, each ghost guided by a distinguished strategy and moving at its own speed. The various levels differ by the ghosts' strategy and the speed of the game. Opposed to this, the game as described here will be populated by ghosts employing a shared set of movement strategies. (The speed will probably be the same as the speed of the pacman character or a fraction of it.) In order to entertain some difference to the game play each level will have its unique layout. This conforms with the typical appearance of a Pac-Man clone. The original "Pac-Man" by Namco and its clones share the following features – as does the game described here: The player guides a little yellow ball (the pacman) through a maze-like labyrinth in order to clear all the food (embodied by tiny white dots) laid out in the passages of the labyrinth. His opponents are 4 ghosts of different color roaming the labyrinth in search for the pacman. If any of the ghosts comes in touch with the pacman, the pacman looses a life and is reset to its original position. Some of the food dots (usually four of them) are bit bigger and provide a reversed game play, when eaten by the pacman: For a limited amount of time the pacman now may haunt and eat the ghosts. (This phase is indicated by the ghosts' color – usually a deep blue.) If the pacman manages to get grip of a ghost in this special phase, the ghost is not killed, but set to the central cage, from which it emerged at the beginning of the level. Pac-Man™and Namco™ are trademarks of the specific vendor(s). 1) ResourcesBefore we begin with our script, we should consider the elements of our game display (the actual user experience), what resources are therefore needed, and if any structure obliges to these. For this example we'll base on the following assumptions:
for the characters we'll need some states for the animation phases:
To save some resources, we'll skip any scoring indicators (like "200", "400" and so on for any ghost). And we're not going to implement a direction dependent looking angle for the ghosts in order to safe some more resources as well. All these informations will be displayed as gif-images, so we're left with the following images:
+ some extra images for level display (10 figures), a game over display, and so on. 1.1) Character Image NamesIn order to have access to these images via JavaScript, we definitely should name them in some structured manner. For JavaScript robustness every name will begin with a character, since we're going to store these names in an associative array. Here we decide to name them in the following way:
1.2) Maze TilesHow many tiles do we need? borders:The whole game is governed by the 4 directions of a 2D-surface. So most of the tiles can be ordered in quadruples. Here we'll list them by connected sides:
(The cage will consist of 4 empty tiles in the middle of the maze. The door (a dotted border tile) will be placed at the lower right. In order to have nice edges of this door we'll use 2 special corner tiles here.) For the naming scheme we could any names and refer to them via a reference array. Since we're going to access them only while displaying a new maze at the beginning of a new level, this operation is not time critical. Here we're using a binary 4-bit vector, encoding the connected endings prefixed by 'tile', where 'tile0.gif' is just a blank space and 'tile15.gif' the tile with 4 connections (cross). We'll use 'tile16.gif' to 'tile19.gif' for our 4 special tiles. 1.3) Implementing the Maze (HTML)Since we want to display the maze on a HTML-page, we're going to setup a HTML-table, with 20 images in 14 rows. In order to access these tiles via JavaScript, we must name them in some structured manner. Here we're using a scheme 'r'+row+'c'+col, where row will be an index from 1 to 14 and col an index from 1 to 20. So an IMG-tag (displaying an empty tile) will look like <IMG SRC="images/tile0.gif" NAME="r1c1" ...> 1.4) Implementing the Characters (HTML/CSS)Since our characters will be able to move smoothly, we'll need to implement them in layers or CSS-divisions. We need a naming scheme here too, since we'll have to access them via JavaScript. We'll use 6 layers in total (1 for the pacman, 4 for the 4 ghost's, and 1 to display a "game over" information.) In order to not interfere with any possible browser's layout engine, we'll place them just before the BODY-end-tag (</BODY>). Since we're possibly going to loop through the ghosts, these layers will obviously be using an indexed name. These layers hold each one single image to display the according character. Since these images will have to be replaced for every animation step, the will be named too. Here we're using the following definition: <DIV ID="gLr1" STYLE="height:27; width:27; position:absolute; top:0; left:0; visibility:hidden; z-index:2"><IMG NAME="g_i1" SRC="images/tile0.gif"></DIV> (We could have used some stand alone images as well, but in order to support Netscape 4, we have to place them in a layer in order to move them around.) Remember for support of NS4: Don't use HTML4-tags like <TBODY> in the page to not confuse the CSS-engine of NS4. (Actually we do not offer a full support of NS4, since the very first versions of NS4.0 do not recognize CCS-divisions. But I think, there is probably no installation of generic NS4.0 not updated left out there.) 2) Setting up the Script2.1) Resource SetupFor any animation images have to be preloaded and stored in an array. To access these in a structured way, we are using an associative array (using names rather than index numbers to identify an entry). The implementation of this is quite trivial: we're using the base of our naming scheme (omitting the '.gif') as indices and store them in an array 'pacimgs'. So 'pacimgs.r1' will hold the image object associated with the first right movement phase of our pacman character. Since we're using a quite structured naming scheme, we can build some of these names on the fly, while few others have to be enumerated extensively. We will trigger this at loading time
// pre-loading
function preLoad() {
...
}
// load only, if images are supported
if (document.images) preLoad();
The array 'pacimgs' is a global variable, since these resources have to be accessible all over the script. 2.2) Browser Abstraction / Cross-Browser AnimationThe other thing to do before we're going to script the game, is to form a connection between our HTML-elements and our script. Since this is highly browser depended, we're going to implement a cross-browser API abstracting these differences in a common front door. We are supporting any browser newer than Netscape 3, using JavaScript 1.2 or higher. These are basically 3 types of browsers:
Definitely any new browser coming up in the next few years will be of the DOM-type. In order to understand this approach (this is only one of others possible), we should understand that a JS-function is just another variable holding a bit of code. Declaring a function with a name just associates this bit of code with a variable name. Since in JavaScript passing a complex object from one variable to another just copies a reference to the object and not the object itself, we can pass a function's code from one variable to another without much overhead.
So we can define some GUI functions here and pass a reference to the according browser function to global variables abstracting any differences. The benefit of this approach is the absence of any conditions to be evaluated at run time. Besides: never use eval() since this will start a whole compilation-interpretation cycle. You should always be able to construct a reference to the object you want. (Dreamveaver uses eval() all the time, but this is just poor style in terms of efficiency.) Just keep in mind that a point-notation of any JS-object is equivalent to a named array reference (document.layers.someLayer == document['layers']['someLayer']).
// accessing JS-objects via associative array notation at run time:
var a = 'someLayer';
alert( document.layers.someLayer == document.layers[a] ); // "true"
We're defining the following global variables and pass references to them based on the browser in use: To make things easier, we're going to abstract any layer references and hold them in a global array 'divisions'. The array divisions holds references of these types:
divisions[div]=document.getElementById(div) // DOM
divisions[div]=document.all[div] // MSIE 4/5
divisions[div]=document.layers[div] // NS 4
(The array is used to not have to call document.getElementById(div) every time we access a layer/div. Also it is used to abstract some differences of MSIE and the DOM-API.) In order to do this, we can call our cross-browser-abstraction-set-up function only at runtime, since the entries of our 'divisions' array refer to HTML/CSS elements, and these have to be present at the time the function is called. Else they will just hold a null reference. (So we'll check this on every call for a new game. Another reason for this is that 'document.layers' in NS4 is not present for any external script called in the HEADer-section and would fail.) Since we're going to support as many browsers as possible, we're not going to identify them by some erratic navigator.userAgent sniffer, but on the presence of some top-level JS-Objects. In fact we did that earlier by checking 'document.images'. So all we need to know what features or API is supported is a set of well known top level objects:
document.getElementById -> DOM
document.all -> MSIE 4/5
document.layers -> NS 4
Our abstracted API will take the following arguments:
setSprite(lr,img,spr)
showLayer(lr)
hideLayer(lr)
moveLayer(lr,x,y)
where And we'll use a fifth GUI-function used to change any image just embodied in the page-body: So we're done. But there's another issue left: To do this we use a function that evaluates the x and y coordinates of the maze's origin and stores it in the global vars 'mazeX', 'mazeY'. (For example we could use the position of an image with known ID for DOM and MSIE and an ILAYER for NS4. Since we placed these elements just next to our maze, we can easily get the coordinates of the maze's origin.) The calculations used to get an element's position are not trivial and not covered here. We should connect this function to a window.onresize handler, because the origin of maze will change with any resize of the window. (As for window.Timeout and all other 'window'-methods, you can omit the 'window.' portion while in script context.) Now we have all resources together:
and are ready for our main task... 3) Programming the Game3.1) Defining the RulesFirst we should consider the characters behaviors and how the game play could be defined. We define the following rules
As we can see, there is much more to do for the ghosts, and the most definitions are about movements. Some of these rules are general features of Pac-Man, while others are specific
to our implementation. To be strict, we had to define some additional rules concerning the display .... In short we define:
In addition we stick with our naming convention for images:
pacman: d + p
d = {'r', 'l', 'f', 'b', 'x'} (direction code)
p = {1, 2, 3} (animation phase)
ghosts: 'g' + i + p | 'gx'
i = {1, 2, 3, 4, 'a', 'n'} (index/color code)
p = {1, 2} (animation phase)
tiles: 'tile'+n
n = {1 .. 19}
and the maze tile ids 'r'+row+'c'+col, where row = {1 .. 14} and col = {1 .. 20} 3.2) Basic LayoutBasically the game is a big loop, entered at the start of a new game and only
left when the game is over.
The later may need some explanation: So if we would write:
while (gameOn) {
// do something
}
and trigger a user input with a JavaScript handler, the handler will not be called until our 'while'-loop is ended. That's definitely not what we want. What could we do? We break up the loop in a single call that will fall back to idle after its completion and will be revoked later. This revocation can be done by a window.setTimeout call. So we'll write:
function doGame() {
// do something
if (gameOn) setTimeout('doGame()', 400);
}
In fact our construct will be somewhat more complex for the following reasons:
So this is the way to do it:
var pacTimer; // store the timer here
function doMove() {
// main function
// delete any second timer first
if (pacTimer) clearTimeout(pacTimer);
// store our entry time
var dateA = new Date();
// do something
// calculate execution time and final timeout delay
if (gameOn) {
var dateB=new Date;
mTO= dateA.getTime()-dateB.getTime();
mTO+=Math.round(aSpeed/aStep);
if (mTO<5) mTO=5; // minimal delay 5 msecs
pacTimer=setTimeout("doMove()",mTO);
}
}
In fact we'll go further and leave as many timeout gaps as possible to provide sensible user input at almost any time. Further we could pass the timeout-string to another function as parameter. p.e. here the second function has 2 endings, a normal calling the passed timeout-string, and another changing the flow of our 'loose loop'.
function someFunction() {
// ....
testCrash("doMoveF()");
}
function testCrash(tos) {
// evaluate any encounters
if (crash>0) {
// pacman dies
// call a specific function
}
else pacTimer= setTimeout(tos,1);
}
So what are the basic tasks to be performed:
As we can see there are possible alterations at the test for collisions of ghosts and the pacman, which occurs twice for every ghost, and another, if all food is eaten. Otherwise we just continue our main loop. Moving the ghosts is not just as simple. In fact, as we look to our rules above, we'll have to decide which kind of movement is needed out of the following:
3.3) DataSo what (global) data structures do we need?
The character based data is obviously best encapsulated in objects. One for the pacman and a ghost type object held in an array (in order to loop over the ghosts). We'll need:
for the ghosts:
Now we're ready for the "big thing": 3.4) Maze-Data: Layout and DirectionsSince this script was designed in the early days and JavaScript as well as computers were rather slow, it was decissivly important to save as much runtime as possible. Since this is not a bad habit, we are going a bit into details: First, it would be really bad, if any character moving would have to calculate a 'wish'-direction, then look up the maze map, recalculate again, if there was a wall and not a passage, and so on. So it would be nice to have some map encoding any possible direction for the exact position in a handy way. So we're coming up with two types of maze data to store:
In fact we could calculate the second from the first one, but this would use some extra time for the game to come up. So we have two sets of arrays for every level:
The layout map is quite trivial: We use any encoding (here alphabetic characters) referring to our border-tiles. Further a simple blank will refer to a normal passages, a 'p' to pills, and a 'x' to empty spaces (mainly the teleport passages and the pacman's start position). Any normal passage will be inhabited by a food (we'll have to count this at level set up). For the directions it might be wise to invest some more consideration. On a 2D surface (as our maze obviously is) there are 4 possible directions. So we could encode them using binary numbers as a 4-bit vector (one bit for every possible direction). Here we define (as powers of 2):
2 ** 0 => 1 ... right
2 ** 1 => 2 ... left
2 ** 3 => 4 ... up
2 ** 4 => 8 ... down
leaving 0 (zero) for a straight passage (no crossing). This enables us to access this information via bitwise operations (| = bitwise "or", & = bitwise "and"):
left, right, up => 1 | 2 | 4 = 7
left, right, up, down => 1 | 2 | 4 | 8 = 15
7 & 2 != 0 => yes, we can go right
7 & 8 == 0 => no way down here
Now we define an array 't1', a table holding the references between an arbitrary map code and its according bit-vector-value. (We're going to store a row's code data in a string of digits; see below.)
var t1= new Array();
t1[0]= 0;
t1[1]= 9; // rd (right and down)
t1[2]=10; // ld
t1[3]= 5; // ru
t1[4]= 6; // lu
t1[5]=13; // rdu
t1[6]=14; // ldu
t1[7]=11; // rld
t1[8]= 7; // rlu
t1[9]=15; // rlud
Now we can store the maze directions in a handy manner, so we can edit them manually. Any single digit represents a point on our grid. We'll have to decode this map to the 't1'-values at the beginning of each level.
mazeGrid[0]= new Array(
"00000000000000000000", // 1st row
"01000205000060100020", // 2nd row
"00000506000050600000", // ...
"05070605000060507060",
"00000000000000000000",
"00000000000000000000",
"06030600000000504050",
"00000000000000000000",
"03700908700780900740",
"00000000000000000000",
"01820001800820001820",
"00000000000000000000",
"03080809000090808040",
"00000000000000000000" // last row
);
So a '1' will indicate a corner with connections on the right and down way (t1[1] == 9 == 1 | 8). Exploring our bit-vector approach further, we find that we could store results of common calculation in arrays just to safe runtime calculations – especially for the ghosts' movements. So we define some arrays storing information of this type using our bit-vector grand design:
var tx= new Array();
var ty= new Array();
tx[0]= 0; ty[0]= 0; // no movement
tx[1]= 1; ty[1]= 0; // right
tx[2]=-1; ty[2]= 0; // left
tx[4]= 0; ty[4]=-1; // up
tx[8]= 0; ty[8]= 1; // down
var t2 = new Array();
t2[1]= [1];
t2[2]= [2];
t2[4]= [4];
t2[8]= [8];
t2[3]= [1, 2];
t2[9]= [1, 8];
t2[10]=[2, 8];
t2[12]=[4, 8];
t2[5]= [1, 4];
t2[6]= [2, 4];
t2[7]= [1, 2, 4];
t2[11]=[1, 2, 8];
t2[13]=[1, 4, 8];
t2[14]=[2, 4, 8];
t2[15]=[1, 2, 4, 8];
var t3 = new Array();
t3[0]=0; t3[1]=2; t3[2]=1; t3[4]=8; t3[8]=4;
'tx' and 'ty' store the delta x and delta y information associated with our
bit-vector definition. We'll need these for movement. Now we know that a
character with direction value d==2 will have a dx value of -1 and a dy value
of 0. (In effect it's for these definitions that our bit-vector-values get some semantical meaning.)
We can simply access this by
dx=tx[d];
dy=ty[d];
No calculations here, just variable-look-ups! The complex array 't2' encodes possible movement directions for ghosts: The first index indicates the crossing-code, the second index encodes each possible direction. In mathematical terms 't2' just enumerates the binary atoms of any 4 bit digit. Now we can simply calculate a random movement for a ghost: Given a ghost is positioned at a crossing holding the direction-vector 'k', we know that there are t2[k].length possible directions. So with just one random number 'n' we know our new direction:
d = t2[k][n]
or in detail:
n = Math.floor(Math.random() * t2[k].length);
d = t2[k][n]
or short:
d = t2[k][Math.floor(Math.random() * t2[k].length)]
Just one line of code for this! For strategic movement we'll have to calculate the offset to the pacman and
encode our best move's direction. (If the pacman is above and right, we would
want to move either up or right, giving 1 | 4 == 5)
// bd: best direction, cd: crossing's directions
d = bd & cd;
if (d==0) {
// no way in our direction here
// move randomly
}
So if bd == 5 and cd == 13, d == 4 meaning we're going up.
d = bd & cd;
if (d>0) {
// get random direction out of possible directions
d = t2[d][Math.floor(Math.random() * t2[d].length)];
}
else {
// no way in our direction bd here
// get random direction for this crossing
d = t2[cd][Math.floor(Math.random() * t2[cd].length)];
}
In an actual script we would put our random-formula in a function so we're left with:
function getRandomDir(k) {
return t2[k][Math.floor(Math.random() * t2[k].length)];
}
d = bd & cd;
if (d>0) {
d = getRandomDir(d);
}
else {
d = getRandomDir(cd);
}
or shorter:
d = bd & cd;
d = (d>0)? getRandomDir(d) : getRandomDir(cd);
Nice, isn't it? The array 't3' stores opposite directions. So for d==4 => t3[d]==8. We'll need
this to reverse movements. Just a word on rule 7:How could it be done simply to not reverse a ghost's movement in a random choice?
md = cd & (15^t3[d]);
with 'md' being the resulting vector of movements, 'cd' being the current crossing's value, and 't3[d]' being the opposite of the current direction. (Since our assignment of bits to encode a direction was just arbitrary, we can't access the opposites via bitwise operation.) The operation "c = a & (15^b)" is about masking a 4 bit binary digit. We ex-or 15 (binary 1111) on the direction 'b' and perform a binary <and> on 'a'. So we just cleared those bits that are set in 'b'. Now we can use 'md' to get any direction encoded in 'cd' but that in 'd':
d = getRandomDir(md);
That's all. 3.5) Moving AroundNow we're just implementing the stuff necessary for a pacman character to roam the maze. (So we do not implement ghosts or any food.) We take for granted, that the layout is being displayed some way and that our crossing-encodings are stored in the 2D-array 'f2' representing a 20 x 14 grid in rows and columns (f2[1..20][1..14]). For this purpose we're mainly interested in the tile's positions (or grid points). We'll just hop from tile to tile and fix the intermediate steps via offsets.
// moving a pacman through the maze
// (c) N. Landsteiner 1997
// object constructors
function Pacman() {
this.r= 0; // row
this.c= 0; // col
this.p= 0; // animation phase
this.pn= 0; // next delta for p (+1 or -1)
this.dir= 0; // the directions we could go
this.md= 0; // the current moving direction
this.dx= 0; // delta value for x-movement
this.dy= 0; // delta value for y-movement
this.osx=0; // x-offset for smooth animation
this.osy=0; // y-offset for smooth animation
}
// global vars
var pac= new PacMan(); // our instance of Pacman
var aSpeed=400; // the cycle delay (from tile to tile) in msecs
var aStep=4; // 4 intermediate steps in both directions for
smooth animation
var aSpan= new Array(); // we'll store animation offsets in pixels here
var movedir; // stores the current user input
var mazeX= 0; // maze's origin on the page in px
var mazeY= 0;
var pacTimer; // timer stored here
var gameOn=flase; // boolean flag: game on?
var runThru=false; // boolean flag: pacman is moving?
var f2=new Array(); // array holding our maze grid information
var pacStr= new Array(); // used for display tasks
// associates possible direction codes
// with chars to compose image-names
pacStr[1]='r'; pacStr[2]='l';
pacStr[4]='b'; pacStr[8]='f';
pacStr[0]='f';
// vector-code : dx/dy reference
var tx= new Array();
var ty= new Array();
tx[0]=0; ty[0]=0;
tx[1]=1; ty[1]=0; //r
tx[2]=-1; ty[2]=0; //l
tx[4]=0; ty[4]=-1; //u
tx[8]=0; ty[8]=1; //d
// *** things not defined here
function moveLayer(lr, x, y) {
// move a layer to a given position
}
function setSprite(lr, img, s) {
// exchange the image img of layer lr to src of s
}
function buildMaze() {
// parse maze date
// display the maze
// and put direction data into 2D-array f2
}
// *** sorry (we want to keep this short)
// set up (must be called on start up)
function setSpan() {
// a function to calculate our offsets
// our tile width is 27px
// offsets will be stored in array aSpan for any value of osx or osy
// using negative indices is JavaScript 1.2 or higher
for (n=1-aStep; n<aStep; n++) {
if (n==0) aSpan[0]=0
else aSpan[n]=Math.round(n*27/aStep);
}
}
// (re)set pacman to home position
function pHome() {
movedir=0; // reset any user input
// reset the pacman
with (pac) {
r=9; c=10; // start position: row 9, col 10
osx=0; osy=0; // offsets for x and y values to zero
md=0; // not moving anywhere
dir= 3; // the directions we can move (left or right)
dx=0; dy=0; // dx and dy are set to zero
pn=1; p=1; // reset animation values
setPac(r,c,'r1'); // display the pacman
}
}
// display function
function setPac(r,c,s) {
// displays the pacman with offsets and given image-source
// unfortunatly we started our grid at origin [1,1],
// so we have to substract 1 from r and c
// rows and cols are multiplied by tile width 27px
moveLayer(
'pacLr',
mazeX+27*(c-1)+aSpan[pac.osx],
mazeY+27*(r-1)+aSpan[pac.osy]
);
setSprite('pacLr','pac_i',s);
}
// start here
function newGame() {
// leave, if we are running already
if (gameOn) return;
// set up the maze
buildMaze();
// initiate the pacman
pHome();
runThru=false;
gameOn=true;
// enter main loop
doMove();
}
function move(x) {
// store current user input in a global var
// triggered by some javascript-handler
movedir=x;
}
function doMove() {
if (pacTimer) clearTimeout(pacTimer); // clear any duplicate timer
var dateA=new Date(); // store entry time
with (pac) {
// "with": in this block look up properties of pac first
// only if the offset is zero we're exactly over a tile.
// any new directions of the pacman have to be evaluated
if (osx+osy==0) pMove();
// in case we're moving, we have to adjust our offset values
// and display our new position
if (runThru) {
// add delta values to our x and y offsets
osx+=dx;
osy+=dy;
// in case we're going out of bounds, reset any offsets
// to be prepared for teleporting (moving from side to side)
if ((c+dx)%21==0) osx=0;
if ((r+dy)%15==0) osy=0;
// limit our offsets to aStep
osx%=aStep;
osy%=aStep;
// if offsets are zero, increment r, c
// and handle any teleporting as well -> trunkBy(value, limit)
if (osx==0) c=trunkBy(c+dx,20);
if (osy==0) r=trunkBy(r+dy,14);
// set phase pac.p to next step
p+=pn;
// if phase pac.p is either 3 or 1 reverse the direction
// so we are going 1, 2, 3, 2, 1 ...
if (p==3) pn=-1;
if (p==1) pn=1;
// if we are going up, just display our only backside image,
// else compose the string for the correct movement phase.
// pacStr associates pac.md with the chars 'r', 'l', 'f'
if (md==4) setPac(r,c,'b1')
else setPac(r,c,pacStr[md]+p);
// in case we're placed on the center of a tile
// (both offsets are zero) and we are at a crossing
// (f2[r][c] != 0), read the crossing's information
// and store it in pac.dir for later use
// so we take with us the information of the last
// crossing passed
if ((osx+osy==0) && (f2[r][c])) dir=f2[r][c];
}
}
// if the game is still on, calculate execution time
// and substract it from our standard delay aSpeed/aStep
// (game speed should not depend on animation step settings)
if (gameOn) {
var dateB=new Date();
var mTO= dateA.getTime()-dateB.getTime();
mTO+=Math.round(aSpeed/aStep);
if (mTO<5) mTO=5; // minimum delay 5 msecs
// set up the timout and store a reference in pacTimer
pacTimer= setTimeout("doMove()",mTO);
}
}
// getting a new direction
function pMove() {
with (pac) {
// evaluate the direction to go
// pac.dir holds the current crossing's information
// (current crossing: last grid code stored in pac.dir)
// let's see, if there is a passage in the direction
// of the last user input. if so, store it in pac.md
// for we do not clear movedir, the last input will be
// re-evaluated at the next grid point. This enables the
// user to stear ahead without further input.
if (dir&movedir) md= dir&movedir
else {
// no valid user input, so reuse our current
// direction and mask it with the current crossing
// (just binary and)
md&=dir;
// no direction left, so we're stuck agains a wall
// stop the animation
if (md==0) runThru=false;
}
// in case we are now moving
if (md) {
// yes we're moving (just in case we were stuck earlier)
runThru=true;
// intermediatly store any x and y values of our new direction
// (don't waste another var here)
dx=(md&3);
dy=(md&12);
// if there is a dx value
if (dx) {
// if we came this way, it must be legal to reverse later.
// just store that horizontal movement is possible
dir=3;
// look up our current dx in tx
dx=tx[dx];
};
if (dy) {
// just as above with vertical and dy
dir=12;
dy=ty[dy];
}
}
// whow, everything done here.
// if not for intermediate offset calculations and
// teleporting, this would be all we need.
}
}
function trunkBy(v,m) {
// evaluate any teleportation
// resulting value v: 0 > v < m
// so with m==20 => (v>=1) && (v<=19)
// that's why we startet our grid at [1,1]
v%=m;
if (v==0) v=m;
return v;
}
// end of roaming script
To complete this basic script to a full featured game we have to add the following features
Examples: Moving Ghosts by Table Lookups (Compare the descriptions given in 3.4) Maze-Data: Layout and Directions.) The following code snipplets were inserted in 05 2009 to exemplify algorithms presented earlier. (It just seemed more suitable to go into detail here, as we refer to this logic in the excursions on the original game's A.I. below.) Moving a ghost by random (where k is is a bit-vector of directions):
// a simple constructor for our ghost
function Ghost() {
this.r=0;
this.c=0;
this.d=0;
this.dx=0;
this.dy=0;
}
var ghost = new Ghost();
...
// get directions for a ghost's position
var k = f2[ghost.r][ghost.c];
if (k) {
// we are at a junction or crossing, select a new direction to go:
// exclude the direction opposite to the movement (don't turn)
k &= (15^t3[ghost.d]);
// and set the ghost's direction to a random choice from this bit-vector
ghost.d = getRandomDir(k);
// done.
// just store values of delta x, delta y for this direction
ghost.dx = tx[ghost.d];
ghost.dy = ty[ghost.d];
}
...
// a function to select a random choice from a bit-vector (c.f.: 3.4):
function getRandomDir(k) {
return t2[k][Math.floor(Math.random() * t2[k].length)];
}
Moving a ghost towards a target position:
...
// get directions, if at a crossing
// exclude opposite to movement and get closer to pacman
var k = f2[ghost.r][ghost.c];
if (k) {
k &= (15^t3[ghost.d]);
ghostMove2Target(ghost, k, pac.r, pac.c);
...
}
...
function ghostMove2Target(ghost, k, tr, tc) {
// get distances to target
var dx = ghost.c-tc;
var dy = ghost.r-tr;
// compile a bit-vector of directions
// that bring us closer to the target
var v = 0;
if (dx!=0) v = (dx>0)? 1:2;
if (dy!=0) v |= (dy>0)? 8:4;
// multiply it with possible directions (AND k)
v &= k;
// if there is an intersecting range of directions from v and k,
// get one of them, else select a random choice from all possible
// directions
ghost.d = (v)? getRandomDir(v) : getRandomDir(k);
}
Note: Putting ghost movements together:
// basic ghost movements
// based on script (c) N. Landsteiner 1997
/*
does not implement in-cage and at-doorstep modes,
sorry - we want to keep it short!
*/
// ghost constructor
function Ghost() {
this.r=0;
this.c=0;
this.d=0;
this.dx=0;
this.dy=0;
this.osx=0;
this.osy=0;
this.p=1;
// state: 0 = in cage, 1 = doorstep, 2 = cruise, 3 = homebound
this.s=2;
}
var g = new Array();
for (var i=1; i<=4; i++) g[i] = new Ghost();
// a flag for panic mode (pacman eats a power pill)
var panicmode = false;
// a phase flag for panic mode
var skipCycle = false;
// a counter for panic mode
var panicCnt = 0;
// duration of panic mode in tiles to move
var panicDuration = 12;
// ghost home target
var gHome_r = 9;
var gHome_c = 10;
// the higher this value (0..1), the smarter the ghosts
// (adjust this per level and/or for individual ghosts)
var ghostAITreshold = 0.5;
function ghostLoop() {
// main loop for all ghost related tasks
if (panicmode) {
if (--panicCnt==0) {
// panic mode is over, reset it
setPanicMode(false);
}
else {
// prepare to skip every 2nd cycle in panic mode => half speed
skipCycle = !skipCycle;
}
}
for (var i=1; i<=4; i++) {
var ghost = g[i];
// move the ghost
ghostMove(ghost);
// animate it (we ignore the "neutralizing" phase here)
if (ghost.s == 3) {
// display eyes with direction (e.g.: 'ge4.gif')
setGhost(i, 'ge'+ghost.d);
}
else {
var m = (panicmode)? 'a' : i;
var s = 'g'+m+ghost.p;
setGhost(i, s);
}
}
}
function ghostMove(ghost) {
with (ghost) {
// advance the animation phase
p = (p==2)? 1:2;
// skip every 2nd cycle in cruise mode and panic mode
if (skipCycle && (s==2)) return;
if (osx+osy==0) {
// just moved a whole tile
if ((s==3) && (r==gHome_r) && (c==gHome_c)) {
// homebound and home => change state to in-cage-mode
// (not implemented here)
s = 0;
return;
}
var k = f2[r][c];
if (k) {
// at a crossing, get new direction ...
k &= (15^t3[d]);
if (s==3) {
// homebound, move to home target
ghostMove2Target(ghost, k, gHome_r, gHome_c, false);
}
else if (Math.random() < ghostAITreshold) {
ghostMove2Target(ghost, k, pac.r, pac.c, panicmode);
}
else {
d = getRandomDir(k);
}
dx = tx[d];
dy = ty[d];
}
}
// advance, check for ranges and teleports
if (dx) {
osx += dx;
osx %= aStep;
if (osx==0) c = trunkBy(c+dx,20);
}
else if (dy) {
osy += dy;
osy %= aStep;
if (osy==0) r = trunkBy(r+dy,14);
}
}
}
function ghostMove2Target(ghost, k, tr, tc, reverse) {
var dx = ghost.c-tc;
var dy = ghost.r-tr;
if (reverse) {
// revert (move away in panic mode)
dx = -dx;
dy = -dy;
}
var v = 0;
if (dx!=0) v = (dx>0)? 1:2;
if (dy!=0) v |= (dy>0)? 8:4;
v &= k;
ghost.d = (v)? getRandomDir(v) : getRandomDir(k);
}
function getRandomDir(k) {
return t2[k][Math.floor(Math.random() * t2[k].length)];
}
function setGhost(i, s) {
// move the ghost sprite and set the image accordingly
// cf.: "setPac()" above
var ghost = g[i];
var lr = 'gLr'+i;
moveLayer(
lr,
mazeX+27*(ghost.c-1)+aSpan[ghost.osx],
mazeY+27*(ghost.r-1)+aSpan[ghost.osy]
);
setSprite(lr, 'g_i'+i, s);
}
function setPanicMode(v) {
if (v) {
// enter panic mode
panicmode = true;
skipCycle = false;
panicCnt = panicDuration*aStep;
}
else {
// exit panic mode
panicmode = false;
skipCycle = false;
panicCnt = 0;
}
}
Now we're left with one last question: How could we track any collisions? For this purpose we decide to store the exact position in px of each character in the object properties 'posx' and 'posy'. So we do not need to recalculate them while comparing them. Now we can implement a function to detect any crashs between objects:
function isCollision(x1,y1,x2,y2, radius) {
return (Math.abs(x1-x2)+Math.abs(y1-y2)<radius);
}
if (isCollision(pac.posx,pac.posy, g[i].posx,g[i].posy, 25)) {
// pacman and ghost #i collide
}
Maybe you wonder, why we're not using some vector projection like:
c = Math.sqrt(a*a+b*b)
There are two reasons for this:
So for basic techniques, we're done here. With this you should be able to
3.6) Ghost Movements RevisitedPlease skip this section as it is definitely out of date and refer to the descriptions given in sect. 5 and sect. 6! The implementation of ghost movements as described above is mainly based on the need for quick runtime evaluation. The feature that impressed me most of the ghosts' behaviour in the original game, was that they seem to let you one single chance to escape, but come down on you when you miss it. The remodelling of this behaviour with as little resources as possible was the main design goal of "JavaScript-PacMan". Meanwhile I found some texts on the original Pacman AI (Artificial Intelligence), describing the ghosts behaviour as follows:
While this garantees an interesting and quite predictable gameplay, this approach has some drawbacks: First, for the first ghost, you have to design carefully an extensive path (movement pattern) per level. Second, the movement of the forth ghost can only be implemented by defining some key crossings (as entrances to loops) and by tracking the pacman's movement. So you could predict the key position the pacman will be likely to be next. But in order to do this, each level-layout has to tribute to these key positions, meaning that it has be modelled around these crossings, which will obviously limit the range of possible designs. On the other hand our approach - as given above - enables us to set our ghosts free in almost any maze of any design. This minimizes not only efforts of level design, we could even implement random levels using a maze generator. 4) Things to Complex to be Covered Here:
*** update *** 5) Ghost Movements Revisited (once more)Some years after writing this I found another, more accurate description of the original Pac-Man AI and the various "psychologies" or "personalities" of the ghosts:
These are the passages concerning the game's AI in full extend:
Playing the original game also reveals that the game does very much rely on a complex timing pattern:
5.1 More Thoughts on Ghost MovementsAs concerned with movement patterns and programming them, the text passages quoted above conclude to the following:
Getting in front of Pac-ManHow could we get Pinky in front of Pac-Man? Remember our array 't1' holding direction informations coded as bitvectors and our directions grid 'mazeGrid'? We could utilize both of them to build a (complex) table, holding the next crossing's position where Pac-Man should occur when taking a corner one director or the other. To illustrate this, here's an algorithmic layout:
It can be easily seen that most of the calculations can be done before the start of a level resulting in a 3D-table holding the target position for any direction of each row/col position of the 2D array 'mazeGrid'. (We would only calculate them for those grid positions with a value greater zero.) We could even refine this by storing only those positions as targets that end up at a crossing or junction with more than 2 open endings. (So we would treat a winding path as a single passage leading round a corner.) For this we could utilize the 'length' property of the individual sub-arrays of array 't2'. If 't2[d].length > 2', it's a valid target position, else we would go for the next one. We could employ this new movement pattern as another possibility to be selected by random for Clyde or Inky to separate their movements. And even more – to our great amazement this approach does also work with random mazes or mazes resulting from a maze-editor! (This approach is used as a part of the enhanced ghost's AI of "JavaScript-PacMan2" and "FlashPac II" both © N. Landsteiner.)
*** update *** 6) Original Ghost A.I. – The Final WordMeanwhile (2009) there is a definite documentaion of the original Pac-Man A.I.: The Pac-Man Dossier by Jamey Pittman. Have a look at this page for detailed information on the A.I. and timing of the original Pac-Man game! Here is a short description of the ghosts' movement algorithm as given in "The Pac-Man Dossiers": 6.1 The Target TileAs in our tutorial the original Pac-Man A.I. evaluates positions per tile, i.e.: Pac.Man and any of the ghost's inhabit always a specific tile, which attributes to their position as for the A.I., while intermediary positions are handled by offsets (4 steps to the next tile). As a ghost reaches the tile before the next junction or corner, the movement or turn to be executed when reaching the junction is evaluted by the determination of a target tile. (This may also be described as a one-tile-look-ahead.) The ghost will then try to reach this target tile by appling the following rules:
6.2 Ghost Personalities: Target Tile EvaluationEach ghost evalutes the target tile in a specific manner resulting in its individual "personality":
6.3 TimingPlease mind that the effect of this movement logic does heavily depend on the complex timing scheme of the original Pac-Man game, where Pac-Man and the ghosts move at different speeds with the additional effect of Pac-Man slowing down while munching food dots and speeding up while going around corners. (Blinky can catch up with the player while Pac-Man is munching dots, otherwise Pac-Man is in danger to pump into Pinky while moving on clear terrain. The only way to evade a tracking ghost is by taking corners frequently while munching along straight passages is prone to a sad ending. On the other hand a smart player might trick a ghost into a wrong direction by the clever use of look-aheads and target-tile mechanisms.) The following table provides an overview of the essential timing factors based on Pac-Man's top speed (= 100%):
"How To Write a Pacman Game in JavaScript" Norbert Landsteinerhttps://www.masswerk.at/ Vienna, 2004-07-18 Updated 2008-03-19 Updated 2009-05-23 This tutorial (c) N. Landsteiner 2004 Document location: <URL: https://www.masswerk.at/JavaPac/pacman-howto.html>
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||