[Help] Writing a Field Of View scanner

Post Reply
User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

[Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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à
Member
Posts: 115
Joined: Sun Feb 22, 2015 07:11
GitHub: melzua
IRC: melzua
In-game: melzua
Location: Catalonia

Re: [Help] Writing a Field Of View scanner

by Ivà » Post

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:

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.

User avatar
lag01
Member
Posts: 293
Joined: Sun Mar 16, 2014 03:41
GitHub: AndrejIT
IRC: lag01
In-game: lag

Re: [Help] Writing a Field Of View scanner

by lag01 » Post

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

User avatar
TeTpaAka
Member
Posts: 141
Joined: Sat Dec 28, 2013 21:54

Re: [Help] Writing a Field Of View scanner

by TeTpaAka » Post

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

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

User avatar
lag01
Member
Posts: 293
Joined: Sun Mar 16, 2014 03:41
GitHub: AndrejIT
IRC: lag01
In-game: lag

Re: [Help] Writing a Field Of View scanner

by lag01 » Post

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
Oh, it was that easy? Thanks!
TeTpaAka wrote:

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.

User avatar
TeTpaAka
Member
Posts: 141
Joined: Sat Dec 28, 2013 21:54

Re: [Help] Writing a Field Of View scanner

by TeTpaAka » Post

lag01 wrote:
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
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.
lag01 wrote:
TeTpaAka wrote:

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.

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

Re: [Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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.

User avatar
TeTpaAka
Member
Posts: 141
Joined: Sat Dec 28, 2013 21:54

Re: [Help] Writing a Field Of View scanner

by TeTpaAka » Post

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

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.

User avatar
BrandonReese
Member
Posts: 839
Joined: Wed Sep 12, 2012 00:44
GitHub: bremaweb
IRC: BrandonReese
In-game: BrandonReese
Location: USA

Re: [Help] Writing a Field Of View scanner

by BrandonReese » Post

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/

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

Re: [Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

Re: [Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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:

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:

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.

User avatar
BrandonReese
Member
Posts: 839
Joined: Wed Sep 12, 2012 00:44
GitHub: bremaweb
IRC: BrandonReese
In-game: BrandonReese
Location: USA

Re: [Help] Writing a Field Of View scanner

by BrandonReese » Post

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

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.

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

Re: [Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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:

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?
BrandonReese wrote: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.
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.
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.

User avatar
TeTpaAka
Member
Posts: 141
Joined: Sat Dec 28, 2013 21:54

Re: [Help] Writing a Field Of View scanner

by TeTpaAka » Post

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

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.

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

Re: [Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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, so

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:

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.

User avatar
TeTpaAka
Member
Posts: 141
Joined: Sat Dec 28, 2013 21:54

Re: [Help] Writing a Field Of View scanner

by TeTpaAka » Post

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 :

Code: Select all

       90
180 ------- 0
       90
When it should be:

Code: Select all

       0
90 ------- 90
      180

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

Re: [Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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 :

Code: Select all

       90
180 ------- 0
       90
When it should be:

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.

User avatar
TenPlus1
Member
Posts: 2718
Joined: Mon Jul 29, 2013 13:38
GitHub: tenplus1

Re: [Help] Writing a Field Of View scanner

by TenPlus1 » Post

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,

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

Re: [Help] Writing a Field Of View scanner

by MirceaKitsune » Post

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.

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

User avatar
MirceaKitsune
Member
Posts: 860
Joined: Sat May 21, 2011 22:31
GitHub: MirceaKitsune
IRC: Taoki
In-game: MirceaKitsune
Location: Romania, Bucharest
Contact:

[Solved] Writing a Field Of View scanner

by MirceaKitsune » Post

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

Post Reply

Who is online

Users browsing this forum: Nathan.S and 1 guest