.jpg)
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:
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
Thank you! But yours had all the bells and whistles, mine is really just one part of your great system!
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.
Here now, your routine works perfectly !
Use arrow keys to control both sprites. Swap between which with ❎.
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.
Actually no problems, @taxicomics. It works perfectly. Try the demo above to really see it works in all situations.
Well done, gold star work !
Thought I would try to recode that without the exponent or SQRT. Here is what I have:
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
|
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.
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!
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)
|
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.
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 |
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?
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.
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:
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!
@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.
@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.
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!
Wow, I had no idea you made this.
That why you asked for my code, to see if I made a better version.
[Please log in to post a comment]
