Log In  

Line Of Sight Function

I`ve created a Line-Of-Sight function that should work for most projects. It checks for map-collisions(using flag0 as the collision layer). Please use it and let me know what you do with it!

I was inspired by this post: https://www.lexaloffle.com/bbs/?tid=48889
But i wanted a simpler starting point for my own approach. A Line Of Sight check is a good starting point for you own approach but also involves some math. So to bypass that step use my function:

UPDATE 16/9/22
added a optional length-variable. Use it to define a max "range" of the that line. Keep in mind that the function already neglects far away points.
Also added a new break point for perfomance.

function can_see(x1,y1,x2,y2,length)
--x1 and y1 are the point of view,length is the max distance of the two points
    local max_length=length or 1000
    local xvec=0
    local yvec=0
    local len=0
    local ret=true  
    local tx=x1
    local ty=y1
    xvec=x2-x1
    yvec=y2-y1
    len=sqrt(xvec^2+yvec^2)
    if len==0 or len>max_length then
     ret=false
    end
    xvec=(xvec/len)
    yvec=(yvec/len)
    if ret then
        for i=1,len do
        tx+=xvec
        ty+=yvec
            if fget(mget(flr(tx/8),flr(ty/8)),0) then
                ret=false
                break
            end
        end
    end
    return ret
end

Features (if you're intrested)

  • handling LOOONG Distances with a big "Nay" from the function
  • always checking from x1/y1 point of view
  • stopping when no more calculations are necessary

How it works

  • set standard return to a yes (true)
  • create a directional vector from 1 to 2
  • calculate the distance of that vector
  • check wether that distance is too big
  • normalize it(max it out at 1) with that distance(so your steps don't get bigger than 8(which would skip a whole sprite, thus negating the whole point of this function))
  • loop through incremental steps with that normalized vector
  • check for collisions on each point
  • if a collision occurs change the output to no and exit the loop to save power

How you might use it(and how i use it)

  • Use it for a stealth game and combine it with the general direction the enemys are facing
  • Use it for shooting stuff to see how far things will go
  • Use it as a starting point for a raycast by returning the distance the ray traveled (I'd like to do that too)
  • I'm making my first roguelike to learn about Mazecreations and get better at making fights fun (Which i'm terrible at)
  • in this game the enemys, similar to that post linked above, remember the last point where they saw you and approach that point(the white dot). They also have a timer, so they only try to spot you every now and then.

You can find a minimal setup for the function right here:

Cart #lineofsight-1 | 2022-09-02 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
16

P#116768 2022-09-02 10:18 ( Edited 2022-09-16 06:44)

Wow this is amazing! I'm saving this one to use on future games. Makes me glad to know you were inspired by my bullet trail approach :D yours is way more elegant! 10/10

P#116782 2022-09-02 16:02
1

Thank you! But yours had all the bells and whistles, mine is really just one part of your great system!

P#116795 2022-09-02 21:12
1

This should be possible to do without using SQRT() or exponent, @taxicomics.

Also does it register bricks not just below but above ?

Hmm ... This stands to write code.

Cart #kebuyusejo-0 | 2022-09-02 | Code ▽ | Embed ▽ | No License
1

Here now, your routine works perfectly !

Use arrow keys to control both sprites. Swap between which with ❎.

P#116798 2022-09-02 22:07 ( Edited 2022-09-02 22:50)
1

What do you mean by below or above?
If you`re talking about the width of the line-yes, i have been thinking about that. Maybe ill add another line so the FOV gets a little less tight, but that'll cost more power. But in some situations it might be able to see through a wall if the two tiles have just one joined corner.

And yes, i do remember that there was a neat way to avoid sqrt, but as i figured that my application only deals with numbers smaller than 128 i did not utilize it.

P#116800 2022-09-02 22:25
1

Actually no problems, @taxicomics. It works perfectly. Try the demo above to really see it works in all situations.

Well done, gold star work !

P#116802 2022-09-02 22:51
3

Thought I would try to recode that without the exponent or SQRT. Here is what I have:

Cart #nipuwuwoda-0 | 2022-09-02 | Code ▽ | Embed ▽ | No License

function can_see2(a,b,c,d)
local e,f=abs(a-c),abs(b-d)
  if (e<f) e=f
  e=max(1,e)
  repeat
    if (fget(mget(c\8,d\8),0)) return
    c+=(a-c)/e
    d+=(b-d)/e
  until a==(c+.5)\1 and b==(d+.5)\1
  return true
end
P#116804 2022-09-02 23:21
1

Cart #geyatoyazu-0 | 2022-09-03 | Code ▽ | Embed ▽ | No License
1

Here is a further variation. This one checks only grid boxes assuming that all sprites to move in an 8x8 format.

Use arrow keys to navigate. Press ❎ to swap between control of sprite. If one can see the other, the background will tint dark blue, otherwise black.

The dots you see are the line of sight and optionally drawn in the function.

P#116827 2022-09-03 15:37

Hey, thanks for the rewrite! Intresting approches too, now this is the perfect compilation for everybody to choose a version depending on their needs. Good collab!

