Line of sight

[slenkar]

To see if 2 game characters can see each other you need 2 functions

distance:

Code:

Function distance (x1 as Integer, y1 as Integer, x2 as Integer, y2 as Integer) as Integer
Dim x as Integer
x=ABS(x1-x2)
Dim y as Integer
y=ABS(y1-y2)

Return Sqr((x^2)+(y^2))
End Function

line:

Code:

Function line(X1 as Integer,Y1 as Integer,X2 as Integer,Y2 as Integer) as Integer
'creates a line of individual co-ords from X1,Y1 to X2,Y2 at any angle

Dim dist as Integer
dist=distance(X1,Y1,X2,Y2)
dim bresiter as Integer
For bresiter=0 To dist
bresx(bresiter)=0
bresy(bresiter)=0
Next

Dim steep as Integer
if Abs(Y2-Y1) > Abs(X2-X1) then
steep=1
else
steep=0
end if

PRINT AT 1,0 ; PAPER 1 ; INK 0 ; "steep "+STR(steep)
  
If steep =1 Then
Dim Temp as Integer
Temp=X1
X1=Y1
Y1=Temp
Temp=X2
X2=Y2
Y2=Temp
End If
   Dim DeltaX as Integer
    DeltaX=Abs(X2-X1)
   Dim DeltaY as Integer
    DeltaY=Abs(Y2-Y1)
   Dim IError as Integer
    IError=0
   Dim DeltaError as Integer
    DeltaError=DeltaY
   Dim x as Integer
    x=X1      'Start at X1,Y1
   Dim y as Integer
    y=Y1      
   Dim XStep as Integer
   Dim YStep as Integer
   If X1<X2 Then
    XStep=1
    Else
    XStep=-1
    end if
    If Y1<Y2 Then
    YStep=1
    Else
    YStep=-1   'Direction
   end if
   Dim iter as Integer
    iter=1
  
   While x<>X2
      x=x+XStep      'Move in X
      IError=IError+DeltaError      'Add to counter
      If (IError SHL 1)>DeltaX then      'Would it overflow?
      y=y+YStep      'Move in Y
      IError=IError-DeltaX      'Overflow/wrap the counter
      End if
  
   If steep then
      bresx(iter)=y
      bresy(iter)=x
   Else
      bresx(iter)=x
      bresy(iter)=y
   End If
      iter=iter+1
      
   If iter>dist then
  'Print  at 3,0;PAPER 1;INK 0;"bresenham over distance "+STR(dist)
   Return dist
   End If
  
   Wend
   Return dist
End Function

create 2 arrays to hold the x and y coordinates of the line

Code:

Dim bresx(350) as Integer
Dim bresy(350) as Integer

The size of the arrays should be the distance of the longest line you intend to create
a line going across the screen of the speccy is about 322 in length

You have 2 characters on a playing field that has x and y coordinates

you call the line function:
one character is at 1,1
the other is at 100,95

Code:

Dim dist as Integer
dist=line(1,1,100,95)

then finally you go through the co-ordinates on the line to check if anything is in the way, like walls or other characters

Code:

Dim can_see:UByte
can_see=1
for x=0 to dist
if wall_in_way(bresx(x),bresy(x)) then
can_see=0
end if
next

if can_see =1 then
'yes they can see each other
end if
if can_see =0 then
'no they can not see each other
end if

[britlion]

It occurs to me you can speed this up, if you quit checking as soon as you know they can't see by exiting the loop:

Code:

Dim can_see:UByte
can_see=1
for x=0 to dist
if wall_in_way(bresx(x),bresy(x)) then
can_see=0

EXIT FOR  ' <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Jump out here.

end if
next

if can_see =1 then
'yes they can see each other
end if
if can_see =0 then
'no they can not see each other
end if

[slenkar]

ah yes very good thanks

[na_th_an]

There's a much faster distance formula, which doesn't require square roots, albeit it's not as precise, but it works. It's what I use in my games - I can't afford a square root per frame so I just...

Code:

