Jump to content
  • entries
    16
  • comments
    181
  • views
    35,236

Difficulties with Frenzy's Maze

Sign in to follow this  
PacManPlus

1,179 views

Ugh.

 

I've been having a hell of a time with Frenzy/Berzerk's maze collision detection for the past week. I'm actually stumped for the time being.

This detection is different than the others I've worked on because it's not *just* the maze piece if it's there or not, but it also matters *where* the player hits the maze piece. To make matters worse, the zones are 8 scanlines high, and the sprites can be 16 scanlines high. This means that any sprite can occupy up to 3 zones at one time.

 

To give you a better example, Here is the screen with a grid to show how I split it up (I tried to find the best way, and this was it):

blogentry-1787-126266138671_thumb.png

 

I had to reduce this by 2 zones, to get 23 zones high + 1 for the score zone. There are also 32 columns (the max). You will notice that the maze is on the left and bottom of each cell. I cannot center them as that will split the 'bubbles' in half, making for too many maze cell variations.

This means that the player *can* occupy the top right of each maze cell without issue. Plus, I have the entire height of the sprite to worry about. I chose three points (for the three zones a sprite could potentially occupy) on the left side or right side of the sprite: top (0), bottom/2 and bottom. The 'bottom' varies, as all of the sprites are top justified, and the objects themselves are different heights (i.e. player, robot, skeleton, etc.) Plus I have to check the top or bottom (depending of which direction the player is moving).

 

I'm just having a very difficult time coming up with an algorithm for this.

 

I imagine in the arcade some type screen buffer is used, so that if the sprite hits any 'non-black' area, a collision is registered. Wish I could do that here...

 

I'm open to ideas...

 

These are how I have the maze peices in my character mode:

blogentry-1787-126266100864_thumb.png

Sign in to follow this  


12 Comments


Recommended Comments

Because nearly every tile occupies the bottom left corner, you only need to check whether the bounding box of the sprite intersects with those coordinates. You don't need pixel perfect.

 

For SpaceWar!7800 I actually AND'd the sprite graphics together to check collisions. Fortunately, there aren't that many sprites to test.

Share this comment


Link to comment

I can't help with the problem, but WOW what an awesome game to port to the 7800!! :thumbsup:

Share this comment


Link to comment

Because nearly every tile occupies the bottom left corner, you only need to check whether the bounding box of the sprite intersects with those coordinates. You don't need pixel perfect.

 

Nah! I can see it being done with tables, compares and special ordering of the indirect characters used in the map.

Share this comment


Link to comment

@EricBall - Thanks for the info, but remember there are other things to consider (like if the *middle* of the sprite runs into a horizontal maze wall (or one with two 'bubbles' horizontally)... things like that.

 

@SpiceWare & Moycon - Thanks!... but I'm not even close to having something playable yet :thumbsup:

 

@GroovyBee - I actually *have* special ordering of the indirect characters already (it took me a while to get this order) ;) You will see - moving from $80-$87 you have vertical, horizontal, vertical, horizontal, followed by 4 'L' shaped characters. The pattern then repeats, until $C0 where all of the extraneous maze pieces are. This way I can AND the character with $0F (after checking for a negative number so I know I hit a maze) and just check for $00/$02, $01/$03, and $04 or greater. The $C0 chars and above are special cases. Although I see that if I put the two vertical pieces as $00 and $01, and the two horizontal pieces as $02 and $03, I can AND the character with $0E and just check for $00, $02, and $04 (BPL).

 

I was thinking of tables for the shots, depending on where they are hit, which character replaces the one that the shot collides with. Not sure how tables would help with this type of collision, though.

 

BTW, I am doing this in 320A mode, with 16 High (max) sprites.

 

Thanks,

Bob

Share this comment


Link to comment

Hi Bob

Wow,this look really cool.Cannot wait to see a playable version.

greetings Walter

Share this comment


Link to comment

Hmm... thinking a little more about this. Assuming x,y=0,0 is the bottom left.

53 of the tiles are based on the bottom left corner. So test and see if those pixels overlap the bounding box of the sprite.

if (sprite.ymax < grid.y) and (sprite.ymin > grid.y+4) and (sprite.xmax < grid.x) and (sprite.xmin > grid.x+4) then collision

Okay. Next set up your tile numbering so the 2 LSBs indicate whether the horizontal or vertical pixels are used.

