[Help] Writing a Field Of View scanner

[MirceaKitsune]

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!

[Ivà]

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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


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.

[lag01]

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

[TeTpaAka]

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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


This returns the angle in radian. If you want it in degree, you need to multiply it by 180/math.pi

[lag01]

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

local function yaw2vec(yaw)
        return { x = math.cos(yaw), z = math.sin(yaw), y = 0 }
end


Oh, it was that easy? Thanks!

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

 return math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2)))

Please make sure to not divide by zero here, or it will produce random game hangs.

[TeTpaAka]

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

local function yaw2vec(yaw)
        return { x = math.cos(yaw), z = math.sin(yaw), y = 0 }
end


Oh, it was that easy? Thanks!

The yaw is the angle in radian. It is only in the x-z plane, since neither pitch nor roll are there. So basically, yes, it is that easy.

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

 return math.acos(dotproduct(v1, v2) / (vector.length(v1) * vector.length(v2)))

Please make sure to not divide by zero here, or it will produce random game hangs.

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.

[MirceaKitsune]

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.

[TeTpaAka]

You'd replace yaw2vec to a function that also takes the pitch to set the y value:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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


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.

[BrandonReese]

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- ... rs-part-2/

[MirceaKitsune]

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- ... rs-part-2/

Aha... very useful! Is it okay if I adapt that same paragraph of code? It seems very simple and exactly what I needed too.

[MirceaKitsune]

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

0.50313994472358
{
        y = 0,
        x = -0.082862613092331,
        z = -0.99656098024733
}

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.

[BrandonReese]

If I remember correctly this bit of code was key to actually get a number I could use:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

local an = ( d.x * p.x ) + ( d.z * p.z )   
local a = math.deg( math.acos( an ) )


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.

[MirceaKitsune]

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

If I remember correctly this bit of code was key to actually get a number I could use:

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.

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.

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 hard-code pitch to 0.

[TeTpaAka]

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

vector.subtract(pos2, pos1)


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 left-handed coordinate system while in school, you always use right-handed ones, so the formula has to be inverted, also. (Which mine is)

EDIT:
http://irc.minetest.ru/minetest/2015-06-24#i_4297415
This produces 90 because you print 90-0.

[MirceaKitsune]

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

vector.subtract(pos2, pos1)


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 left-handed coordinate system while in school, you always use right-handed ones, so the formula has to be inverted, also. (Which mine is)

EDIT:
http://irc.minetest.ru/minetest/2015-06-24#i_4297415
This produces 90 because you print 90-0.

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

And yes, it still outputs 90 when parallel to the mob, which is why I had the final product be 90 - result. I'm confused as well why that is... normally it should be 0 or 180 or something.

[TeTpaAka]

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 :

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

       90
180 ------- 0
       90


When it should be:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

       0
90 ------- 90
      180


[MirceaKitsune]

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 :

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

       90
180 ------- 0
       90


When it should be:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

       0
90 ------- 90
      180


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

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.

[TenPlus1]

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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]

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.

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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]

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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