## Line of sight

Posts: 282

Joined: Sun Feb 13, 2011 3:33 am

Location: Kentucky US, used to be Birmingham UK

### Line of sight

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 IntegerDim x as Integerx=ABS(x1-x2)Dim y as Integery=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 angleDim dist as Integerdist=distance(X1,Y1,X2,Y2)dim bresiter as IntegerFor bresiter=0 To distbresx(bresiter)=0bresy(bresiter)=0NextDim steep as Integerif Abs(Y2-Y1) > Abs(X2-X1) thensteep=1elsesteep=0end ifPRINT AT 1,0 ; PAPER 1 ; INK 0 ; "steep "+STR(steep)   If steep =1 ThenDim Temp as IntegerTemp=X1X1=Y1Y1=TempTemp=X2X2=Y2Y2=TempEnd 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 distEnd Function`

create 2 arrays to hold the x and y coordinates of the line
Code:
`Dim bresx(350) as IntegerDim 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 Integerdist=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:UBytecan_see=1for x=0 to distif wall_in_way(bresx(x),bresy(x)) thencan_see=0end ifnextif can_see =1 then'yes they can see each otherend ifif can_see =0 then'no they can not see each otherend if`

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

### Re: Line of sight

slenkar wrote: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:UBytecan_see=1for x=0 to distif wall_in_way(bresx(x),bresy(x)) thencan_see=0EXIT FOR  ' <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< Jump out here.end ifnextif can_see =1 then'yes they can see each otherend ifif can_see =0 then'no they can not see each otherend if`

Posts: 282

Joined: Sun Feb 13, 2011 3:33 am

Location: Kentucky US, used to be Birmingham UK

### Re: Line of sight

ah yes very good thanks

Posts: 73

Joined: Fri May 07, 2010 7:34 am

### Re: Line of sight

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));}`

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

### Re: Line of sight

na_th_an wrote: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%.

Posts: 73

Joined: Fri May 07, 2010 7:34 am

### Re: Line of sight

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 (http://en.wikipedia.org/wiki/Taylor_series). If you need more accurate results, you can keep extending it with more elements.

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

### Re: Line of sight

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

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

### Re: Line of sight

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...

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

### Re: Line of sight

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

Posts: 282

Joined: Sun Feb 13, 2011 3:33 am

Location: Kentucky US, used to be Birmingham UK

### Re: Line of sight

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

Posts: 73

Joined: Fri May 07, 2010 7:34 am

### Re: Line of sight

britlion wrote: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

Site Admin

Posts: 1463

Joined: Wed Nov 01, 2006 6:18 pm

Location: Santa Cruz de Tenerife, Spain

### Re: Line of sight

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: http://code.boriel.com/zxbasic/changesets (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).

Posts: 73

Joined: Fri May 07, 2010 7:34 am

### Re: Line of sight

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

Code:
`Dim lsb, msb as uByteDim 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 uByteDim 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.

Site Admin

Posts: 1463

Joined: Wed Nov 01, 2006 6:18 pm

Location: Santa Cruz de Tenerife, Spain

### Re: Line of sight

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

Code:
`Dim lsb, msb as uByteDim 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 uByteDim address as uInteger...address = lsb + CAST(Uinteger, msb) << 8`

na_th_an wrote:In the same fashion:

Code:
`Dim x, cx as uByteDim 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.

Posts: 73

Joined: Fri May 07, 2010 7:34 am

### Re: Line of sight

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, msbDim as uInteger addressDim as uByte x, cxDim as Integer dxlsb = 0: msb = 60x = 0: cx = 100address = lsb + (msb Shl 8)Print addressdx = x - cxPrint 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 aEnd SubDim as uByte x, cxx = 0: cx = 100printMe (x-cx)`

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

Boriel wrote:[...]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 - cyDraw 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.
Next

Return to How-To & Tutorials

### Who is online

Users browsing this forum: No registered users and 1 guest

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by Vjacheslav Trushkin for Free Forums/DivisionCore.