[Help] Writing a Field Of View scanner
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
[Help] Writing a Field Of View scanner
As you probably know I maintain an advanced mob mod called Creatures. Despite mobs being almost feature complete, there's one more thing I'd still like to add: Field of view simulation. Currently mobs can see people who are behind them, and that's obviously not very realistic... we want them to only notice targets within their field of perspective.
Problem is that I'm not sure what formula I should write up to fix this. Basically I work with the following parameters: position1 (the mob's location), yaw1 (the mob's rotation), fov1 (the mob's field of vision in degrees), position2 (the target's location). How would I be able to determine if at rotation yaw1, through the focal length fov1, position2 can be seen from the perspective of position1? Basically compute the virtual cone from position1 and know if position2 is within it.
I imagine it's not a very complex formula, but still more than my mind can work out on its own right now. If someone with a more functional brain could offer one, that would be very appreciated!
Problem is that I'm not sure what formula I should write up to fix this. Basically I work with the following parameters: position1 (the mob's location), yaw1 (the mob's rotation), fov1 (the mob's field of vision in degrees), position2 (the target's location). How would I be able to determine if at rotation yaw1, through the focal length fov1, position2 can be seen from the perspective of position1? Basically compute the virtual cone from position1 and know if position2 is within it.
I imagine it's not a very complex formula, but still more than my mind can work out on its own right now. If someone with a more functional brain could offer one, that would be very appreciated!

 Member
 Posts: 115
 Joined: Sun Feb 22, 2015 07:11
 GitHub: melzua
 IRC: melzua
 Ingame: melzua
 Location: Catalonia
Re: [Help] Writing a Field Of View scanner
There is a core function (minetest.line_of_sight) that my help in this case, but I think that you are aware of it.
Anyway, I tried to implement a kind of radar for mobs too, mine looks like this:
I use the dot product to determine if a node is in front off or behind the entity, but I don't use a fov angle. I think that you can relate a fov angle with a dot product result, I mean: if iProjection > some_number then ...
Anyway my 'radar' don't function as expected for some reason I don't know. When the luaentity is near yaw 180 degrees, the find_nodes_in_area function don't return the expected values.
Hope that helps you.
Anyway, I tried to implement a kind of radar for mobs too, mine looks like this:
Code: Select all
function test:dotproduct(v1, v2)
if v1 and v2 then
return ((v1.x * v2.x) + (v1.y * v2.y) + (v1.z + v2.z))
else return nil
end
end
local vNormalizedVel = vector.normalize(self.object:getvelocity())
local pEntityPos = self.object:getpos()
local distance = 3
local minp = {x = self.vAgentPos.x  distance, y = self.vAgentPos.y  3.5, z = self.vAgentPos.z  distance}
local maxp = {x = self.vAgentPos.x + distance, y = self.vAgentPos.y + 1.5, z = self.vAgentPos.z + distance}
local nodes = minetest.find_nodes_in_area(minp, maxp, {"group:water"})
if #nodes > 0 then
for _,node in ipairs(nodes) do
local pTargetPos = node:getpos()
local vTargetPos = vector.normalize(vector.subtract(pTargetPos,pEntityPos))
local iProjection = test:dotproduct(vTargetPos,vNormalizedVel)
if iProjection > 0 then
print("node = "..minetest.pos_to_string(node))
end
end
end
Anyway my 'radar' don't function as expected for some reason I don't know. When the luaentity is near yaw 180 degrees, the find_nodes_in_area function don't return the expected values.
Hope that helps you.
Re: [Help] Writing a Field Of View scanner
Maybe find a point in front of mob, and use that point for player detection instead.
Something like this(needs testing):
local radius = 10
local mob_position = <get mob position somehow>
local mob_look_direction = <somehow convert yaw to vector>
local mob_look_vector = vector.add(mob_look_direction, radius)
local position_center = vector.add(mob_position, mob_look_vector)
Then you hawe two options: use get_connected_players() and check distance to each player vector.distance(position_center, player position) or use get_objects_inside_radius(position_center, radius) and check if this is player.
UPD:
After player is found, maybe line_of_sight(mob_position, player_position) also can be checked. http://dev.minetest.net/minetest.line_of_sight
Something like this(needs testing):
local radius = 10
local mob_position = <get mob position somehow>
local mob_look_direction = <somehow convert yaw to vector>
local mob_look_vector = vector.add(mob_look_direction, radius)
local position_center = vector.add(mob_position, mob_look_vector)
Then you hawe two options: use get_connected_players() and check distance to each player vector.distance(position_center, player position) or use get_objects_inside_radius(position_center, radius) and check if this is player.
UPD:
After player is found, maybe line_of_sight(mob_position, player_position) also can be checked. http://dev.minetest.net/minetest.line_of_sight
Re: [Help] Writing a Field Of View scanner
You need to convert the yaw to a vector and determine the vector between the two positions. If you got that, you need to measure the angle between the two vectors:
This returns the angle in radian. If you want it in degree, you need to multiply it by 180/math.pi
Code: Select all
local function yaw2vec(yaw)
return { x = math.cos(yaw), z = math.sin(yaw), y = 0 }
end
local function dotproduct(v1, v2)
if v1 and v2 then
return ((v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z))
else
return nil
end
end
local function angle(v1, v2)
if v1 and v2 then
return math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2)))
end
end
Re: [Help] Writing a Field Of View scanner
Oh, it was that easy? Thanks!TeTpaAka wrote:You need to convert the yaw to a vector and determine the vector between the two positions. If you got that, you need to measure the angle between the two vectors:Code: Select all
local function yaw2vec(yaw) return { x = math.cos(yaw), z = math.sin(yaw), y = 0 } end
Please make sure to not divide by zero here, or it will produce random game hangs.TeTpaAka wrote:Code: Select all
return math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2)))
Re: [Help] Writing a Field Of View scanner
The yaw is the angle in radian. It is only in the xz plane, since neither pitch nor roll are there. So basically, yes, it is that easy.lag01 wrote:Oh, it was that easy? Thanks!TeTpaAka wrote:You need to convert the yaw to a vector and determine the vector between the two positions. If you got that, you need to measure the angle between the two vectors:Code: Select all
local function yaw2vec(yaw) return { x = math.cos(yaw), z = math.sin(yaw), y = 0 } end
You're right. Though in this situation, vector.length(v1) is always 1 and if vector.length(v2) is zero, you are inside you're opponent. But to be sure, you should first check for 0.lag01 wrote:Please make sure to not divide by zero here, or it will produce random game hangs.TeTpaAka wrote:Code: Select all
return math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2)))
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
Re: [Help] Writing a Field Of View scanner
Regarding minetest.line_of_sight: I know of it of course, and my mobs already use it. But it's unrelated to FOV calculation. That function simply checks that there are no nodes in between pos1 and pos2, and that one is visible from the other.
Anyway thanks for all the suggestions! I will try them out and see how it goes.
One more thing however: Right now my mobs don't support looking up or down, and I doubt they ever will. But just in case, and if someone feels like it... what would be a version that accounts pitch as well please? FOV is the same vertically and horizontally, so the same value can be used.
Anyway thanks for all the suggestions! I will try them out and see how it goes.
One more thing however: Right now my mobs don't support looking up or down, and I doubt they ever will. But just in case, and if someone feels like it... what would be a version that accounts pitch as well please? FOV is the same vertically and horizontally, so the same value can be used.
Re: [Help] Writing a Field Of View scanner
You'd replace yaw2vec to a function that also takes the pitch to set the y value:
Edit: Fixed the code. You have to multiply x and z by math.cos(pitch) to counter the added length of the y. For small angles this doesn't matter, but for bigger angles it is needed.
Code: Select all
local function yaw2vec(yaw, pitch)
pitch = pitch or 0
return { x = math.cos(yaw) * math.cos(pitch), z = math.sin(yaw) * math.cos(pitch), y = math.sin(pitch) }
end
 BrandonReese
 Member
 Posts: 839
 Joined: Wed Sep 12, 2012 00:44
 GitHub: bremaweb
 IRC: BrandonReese
 Ingame: BrandonReese
 Location: USA
