Maze games and movement

[cdr]

I was wondering how games like pacman prevent the player from going through the maze walls. I was thinking a simple way was to keep track of the position of the player and when checking the joystick, see if the player is in a position that allows that motion. But that would be a ton of checking and would need to be different for each maze.

 

Thoughts?

 

Sorry if this is explained somewhere else – I was having a hard time finding anything like this in the forums or the Stella archives.

 

-Ben

[Robert M]

You have pretty much nailed the technique down. You keep track of the player's position and compare it to data describing the maze in ROM, and restrict the player accordingly. Its not much work really if you set the maze data up correctly.

[Nukey Shay]

The maze area is usually divided up into matrix zones called cells (basically, wherever a possible north/south-east/west intersection exists)...and all of these cells in this matrix have a single bit that is on or off depending on if movement is allowed in that direction. Then this cell value is just AND-ed to the current direction that the sprite is trying to move.

 

The current direction value could be just the value of the joystick value pulled from SWCHA - where a bit would be turned on or off in the right/left/down/up pattern (the bitpattern in SWCHA corresponds to the direction pressed for each joystick...the high nybble is for the left joystick, and the low nybble is for the right joystick. So a value of %01111001 coming from SWCHA would indicate that the left joystick is being pressed to the right, and the right joystick is being pressed left+down).