Function distance (x1 as uByte, y1 as uByte, x2 as uByte, y2 as uByte)
   dim dx as uByte
   dim dy as uByte
   dim mn as uByte

   dx = Abs (x2 - x1)
   dy = Abs (y2 - y1)
  
   If dx < dy Then
      mn = dx
   Else
      mn = dy
   End If

   Return (dx + dy - (mn >> 1) - (mn >> 2) + (mn >> 4))
End Function

Roughly translated from C code, but should work:

Code:

unsigned char distance (unsigned char x1, unsigned char y1, unsigned char x2, unsigned char y2) {
    unsigned char dx = abs (x2 - x1);
    unsigned char dy = abs (y2 - y1);
    unsigned char mn = dx < dy ? dx : dy;
    return (dx + dy - (mn >> 1) - (mn >> 2) + (mn >> 4));
}

[britlion]

There's a much faster distance formula, which doesn't require square roots, albeit it's not as precise, but it works. It's what I use in my games - I can't afford a square root per frame so I just...

Roughly translated from C code, but should work:

Code:

unsigned char distance (unsigned char x1, unsigned char y1, unsigned char x2, unsigned char y2) {
    unsigned char dx = abs (x2 - x1);
    unsigned char dy = abs (y2 - y1);
    unsigned char mn = dx < dy ? dx : dy;
    return (dx + dy - (mn >> 1) - (mn >> 2) + (mn >> 4));
}

So in a right angle triangle with sides A and B, and hypotenuse H, it returns (A+B) - (half the smallest of A and B) - (1/4 the smallest of A and B) + (1/16 the smallest of A and B) ?

I just put that into excel. That's...actually surprisingly good - though the error does go up as high as 7% sometimes. If you int the values, It's likely to be solid for x|y < 4, but can actually compound errors to 13%.

[na_th_an]

I've used it in several games and it works quite fine. A couple of pixels aren't big deal when it comes to fast-paced action. Square-rooting is quite slow for something you need to do in every frame.

I think the formula was derived from extracting the Taylor series related to sqrt X (<!-- m --><a class="postlink" href="http://en.wikipedia.org/wiki/Taylor_series">http://en.wikipedia.org/wiki/Taylor_series</a><!-- m -->). If you need more accurate results, you can keep extending it with more elements.

[britlion]

But...but...but...I wrote a really cool integer square root function. And it was REALLY hard to do...because I'm not a mathematician, and it gave me a headache!

(Yours is presumably faster, though. I'll give you that. It's sacrificing another layer of accuracy for it).

To be fair, mine does run in constant time, based on the number of bits in the input - 16 or 32. You can very easily, if sticking with 16 bit unputs, carve off the 16 bit version at the end, unroll the 7 * loop, and it will be done pretty darn quick. I'm tempted to add that version to see off the competition

[britlion]

A quick speed test of

answer=distance (i,j) against
answer=iSqrt(i*i+j*j) shows:

• distance 8.98 seconds
  iSqrt 50.1 seconds
  

This is definitely faster, if you're willing to accept the greater inaccuracy. (you probably are).

By the by - standard floating point square root:

my fSQRt function: 44 minutes (2625.14 seconds)
SQR - 122 minutes. (7336.86 seconds)

Shows how awful that ROM SQR routine really is...

[britlion]

I've added distance.bas to the ZX Basic Wiki in the library section. May it be useful in your games!

[slenkar]

thanks that would be useful for making a vector type game ^_^

[na_th_an]

A quick speed test of

answer=distance (i,j) against
answer=iSqrt(i*i+j*j) shows:

• distance 8.98 seconds
  iSqrt 50.1 seconds
  

This is definitely faster, if you're willing to accept the greater inaccuracy. (you probably are).

By the by - standard floating point square root:

my fSQRt function: 44 minutes (2625.14 seconds)
SQR - 122 minutes. (7336.86 seconds)

Shows how awful that ROM SQR routine really is...

Impressive results. I have a couple of uses for your fSQRt function - thanks for sharing

[boriel]

Don't know if I previously commented this, but those routines could be used in the near :?: (ahem...) future, by using --fast-floating-point or --fast-math (can't recall the 'standard' parameter name) ZX Basic will use available faster functions (SQR, SIN, COS, etc...) instead of the ROM ones at expenses of memory.

