Beyond Evil - now playable

[Heaven/TQA]

The simple Dx, Dy comparison gives you a rectangular strike area.

 

Going table-based with value pairs as I suggested gives you a polygonial strike area.

 

If you're simply adding the X and Y differences, you don't really get a distance value.

e.g. X or Y values are the same if the objects are aligned horizontally or vertically. So, you get a smaller value.

If the objects are 45 degrees apart but reasonably close, it could generate a bigger distance value using that approach.

I agree, that's why I was suggesting a 2D array lookup as part of the deal.

I figured the DX and DY skip checks eliminate anything outside the rectangle quickly (and the array) and then only close objects get the slower lookup.

Odds are that most monsters are out of range to start and since you kill monsters as you go you shouldn't see a slowdown.

It also only keeps the table as large as the maximum range a monster (any monster) can see.

Sinve different monsters see different distances then you have the added check after the table lookup to see if it's value exceeds that of the monster.

 

hmmm... just think about it but do not get it 100%... need to scribble on a graph paper... analytic geometry is long time ago...

 

James...for what are the difftables? what is dxy representing?

[JamesD]

hmmm... just think about it but do not get it 100%... need to scribble on a graph paper... analytic geometry is long time ago...

 

James...for what are the difftables? what is dxy representing?

Distance with x and y (Not just one or the other) from the lookup table. The actual integer distance.

Since we have differences in x and y we can use that to calculate the actual distance based on a triangle.

The relationship between sides of a triangle is A^2 + B^2 = C^2.

In our case A and B are DX and DY.

 

To calculate the long side C (DXY in my example) from the other two, you take the square root of A squared + B squared

That is slow so we build an array that contains pre-calculated distances converted to integers.

The array dimensions is the maximum difference allowed in x and y directions. (hence the skip before the lookup)

 

To build the table you would do something like this (use whatever the square root function is actually called):

 

DIM Dist(MaxX, MaxY)

FOR X = 0 TO MaxX

FOR Y = 0 TO MaxY

Dist(X,Y) = INT(SQRT(X^2 + Y^2))

NEXT Y

NEXT X

 

 

<edit>

The array lookup is for a 2d array on this. If you can just add the two (DX & DY) for a lookup value that would be faster. I'd need to check the math to see if it works though.

I didn't account for arrays starting at 0 so that will need fixed.

Edited April 19, 2009 by JamesD

[JamesD]

Since sides A and B of the triangle are interchangeable in the formula a 1D array should work and eliminate redundant values. I think.

 

DIM Dist(MaxX+MaxY+1) '+1 for 0?

FOR X = 0 to MaxX

FOR Y = 0 to MaxY

Dist(MaxX+MaxY) = INT(SQRT(DX^2+DY^2))

NEXT Y

NEXT X

 

If you look up distances using the two different tables and they match then it should work fine.

There is a REM at the end of the DIM statement btw

Edited April 19, 2009 by JamesD

[Rybags]

Too much data IMO, plus you need to calculate indexes to look stuff up.

 

I reckon the cut-down method I put forward would be better.

It's not like you need pixel exact precision for an imaginary circle around monsters... a polygon which approximates the shape and has a fraction of the number of table entries should be more than sufficient.

 

Kinda on this topic... the arcade version of Asteroids supposedly uses "collision hexagons". Would be interesting if the algorithm it uses was documented.

[JamesD]

Actually, that table is larger than it needs to be and could be cut back further since it handles larger values than needed.

But I've been thinking...

I think we will discover after looking at the table that DX+DY will have a maximum value for each distance (monster) and that is all you will need to check against rather than a lookup table. We have to look up that distance anyway, it will just be a pre-calculated max for DX+DY instead of actual distance.

So...

 

DX = ABS(X1-X2)

DY = ABS(Y1-Y2)

DXY=AX+DY

IF DXY > MonsterDistVal THEN skip

 

<edit>

Hmmm... if the maximum distance is 10 and the difference is only in the X direction then this value would be 10.

