Line of sight - Printable Version

Line of sight - Printable Version

+- Forum (https://www.boriel.com/forum)
+-- Forum: Compilers and Computer Languages (https://www.boriel.com/forum/forumdisplay.php?fid=12)
+--- Forum: ZX Basic Compiler (https://www.boriel.com/forum/forumdisplay.php?fid=11)
+---- Forum: How-To & Tutorials (https://www.boriel.com/forum/forumdisplay.php?fid=13)
+---- Thread: Line of sight (/showthread.php?tid=427)

Pages: 1 2

Line of sight - slenkar - 02-15-2012

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

Re: Line of sight - britlion - 02-20-2012

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

Re: Line of sight - slenkar - 02-22-2012

ah yes very good thanks Big Grin

Re: Line of sight - na_th_an - 02-23-2012

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

}

Re: Line of sight - britlion - 02-23-2012

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

Re: Line of sight - na_th_an - 02-24-2012

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

Re: Line of sight - britlion - 02-25-2012

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 Wink

Re: Line of sight - britlion - 02-27-2012

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

Re: Line of sight - britlion - 02-27-2012

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

Re: Line of sight - slenkar - 02-28-2012

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

Re: Line of sight - na_th_an - 02-29-2012

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 Smile

Re: Line of sight - boriel - 02-29-2012

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: <a class="postlink" href="http://code.boriel.com/zxbasic/changesets">http://code.boriel.com/zxbasic/changesets</a> (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).

Re: Line of sight - na_th_an - 02-29-2012

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.

Re: Line of sight - boriel - 02-29-2012

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

na_th_an Wrote: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.

Re: Line of sight - na_th_an - 02-29-2012

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

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

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