Re: [Help] Writing a Field Of View scanner
I did FOV in my version of simple mobs for Adventuretest.
https://github.com/Bremaweb/adventurete ... i.lua#L148
This is where I found the formulas, very helpful reference.
http://blog.wolfire.com/2009/07/linear ... rspart2/
https://github.com/Bremaweb/adventurete ... i.lua#L148
This is where I found the formulas, very helpful reference.
http://blog.wolfire.com/2009/07/linear ... rspart2/
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
Re: [Help] Writing a Field Of View scanner
Aha... very useful! Is it okay if I adapt that same paragraph of code? It seems very simple and exactly what I needed too.BrandonReese wrote:I did FOV in my version of simple mobs for Adventuretest.
https://github.com/Bremaweb/adventurete ... i.lua#L148
This is where I found the formulas, very helpful reference.
http://blog.wolfire.com/2009/07/linear ... rspart2/
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
Re: [Help] Writing a Field Of View scanner
Alright, I'm trying to implement this now (TeTpaAka's version). I don't seem to get how the functions and vectors work exactly however. Basically, this is the test function I put together so far, which currently just prints the values:
Mobs don't currently have pitch so I use 0, and 90 is the test value for the FOV before I use a real one. Anyway I'm expecting something like 'yaw2vec' to output the angle limit in each direction, and 'angle' to print the mob's actual field of view. The values however don't represent anything that I can comprehend, and seem to range somewhere between 0 and 1.5. This is an example of the output:
First of all, is my test function written correctly? Second, what does each value represent exactly... so I know which is the angle and which is the limit per direction, or which is the angle difference if that's what it should output.
Code: Select all
local function in_fov (pos1, pos2, yaw, pitch, fov)
local function yaw2vec (yaw, pitch)
return {x = math.cos(yaw) * math.cos(pitch), y = math.sin(pitch), z = math.sin(yaw) * math.cos(pitch)}
end
local function dotproduct (v1, v2)
return ((v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z))
end
local function angle (v1, v2)
return math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2))) * 180 / math.pi
end
print(angle(pos1, pos2).."\n"..dump(yaw2vec(yaw, pitch)))
end
 somewhere in the mob's on_step function