Same goes for Y difference only.

If DX is 5 and DY is 5 then actual distance is a little over 7, not 10.

This would yield an odd shape for the distance check.

A rectangle again only on a point.

A 1D array may not even work.

Edited April 19, 2009 by JamesD

[JamesD]

I ran the calculations, a 1D array doesn't give the same results.

[Rybags]

 

That's a representation of how the coverage would look with 5 table entries (5 degrees, 25, 45, 65, 85), calculated to a radius of 20 pixels.

 

Pretty close to a circle shape, cheap on memory use. Even smaller tables with less entries still look OK.

 

Actually, you can reduce the table size too since the entries for the angles >45 degrees are just swapped h/v versions of the earlier ones.

 

Dx	  Dy	Angle
1		 19	5
8		 18	25
14		14   45
18		8	 65
19		1	 85

[JamesD]

 

That's a representation of how the coverage would look with 5 table entries (5 degrees, 25, 45, 65, 85), calculated to a radius of 20 pixels.

 

Pretty close to a circle shape, cheap on memory use. Even smaller tables with less entries still look OK.

 

Actually, you can reduce the table size too since the entries for the angles >45 degrees are just swapped h/v versions of the earlier ones.

 

Dx	  Dy	Angle
1		 19	5
8		 18	25
14		14   45
18		8	 65
19		1	 85

It looks like Dx and Dy are inverse so you could just index from the opposite direction for Y?

[Rybags]

Yep.

 

Just calculate your Dx, Dy (differences).

 

Compare against the first 2 table entries, and compare Dx against Dy entry etc.

The third table entry is for 45 degrees, so Dx/Dy entries there should always be alike so you can omit one.

[Heaven/TQA]

just looking through maths books and the damned pythagoras... ages ago it was a piece of cake for me... Rybags...how do I calc your tables???

 

ts...

 

1006 DEG

1010 COLOR 1

1015 C=0

1016 FOR I=5 TO 89 STEP 20

1020 PLOT 20*SIN(I),20*COS(I)

1030 DXTAB©=INT(20*SIN(I))

1040 DYTAB©=INT(20*COS(I))

1050 C=C+1

1060 NEXT I

Edited April 19, 2009 by Heaven/TQA

[Heaven/TQA]

i guess this is correct?

 

0 DIM DXTAB(16),DYTAB(16)
1 EXEC DEMO
5 GRAPHICS 15
6 COLOR 1
10 DEG 
20 MX=RAND(40)
25 MY=RAND(40)
30 PX=RAND(40)
40 PY=RAND(40)
45 TEXT PX,PY,"P"
46 TEXT MX,MY,"M"
47 COLOR 2
48 CIRCLE MX,MY,20,40
50 EXEC TEST
60 GET K
70 GOTO 5
999 END 
1000 PROC DEMO
1005   GRAPHICS 7
1006   DEG 
1010   COLOR 1
1015   C=0
1016   FOR I=5 TO 89 STEP 20
1020	 PLOT 20*SIN(I),20*COS(I)
1030	 DXTAB(C)=INT(20*SIN(I))
1040	 DYTAB(C)=INT(40*COS(I))
1050	 C=C+1
1060   NEXT I
1099 ENDPROC 
1100 PROC TEST
1110   DX=ABS(MX-PX)
1120   DY=ABS(MY-PY)
1130   C=0
1135   RFLAG=0
1140   REPEAT 
1150	 IF DX>DXTAB(C) THEN 1190
1160	 IF DY>DYTAB(C) THEN 1190
1170	 RFLAG=1
1190	 C=C+1
1200   UNTIL C=5
1210   IF RFLAG=1 THEN PRINT "IN RANGE"
1220 ENDPROC

Edited April 19, 2009 by Heaven/TQA

[Rybags]

I think you've done similar to what I have. Although you'd be dealing with INT values in Assembler so probably an idea to round the values up.

 

I think my collision calculations are out though... you don't get a near-circle. You should get something like a stepped shape.

 

 

