2
\$\begingroup\$

Say I have an agent in 2D in a world filled with circular obstacles of different kind and across many scales (some may be very large, practically filling an agent's view, some may be very small).

The agent has some vision cone and can these obstacles and their kinds if they are within that cone.

I would like to be able to test how much of the agent's cone is occupied by each sort of object and in what direction this happens.

I have already worked out what it takes to find how large a circle would appear in the field of vision of an agent. However, currently the agent can also just see through any object and also react to whatever is behind (the ultimate result is an average weighted by how large each kind of object appears)

Using Physics2D.OverlapCircleNonAlloc and an angle-based second check to see if things are still in the vision cone (and how big they are in that cone), I can find all seen objects in order of closeness and give them the appropriate weighting. Currently I'm not doing anything with the ordering information.

I think what I roughly need to do is to define an interval, and fill it up with each object kind (something like a tuple of the kind index, and the left and right bounds of the interval) and check that no previous object already fell in those interval bounds. (If that part of the interval is already covered, clip to parts of the space that are still free) After that I'd have to loop over each segment of the interval and accumulate the weighted average view accordingly.

However, that sounds quite slow. I have potentially hundreds of such agents able to see any kind of obstacle including each other, and even the simpler current vision system is definitely a bottleneck.

Are there ways to do this faster? (Keep in mind that each obstacle is a potentially small 2D circle that appears as a 1D line to an agent)


To get the part of an object that's in the field of vision, I'm currently doing roughly this:

float r = object.GetObjectRadius(); // the radius of the seen object
Vector2 d = this.transform.position - base.transform.position;  // "this" being the seen object, "base" the agent. The vector from the agent to the target)

float rd2 = Mathf.Min(r * r / d.sqrMagnitude, 1f); // if it's smaller than 1, you are inside the object. Pretend you're just touching it

Vector2 d_tangent = d * (1f - rd2);
Vector2  d_perp_tangent = Vector2.Perpendicular(d) * rd2 * Mathf.Sqrt(1f / rd2 - 1f);

Vector2 left_tangent = d_tangent  + d_perp_tangent;
Vector2 right_tangent = d_tangent - d_perp_tangent

float fov_overlap = Mathf.Min(Vector2.SignedAngle(agentUpVect, left_tangent), half_view) + Mathf.Min(Vector2.SignedAngle(right_tangent, agentUpVect), half_view) // agentUpVect is the direction the agent faces in, half_view is half the vision cone. If fov_overlap < 0, the object is not seen.

This should give me the precise part of the view that's occupied by a circular object of radius r which is |d| units away from an agent. I tried figuring out the above myself and I'm fairly confident it's right. I verified this by also implementing this math in GeoGebra:

circle in fov schematic


EDIT: Adapted from @Mangata, here is a simplified schematic of what is needed:

interval schematic

for simplicity, I have normalized it here such that the view is in the interval [-1, 1] and anything outside that gets discarded. You can see here three different kinds of objects and "the horizon" all of which need to correctly handle occlusions. In the end I'd like to have the total length of the intervals of each kind of "color" (note, these are a small number of fixed labels for me, one per kind of object, not actually RGB colors. For instance, black might be another agent, small but close by, red might be food, and green poison. The blue part is nothing / "the horizon")

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Here are some optimization suggestions:

1. Filter unnecessary tests

  1. Objects located outside the field of view circle(distance>r1+r2) do not need to be detected. Considering that calculating distance requires multiplication, AABB detection is better.
  2. Space_partitioning.

2. Angle calculation

enter image description here

BF and BG are tangents of circle A, ∠AGB = 90°, so that ∠ABG=arcsin(|AG|/|AB|).

3. Visibility calculation

  1. Establish a rectangular coordinate system in which the abscissa is distance and the ordinate is angle. At this time, the field of view is a rectangle and the object is a line segment. Of course this only happens in your head, just to make it easier to understand.

enter image description here

  1. You don't need to define an interval to check again. Because the y coordinates of all line segment endpoints will divide the field of view into areas, and the visible conditions inside each area are consistent. In the picture below, 4 line segments divide the field of view into 7 areas, and their bounds have floating point precision:

enter image description here

  1. Sort all endpoints, get the mapping of y(float) to area index(int). Traverse all line segments and find all areas it covers. pseudocode:
points = [view.left,view.right]
for segment in segments:
    segment.left = clamp(segment.left,view.left,view.right)
    segment.right = clamp(segment.right,view.left,view.right)
    points.append(segment.left)
    points.append(segment.right)

points = list(set(points)) #Remove duplicate values
points.sort()

areas = [Area()] * len(points)

for segment in segments:
    leftIndex = points.index(segment.left)
    rightIndex = points.index(segment.right)
    for i in range(leftIndex,rightIndex):
        areas[i].segments.append(segment)

*PS.Code is untested, please be aware of bounds issues and floating point precision issues

\$\endgroup\$
4
  • \$\begingroup\$ I think the Physics2D.OverlapCircleNonAlloc already takes care of the first part of that, right? I'm first filtering down to all the objects that could be seen with that. I'm already calculating the angles in Part 2 anyways. That's what the fov_overlap does. I'm not quite sure I get what you are saying in Part 3.2. I'll have to try to adapt your code from 4. That's python, right? I'm going for C# but I think I can translate that. Note, there are different kinds of objects (effectively different labelled "colors") that I also need to keep track of. \$\endgroup\$
    – kram1032
    Nov 7, 2023 at 18:42
  • 1
    \$\begingroup\$ @kram1032 1. Yes, but in this case, physical detection is still slower than AABB testing. 2. Yes, but it's faster to use arcsin. These two points are just optimization suggestions. They can serve as directions to consider when you need to further improve performance. \$\endgroup\$
    – Mangata
    Nov 8, 2023 at 6:44
  • \$\begingroup\$ @kram1032 As for 3.2, To put it another way, it is to divide the fov into several areas. The content seen from any angle in the area is the same. For example, area a=[10°,20°], assuming that the 11° line of sight sees object 1 and object 2, the 17° line of sight should also see object 1 and object 2. So we use the angle(y in image3.2) values ​​of all line segment endpoints to divide fov into several areas. \$\endgroup\$
    – Mangata
    Nov 8, 2023 at 7:02
  • 1
    \$\begingroup\$ @kram1032 Another way, if you can understand the solution of using fixed interval ray casting, I suggest using a Segment_tree. It allows querying which of the stored segments contain a given point. In this case, equals a much cheaper raycast. \$\endgroup\$
    – Mangata
    Nov 8, 2023 at 7:10
1
\$\begingroup\$

My first move would be to use a Raycast at regular intervals between the start & end angles. In other words:

  1. begin at the starting angle
  2. perform a raycast from the observer
  3. increment the angle
  4. if the angle is inside the the FOV range go back to 2.
  5. otherwise perform one last raycast along the end angle

The above is has slightly uneven precision in because of the extra raycast at the end. If that's an issue you could alternatively start from the center & work your way toward the edges. In either case, excluding any intersections that further away than the sensor range will clip the results to the FOV.

As described in this answer, the Unity engine does some work to calculate raycast intersections efficiently. But at some point, a large enough scale simulation is going to run into bottlenecks as the number of simultaneous agents scales up.

\$\endgroup\$
6
  • \$\begingroup\$ I'm on mobile right now - I'll double back later when I can add a diagram or two. \$\endgroup\$
    – Pikalek
    Nov 7, 2023 at 15:08
  • \$\begingroup\$ I have to do this for potentially 100s of agents at the same time and some of the obstacles might be pretty small, making evenly spaced raycasts relatively unlikely to hit everything unless I go for a pretty small ray cast increment. It's an option if no other way presents itself but I'm hoping there is a method that can overcome these limitations. I was hoping the fact I'm dealing only with circles might help \$\endgroup\$
    – kram1032
    Nov 7, 2023 at 15:12
  • \$\begingroup\$ Back when I did UAV research, we had some real world limitations that we had to account for. I haven't checked what the latest state of the art is in sensor resolution, but depending on exactly what you're modelling, it might be a consideration. That said, the above is poorly suited to dealing with small obstacles at long ranges - if that's a design constraint, please edit that into your problem description. \$\endgroup\$
    – Pikalek
    Nov 7, 2023 at 15:40
  • 1
    \$\begingroup\$ There are some shadow casting techniques that are better suited to dealing with the small object aspect. I suspect they will have a heavier computational expense, but Unity may have some built in optimizations to lighten the load. \$\endgroup\$
    – Pikalek
    Nov 7, 2023 at 15:44
  • \$\begingroup\$ The context is basically a life-sim of sorts. Agents can see different objects and react to them accordingly. They need to find and compete for food to survive etc. And the size of an object may grow or shrink over time (i.e. an agent grows with age, food gets consumed and shrinks until it's all used up) \$\endgroup\$
    – kram1032
    Nov 7, 2023 at 15:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .