14 replies to this topic

[PacManPlus]

Hi Guys:

I am working on Frenzy again, but I'm stuck at the moment. Here's my situation:

My DL:

DLISTS
         .byte    <(SCREEN),$60,>(SCREEN),$00+$00,#LEFTSIDE;SCREEN - PLAY FIELD
         .byte    $00,$40,>(STAMPS),$20+$1F,OFFSCRN        ;PLAYER 1
         .byte    $00,$40,>(STAMPS),$40+$1F,OFFSCRN        ;PLAYER 2
         .byte    $00,$40,>(STAMPS),$20+$1F,OFFSCRN        ;PLAYER SHOT 1
         .byte    $00,$40,>(STAMPS),$40+$1F,OFFSCRN        ;PLAYER SHOT 2
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT SHOT 1 / BIG OTTO 1
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT SHOT 2 / BIG OTTO 2
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT SHOT 3 / BIG OTTO 3
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT SHOT 4 / BIG OTTO 4
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT SHOT 5
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;EVIL OTTO
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT 1
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT 2
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT 3
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT 4
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT 5
         .byte    $00,$40,>(STAMPS),$60+$1F,OFFSCRN        ;ROBOT 6

         .byte    $00,$00,$00,$00,$00

The above DL in 320A mode uses 410 Maria cycles, I know that thanks to GroovyBee's utility.