Also --use-rom-print (or the like) will remove PRINT routine and use the ROM's one (slower, but saves memory and you can use if for games in which you use your own sprite routine).

The problem is I'm at the moment refactoring (heavy!) the compiler in a new branch, 2.x: <!-- m --><a class="postlink" href="http://code.boriel.com/zxbasic/changesets">http://code.boriel.com/zxbasic/changesets</a><!-- m --> (see cyan commit line). This pre-alpha almost can't compile anything, so use to test the compiler only. This branch will eventually lead to a more well-designed compiler toolkit (allowing other architectures in a easier way, and more people to contribute on it).

[na_th_an]

While you are at it, you should try to solve the type casting of some expressions... This should work:

Code:

Dim lsb, msb as uByte
Dim address as uInteger

...

address = lsb + (msb << 8)

But it doesn't, as it tries to shoft msb left 8 times but using 8 bits, so it always equals 0. You have to define msb as uInteger for it to work correctly.

In the same fashion:

Code:

Dim x, cx as uByte
Dim dx uInteger

...

dx = x - cx

dx is always positive, as x and cx are unsigned... But the results should be considered signed integer, and not unsigned char.

I find this to be the biggest problem with the compiler. No other language that I know behaves that way, and it forces you to find dirty walkarounds.

[boriel]

While you are at it, you should try to solve the type casting of some expressions... This should work:

Code:

Dim lsb, msb as uByte
Dim address as uInteger

...

address = lsb + (msb << 8)

But it doesn't, as it tries to shoft msb left 8 times but using 8 bits, so it always equals 0. You have to define msb as uInteger for it to work correctly.

Are you sure C does not behave this way? I mean msb (as char) << 8 should be 0 in C also.
Anyway, you can enforce typecast explicitly, using CAST:

Code:

Dim lsb, msb as uByte
Dim address as uInteger

...

address = lsb + CAST(Uinteger, msb) << 8

In the same fashion:

Code:

Dim x, cx as uByte
Dim dx uInteger

...

dx = x - cx

dx is always positive, as x and cx are unsigned... But the results should be considered signed integer, and not unsigned char.
I find this to be the biggest problem with the compiler. No other language that I know behaves that way, and it forces you to find dirty walkarounds.

I need an example in other languajes (ej. C), because as far as I know, dx variable is positive only if x is ALWAYS >= cx. I will use CAST(Uinteger, x) to avoid this problem.

[na_th_an]

I usually code in C, and I can assure you that this code works as intended

Code:

#include <stdio.h>

void main (void) {
    unsigned char lsb = 0;
    unsigned char msb = 60;
    unsigned int address;
    
    unsigned char x = 0, cx = 100;
    int dx;
    
    address = lsb + (msb << 8);
    printf ("%d\n", address);
    
    dx = x - cx;
    printf ("%d\n", dx);
}

15360 and -100 are printed on screen. This works in any C compiler I've tried so far (z88dk and gcc).

Freebasic also works this way:

Code:

Dim as uByte lsb, msb
Dim as uInteger address
Dim as uByte x, cx
Dim as Integer dx

lsb = 0: msb = 60
x = 0: cx = 100

address = lsb + (msb Shl 8)
Print address

dx = x - cx
Print dx

Also prints 15360 and -100. Usually, operands are automaticly casted to the result type. This also works when calling a function. This should print -100:

Code:

Sub printMe (a as Integer)
   Print a
End Sub

Dim as uByte x, cx

x = 0: cx = 100
printMe (x-cx)

Anyways, good to know about Cast. I should read the docs more often...

[...]as far as I know, dx variable is positive only if x is ALWAYS >= cx. I will use CAST(Uinteger, x) to avoid this problem.

It doesn't work correctly, I've just found it. Instead of

Code:

Draw x - cx, y - cy

With all variables involved typed "uByte", DRAW always draws up and right (i.e.: positive). So I changed it to:

Code:

dx = x - cx: dy = y - cy
Draw dx, dy

With dx and dy typed Integer. Stil didn't work. dx and dy were always positive. I had to do this:

Code:

            dx = x: dx = dx - cx
            dy = y: dy = dy - cy
            Draw dx, dy

And then it worked.