Basic Efficient Collision Detection Routine

[tjohnson]

I'm writing a basic game in basic and want an efficient routine for collision detection.  I'm using character mode for this and effectively there can be a small number of bullets and small number of targets but I don't want to use brute force to check every potential collision which is way too slow.  I have not written any sort of computer game before.  Any suggestions?

[SRS]

Once uppon a time I used the move of the bullet (like bx=bx+1:by=by+1) to check if its new postion is that of a target (if bx=playerx and by=playery ...). But that was the 80is

How about using the routines from here:

http://www.cpcwiki.eu/forum/programming/basic-shoot-em-up-engine/

[tjohnson]

I'll have a look at that ideally trying to avoid a check every loop.  The targets are pretty predicable so i should be able to calculate a collision once and then refresh after certain number of iterations but if a new target appears it would need recalculating.

Sent from my E5823 using Tapatalk

[AMSDOS]

There is certainly potential to expand on what I posted earlier, though the BASIC code could also be enhanced as well. It's main setbacks is the use of Logical Conditions & Screen Mode. Dropping the screen mode from MODE 1 to MODE 0 will the amount of character positions from 40x25 to 20x25, hence less space to move objects around the screen. The use of Logical Conditions (AND & OR in this case) is good for program readability, though are slow in operation. Locomotive BASIC in this case seems to handle "IF <condition> THEN IF <condition>....and so on" much better than the ANDs & ORs. Though what I said initially about expanding the Collision Detection could be used. I guess in my example the simplest approach is to check first is the bullet (by[]) is on the same line as the Alien (ay), if it isn't the check could be skipped and just allow everything to move accordingly. If it's on the same line I suppose what you could do is check if the position of the bullet or the area next to it contains the alien, that should theoretically remove the need to check each time the alien has moved and the check just needs to be done after the Bullet has moved.

[AMSDOS]

This is what I ended up with which only does a single check now, but I think it's an improvement:

Code: [Select]

100 ' Setup Inks and Screen Mode
110 INK 0,0
120 INK 1,26
130 INK 2,20
140 INK 3,18
150 BORDER 11
160 PAPER 0
170 PEN 1
180 MODE 1
200 ' Define Characters & Objects
210 DEFINT a-z
220 s$=CHR$(143)
230 a$="@"
240 b$="-"
250 x=1
260 y=1
270 DIM bx(2)
280 DIM by(2)
290 b=1
300 t=0
310 sc=0
320 ay=1+INT(RND*23)
330 ax=37
340 GOSUB 810 ' Print Ship
350 GOSUB 1010 ' Print Alien
360 LOCATE 1,25
370 PRINT"Score:"
400 ' Main Loop
410 WHILE 1
420   IF INKEY(1)<>-1 AND x<30 THEN GOSUB 910:x=x+1:GOSUB 810
430   IF INKEY(8)<>-1 AND x>1 THEN GOSUB 910:x=x-1:GOSUB 810
440   IF INKEY(0)<>-1 AND y>1 THEN GOSUB 910:y=y-1:GOSUB 810
450   IF INKEY(2)<>-1 AND y<24 THEN GOSUB 910:y=y+1:GOSUB 810
460   GOSUB 710
470   GOSUB 1140 : GOSUB 1010 ' Delete & Reprint Alien
475   GOSUB 610
480   IF INKEY(47)<>-1 AND t<>2 THEN t=t+1:bx(t)=x+1:by(t)=y
490   IF t<>0 THEN GOSUB 1210
500 WEND
600 ' Has bullet or alien collided?
610 IF by(1)<>ay THEN IF by(2)<>ay THEN GOSUB 1210:RETURN:ELSE GOSUB 611:RETURN
611 FOR n1=1 TO t
612   IF bx(n1)=ax THEN GOSUB 1410
613   IF bx(n1)+1=ax THEN LOCATE bx(n1),by(n1):PRINT" ";:bx(n1)=bx(n1)+1:LOCATE bx(n1),by(n1):PRINT b$;:GOSUB 1410
614 NEXT n1
620 RETURN
700 ' Has Alien Collided with Ship?
710 IF (x=ax) AND (y=ay) THEN GOSUB 1410:LOCATE 15,12:PRINT"You're Dead!":END
720 RETURN
800 ' Display Ship
810 LOCATE x,y
820 PEN 1
830 PRINT s$;
840 RETURN
900 ' Delete Ship
910 LOCATE x,y
920 PRINT" ";
930 RETURN
1000 ' Display and Move Alien
1010 LOCATE ax,ay
1020 PEN 2
1030 PRINT a$;
1040 ax=ax-1
1050 GOSUB 710
1060 WHILE ax=0
1070   LOCATE 1,ay
1080   PRINT" ";
1090   ax=37
1100   ay=1+INT(RND*23)
1110 WEND
1120 ' GOSUB 610
1130 RETURN
1140 LOCATE ax+1,ay
1150 PRINT" ";
1160 RETURN
1200 ' Routine to Move Shots Fired
1210 FOR n=b TO t
1220   LOCATE bx(n),by(n)
1230   PRINT" ";
1240   PEN 3
1250   bx(n)=bx(n)+1
1260   LOCATE bx(n),by(n)
1270   PRINT b$;
1280   IF bx(n)=38 THEN LOCATE 38,by(n):PRINT" ";:b=b+1
1290 NEXT n
1300 IF bx(n-1)=38 AND b=3 THEN GOSUB 1590
1310 ' GOSUB 610
1320 RETURN
1400 ' Death Sequence for Alien or Ship should they Collide
1410 LOCATE ax,ay
1420 PRINT" ";CHR$(238);
1430 sc=sc+20
1440 LOCATE 8,25
1450 PRINT sc;
1460 ax=39
1470 ay=1+INT(RND*23)
1480 FOR v=15 TO 0 STEP -1
1490   BORDER 6
1500   SOUND 1,0,3,v,,,31
1510   BORDER 11
1520   SOUND 2,1000,3,v,,,31
1530 NEXT v
1540 FOR c=1 TO t
1550   LOCATE bx(c),by(c)
1560   PRINT" ";
1570   bx(c)=0:by(c)=0
1580 NEXT c
1590 b=1:t=0
1600 RETURN