In this example, the upper left corner in a Pacman game could have a cell value of %01010101 (you can move right, so a zero is placed in the high bit. You can't move left, so a 1 is placed in the next bit. And so on.) Then all you need to do is take SWCHA and AND it to the cell value.

 

LDA SWCHA

AND position,Y

 

...and then each bit is checked to see if the player is trying to move in that direction. If the test for that bit results in a zero, movement is allowed.

[Cybergoth]

Hi there!

 

You have pretty much nailed the technique down.  You keep track of the player's position and compare it to data describing the maze in ROM, and restrict the player accordingly.   Its not much work really if you set the maze data up correctly.

 

Hm... is that why in most Pac Games you can change your direction only on crossings? So it requires only a "grid" check, instead of actual screen coords?

 

Greetings,

Manuel

[Nukey Shay]

Yep. The current Pac position (the value of Y above) could be just the vertical coordinate divided by ~N (scanlines) plus the horizontal coordinate divided by ~N (pixels).

[cdr]

Thanks for the info!

 

What is N in your example?

 

Also, wouldn't being 10 over and 20 down give me the same cell as being 20 over and 10 down?

 

I am a little confused (which is obvious), but in your pacman example, I see what you mean about being in the upper left hand corner (can move down and right), but if you are one pixel below that, you can move up and down (not right). What cell are you in there? Are there as many cells as there are positions on the screen?

 

Thanks again!

-Ben

[Nukey Shay]

Think of a grid pattern...where each line of the grid is in the center of the "hallways"...extending border to border even through the onscreen walls at equal intervals. ~N is the number of scanlines or pixels between each imaginary line.

Actually, in a maze like Pacman's, you can just reuse the same maze info for the right portion of the screen by EORing the left/right bits.

But anyway, the imaginary grid pattern shows where the lines meet...at 8 points in each half of the screen. With reusing the data, that works out to 8 cells for each row (intersection = 1 cell)...spaced 16 pixels apart. 16 is a good number, because it's easily worked with in binary math (if you want to divide by 16...just LSRx4).

The rows are also 16 scanlines apart vertically in this example.

So, the formula here would be:

H=horizontal position

V=vertical position

Y=cell number

 

( V/8 ) + ( H/16 ) = Y

 

Then you'd use Y as an index to get the maze info for that cell from a matrix in rom...

LDA CellMatrix,Y

 

The subroutine would also need handle EORing the left/right bits when X/16 > 7 (that would indicate that the player is positioned in the right half of the screen).

[Nukey Shay]

BTW if you were 1 pixel away from an intersection, you could just exit the routine and use whatever previous data you had No point in looking up a new one if a cell number change isn't possible anyway. Something like:

LDA VerticalLocation

AND #$0F

BNE .exit ;skip if not divisible by 16 (scanlines)

LDA HorizontalLocation

AND #$0F

BNE .exit ;skip if not divisible by 16 (pixels)

[Robert M]

So, the formula here would be:

H=horizontal position

V=vertical position

Y=cell number

 

( V/8 ) + ( H/16 ) = Y

 

just one minor correction to Nukey's formula:

 

Y = (V / CELL_HEIGHT)*NUM_COLUMNS + (H / CELL_WIDTH)

 

I made the cell sizes generic rather than fixed values just to show that they can be any integer you wish. For Nukey's example:

 

CELL_HEIGHT = 8

CELL_WIDTH = 16

[Robert M]

BTW if you were 1 pixel away from an intersection, you could just exit the routine and use whatever previous data you had  No point in looking up a new one if a cell number change isn't possible anyway.  Something like:

LDA VerticalLocation

AND #$0F

BNE .exit ;skip if not divisible by 16 (scanlines)

LDA HorizontalLocation

AND #$0F

BNE .exit ;skip if not divisible by 16 (pixels)

 

Just another minor correction to Nukey's idea. You need to do a little more then just reuse the movement restrictor for the last intersection until you reach a new one. If you do that, then the player will be able to exit an intersection and turn before reaching the next intersection in a valid direction for the last intersection that outside the intersection is no longer valid. Hence, the player can pass through walls.

 

Instead, you need to build and maintain a movement restrictor for the passageway the player is in. If the player is at an intersection, then use that movement restrictor instead. But, as soon as the player leaves an intersection you must construct and save a movement restrictor for the passageway. To construct the restrictor is easy. It is just the direction the player left the intersection plus the opposite direction. While the player is between intersectionws the passageway restrictor applies.

[Nukey Shay]

Yup...that's what I was trying to explain by mentioning "previous data"...but you did it better Many maze games allow the sprites to continue moving even after the stick is no longer being pressed...so it wouldn't burn any more ram than what they are already using to store the current direction.

The only time you'd be looking at the matrix table to find valid new directions is when the object is at an intersection.

[+johnnywc]

Hello all,

 

I working on a rewrite of Wizard of Wor (mostly to teach myself 2600 programming and to get rid of that horrible flicker). I've implemented the maze and I'm thinking of how I am going the logic for maze movement. Here was my basic idea (taken from this thread):

 

for each monster each frame:

 

- compute the cell (x, y) that the monster is in. the wizard of wor maze is 11 x 6 cells; each cell is 20x12. (16x8 open, 4x4 walls surrounding it)

- while computing the cell, determine if the monster is at an intersection (x%20 = 0, y%12=0)

- if the monster is at an intersection, choose a random direction to go based on the valid moves. valid moves stored in a lookup table (66 bytes), much like Nukey Shay described (mimic the up/down/left/right bit pattern of SWCHA/B)

 

Edit: I will only need 33 bytes since the mazes are symmetric and I can use the EOR trick described by Nukey...

 

for the players, use a similar approach, except you need to allow the user to turn around when not at an intersection.

 

Does this sound feasible? Is there a quick way to divide by 20 and 12? I know I can divide by 8 first and use a lookup table, but this will only give me the cell. I need to know if there is an intersection. Of course, I could do division by subtraction, but I'm worried this will take too long (but it will give me both cell and yes/no for the intersection).

 

Any ideas are greatly appreciated.

 

Thanks,

Edited September 10, 2005 by johnnywc

[supercat]

Instead, you need to build and maintain a movement restrictor for the passageway the player is in.

807294[/snapback]

 

Either that or just don't check the joystick until the player reaches the next intersection.

[Jacob Rose]

Either that or just don't check the joystick until the player reaches the next intersection.

928643[/snapback]

 

But then you can't turn around...