Something like that.

 

Here's the program I used to generate the tables and show the boundaries.

So, ignoring what I said before... you probably want a few more entries in the table to improve the resolution.

Also, since you might be working in multicolour 2:1 pixels, you can always adjust the calculation of the table so you get something nearer to circular rather than oval shape.

 

10 GOSUB 1000
20 GRAPHICS 7
25 COLOR 1
30 PLOT 80,80
35 FOR H=-1 TO 1 STEP 2:FOR V=-1 TO 1 STEP 2
40 FOR A=0 TO 3
50 PLOT 80+RX(A)*H,40+RY(A)*V
60 DRAWTO 80+RX(A+1)*H-1,40+RY(A)*V:DRAWTO 80+RX(A+1)*H-1,40
90 NEXT A
190 NEXT V:NEXT H
999 STOP 
1000 DEG :DIM RX(4),RY(4)
1010 FOR A=0 TO 4
1020 RX(A)=INT(SIN(A*20+5)*20)
1030 RY(A)=INT(COS(A*20+5)*20)
1040 NEXT A
1990 RETURN

Edited April 20, 2009 by Rybags

[Heaven/TQA]

but this approximation looks file. I will test tonight in Beyond code.

[Heaven/TQA]

interesting conversation on #c-64...

 

how would you simplify to following code?

 

lda #abs(mx-px)

ldy #abs(my-py)

cmp (lookup),y

bcs nohit

...

 

?

 

how would we need to setup the lookup table?

[Rybags]

I don't think it's quite that simple. The table should have multiple entries, so addressing becomes a bit more complex.

 

If the total table size is under 256 bytes per axis you could have a "monster type" byte which could become the low pointer.

You have to compare both Dx and Dy, and both need to fall within the boundaries to generate a "Yes" result for reachability.

[Heaven/TQA]

?

check_overlapping: 
	ldx #-1;default no overlapp
	lda mx;calc dx=abs(mx-px)
	sec
	sbc px
	bpl got_abs
	eor #$ff
	adc #1
got_abs;now accu has DX		
	cmp dxtab
	bcs no_overlap
	cmp dxtab+1
	bcs no_overlap
	cmp dxtab+2
	bcs no_overlap
	cmp dxtab+3
	bcs no_overlap
	cmp dxtab+4
	bcs no_overlap
;ok...we are here so dx is in range, now dy
	lda my
	sec
	sbc py
	bpl got_abs2
	eor #$ff
	adc #1
got_abs2;now accu has dy
	cmp dytab
	bcs no_overlap
	cmp dytab+1
	bcs no_overlap
	cmp dytab+2
	bcs no_overlap
	cmp dytab+3
	bcs no_overlap
	cmp dytab+4
	bcs no_overlap
;ok... we are in range
	ldx #1
no_overlap txa
	rts
	
;rangetab based on range 20/40 pixel
;dxtab	.byte 1,8,14,18,19
;dytab	.byte 39,36,28,16,3
;dxtab	.byte 0,4,7,9,9
;dytab	.byte 19,18,14,8,1		
dxtab	.byte 1,2,3,4,4
dytab	.byte 8,8,6,4,1

[Heaven/TQA]

check_overlapping: 
	ldx #-1;default no overlapp
	lda mx;calc dx=abs(mx-px)
	sec
	sbc px
	bpl got_abs
	eor #$ff
			clc
	adc #1
got_abs;now accu has DX		
	sta $06f0
	cmp dxtab
	bcc check_overlappy
	cmp dxtab+1
	bcc check_overlappy
	cmp dxtab+2
	bcc check_overlappy
	cmp dxtab+3
	bcc check_overlappy
	cmp dxtab+4
	bcs no_overlap
;ok...we are here so dx is in range, now dy
check_overlappy	lda my
	sec
	sbc py
	bpl got_abs2
	eor #$ff
			clc
	adc #1