if player:get_player_name() == "singleplayer" then
in_fov(self.object:getpos(), player:getpos(), self.object:getyaw(), 0, 90)
end
Code: Select all
0.50313994472358
{
y = 0,
x = 0.082862613092331,
z = 0.99656098024733
}
 BrandonReese
 Member
 Posts: 839
 Joined: Wed Sep 12, 2012 00:44
 GitHub: bremaweb
 IRC: BrandonReese
 Ingame: BrandonReese
 Location: USA
Re: [Help] Writing a Field Of View scanner
If I remember correctly this bit of code was key to actually get a number I could use:
local an = .... is basically your dotproduct function without Y.
Then if a is greater than your fov the position is outside of your fov.
Since mobs don't have pitch I think you have to treat it like a 2D world and exclude pitch and the Y coordinate from your formulas.
Code: Select all
local an = ( d.x * p.x ) + ( d.z * p.z )
local a = math.deg( math.acos( an ) )
Then if a is greater than your fov the position is outside of your fov.
Since mobs don't have pitch I think you have to treat it like a 2D world and exclude pitch and the Y coordinate from your formulas.
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
Re: [Help] Writing a Field Of View scanner
So this code is reaching the point where getting it to work requires rocket science. I brought the matter up on IRC, and thankfully many coders were willing to help... sadly none ultimately succeeded, although it is much closer now.
Nore adapted the code posted by TeTpaAka, while TheWild rewrote part of it in a simpler form. This is the best version I currently have running:
What works: If the player sits in front of the mob (parallel to its face) the formula prints 0. Moving back or forth across this axis does not change it, meaning the horizontal angle is computer properly. If from there the player steps a bit to the left or to the right, the angle decreases or increases equally on both sides, and the strength of this variation accordingly depends on distance. Perfect!
What doesn't work: Two things. First of all, pitch is not being accounted properly. If it's 0*, the calculations work correctly... but if I set it to a value like 45*, all calculations return incorrect results. I could test this by moving left and right in front of the mob, and noticing that when the pitch is above 0 the horizontal component of the cone is no longer centered (I would not get an equal variation around the center while moving sideways in front of the mob).
The second issue is that this outputs the same values both in front of and behind the mob. You get the same output if you're standing at a given position from the mob as if you're standing at the same position behind it. Obviously I don't want this, since I have no way to tell between the two! If standing right in front of the mob returns 180* for instance, I'd want standing behind it to return 360* or 180* or something else that is distinctive.
So anyone know how to fix these final issues? What is the code above missing?
Nore adapted the code posted by TeTpaAka, while TheWild rewrote part of it in a simpler form. This is the best version I currently have running:
Code: Select all
local function in_fov (pos1, pos2, yaw, pitch, fov)
local function yaw2vec (yaw, pitch)
return {x = math.sin(yaw) * math.cos(pitch), y = math.sin(pitch), z = math.cos(yaw) * math.cos(pitch)}
end
local function dotproduct (v1, v2)
return ((v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z))
end
local function angle (v1, v2)
return math.deg(math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2))))
end
print(90  angle(yaw2vec(yaw, pitch), vector.subtract(pos1, pos2)))
end
What doesn't work: Two things. First of all, pitch is not being accounted properly. If it's 0*, the calculations work correctly... but if I set it to a value like 45*, all calculations return incorrect results. I could test this by moving left and right in front of the mob, and noticing that when the pitch is above 0 the horizontal component of the cone is no longer centered (I would not get an equal variation around the center while moving sideways in front of the mob).
The second issue is that this outputs the same values both in front of and behind the mob. You get the same output if you're standing at a given position from the mob as if you're standing at the same position behind it. Obviously I don't want this, since I have no way to tell between the two! If standing right in front of the mob returns 180* for instance, I'd want standing behind it to return 360* or 180* or something else that is distinctive.
So anyone know how to fix these final issues? What is the code above missing?
I tried the code you linked too, but couldn't get it working the way I needed. The full formula is a bit more complex than what's been posted until now... for instance I have to subtract the target's position from the mob's position.BrandonReese wrote:If I remember correctly this bit of code was key to actually get a number I could use:
My mobs don't currently have pitch, but eventually they might. Therefore I want the code to have a slot for pitch as well, and use a full 3D cone instead of a flat 2D cone (horizontal scan only). Until then I will hardcode pitch to 0.BrandonReese wrote:Since mobs don't have pitch I think you have to treat it like a 2D world and exclude pitch and the Y coordinate from your formulas.
Re: [Help] Writing a Field Of View scanner
My code is correct. But you have to invert the order in vector.subtract. To get the direction from one point to the other, you need to subtract the origin from the target, so
should return the right vector.
The 90 has to be removed and the formula in yaw2vec reverted to my function.
The problem is, that minetest uses a lefthanded coordinate system while in school, you always use righthanded ones, so the formula has to be inverted, also. (Which mine is)
EDIT:
http://irc.minetest.ru/minetest/20150624#i_4297415
This produces 90 because you print 900.
Code: Select all
vector.subtract(pos2, pos1)
The 90 has to be removed and the formula in yaw2vec reverted to my function.
The problem is, that minetest uses a lefthanded coordinate system while in school, you always use righthanded ones, so the formula has to be inverted, also. (Which mine is)
EDIT:
http://irc.minetest.ru/minetest/20150624#i_4297415
This produces 90 because you print 900.
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
Re: [Help] Writing a Field Of View scanner
I've applied these changes, but unfortunately the two problems are still there. Firstly, I still get 90 both when standing right in front of the mob and when standing right behind it, so there is no way to tell the difference between the two. Secondly, pitch doesn't work... with it set to 0 (perfectly horizontal cone), flying up or down without moving horizontally does not change the value or only does so by a very few decimals. This is the exact code I have now:TeTpaAka wrote:My code is correct. But you have to invert the order in vector.subtract. To get the direction from one point to the other, you need to subtract the origin from the target, soshould return the right vector.Code: Select all
vector.subtract(pos2, pos1)
The 90 has to be removed and the formula in yaw2vec reverted to my function.
The problem is, that minetest uses a lefthanded coordinate system while in school, you always use righthanded ones, so the formula has to be inverted, also. (Which mine is)
EDIT:
http://irc.minetest.ru/minetest/20150624#i_4297415
This produces 90 because you print 900.
Code: Select all
local function in_fov (pos1, pos2, yaw, pitch, fov)
local function yaw2vec (yaw, pitch)
return {x = math.cos(yaw) * math.cos(pitch), y = math.sin(pitch), z = math.sin(yaw) * math.cos(pitch)}
end
local function dotproduct (v1, v2)
return ((v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z))
end
local function angle (v1, v2)
return math.deg(math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2))))
end
print(angle(yaw2vec(yaw, pitch), vector.subtract(pos2, pos1)))
end
Re: [Help] Writing a Field Of View scanner
For player:get_look_yaw, it works with my formula. Could it be, that for entities, the yaw has another reference point?
Anyway, could you try flipping x and z (again, sorry).
It seems to be :
When it should be:
Anyway, could you try flipping x and z (again, sorry).
It seems to be :
Code: Select all
90
180  0
90
Code: Select all
0
90  90
180
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
Re: [Help] Writing a Field Of View scanner
I'm testing the code from the mob's point of view. Therefore yaw is self.object:getyaw(), whereas pos1 is self.object:getpos() and pos2 is player:getpos().TeTpaAka wrote:For player:get_look_yaw, it works with my formula. Could it be, that for entities, the yaw has another reference point?
Anyway, could you try flipping x and z (again, sorry).
It seems to be :When it should be:Code: Select all
90 180  0 90
Code: Select all
0 90  90 180
I tried flipping x and z that way last night. While that would differentiate between front and back, and caused an identical 90 / 90 to be on the sides, it introduced a new problem: The cone is itself aligned along the sides and was rotated 90*. So if I walk back or forth while parallel to the mob's face, the angle now increases, which it obviously shouldn't.
Re: [Help] Writing a Field Of View scanner
If it helps any, here is the in_fov code from mobs redo mod that works (self is mob, pos is player position and self.fov is set to 90, self.rotate is usually 0 for front facing mobs):
Code: Select all
in_fov = function(self,pos)
 checks if POS is in self's FOV