if (grid.type & vertical) and (sprite.ymax < grid.y) and (sprite.ymin > grid.y+ and (sprite.xmax < grid.x) and (sprite.xmin > grid.x+4) then collision
if (grid.type & horizontal) and (sprite.ymax < grid.y) and (sprite.ymin > grid.y+4) and (sprite.xmax < grid.x) and (sprite.xmin > grid.x+ then collision

Now, you may need to fudge the bounding boxes slightly, but that's the best start.

Share this comment


Link to comment

Thanks, Eric, GroovyBee - and everyone else for the compliments :)Actually, I found the source code to the arcade game on line. So, I'm trying to see how much of it (if any) I can apply to the 7800 version. The only problem is, there are many things about z80 code I don't follow.Below is the 'IQ' module, which is the module for wall detection. Knowing that the 7800 does things *very* differently than the screen buffer of the arcade, I'm still trying to see if I can apply anything to this port:

.title	"WALL DETECTER AND AVOIDANCE CONTROL".sbttl	"FRENZY".ident IQ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;	Intelligence;_______________________________.insert EQUS; DURL refered to thru out this program stands for; Down,Up,Right,Left bits in directions and wall encoding.DOWN	==	3UP	==	2RIGHT	==	1LEFT	==	0;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;  Check walls and avoid them;_______________________________;a=new DURL, c=old DURL, ix->vector, iy->mansIQ::	push	b		;save tracker	push	d	mov	l,D.P.L(x)	;get height thru	mov	h,D.P.H(x)	;pattern pointer	mov	e,m	inx	h	mov	d,m	xchg	mov	d,a		;save DURL		inx	h		;skip x bytes	mov	a,m		;y lines (height)	mov	c,a		;for down test	srlr	a		;h/2	adi	1		;(h/2)+2	mov	e,a		;number of lines to test	mov	h,P.Y(x)	;get current position	mov	l,P.X(x); Regs: HL=YXpos, E=height, c=DURL to test; Down tests	bit	DOWN,d	jz	..TU	push	h	mov	a,c		;height of pattern	adi	3		;margin of error	add	h		;offset to look	mov	h,a		;at for wall color	push	d	mvi	e,5	call	testx		;check for white below	pop	d	pop	h	jz	..TR		;if ok check right,left	res	DOWN,d		;else forget that direction	jmp	..TR;up tests..TU:	bit	UP,d	jz	..TR	push	h	mvi	a,-3	add	h	mov	h,a	push	d	mvi	e,5	call	testx	pop	d	pop	h	jz	..TR	res	UP,d;	jmp	..TR;right tests..TR:	bit	RIGHT,d	jz	..TL	push	h	mvi	a,11	add	l	mov	l,a	push	d	call	testy	pop	d	pop	h	jz	..done	res	RIGHT,d	jmp	..done;left tests..TL:	bit	LEFT,d	jz	..done	push	h	mvi	a,-3	add	l	mov	l,a	push	d	call	testy	pop	d	pop	h	jz	..done	res	LEFT,d;	jmp	..done..done:	mov	a,d		;final result DURL	pop	d	pop	b	ret;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;	Test in X direction;_______________________________; input: h=Y, l=X, c=DURL; output: Z if robot color in that boxTestx:	dcr	l		;test -1 line	inr	e..x:	call	CheckBox	rnz	exaf			;save test results	mov	a,l		;get x	adi	2		;add 2	mov	l,a	exaf			;now return test results	dcr	e		;number of times to look	jnz	..x	ret			;returns Z;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;	Test in Y direction;_______________________________; input: h=Y, l=X, c=DURL; output: Z if robot color in that boxTesty:	dcr	h	inr	e..y:	call	CheckBox	rnz	exaf			;save test results	mov	a,h		;get Y	adi	2		;add 2	mov	h,a	exaf			;now return test results	dcr	e		;number of times to look	jnz	..y	ret			;returns Z;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~; Check pixel for use;_______________________________CheckBox:	push	h		;save YX	call	RtoAx#		;in hl out hl,a	ani	0fh		;save shift&flop	bit	Flop,a	jz	..fl	xri	0Fh		;flip flop and shift..fl:	xri	07h		;reverse shift	di			;using magic	out	MAGIC	res	5,h		;convert magic->normal addr	mov	a,m		;get normal screen	sta	TEMP+(1<13)	;magic scratch	ei	lda	TEMP		;normal scratch	ani	1		;check it	pop	h		;restore YX	ret;---------------+; get durl bits |;---------------+; input: h=x l=y; output: a=durl bits for room xy is in; used by man,robot to check for others in squareWallIndex::	mov	a,l		;get y position	sui	8		;edge of first room	mvi	e,0	cpi	48		;1st row	jrc	..sk	mvi	e,6		;2nd row	cpi	48*2	jrc	..sk	mvi	e,6*2		;3rd row	cpi	48*3	jrc	..sk	mvi	e,6*3		;4th row..sk:	mov	a,h		;x pos	sui	8		;edge of first room	dcr	e..xlp:	sui	40		;room x width	inr	e	jrnc	..xlp	xchg	lxi	b,WALLS		;->walls array	mvi	H,0		;add index	dad	b	mov	a,m		;get durl for room	xchg	ret	.end

For instance, the 'WallIndex' function - WTF is 'sui'? I get 'push' and 'pop' have to so with the stack (like PHA and PLA in 6802) 'mov' I also get, but some of it (lxi?) is really confusing me. I'll have to check some on-line resources of Z80 assembler. In the meantime, can anyone give me a nutshell version of what this is doing? The comments help, but they stop just short of aiding me in understanding what is going on.

Share this comment


Link to comment

Thanks again, Eric :thumbsup:

I will be looking more at the code for the arcade version of Frenzy as I get more into the game logic.

 

I forgot to post this this morning:

 

Regarding the maze collision detection, *I GOT IT!*

 

I arranged the maze pieces like this:

$80-$8F = full horizontal width section

$90-$AF = "L" shaped sections

$B0-$BF = full vertical height sections

$C0-$CF = lower-left corner sections only

$D0-$DF = upper-left corner sections only

$E0-$EF = lower-right corner sections only

$F0-$FF = full character (like the power plant sections)

 

I then stripped the high bit and lower nybble, and shifted right twice. This leaves the two lower bits open for X and Y position within the character.

 

I shifted the X coordinate and the Y coordinate of the sprite within the maze cell character until I got it down to quarters:

It looks like this:

 

00 | 10
---+---
01 | 11

 

So if a certain point of the sprite occupies the top-right corner, it will be the "10" value.

 

That value got added in to the character cell above, and then it was just a table lookup for a $01 or $00 to see if it was valid or not.

 

For the X positioning, I had to look at every third raster, otherwise there were some spots where the player could move horizontally through a horizontal maze edge. The same applies to vertical checking.

I think I sill be ok, CPU Clock-Wise, as it looks like Frenzy/Berzerk only moves one robot per frame (that's why they start out slow and get faster as more are killed).

 

Here is the code (it works!) Please let me know what you think, and if you think it could be made more efficient:

 

;  OBJECTPF - CHECK FOR OBJECT/PLAYFIELD COLLISION (ONLY APPLIES TO PLAYER / ROBOTS) SHOTS AND EVIL OTTO HAVE THEIR OWN
;  INPUT: X - OBJECT NUMBER, MXLIST - X OFFSET TO MOVE, MYLIST - Y OFFSET TO MOVE
;  OUTPUT: UPDATED MXLIST, MYLIST, A=0 OK TO MOVE IN DESIRED DIRECTION, A>0 NOT OK TO MOVE IN DESIRED DIRECTION
;  USES: A, Y, TEMP0, TEMP1, (TEMP2, TEMP3 USED IN GETCHAR), TEMP4, TEMP5, TEMP6, TEMP7, TEMP8, TEMP9, TEMP10, TEMP11, TEMP15
OBJECTPF
         LDA     OTLIST,X
         CMP     #OTTOKILL              ;IF THE OBJECT TYPE IS OTTO OR GREATER, SKIP
         BMI     OPFCONT                ;LESS? CONTINUE ON
         RTS                            ;NOPE - EXIT
OPFCONT
         LDA     #$00
         STA     TEMP4                  ;HORIZONTAL EDGE (LEFT OR RIGHT - DEPENDS ON DIRECTION OF MOVEMENT)
         STA     TEMP5                  ;VERTICAL EDGE (TOP OR BOTTOM - AGAIN, DEPENDS ON DIRECTION OF MOVEMENT)
         STA     TEMP6                  ;RETURN FLAG TO INDICATE A COLLISION (0 = NO COLLISION, >0 = COLLISION)
         LDA     MXLIST,X               ;CHECK FOR HORIZONTAL MOVEMENT
         BNE     OPFHORZ                ;MOVING HORIZONTALLY; GO ON
         JMP     OPFVERT                ;NOT MOVING HORIZONTALLY; SKIP TO VERTICAL
OPFHORZ
         BMI     OPFHORZL               ;MOVING LEFT, SKIP THIS NEXT PART
         LDA     #$03                   ;MOVING RIGHT; USE RIGHT EDGE OF OBJECT (POSITIONING IS STILL DONE IN 2-PIXEL INCREMENTS)
         STA     TEMP4 
OPFHORZL
         LDA     #$00
         STA     TEMP15                 ;THIS WILL BE USED TO CHECK EVERY TWO RASTERS TO SEE IF THERE IS A COLLISION
         LDA     HPLIST,X               ;GET THE HORIZONTAL POSITION
         CLC
         ADC     TEMP4                  ;ADD IN LEFT OR RIGHT EDGE
         ADC     MXLIST,X               ;ADD IN MOVEMENT
         STA     TEMP8                  ;SAVE NEW X POSITION FOR LATER
         JSR     HTOC                   ;CONVERT TO COLUMN
         STA     TEMP1                  ;SET UP COLUMN VARIABLE FOR 'GETCHAR'
         LDA     TEMP8                  ;WE NEED THE HORIZONTAL OFFSET WITHIN THE CHARACTER
         AND     #$02                   ;THERE ARE 4 POSITIONS ACROSS (MOVES IN INCREMENTS OF 2), SO ONLY KEEP THE 2ND BIT
         STA     TEMP10                 ;THIS IS NOW THE HORIZONTAL POSITION OF THE OBJECT WITHIN THE SCREEN CHARACTER (LEFT = 00/RIGHT = 10)
OPFLOOP
         LDA     VPLIST,X               ;GET VERTICAL POSITION
         CLC
         ADC     TEMP15                 ;ADD IN VERTICAL RASTER OFFSET
         STA     TEMP9                  ;SAVE NEW Y POSITION FOR LATER
         JSR     VTOZ                   ;CONVERT TO ZONE
         STA     TEMP0                  ;SET UP ZONE VARIABLE FOR 'GETCHAR'
         LDA     TEMP9                  ;WE NEED THE VERTICAL OFFSET WITHIN THE CHARACTER
         AND     #$04                   ;THERE ARE 8 POSITIONS VERTICALLY, WE ONLY WANT 'TOP' AND 'BOTTOM', SO ONLY KEEP THE 3RD BIT
         LSR                            ;SHIFT RIGHT TWICE
         LSR
         STA     TEMP11                 ;THIS IS NOW THE VERTICAL POSITION OF THE OBJECT WITHIN THE SCREEN CHARACTER (TOP = 00/BOTTOM = 01)
         JSR     GETCHAR                ;GET THE CHARACTER AT THIS POSITION
         BPL     OPFNEXT                ;MAZE PIECES ARE ONLY NEGATIVE (> $80)
         AND     #$70                   ;STRIP OUT HIGH BIT AND LAST FOUR BITS
         LSR                            ;SHIFT RIGHT TWICE TO LINE UP WITH 'X' AND 'Y', WHICH WILL BE 'ORA'D IN
         LSR
         ORA     TEMP10                 ;OR THE X POSITION IN
         ORA     TEMP11                 ;OR THE Y POSITION IN
         TAY
         LDA     OBJALLOW,Y             ;SEE IF THIS POINT IS ALLOWED TO OCCUPY THE SPACE IT IS IN
         BEQ     OPFNEXT                ;YEP, NO COLLISION
         LDA     #$00                   ;NO, NOT ALLOWED TO MOVE IN THIS DIRECTION
         STA     MXLIST,X
         INC     TEMP6                  ;INCREMENT COLLISION FLAG
         BNE     OPFVERT                ;WE CAN'T MOVE, NO NEED TO CHECK THE REST
OPFNEXT
         INC     TEMP15                 ;ADD 3 TO TEMP15
         INC     TEMP15
         INC     TEMP15
         LDY     OTLIST,X               ;GET OBJECT TYPE
         LDA     OBJBE,Y                ;GET OBJECT HEIGHT
         CMP     TEMP15                 ;ARE WE PAST IT?
         BPL     OPFLOOP                ;NO, CONTINUE
OPFVERT
         LDA     MYLIST,X               ;CHECK FOR VERTICAL MOVEMENT
         BNE     OPFVERT2               ;MOVING VERTICALLY; GO ON
         JMP     OPFEXIT                ;NOT MOVING VERTICALLY; EXIT
OPFVERT2
         BMI     OPFVERTU               ;MOVING UP, SKIP THIS NEXT PART
         LDY     OTLIST,X               ;MOVING DOWN; USE BOTTOM EDGE OF OBJECT
         LDA     OBJBE,Y
         STA     TEMP5 
OPFVERTU
         LDA     #$00
         STA     TEMP15                 ;THIS WILL BE USED TO CHECK THE LEFT AND RIGHT SIDE OF THE OBJECT MOVING VERTICALLY
         LDA     VPLIST,X               ;GET THE VERTICAL POSITION
         CLC
         ADC     TEMP5                  ;ADD IN TOP OR BOTTOM EDGE
         ADC     MYLIST,X               ;ADD IN MOVEMENT
         STA     TEMP9                  ;SAVE NEW Y POSITION FOR LATER
         JSR     VTOZ                   ;CONVERT TO ZONE
         STA     TEMP0                  ;SET UP ZONE VARIABLE FOR 'GETCHAR'
         LDA     TEMP9
         AND     #$04                   ;THERE ARE 8 POSITIONS VERTICALLY, WE ONLY WANT 'TOP' AND 'BOTTOM', SO ONLY KEEP THE 3RD BIT
         LSR                            ;SHIFT RIGHT TWICE
         LSR
         STA     TEMP11                 ;THIS IS NOW THE VERTICAL POSITION OF THE OBJECT WITHIN THE SCREEN CHARACTER (TOP = 00/BOTTOM = 01)
OPFLOOP2
         LDA     HPLIST,X               ;GET THE HORIZONTAL POSITION
         CLC
         ADC     TEMP15                 ;ADD IN HORIZONTAL EDGE
         STA     TEMP8                  ;SAVE NEW X POSITION FOR LATER
         JSR     HTOC                   ;CONVERT TO COLUMN
         STA     TEMP1                  ;SET UP COLUMN VARIABLE FOR 'GETCHAR'
         LDA     TEMP8                  ;WE NEED THE HORIZONTAL OFFSET WITHIN THE CHARACTER
         AND     #$02                   ;THERE ARE 4 POSITIONS ACROSS (MOVES IN INCREMENTS OF 2), SO ONLY KEEP THE 2ND BIT
         STA     TEMP10                 ;THIS IS NOW THE HORIZONTAL POSITION OF THE OBJECT WITHIN THE SCREEN CHARACTER (LEFT = 00/RIGHT = 10)		  
         JSR     GETCHAR                ;GET THE CHARACTER AT THIS POSITION
         BPL     OPFNEXT2               ;MAZE PIECES ARE ONLY NEGATIVE (> $80)
         AND     #$70                   ;STRIP OUT HIGH BIT AND LAST FOUR BITS
         LSR                            ;SHIFT RIGHT TWICE TO LINE UP WITH 'X' AND 'Y', WHICH WILL BE 'ORA'D IN
         LSR
         ORA     TEMP10                 ;OR THE X POSITION IN
         ORA     TEMP11                 ;OR THE Y POSITION IN
         TAY
         LDA     OBJALLOW,Y             ;SEE IF THIS POINT IS ALLOWED TO OCCUPY THE SPACE IT IS IN
         BEQ     OPFNEXT2               ;YEP, NO COLLISION
         LDA     #$00                   ;NO, NOT ALLOWED TO MOVE IN THIS DIRECTION
         STA     MYLIST,X
         INC     TEMP6                  ;INCREMENT COLLISION FLAG
         BNE     OPFEXIT                ;WE CAN'T MOVE, NO NEED TO CHECK THE REST
OPFNEXT2
         INC     TEMP15                 ;ADD 1 TO TEMP15
         LDA     #$03                   ;RIGHT EDGE OF OBJECT
         CMP     TEMP15                 ;ARE WE PAST IT?
         BPL     OPFLOOP2               ;NO, CONTINUE
OPFEXIT
         LDA     HPLIST,X               ;SAVE HORIZONTAL POSITION AND COLUMN
         CLC
         ADC     MXLIST,X               ;OBJECT MOVEMENT
         STA     HPLIST,X               ;UPDATE HORIZONTAL POSITION
         LDA     VPLIST,X               ;SAVE VERTICAL POSITION, ZONE AND OFFSET
         CLC
         ADC     MYLIST,X               ;OBJECT MOVEMENT
         STA     VPLIST,X               ;UPDATE VERTICAL POSITION
         LDA     TEMP6                  ;LOAD 'A' WITH THE COLLISION FLAG
         RTS

OBJBE
        .byte    $0F,$0F,$0C,$0C,$01,$06,$06,$06,$0F,$0F,$06
OBJALLOW
        .byte    $01,$01,$00,$00,$01,$01,$00,$01
        .byte    $01,$01,$00,$01,$00,$01,$00,$01
        .byte    $00,$01,$00,$00,$01,$00,$00,$00
        .byte    $00,$00,$00,$01,$01,$01,$01,$01

 

I will post a WIP bin soon.

 

Thanks!

Bob

Share this comment


Link to comment

Hi - being that I got past the maze issue, I am closing this blog and starting another one for Frenzy.

 

Thanks guys!

Bob

Share this comment


Link to comment
Guest
This blog entry is now closed to further comments.
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...