The 6 robots at the end are shared for each zone with up to 22 robots (that's how many you can have with Frenzy). My logic only allows 6 robots to be in a zone at one time. They won't move into the zone otherwise.
My 'list of objects in memory' is set for 38 objects (the 16 in the DL above, + the 22 actual robots on the screen). I only move one robot per frame, as the arcade games does. As you may guess, the robot I'm working on gets checked for his DL 'slot' (0-5) and moved to the Display List above to get put on the screen.

Here's my object list, and what each variable is for:

;  OBJECT VARIABLES
HPLIST          DS      40                   ;40 BYTES - HORIZONTAL POSITION
HCLIST          DS      40                   ;40 BYTES - HORIZONTAL COLUMN
VPLIST          DS      40                   ;40 BYTES - VERTICAL POSITION
VZLIST          DS      40                   ;40 BYTES - VERTICAL ZONE
MXLIST          DS      40                   ;40 BYTES - MOVEMENT IN X DIRECTION
MYLIST          DS      40                   ;40 BYTES - MOVEMENT IN Y DIRECTION
ANLIST          DS      40                   ;40 BYTES - OBJECT ANIMATION OFFSET
SLLIST          DS      40                   ;40 BYTES - LOW BYTE STAMP ADDRESS
DOLIST          DS      40                   ;40 BYTES - SOMETHING CHANGED - RELOAD
OTLIST          DS      40                   ;40 BYTES - OBJECT TYPE LIST ($00=PLAYER, $01=SKELETON, $02=EYEBALL...)
OZLIST          DS      40                   ;40 BYTES - OLD ZONE FROM LAST FRAME
ODLIST          DS      40                   ;40 BYTES - OBJECT DIRECTION
OWLIST          DS      40                   ;40 BYTES - OBJECT WAIT FRAMES BEFORE NEXT MOVE
OFLIST          DS      40                   ;40 BYTES - OBJECT NEXT FRAME TO MOVE
OMLIST          DS      40                   ;40 BYTES - OBJECT IS MOVING (1=YES, 0=NO)
OSLIST          DS      40                   ;40 BYTES - OBJECT SLOT IN DL (ONLY 6 ROBOTS PER ZONE)
OTOPLS          DS      40                   ;40 BYTES - OBJECT TOP BITMAP EDGE
OBOTLS          DS      40                   ;40 BYTES - OBJECT BOTTOM BITMAP EDGE
OLFTLS          DS      40                   ;40 BYTES - OBJECT LEFT BITMAP EDGE
ORHTLS          DS      40                   ;40 BYTES - OBJECT RIGHT BITMAP EDGE
PDLIST          DS      40                   ;40 BYTES - PRIOR DIRECTION OF OBJECT

'Direction' mentioned in the above list, is as folows:

;           6
;        5  |  7
;         \ | /
;       4---+---0      
;         / | \
;        3  |  1
;           2
;

'Object Type' is this:

;  OBJECT DEFINITIONS
HUMANOID  =     $00                    ;PLAYER
SKELETON  =     $01                    ;ROBOT TYPE 1 (SKELETON)
EYEBALL   =     $02                    ;ROBOT TYPE 2 (EYEBALL)
ROBOT     =     $03                    ;ROBOT TYPE 3 (BERZERK ROBOT)
PVSHOT    =     $04                    ;PLAYER VERTICAL SHOT
PDSHOT    =     $05                    ;PLAYER DIAGONAL SHOT
PHSHOT    =     $06                    ;PLAYER HORIZONTAL SHOT
RVSHOT    =     $07                    ;ROBOT VERTICAL SHOT
RDSHOT    =     $08                    ;ROBOT DIAGONAL SHOT
RHSHOT    =     $09                    ;ROBOT HORIZONTAL SHOT
OTTOKILL  =     $0A                    ;'KILLABLE' OTTO (FRENZY)
OTTOINVN  =     $0B                    ;'INVINCABLE' OTTO (BERZERK)
OTTOBORN  =     $0C                    ;OTTO BEING BORN
OTTODETH  =     $0D                    ;OTTO DYING
ROBOTDTH  =     $0E                    ;ROBOT DEATH SEQUENCE
PLAYRDTH  =     $0F                    ;PLAYER DEATH SEQUENCE
DISABLED  =     $FF

This part works well.

The issue arises when I implement collision detection. being that whenever an object moves (which is every frame except in the robot's case) I run out of CPU time. This is because I have to check each object that moves, with the other 30 (22 robots, 1 player, 7 shots, and evil otto)
So that means traversing the list at least 10 times *per frame*. I'm trying to make my collision detection routine as tight as possible, but it doesn't seem to help. I get robots that don't move every frame, and some erratic behavior, like the player running into walls where he didn't before the Collision Detection was implemented (I've attached a bin below).

Here's my collision detection routine: (be nice!)

DOOBJECTCOL
          STX     TEMP3
          LDY     #$00
DOCLOOP
          CPY     TEMP3
          BEQ     DOCNEXT
          LDA     OTLIST,Y               ;SEE IF OBJECT IS ACTIVE
          BMI     DOCNEXT
          JSR     OBJECTCOLL
          BEQ     DOCNEXT

          ; BERZERK WOULD KILL BOTH OBJECTS
          BMI     DOCYDIR
DOCXDIR
          LDA     #$00
          STA     MXLIST,X
          BEQ     DOCNEXT
DOCYDIR
          LDA     #$00
          STA     MYLIST,X

DOCNEXT
          INY
          CPY     #ALLOBJECT
          BMI     DOCLOOP
DOCEXIT
          RTS

;  OBJECTCOLL - THIS ROUTINE CHECKS FOR A COLLISION BETWEEN A MOVING OBJECT AND ANOTHER OBJECT,
;              IDENTIFIED BY X AND Y
;    OBJECTIVE: ADD TOGETHER POSITION OF MOVING OBJECT AND VELOCITY, CHECK FOR COLLISION WITH OTHER OBJECT
;               IF THERE IS ONE, CHECK THE HORIZONTAL DIRECTION WITHOUT THE VELOCITY ADDED IN.
;               IF THERE IS STILL A COLLISION, WE KNOW THAT THE VERTICAL DIRECTION IS WHAT CAUSED THE COLLISION THIS FRAME
;               IF NOT, WE KNOW THAT IT WAS THE HORIZONTAL ONE.  RETURN THE DIRECTION THAT CAUSED THE COLLISION
;               AS FOLLOWS: POSITIVE ($01) FOR X DIRECTION, NEGATIVE ($FF) FOR Y DIRECTION, ZERO ($00) FOR NO COLLISION.
;  INPUT: X - MOVING OBJECT, Y - OTHER OBJECT !!!ASSUMES BOTH OBJECTS ARE VALID TYPES AND NOT EQUAL!!!
;  OUTPUT: A = THE COLLISION INFORMATION: $01 = X DIRECTION, $FF = Y DIRECTION, $00 = NO COLLISION
;  USES: A, TEMP0-2
OBJECTCOLL
          LDA     MXLIST,X               ;TAKE HORIZONTAL VELOCITY
          CLC
          ADC     HPLIST,X               ;ADD IT TO OUR CURRENT HORIZONTAL POSITION
          STA     TEMP0                  ;STORE IT
          LDA     MYLIST,X               ;TAKE VERTICAL VELOCITY
          CLC
          ADC     VPLIST,X               ;ADD IT TO OUT CURRENT VERTICAL POSITION
          STA     TEMP1                  ;STORE IT

          LDA     VPLIST,X               ;FIND OUT WHICH SPRITE IS BELOW THE OTHER TO GET CORRECT HEIGHT
          CMP     VPLIST,Y               ;IS THE VERTICAL POSITION OF THE OBJECT LESS THAN THE OTHER OBJECT?
          BMI     OOXISLESS              ;YES, USE THE HEIGHT OF THE OBJECT FOR THE COMPARISON
OOYISLESS
          LDA     OBOTLS,Y               ;GET THE HEIGHT OF THE LOWER (IN VALUE) SPRITE
          SEC
          SBC     OTOPLS,Y
          JMP     OOSTART                ;START THE COLLISION DETECTION
OOXISLESS
          LDA     OBOTLS,X               ;GET THE HEIGHT OF THE LOWER (IN VALUE) SPRITE
          SEC
          SBC     OTOPLS,X
OOSTART
          STA     TEMP2
          INC     TEMP2                  ;ADD 2 TO GET THE HEIGHT RIGHT
          INC     TEMP2
OOXCOMP
          LDA     TEMP0                  ;TAKE OUR 'NEW' OBJECT POSITION
          SEC
          SBC     HPLIST,Y               ;SUBTRACT OTHER OBJECT POSITION TO GET HORIZONTAL DIFFERENCE
          BPL     OOXCHECK
          EOR     #$FF                   ;USE ABSOLUTE VALUE
          CLC
          ADC     #$01
OOXCHECK
          CMP     #$04                   ;LESS THAN 4 HORIZONTAL PIXELS DIFFERENCE?
          BCS     OOEXIT                 ;NOPE, NO COLLISION
OOYCOMP
          LDA     TEMP1                  ;POSSIBLY, CHECK FOR Y DIRECTION NOW
          SEC
          SBC     VPLIST,Y               ;SUBTRACT OTHER OBJECT POSITION TO GET VERTICAL DIFFERENCE
          BPL     OOYCHECK               ;USE ABSOLUTE VALUE
          EOR     #$FF
          CLC
          ADC     #$01
OOYCHECK
          CMP     TEMP2                  ;LESS THAN (SPRITE HEIGHT) VERTICAL PIXELS DIFFERENCE?
         ;BCS     OOEXIT                 ;NOPE, NO COLLISION
          BCC     OOCOLL                 ;YES, THERE WAS A COLLISION!
OOEXIT
          LDA     #$00
          RTS
OOCOLL
          LDA     HPLIST,X               ;GET HORIZONTAL POSITION -WITHOUT- MOVEMENT ADDED IN
          SEC
          SBC     HPLIST,Y               ;SUBTRACT OTHER OBJECT POSITION
          BPL     OOXCHECK2
          EOR     #$FF                   ;USE ABSOLUTE VALUE
          CLC
          ADC     #$01
OOXCHECK2
          CMP     #$04                   ;LESS THAN 4 HORIZONTAL PIXELS DIFFERENCE?
          BCC     OOYCOLL                ;STILL HAVE A HORIZONTAL COLLISION, WHICH MEANS VERTICAL HAPPENED THIS FRAME
OONOXCOLL
          LDA     #$01                   ;YES, THERE WAS A HORIZONTAL COLLISION THIS FRAME
          RTS
OOYCOLL
          LDA     VPLIST,X               ;GET VERTICAL POSITION -WITHOUT- MOVEMENT ADDED IN
          SEC
          SBC     VPLIST,Y               ;SUBTRACT OTHER OBJECT POSITION
          BPL     OOYCHECK2
          EOR     #$FF                   ;USE ABSOLUTE VALUE
          CLC
          ADC     #$01
OOYCHECK2
          CMP     TEMP2                  ;LESS THAN (SPRITE HEIGHT) VERTICAL PIXELS DIFFERENCE?
          BCC     OOBOTHCOLL             ;STILL HAVE A VERTICAL COLLISION, WHICH MEANS STOP MOVING ALLTOGETHER
OONOYCOLL
          LDA     #$FF                   ;YES, THERE WAS A VERTICAL COLLISION THIS FRAME
          RTS
OOBOTHCOLL
          LDA     #$02                   ;WE MAY USE THIS OR NOT...
          RTS

Any ideas anyone? Maybe a quick and dirty software collision detection routine that I can use here?

Thanks for your help, guys.
Bob

[EricBall]

One immediate suggestion would be to try to eliminate the JSR OBJECTCOLL. Yes, it means you can use RTS to get back to the DOCLOOP, but it's costly in CPU cycles. You may have to use Branch+JMP sequences, but that's still faster than JSR+RTS. You can then also pull back the BEQ DOCNEXT into the OBJECTCOLL logic.

How big are your objects & velocities? Is bounding box good enough or do you need pixel perfect? Can shots collide? You may want to have one set of routines for shots and another for other objects. Test the shots versus the other objects and the objects only against each other.

[GroovyBee]

How about using the information already stored in the Display List and a bit map of objects in each zone. E.g.

You have a byte per zone in RAM that contains bits representing robot slots filled e.g. %00000001 indicates slot 1 is filled, %00000010 slot 2 is filled and so on. This byte will be updated as the robots move around.

A similar byte for the robot shots and a byte for the player shots too.

It would work as follows :-

When the player is cut up into zones look at the robot bit mask for the new zone for his head/upper torso. If any bits are set there are robots to check against. Use a table to convert the robot's bit mask into a number that can be loaded into register Y to extract the X coordinate from the DL headers for the first available robot. Check it against your bounding box for X. If its within the player, kill the player. If not keep going until you've looked at all the robots in the zone. Then look at the zone the player's lower torso and feet will be in and do the same.

If any bits in the robot shots for the players new zone are set then handle them in the same way. However you'll need to check the shots height in the zone too because the shot won't be close to the full size of the zone (I expect).

When you want to move a robot look at the robot bit mask for its new zone. If it contains $63 it can't move vertically up or down so either make him sit still or travel left/right instead. If there is a slot free you can use a table to convert the bit map into a first free slot for the new robot. If there is a free slot compare X coordinates with the existing robots to see if they've collided and need wiping out.

[SpiceWare]

How does Robotron do it? It's got a lot of sprites running around and has to handle collisions between robots, player, and the various family members that are running around.

And is there really a max of 22 objects, or is that 20 robots + player + evil otto? I was looking thru The Source earlier this week, but couldn't figure out where max robots was defined.

Edited by SpiceWare, Thu Jun 9, 2011 1:04 PM.

[GroovyBee]

The source code to Robotron supplied by Curt is for a version of MARIA that didn't ship in the consumer units.

[PacManPlus]

EricBall, on Thu Jun 9, 2011 11:53 AM, said:

How big are your objects & velocities? Is bounding box good enough or do you need pixel perfect? Can shots collide? You may want to have one set of routines for shots and another for other objects. Test the shots versus the other objects and the objects only against each other.

Thanks! I'll try removing the JSRs. The object are various sizes (i.e. player is 16x8, skeleton is also 16x8, but the other robots are 11x8, Otto is 10x8, and the shots are either 1x3 or 3x3 depending on their direction). I need pixel perfect for this. *Everything* can collide. In Berzerk, everything cancels each other out and the player gets points no matter what. In Frenzy, only the shots, Otto and explosions cause something to die. Frenzy collisions between robots/players or robots/robots or playfield with everything except shots and Otto just cause them to stop moving in that direction.

GroovyBee, on Thu Jun 9, 2011 12:38 PM, said:

How about using the information already stored in the Display List and a bit map of objects in each zone. E.g. You have a byte per zone in RAM that contains bits representing robot slots filled e.g. %00000001 indicates slot 1 is filled, %00000010 slot 2 is filled and so on. This byte will be updated as the robots move around. A similar byte for the robot shots and a byte for the player shots too.

It would work as follows :-
When the player is cut up into zones look at the robot bit mask for the new zone for his head/upper torso. If any bits are set there are robots to check against. Use a table to convert the robot's bit mask into a number that can be loaded into register Y to extract the X coordinate from the DL headers for the first available robot. Check it against your bounding box for X. If its within the player, kill the player. If not keep going until you've looked at all the robots in the zone. Then look at the zone the player's lower torso and feet will be in and do the same.

If any bits in the robot shots for the players new zone are set then handle them in the same way. However you'll need to check the shots height in the zone too because the shot won't be close to the full size of the zone (I expect).

When you want to move a robot look at the robot bit mask for its new zone. If it contains $63 it can't move vertically up or down so either make him sit still or travel left/right instead. If there is a slot free you can use a table to convert the bit map into a first free slot for the new robot. If there is a free slot compare X coordinates with the existing robots to see if they've collided and need wiping out.

Thanks, GB - I'll look at that theory more closely and see if I can implement it.

SpiceWare, on Thu Jun 9, 2011 1:02 PM, said:

How does Robotron do it? It's got a lot of sprites running around and has to handle collisions between robots, player, and the various family members that are running around.

And is there really a max of 22 objects, or is that 20 robots + player + evil otto? I was looking thru The Source earlier this week, but couldn't figure out where max robots was defined.

In Robotron, the grunts don't die if they run into each other, so unfortunately that won't work anyway . Also, yes, in Frenzy there is a max of 22 Robots + player + (up to) 5 robot shots + (up to) 2 player shots + Otto.

Thanks guys for the advice - let me see if anything helps

Bob

[kenfused]

Maybe do the Y bounds checks first if they are more likely to fail.

In my bounds check in Beef Drop and b*nQ I was usually doing something like

    sec           ;this should check if ypos differ by 0,1,2,-1,or -2
    lda ypos1
    sbc ypos2
    cmp #3 
    bcc checkx   ; branch if less than 3
    cmp #256-2  ;-2
    bcc nocollide  ; branch if less than 254  (less than -2, ie -3,-4...)
checkx:
    ...check xpos difference for collision...

nocollide:  ;no collision in this object
    

Don't know if that is better than the taking the absolute value of the negative differences or not.

[PacManPlus]

Hi Guys:


I've been trying this every way I could think of. I also realised that I not only have to know if there is a collision, but I have to know the *direction* (horizontal or vertical) of the collision. This is because in Frenzy, if a player or robot is moving diagonally, but something is blocking it's path in one direction (i.e. horizontally) they can still move vertically - they don't just stop. So I have to take each direction as a separate collision. So that would mean having a list of: 1 player (although I planned on having two player simultaneous), 7 shots, Otto, and up to 22 robots... Having to go through that list up to 10 times *per frame* (1 player, 7 shots, otto, + 1 robot), THEN having to take each direction separately (i.e. check each collision twice), there just isn't enough CPU time. That's not even counting all of the other game logic that has to be implemented on a 'per frame' basis (i.e. Otto, or the Robot Factory, etc.)
I know someone is working on this for the 2600, but I don't know how that's going to be possible... maybe the hardware collision detection alleviates some of the headache; I don't know the 2600 well enough.

I don't really think this can be done *using the same rules as the arcade game* - and if I have to change the rules, it's not Frenzy.

I'm letting it go for now.

Thanks guys,
Bob

[SpiceWare]

PacManPlus, on Tue Jun 14, 2011 4:53 AM, said:

I know someone is working on this for the 2600, but I don't know how that's going to be possible... maybe the hardware collision detection alleviates some of the headache; I don't know the 2600 well enough.

I'm not going to be able to use hardware collision as the 2 sprites are being reused multiple times to draw the humanoid, Otto AND all the robots. I am using the Harmony/Melody's 70 MHz ARM for all the game logic.

The following test was generated without any flicker, though of course flicker will eventually come into play.

[PacManPlus]

I didn't mention you by name because it wasn't my place to let everyone know what you were working on... Thanks for putting it out there.

That being said, are you having all 22 robots in your version? The screenshot above looks like it's the 'berzerk' maze layout.

If you aren't using hardware collision, aren't you going to run out of CPU time? I was under the impression that the 2600 actually *less* time than the 7800 has (especially using 320 mode).

I don't mean to be a pain, but I always feel like I'm 'missing something' when I attempt a project like this, and then someone else comes along and does it with no issue.

Thanks,
Bob

EDIT - I just thought of something. The only objects that move *every* frame are the shots. The player, otto, and the robots (at their fastest - i.e. 1 robot left on screen) move once every 4 frames (or they would be too fast). That may mean that I can move them on one frame, and split the collision detection between the last three frames (doing only the shots every frame). I wonder if that would work... it would be a pretty big undertaking though...

EDIT2 - That didn't work too well either - still skipping frames.

Edited by PacManPlus, Thu Jun 16, 2011 5:45 AM.

[SpiceWare]

It's not secret - I've been documenting the development of Frantic in my blog since April.

It started out as an updated version of Berzerk, but I decided to see if I couldn't make it support both Berzerk and Frenzy. Currently the maze generation is controlled by the Right Difficulty switch: A = Frenzy, B = Berzerk.


I'll try to support 22 robots, though being that the 2600 is all about tradeoffs I won't be upset if I can't. One issue is I'd like to play back digitized samples and that takes up a bit of space & time.

This is going to be a Melody game using DPC+ and custom ARM routines - all game logic is running on a 70 MHz ARM.

[SpiceWare]

Don't know if this will help, but I just got pixel perfect collision detection working for Frantic. The routine is written in C and found in function Collision() at the end of custom/main.c.

It doesn't detect playfield collisions yet, just sprite-to-sprite.

Edited by SpiceWare, Sun Aug 14, 2011 1:33 PM.

[Stephen]

SpiceWare, on Tue Jun 14, 2011 10:03 AM, said:

It's not secret - I've been documenting the development of Frantic in my blog since April.

It started out as an updated version of Berzerk, but I decided to see if I couldn't make it support both Berzerk and Frenzy. Currently the maze generation is controlled by the Right Difficulty switch: A = Frenzy, B = Berzerk.
frantic_harmony.bin_29.png

I'll try to support 22 robots, though being that the 2600 is all about tradeoffs I won't be upset if I can't. One issue is I'd like to play back digitized samples and that takes up a bit of space & time.

This is going to be a Melody game using DPC+ and custom ARM routines - all game logic is running on a 70 MHz ARM.

Am I to understand that since the Melody is a stripped down Harmony cart, the game will work on Harmony as well?

[SpiceWare]

Stephen, on Sun Aug 14, 2011 8:27 PM, said:

Am I to understand that since the Melody is a stripped down Harmony cart, the game will work on Harmony as well?

yep - it's what I'm using to develop Frantic

[DEBRO]

Hi there,

I'm a little late to the party. I've e-mailed Bob directly but thought I'd post here too. Maybe we could figure this out together.

I didn't see in the supplied snippet where you don't do this check when it is not time to move an object. Am I missing it? You might gain some cycles there. Also, is the list sorted in a certain way where you only need to check adjacent objects in the list? The routine seems to only look at adjacent objects but I could be missing something.