[tjohnson]

Thanks! alot of that code looks similar to my game, i have 6 potential bullets and 4 potential targets which as the number increases the performance falls away.  I'm hoping to work on it again today so will post an update later on what I'm doing.

Sent from my E5823 using Tapatalk

[SRS]

Just for fun I added a part that deletes old explosion clouds after roundabout 4 seconds:

Code: [Select]

100 ' Setup Inks and Screen Mode
110 INK 0,0
120 INK 1,26
130 INK 2,20
140 INK 3,18
150 BORDER 11
160 PAPER 0
170 PEN 1
180 MODE 1
190 ' Define Characters & Objects
200 DEFINT a-z
210 s$=CHR$(143)
220 a$="@"
230 b$="-"
240 x=1
250 y=1
260 DIM bx(2)
270 DIM by(2)
280 b=1
290 t=0
300 sc=0
310 ay=1+INT(RND*23)
320 ax=37
330 GOSUB 600 ' Print Ship
340 GOSUB 690 ' Print Alien
350 LOCATE 1,25
360 PRINT"Score:"
370 ' Main Loop
380 WHILE 1
390   IF INKEY(1)<>-1 AND x<30 THEN GOSUB 650:x=x+1:GOSUB 600
400   IF INKEY(<>-1 AND x>1 THEN GOSUB 650:x=x-1:GOSUB 600
410   IF INKEY(0)<>-1 AND y>1 THEN GOSUB 650:y=y-1:GOSUB 600
420   IF INKEY(2)<>-1 AND y<24 THEN GOSUB 650:y=y+1:GOSUB 600
430   GOSUB 570
440   GOSUB 820 : GOSUB 690 ' Delete & Reprint Alien
450   GOSUB 500
460   IF INKEY(47)<>-1 AND t<>2 THEN t=t+1:bx(t)=x+1:by(t)=y
470   IF t<>0 THEN GOSUB 860
480 WEND
490 ' Has bullet or alien collided?
500 IF by(1)<>ay THEN IF by(2)<>ay THEN GOSUB 860:RETURN:ELSE GOSUB 510:RETURN
510 FOR n1=1 TO t
520   IF bx(n1)=ax THEN GOSUB 990
530   IF bx(n1)+1=ax THEN LOCATE bx(n1),by(n1):PRINT" ";:bx(n1)=bx(n1)+1:LOCATE bx(n1),by(n1):PRINT b$;:GOSUB 990
540 NEXT n1
550 RETURN
560 ' Has Alien Collided with Ship?
570 IF (x=ax) AND (y=ay) THEN GOSUB 990:LOCATE 15,12:PRINT"You're Dead!":END
580 RETURN
590 ' Display Ship
600 LOCATE x,y
610 PEN 1
620 PRINT s$;
630 RETURN
640 ' Delete Ship
650 LOCATE x,y
660 PRINT" ";
670 RETURN
680 ' Display and Move Alien
690 LOCATE ax,ay
700 PEN 2
710 PRINT a$;
720 ax=ax-1
730 GOSUB 570
740 WHILE ax=0
750   LOCATE 1,ay
760   PRINT" ";
770   ax=37
780   ay=1+INT(RND*23)
790 WEND
800 ' GOSUB 610
810 RETURN
820 LOCATE ax+1,ay
830 PRINT" ";
840 RETURN
850 ' Routine to Move Shots Fired
860 FOR n=b TO t
870   LOCATE bx(n),by(n)
880   PRINT" ";
890   PEN 3
900   bx(n)=bx(n)+1
910   LOCATE bx(n),by(n)
920   PRINT b$;
930   IF bx(n)=38 THEN LOCATE 38,by(n):PRINT" ";:b=b+1
940 NEXT n
950 IF bx(n-1)=38 AND b=3 THEN GOSUB 1180
960 ' GOSUB 610
970 RETURN
980 ' Death Sequence for Alien or Ship should they Collide
990 LOCATE ax,ay
1000 ex=ax:ey=ay:AFTER 200 GOSUB 1210
1010 PRINT" ";CHR$(238);
1020 sc=sc+20
1030 LOCATE 8,25
1040 PRINT sc;
1050 ax=39
1060 ay=1+INT(RND*23)
1070 FOR v=15 TO 0 STEP -1
1080   BORDER 6
1090   SOUND 1,0,3,v,,,31
1100   BORDER 11
1110   SOUND 2,1000,3,v,,,31
1120 NEXT v
1130 FOR c=1 TO t
1140   LOCATE bx(c),by(c)
1150   PRINT" ";
1160   bx(c)=0:by(c)=0
1170 NEXT c
1180 b=1:t=0
1190 RETURN
1200 ' Delete old explosion
1210 LOCATE ex,ey:PRINT "  ";
1220 RETURN

[tjohnson]

Right here is my basic game inspired by the arcade game depth charge.  Its not really finished yet but the basics are there now, for example no sound.  Its all in character mode so chunky movements.  Anyone know how to make the sonar ping from the arcade machine would be great.  The collision detection isn't exactly great and could be faster and more efficient I think, was thinking of holding locations in a 2D array and checking against that rather than the loops.

O - left
P - right
Hold left or Right to move more quickly
Q - drop left depth charge
W - drop right depth charge

Please feel free to hack it about and make it better and faster, but be gentle on me as I've not written anything in basic before, have never written any sort of computer game and last time I coded anything was probably about 1993.


~~~~

I've added another game to the zip file called bomb drop (wow novel name), this is similar, you control a ship and the aim is to destroy all 6 targets by dropping bombs on them before the time runs out or you get shot out by one of the aliens.
Q - up
A - down
O - left
P - right
Space - drop bomb
E - escape


I knocked this together before the other game but used the screen character detection for collision detection which I think is only compatible with basic 1.1.  I think it also has a bug that occasionally a target will be under another but it doesn't happen often so I didn't bother fixing it.

[tjohnson]

I've also compiled the Depth Charge game using CPC Basic 3 compiler which makes it a bit faster and enjoyable, if you actually want to play it this is the one to use.


**** actually this compiled version is bugged slightly, the time doesn't work correctly after modifying to compile, will have to fix that, maybe once I make the further enhancements I'm planning ****.

[Sykobee (Briggsy)]

Checking N bullets with M targets results in an O(n^2) algorithm - increase N or M and performance drops away as you need to do N*M collision tests. Obviously in BASIC you should use integers, not reals, but I expect you have defint a-z in the code already, or are using x%, y% type variables.


So many games limited the bullet count (1 player bullet, M targets) typically, or the target count. (N enemy bullets, 1 player), or a compromise (4 bullets and 4 targets means 32 compares on x and y locations, which isn't bad in assembler but in basic would start to exhibit issues, let's not consider 8 bullets and 8 targets, or 256 bullets and 2 targets (like chibi akuma?)).


Beyond that, games would use solutions such as binning bullet and target locations into screen areas, for example. That meant you had to update the bin information when something moved from one bin to another (less frequent), but the runtime checks (more frequent) were quicker as you only had to check within that bin.


In a horizontal scrolling shoot-em-up, or any game where bullets can only travel horizontally, a potential binning strategy would have been a bin per character line of the screen. Enemy moves vertically? Change the bins they are in (they'll overlap if they have fine-grained movement). Try not to have too many enemies on the same line or you'll get chugging. The time to execute a bin change is quick compared to the re-render of the sprite, so it's not a big issue. But it's a debugging hell until the code is correct.


You can see why hardware-based collision detection for sprites was a life-saver for performance and coding difficulty back in the day! Even if it was a simple "yes/no collision occurred", you'd only have to do the checks when that was set, and you could get away with using a slow algorithm because a frame skip in this situation is excusable.

[AMSDOS]

I had a look at the source code for Depth Charge, while I like the descriptive names for the variables, that's going to be holding up BASIC a lot. I also noticed you're using INKEY$ which is slower than INKEY("key number")<>-1, though with INKEY$ you can use Speed Key (use with care though). I tried this last night, though after the changes, the boat moved briefly and then stopping  Initially I thought the CALL &BB03 was the culprit, but it still occured after I commented them out, something to do with TIME I guess? I had DI/EI around the INPUT routine, probably should have around the TIME routine 

For the variable names, I would just write all those names in Notepad and put a single letter variable next to it, I saw some single letter variables being used, so perhaps use 2 character names for those descriptive variables, a number could be used following a letter - A1, A2 so it kind of groups with the related stuff I suppose.

[ervin]

I had a look at the source code for Depth Charge, while I like the descriptive names for the variables, that's going to be holding up BASIC a lot. I also noticed you're using INKEY$ which is slower than INKEY("key number")<>-1, though with INKEY$ you can use Speed Key (use with care though). I tried this last night, though after the changes, the boat moved briefly and then stopping  Initially I thought the CALL &BB03 was the culprit, but it still occured after I commented them out, something to do with TIME I guess? I had DI/EI around the INPUT routine, probably should have around the TIME routine 

For the variable names, I would just write all those names in Notepad and put a single letter variable next to it, I saw some single letter variables being used, so perhaps use 2 character names for those descriptive variables, a number could be used following a letter - A1, A2 so it kind of groups with the related stuff I suppose.

I've been looking into the code too... it's very interesting.
The boat's moving/stopping is to do with all the sub/bomb processing that goes on after the boat has moved a few steps.

[freemac]

I found that : http://amstrad.eu/modules/lexikon/entry.php?entryID=179 

10 CLS
20 PRINT"coin superieur"
30 LOCATE 1,1
40 a$=COPYCHR$(#0)
50 LOCATE 1,20
60 PRINT a$
RUN

[tjohnson]

Thanks for the feedback, all feedback is welcomed and if you can improve and make it better please feel free!   I didn't realise the descriptive names would slow basic down so that's great.
On INKEY$ i did try INKEY but didn't find it worked as well in practice.  I put the calls in to clear the key buffer to stop the key inputs queing up and the ship moving multiple space when you only want it to move once.
I put the counter into the ship movement as a late addition to allow the ship to move faster than the subs, there is probably a better way of doing it.

Sent from my E5823 using Tapatalk

[tjohnson]

I found that : http://amstrad.eu/modules/lexikon/entry.php?entryID=179 

10 CLS
20 PRINT"coin superieur"
30 LOCATE 1,1
40 a$=COPYCHR$(#0)
50 LOCATE 1,20
60 PRINT a$
RUN

I didn't use that method of reading the screen in the depth charge game as I don't think it works on the 464 and wanted it compatible, I did however used it in my other bomb drop game though which I wrote before the depth charge game.

Ive been thinking about another way of checking collision but will need to put down some code to see if it works and is any quicker.

Sent from my E5823 using Tapatalk

[freemac]

10 x%=int(rnd*20)+1
20 y%=20
25 pen 2
30 locate x%,y%:print "I"
31 locate x%,y%:print "I"
32 locate x%,y%:print "I"
33 locate x%,y%:print "I"
34 locate x%,y%:print "I"
35 locate x%,y%:print "I"
36 locate x%,y%:print "I"
37 locate x%,y%:print "I"
38 locate x%,y%:print "I"
39 locate x%,y%:print "I"
40 locate x%,y%:print " "
45 y%=y%-1
46 locate x%,y%:a$=copychr$(#0)
47 if a$="O" then 50
48 if asc(a$)<>32 then print "O":goto 10
50 if y%=1 then 10
60 goto 30
5 pen 1:cls:cat

 

[AMSDOS]

I didn't use that method of reading the screen in the depth charge game as I don't think it works on the 464 and wanted it compatible, I did however used it in my other bomb drop game though which I wrote before the depth charge game.

Ive been thinking about another way of checking collision but will need to put down some code to see if it works and is any quicker.

Sent from my E5823 using Tapatalk

Indeed, the COPYCHR$(#0) doesn't exist on a 464 with BASIC 1.0, though in the firmware the function exists, so with a little bit of M/C it's possible to write one. However there is a subtle difference which created havoc in the early days (prior to the 664). The main problem with the firmware relates to when graphics were checked, by this I mean something like a graphical line at a certain text coordinate position. I wrote this little program in the BASIC Programming Tips which demostrates the issue, which relates to what the PEN colour is. On the 464 it doesn't care what the colour is, unlike the later computers which do.


You may also want to try a game I reworked from AA84, I've attached a CDT (tape image) of it here, which has a link to the original game. I bring it up because the game on the CDT is now using an Array for the playing field. What I seem to notice with that and the original game which is checking what's at a position with COPYCHR$(#0) is the array version is running a little bit faster. The only thing lagging in the TAPE version (apart from the TAPE!  ), is the drawing process for the time it takes to draw the screen. I didn't think this was as critical though. 

[ervin]

A couple of little things that I noticed, not related to the collision checking:
- The entire status line is reprinted every single frame on line 10920. It's better to print the static text once when the game starts, and then just print the numeric values when they change.
- a line of 40 spaces is printed every frame by line 10905. It doesn't seem to be required (at least, not at this stage), and it slows things down quite a lot.

[tjohnson]

I dug this out and made a few small changes today.  Next step will be to start trying to code bits of it in assembler to try to get the speed up and move away from the character movement.

[tjohnson]

Hi all,

I've made a few small improvements to my basic game.  Latest disk attached, no assembler.

Press 3 to add credits, press 1 to start
O and P to make the ship move left and right
Q and W to drop a depth charge either side of the ship.

Cheers Trevor

[AMSDOS]

I made this basic Assembly routine to move something initially along the screen which you're more than welcome to use. I'd adjusted the routine to shoot down the screen. It's not pixel perfect, but it will take some of the strain off BASIC by not having BASIC move the shots fired. But there's still things you need to do in BASIC. I posted this example, which shows that, though I've since improved the code so things move during the shooting sequence. Let me know if you want to have a look at it.

Code: [Select]

org &9000

;; CALL &9000,bx,by


ld a,(ix+02) ;; a:=bx
ld (bx),a ;; bx:=a
ld a,(ix+00) ;; a:=by
ld (by),a ;; by:=a


ld hl,(by) ;; l:=bx h:=by
call &bb75
ld a,32
call &bb5a


ld a,(by) ;; a:=by
inc a ;; a:=a+1
ld (by),a ;; by:=a

ld hl,(by) ;; l:=bx h:=by
call &bb75
ld a,238
call &bb5a


ret ;; back to BASIC


.by defb 0 ;; x position of bullet
.bx defb 0 ;; y position of bullet

[tjohnson]

Hi thanks for the code,  I had a quick looks at the call routines and can see that the first locates the cursor and the second prints the character.  If you can share some other improvements and suggestions it would be welcomed.  If I have time tonight I'll try and build your machine code suggestion into my game.
Thanks Trevor

I made this basic Assembly routine to move something initially along the screen which you're more than welcome to use. I'd adjusted the routine to shoot down the screen. It's not pixel perfect, but it will take some of the strain off BASIC by not having BASIC move the shots fired. But there's still things you need to do in BASIC. I posted this example, which shows that, though I've since improved the code so things move during the shooting sequence. Let me know if you want to have a look at it.

Code: [Select]

   org &9000
   
   ;; CALL &9000,bx,by


   ld a,(ix+02)      ;; a:=bx
   ld (bx),a      ;; bx:=a
   ld a,(ix+00)      ;; a:=by
   ld (by),a      ;; by:=a


   ld hl,(by)      ;; l:=bx h:=by
   call &bb75
   ld a,32
   call &bb5a


   ld a,(by)      ;; a:=by
   inc a         ;; a:=a+1
   ld (by),a      ;; by:=a
   
   ld hl,(by)      ;; l:=bx h:=by
   call &bb75
   ld a,238
   call &bb5a


   ret         ;; back to BASIC


.by   defb 0         ;; x position of bullet
.bx   defb 0         ;; y position of bullet

[AMSDOS]

Hi thanks for the code,  I had a quick looks at the call routines and can see that the first locates the cursor and the second prints the character.  If you can share some other improvements and suggestions it would be welcomed.  If I have time tonight I'll try and build your machine code suggestion into my game.
Thanks Trevor

Probably the only thing that could be improved in that Assembly code is section of code which increments the 'by' variable:

Code: [Select]


   ld a,(by)      ;; a:=by
   inc a         ;; a:=a+1
   ld (by),a      ;; by:=a
   


which can be written like this:

Code: [Select]

   ld hl,by      ;; hl:=address of by
   inc (hl)      ;; increases contents of by variable


which removes the 3rd instruction.


I've also just recently made some adjustments to a sprite driver, so it works with this sort of Assembly routine, unfortunately it's strictly MODE 0 only because of the way it calculates screen addresses, it also uses Text Coordinate based positions for Sprite Placement.

[tjohnson]

Thanks i started having a play with this last night, i entered the assembler in winape to generate the machine code for the data strings.  Added a third call variable to change the printed character and started updating the basic to use it.  Hopefully i can complete that tonight.

Sent from my E5823 using Tapatalk

[tjohnson]

Probably the only thing that could be improved in that Assembly code is section of code which increments the 'by' variable:

Code: [Select]


   ld a,(by)      ;; a:=by
   inc a         ;; a:=a+1
   ld (by),a      ;; by:=a
   


which can be written like this:

Code: [Select]

   ld hl,by      ;; hl:=address of by
   inc (hl)      ;; increases contents of by variable


which removes the 3rd instruction.


I've also just recently made some adjustments to a sprite driver, so it works with this sort of Assembly routine, unfortunately it's strictly MODE 0 only because of the way it calculates screen addresses, it also uses Text Coordinate based positions for Sprite Placement.

Right so I've had a play, I modified the code slightly following your suggestion to load directly into HL as follows and it seems to work so far, the first part call &9000 to erase and print and the second part call &901f to just erase.  Disk updated.  Not 100% sometimes some of the bombs don't get wiped so will look at that.

org &9000

ld h,(ix+04)
ld l,(ix+02)
call &bb75
ld a,32
call &bb5a
ld h,(ix+04)
ld l,(ix+02)
inc l
call &bb75
ld a,(ix+00)
call &bb5a
ret

ld h,(ix+02)
ld l,(ix+00)
call &bb75
ld a,32
call &bb5a
ret