1. LOS
I need a FAST routine that can check "line of sight" between two points.
This is for use in Hayes. I want to track a straight line from a to b, and
if somewhere on the way this line hits the wall, the routine returns 0. Else
it returns 1.
The sequence LEVEL is a 2D sequence, and to see if a given point lies on a
wall, you can do this:
if LEVEL[ypos/20+1][xpos/20+1] then
-- just hit the wall
end if
Can someone help me with this?
Einar
2. Re: LOS
-----Original Message-----
From: Einar Mogen <nord.staernes at ROLLAG.MAIL.TELIA.COM>
To: EUPHORIA at cwisserver1.mcs.muohio.edu
<EUPHORIA at cwisserver1.mcs.muohio.edu>
Date: Monday, August 24, 1998 7:05 PM
Subject: LOS
>I need a FAST routine that can check "line of sight" between two points.
>This is for use in Hayes. I want to track a straight line from a to b, and
>if somewhere on the way this line hits the wall, the routine returns 0.
Else
>it returns 1.
>
>The sequence LEVEL is a 2D sequence, and to see if a given point lies on a
>wall, you can do this:
>
>if LEVEL[ypos/20+1][xpos/20+1] then
> -- just hit the wall
>end if
>
>Can someone help me with this?
>
>Einar
>
you should find your self a good ray tracer!
3. Re: LOS
I apologize if this routine has already been sent. I'm committing a =
WFRL (write first, read later). The average time for each pass of the =
routine was .0001~.0006 seconds. Is that fast enough for you? However, =
it assumes you know the endpoints for the wall. The code is 121 lines.
------ Tested code ----------
-- nobisect.ex -- This function uses the algebraic line equation =
y=3Dmx+b.
atom t1, t2, ttot, temp
function nobisect(atom x1a,atom y1a,atom x1b,atom y1b,atom x2a,
atom y2a,atom x2b,atom y2b)
atom m1,m2,b1,b2,x3,y3
=20
-- 1 =3D wall, 2 =3D LOS
=20
-- Condition: vertical wall
=20
t1 =3D time()
=20
if x1a =3D x1b then
if x2b =3D x2a then
return 1
end if
m2 =3D (y2b-y2a)/(x2b-x2a)
b2 =3D y2b-(m2*x2b)
y3 =3D (m2*x1a)+b2
if (y1a > y1b) and (y3 <=3D y1a) and (y3 >=3D y1b) then
return 0
elsif (y3 >=3D y1a) and (y3 <=3D y1b) then
return 0
else
return 1
end if
end if
-- Condition: horizontal wall
=20
if y1a =3D y1b then
if x2b =3D x2a then
x3 =3D x2b
else
if y2a =3D y2b then
return 1
end if
m2 =3D (y2b-y2a)/(x2b-x2a)
b2 =3D y2b-(m2*x2b)
x3 =3D (y1a-b2)/m2
end if
if (x1a > x1b) and (x3 <=3D x1a) and (x3 >=3D x1b) then
return 0
elsif (x3 >=3D x1a) and (x3 <=3D x1b) then
return 0
else
return 1
end if
end if
-- Condition: vertical LOS
=20
if x2a =3D x2b then
if x1b =3D x1a then
return 1
end if
m1 =3D (y1b-y1a)/(x1b-x1a)
b1 =3D y1b-(m1*x1b)
y3 =3D (m1*x2a)+b1
if (y2a > y2b) and (y3 <=3D y2a) and (y3 >=3D y2b) then
return 0
elsif (y3 >=3D y2a) and (y3 <=3D y2b) then
return 0
else
return 1
end if
end if
=20
-- Condition: horizontal LOS
if y2a =3D y2b then
if x1b =3D x1a then
x3 =3D x1b
else
if y1a =3D y1b then
return 1
end if
m1 =3D (y1b-y1a)/(x1b-x1a)
b1 =3D y1b-(m1*x1b)
x3 =3D (y2a-b1)/m1
end if
if (x2a > x2b) and (x3 <=3D x2a) and (x3 >=3D x2b) then
return 0
elsif (x3 >=3D x2a) and (x3 <=3D x2b) then
return 0
else
return 1
end if
end if
-- Condition: both diagonals
=20
m1 =3D (y1b-y1a)/(x1b-x1a)
m2 =3D (y2b-y2a)/(x2b-x2a)
b1 =3D y1b-(m1*x1b)
b2 =3D y2b-(m2*x2b)
if m1 =3D m2 then
return 1
end if
x3 =3D (b2-b1)/(m1-m2)
if (x1a > x1b) and (x3 <=3D x1a) and (x3 >=3D x1b) then
return 0
elsif (x3 >=3D x1a) and (x3 <=3D x1b) then
return 0
else
return 1
end if
end function
ttot =3D 0
for a =3D 1 to 1000 do
temp =3D =
rand(100),rand(100))
t2 =3D time()-t1
ttot =3D ttot + t2
printf(1,"Average time: %0.5f, Result: %d\n",{ttot/a,temp})
end for
---------------
Michael J. Sabal
mjs at osa.att.ne.jp
http://home.att.ne.jp/gold/mjs/index.html