P#116883 2022-09-04 17:10

Yup ! Quite a few choices, @taxicomics. Now if I could just write AStar or MyStar in code as small or smaller than I've done above we'd be all set. :)

And yes, that would be a great internal function to add to future Pico-8.

_can_see(x1,y1,x2,y2,v,{sx,sy,ex,ey,{a[]})

x1 + y1 = coordinates of player.
x2 + y2 = coordinates of target.
      v = value looked for.
sx + sy = start of area to look (default 0,0)
ex + ey = end of area to look (default 63,63)
      a = array, if not nil use array[sizex][sizey],
          otherwise if nil then use map() as normal.

wallid=1
if _can_see(playerx,playery,enemyx,enemyy,wallid) then ...

scrn={}
for i=0,15 do
  scrn[i]={}
  for j=0,15 do
    scrn[i][j]=0
  end
end
b=_can_see(playerx,playery,enemyx,enemyy,wallid,0,0,15,15,scrn)
P#116884 2022-09-04 17:25

Those two bundled would be great! I haven't done any A-star-stuff yet, i used the native pathfinding in Godot but i never wrote my own.
But for A-Star you need a little more code around the function, so i think it is not as straightforward to implement as can_see(). But maybe if it is bundled with the movement and maybe a speed or time() variable, then it might be easier to use for beginners.
Like a Move_To(x1,y1,x2,y2,Speed_in_pixels,collision_flag) that returns the progress or proximity.

P#116926 2022-09-05 12:43 ( Edited 2022-09-05 12:44)

I added a new optional variable to the function that i needed in a new project. length, the optional fifth variable, now specifies the max length of that line of sight.

function can_see(x1,y1,x2,y2,length)
--x1 and y1 are the point of view
    local max_length=length or 1000
    local xvec=0
    local yvec=0
    local len=0
    local ret=true  
    local tx=x1
    local ty=y1
    xvec=x2-x1
    yvec=y2-y1
    len=sqrt(xvec^2+yvec^2)
    if len==0 or len>max_length then
     ret=false
    end
    xvec=(xvec/len)
    yvec=(yvec/len)
    if ret then
        for i=1,len do
        tx+=xvec
        ty+=yvec
            if fget(mget(flr(tx/8),flr(ty/8)),0) then
                ret=false
                break
            end
        end
    end
    return ret
end
P#117503 2022-09-16 06:45

If I wanted to use this sort of thing in a platformer, such as to have an archer enemy check for line of site whenever player.y is within 10 pixels of archer.y, then if true, fire an arrow in the direction of the player, would that work?

P#123545 2023-01-02 23:04

This is a very very late reply to your question, but yes, you're right. You could use that function and modify it so it returns the xvec,yvec and ret as a table. So just change the very last line to return [ret,xvec,yvec].
Then you use the xvec( [1] ) and yvec ( [2] ) as the trajectory for the arrow. you can also multiply them to make the arrow faster or slower.

P#135520 2023-10-06 18:26
2

This entire discussion has been very enlightening as a new learner of PICO-8!

@taxicomics I like and understand your code and this is certainly the approach I would have taken myself, however I have come to understand that there are issues with this method of taking distance both in terms of cycle cost (^ and sqrt are both somewhat costly [x*x is better for squares]) and due to the possibility of overflow (e.g.: 128^2+128^2 will wrap around to -32768 so distances approaching 1000 would get troublesome).

Here we have a much better discussion on taking distance than I can provide:
 https://www.lexaloffle.com/bbs/?pid=90968

@dw817 I trust that your code is effective and efficient but I don't fully understand the method it is using. But, this has helped my understanding of PICO-8!

Needing a line-of-sight function (with distance check) that's effective, efficient, and not prone to overflow, I sought to write my own incorporating what I've learned and using a method I understand:

--by koz, CC0 (free to use)
function sees(x1, y1, x2, y2, d)
 local dx,dy=x2-x1,y2-y1
 local adx,ady=abs(dx),abs(dy)
 if (adx>d or ady>d) return --too far on any axis
 if ((dx/d)*(dx/d)+(dy/d)*(dy/d)>1) return --fails mot's "within dist"
 if (adx>ady) then
  for i=0,dx,sgn(dx) do
   if (fget(mget((x1+i)/8, (y1+i*dy/dx)/8),0)) return
  end
 else
  for i=0,dy,sgn(dy) do
   if (fget(mget((x1+i*dx/dy)/8, (y1+i)/8),0)) return
  end
 end
 return true
end

We take the difference in X and in Y (a.k.a. "run" and "rise" respectively), and their absolute values, and we use these for a basic axis/manhattan dist check, and then perform the "within distance" check given by @Mot in the distance discussion above. (The trick is, basically, we don't actually calculate distance but rather simply test if the d value would be long enough to be our hypotenuse. No sqrt or even trig, cool!)

We perform these "escapes" as quickly as possible to avoid running further unnecessary code. You can use "return" immediately rather than setting a value to return at the end of the function to prevent the further code in that function from having to execute needlessly (or having to keep track of escape conditions to skip code). Also, we can use "return" in place of "return false" (false is default) to save a token. (Learned this from @dw817's post)

If both escape checks are passed, we begin checking for LOS in earnest:
First we determine if our rise or run are longer as we'll be iterating over the number of pixels in that direction. Then, we iterate in that direction on the given axis by the sign of that (rise or run) value (which evaluates to +1 or -1) and use our slope to get the other coordinate at each step, finally passing each of these coordinates to a classic fget(mget(x/8,y/8),0) call to get the state of the 0 flag of the map tile at that pixel.

(This function assumes tiles with flag 0 are obstacles to sight.)

Be aware: Because this is a per-pixel check, two diagonally adjacent tiles can allow "sight" to pass between their corners. If your game uses orthogonally adjacent tiles only, this is not a concern:
  

Note: This example iterates by one pixel at a time, but multiplying the for pace (e.g.:2*sgn()) can allow us to step 2, 3 or more pixels at a time which will still work fairly well, reduce the cycle load, but allow a little more tolerance for "sight" to pass around corners. I wouldn't recommend going as high as 4, shown here (X and O can "see" each other):
  

And here's a cart demonstrating the function:

Cart #koz_los_demo_0-0 | 2023-12-01 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
2

I'm certain that this function is not maximally efficient in cycles or token usage, so I fully invite further refinement from the community!

Also, if I have gotten anything simply wrong here, please let me know! I am still learning.

Thanks to everyone in the PICO-8 community!

P#138099 2023-12-01 18:28
1

@kozm0naut Thanks for the effort you put in! I like your approach too, and I learned that return returns false by default, which I did not know. Thanks!
Maybe I'll rename my function and use that to have my code exit the function AsAP. My function does skip the big for loops if it overflows or the distance is greater than what is desired though.
My function does check for overflow, but using sqrt is still inefficient in theory. I never had problems using it though, my latest 3d ish game uses that exact function and it doesn't have the biggest impact on performance.

I like the step idea a lot, maybe as an optional parameter. @dw817 did something similar with limiting the checks to unchecked 8x8 grid tiles.

So thanks again for offering yet another approach and a learning opportunity, now people finding this page have yet another approach to use.

Maybe we should rewrite our functions as raycast functions, so just a starting point and a direction which returns the distance achieved or a specific object. These functions can already to that, but a specific rewrite would feel less hacky and be more comfortable for people who need only the raycast bit.

P#138132 2023-12-02 09:53
1

@taxicomics, in fact there's a difference between return and return false :
If you use return without parameter, there is no return value.
If you try to use the non-existent return value on the caller side, you get NIL.
It's just that Lua considers NIL and false as not true and everything else as true (including things like 0 or ""), so it saves a token in a boolean return context to not return anything.

P#141432 2024-02-12 17:42 ( Edited 2024-02-12 18:03)

I revised the function from my post above to also check for view angles for entities that have a facing angle and field-of-view, since that is also often used in conjunction to determine sighting:

--by koz, cc0 (free to use)
--sees: return true if point at x1,y1 can "see" x2,y2 (nil otherwise)
-- dist: max distance (>1)
-- facing: center angle of field-of-view
-- sweep : angle extent of fov from center (.25=180deg fov)
-- incr: maximum number of pixels to progress by during check
-- obst: tile flag for obstacles to sight
function sees(x1, y1, x2, y2, dist, facing, sweep, incr, obst)
 local d=dist or 128
 local fac=facing or 0
 local swp=sweep or 1
 local incr=incr or 1
 local obst=obst or 0
 if (d<=1 or incr<1 or swp==0) return --invalid arguments / blind
 local dx,dy=x2-x1,y2-y1
 local adx,ady=abs(dx),abs(dy)
 if (adx>d or ady>d) return --too far on any axis
 if (dx/d*dx/d+dy/d*dy/d>1) return --fails mot's "within dist"
 local adif=abs(fac-atan2(dx, dy))%1
 if (adif>swp and (1-adif)>swp) return --facing away
 if (adx>ady) then
  for i=0,dx,incr*sgn(dx) do
   if (fget(mget((x1+i)/8, (y1+i*dy/dx)/8),obst)) return --{x=x1+i,y=y1+i*dy/dx}
  end
 else
  for i=0,dy,incr*sgn(dy) do
   if (fget(mget((x1+i*dx/dy)/8, (y1+i)/8),obst)) return --{x=x1+i*dx/dy,y=y1+i}
  end
 end
 return true
end

I've also added a few more parameters to cover some more use cases. If using this for your own projects, feel free to pull code you don't need and remove parameters and hard-code your own values as you see fit to save tokens and CPU cycles. Obviously the comments can be pulled to save characters.

This should be useful for top-down sneaking games and the like ;) I continue to invite further feedback and refinement from the community!

Cheers!

P#141436 2024-02-12 20:30 ( Edited 2024-02-12 20:42)

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-28 14:41:40 | 0.080s | Q:54