local yaw = self.object:getyaw() + self.rotate
local vx = math.sin(yaw)
local vz = math.cos(yaw)
local ds = math.sqrt(vx^2 + vz^2)
local ps = math.sqrt(pos.x^2 + pos.z^2)
local d = { x = vx / ds, z = vz / ds }
local p = { x = pos.x / ps, z = pos.z / ps }
local an = ( d.x * p.x ) + ( d.z * p.z )
a = math.deg( math.acos( an ) )
if a > ( self.fov / 2 ) then
return false
else
return true
end
end,
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
Re: [Help] Writing a Field Of View scanner
Thank you everyone, especially TeTpaAka and Nore. All problems were at last solved, and the code now reports the angle difference between entities like it should! You get 0* when standing right in front of the mob, 90* when standing parallel to either side, 180* when standing behind... whereas flying up or down now accounts pitch correctly on top of that.
Here is the final and fully functional version. I hope it will be helpful to more people than just me, if anyone ever needs a simple and efficient FOV scanner for Minetest.
Here is the final and fully functional version. I hope it will be helpful to more people than just me, if anyone ever needs a simple and efficient FOV scanner for Minetest.
Code: Select all
local function in_fov (pos1, pos2, yaw, pitch, fov)
local function yaw2vec (yaw, pitch)
 we must invert the yaw for x to keep the result from inverting when facing opposite directions (0* becoming 180*)
