FAQ  •  Register  •  Login

Line of sight

<<

slenkar

Posts: 282

Joined: Sun Feb 13, 2011 3:33 am

Location: Kentucky US, used to be Birmingham UK

Post Wed Feb 15, 2012 6:56 pm

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

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

Post Mon Feb 20, 2012 2:32 am

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

Posts: 282

Joined: Sun Feb 13, 2011 3:33 am

Location: Kentucky US, used to be Birmingham UK

Post Wed Feb 22, 2012 1:54 pm

Re: Line of sight

ah yes very good thanks :D
<<

na_th_an

Posts: 73

Joined: Fri May 07, 2010 7:34 am

Post Thu Feb 23, 2012 1:55 pm

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

britlion

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

Post Thu Feb 23, 2012 3:33 pm

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

na_th_an

Posts: 73

Joined: Fri May 07, 2010 7:34 am

Post Fri Feb 24, 2012 10:27 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.
<<

britlion

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

Post Sat Feb 25, 2012 10:16 pm

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

britlion

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

Post Mon Feb 27, 2012 7:12 pm

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

britlion

Posts: 766

Joined: Mon Apr 27, 2009 7:26 pm

Location: Slough, Berkshire, UK

Post Mon Feb 27, 2012 8:18 pm

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

slenkar

Posts: 282

Joined: Sun Feb 13, 2011 3:33 am

Location: Kentucky US, used to be Birmingham UK

Post Tue Feb 28, 2012 11:04 pm

Re: Line of sight

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

na_th_an

Posts: 73

Joined: Fri May 07, 2010 7:34 am

Post Wed Feb 29, 2012 12:00 pm

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

boriel

Site Admin

Posts: 1463

Joined: Wed Nov 01, 2006 6:18 pm

Location: Santa Cruz de Tenerife, Spain

Post Wed Feb 29, 2012 12:08 pm

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

na_th_an

Posts: 73

Joined: Fri May 07, 2010 7:34 am

Post Wed Feb 29, 2012 1:32 pm

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

Site Admin

Posts: 1463

Joined: Wed Nov 01, 2006 6:18 pm

Location: Santa Cruz de Tenerife, Spain

Post Wed Feb 29, 2012 1:49 pm

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

na_th_an

Posts: 73

Joined: Fri May 07, 2010 7:34 am

Post Wed Feb 29, 2012 3:17 pm

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

Return to How-To & Tutorials

Who is online

Users browsing this forum: No registered users and 1 guest

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

phpBB SEO