got_abs2;now accu has dy
	sta $06f1
	cmp dytab
	bcc yes_overlap
	cmp dytab+1
	bcc yes_overlap
	cmp dytab+2
	bcc yes_overlap
	cmp dytab+3
	bcc yes_overlap
	cmp dytab+4
	bcs no_overlap
;ok... we are in range
yes_overlap	ldx #1
no_overlap txa
	rts
	
;rangetab based on range 20/40 pixel
dxtab	.byte 1,8,14,18,19
dytab	.byte 39,36,28,16,3

Edited April 23, 2009 by Heaven/TQA

[Heaven/TQA]

if (x2-x1)^2 + (y2-y1)^2 <= r^2 then collision

[Heaven/TQA]

if (x2-x1)^2 + (y2-y1)^2 <= r^2 then collision

[JamesD]

if (x2-x1)^2 + (y2-y1)^2 <= r^2 then collision

Like I said... A^2 + B^2 = C^2

But to keep it int you would put x and y in a 2D table to get C.

You would really need to limit the table by minimum x and y values to eliminate extra data.

Each x you eliminate is a total row from the table. Each y eliminated is a column.

 

That would mean

if( Table(x2-x1-min,y2-y1-min) <= range then collision

But there are lots of subtracts, 2 abs functions, and a multiply for the 2d table

 

The other approach is to pre square the r and to look up the square of x2-x1 on y2 - y1.

That would be 1 dimensional.

But if r exceeds 16 you have a table of 16 bit numbers.

<edit>

But if you halve the x and y (just a shift dropping the lsb) you cut the table size and can have an actual distance up to 32... just reduced resolution. (only changes of 2 (probably > 1.5) would register.

 

or I think that would work anyway.

Edited April 24, 2009 by JamesD

[Heaven/TQA]

I am testing another approach with a 512 byte sqrtable (lo,hi) and the above mentioned formular.

 

or... what about testing if 2 circles are overlapping? so one circle around the player and another circle of the monster?

 

have to check that formular, too...

[Rybags]

It gets a bit costly in terms of memory.

 

You could save some by reducing precision - divide all the values by 2 before testing.

 

That then means if you make your highest distance 16 (really 32), that translates to a radius of 4 characters. That's a third of the screen height (diameter).

 

I get 16 here, by saying "255 = 16 squared" - it's a small loss of precision which should make no difference.

[JamesD]

It gets a bit costly in terms of memory.

 

You could save some by reducing precision - divide all the values by 2 before testing.

 

That then means if you make your highest distance 16 (really 32), that translates to a radius of 4 characters. That's a third of the screen height (diameter).

 

I get 16 here, by saying "255 = 16 squared" - it's a small loss of precision which should make no difference.

That was the only thing I could come up with to drastically reduce table size without significant impact on function.

It's definitely worth a try.

[JamesD]

I am testing another approach with a 512 byte sqrtable (lo,hi) and the above mentioned formular.

 

or... what about testing if 2 circles are overlapping? so one circle around the player and another circle of the monster?

 

have to check that formular, too...

With the divide by 2 that's only 256 bytes... one page and much better in assembly.

Even the divide by 2 is simple and fast.

 

The only reason to do multiple circles is to double the possible distance which is already equaled with the divide by 2 at minimal cost to functionality.

It might result in a slightly jagged circle but that is a small price to pay and was a possible solution anyway.

Edited April 24, 2009 by JamesD

[JamesD]

BTW, I was thinking about redoing a BASIC game I wrote as a teenager in assembly and I originally used the A^2 + B^2 = C^2 formula.

The lookup table would have been sooooooooo much faster even in BASIC it's not even funny. I think that change alone might have doubled my frame rate.

 

Also, by 1D I meant lookup A^2, lookup B^2, and add those rather than use sqrt table.

Two lookups vs a multiply (for 2D array) and 1 lookup. I think the multiply is the deal breaker.

Precalculate C^2 when you load the monsters?

<edit>

C^2 should be precalculated outside the program.

Edited April 24, 2009 by JamesD