return {x = math.sin(yaw) * math.cos(pitch), y = math.sin(pitch), z = math.cos(yaw) * math.cos(pitch)}
end
local function dotproduct (v1, v2)
return ((v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z))
end
local function angle (v1, v2)
return math.deg(math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2))))
end
local v = vector.subtract(pos2, pos1)
print(angle(yaw2vec(yaw, pitch), v))
end
 MirceaKitsune
 Member
 Posts: 860
 Joined: Sat May 21, 2011 22:31
 GitHub: MirceaKitsune
 IRC: Taoki
 Ingame: MirceaKitsune
 Location: Romania, Bucharest
 Contact:
[Solved] Writing a Field Of View scanner
I'm sorry for the double post. But for those interested, here is the final version of the function which I'll be including in my mod, simplified to only 5 lines of code but with the same result:
Code: Select all
 returns the angle difference between pos1 and pos2, as seen from pos1 at the specified yaw and pitch
function pos_to_angle (pos1, pos2, yaw, pitch)
 note: we must invert the yaw for x in yaw_vec, to keep the result from inverting when facing opposite directions (0* becoming 180*)
local yaw_vec = {x = math.sin(yaw) * math.cos(pitch), y = math.sin(pitch), z = math.cos(yaw) * math.cos(pitch)}
local pos_subtract = vector.subtract(pos2, pos1)
local pos_dotproduct = (yaw_vec.x * pos_subtract.x) + (yaw_vec.y * pos_subtract.y) + (yaw_vec.z * pos_subtract.z)
local angle = math.deg(math.acos(pos_dotproduct / (vector.length(yaw_vec) * vector.length(pos_subtract))))
return angle
end
Who is online
Users browsing this forum: No registered users and 0 guests