I am working on a system that will obtain points that an NPC will sequentially wander to within a given radius, its RoamArea. As part of this, I want each point after the first point to be a minimum distance away from the previous point.
Essentially, I want to find a random point within the blue area.
The brute force way of doing this would be to keep getting random points within the RoamArea until one is found that falls within the desired area. However, if the minimum distance is close to the radius of RoamArea, many points would have to be obtained before getting a valid one.
I believe there is a mathematical way to accomplish this, but I need help with the math if so.
Idea for Solution
The current thought I have for the approach is to break this down into two steps. First, find the valid range of angles x that can be used.
Using the selected random angle and a random value within y I can then define a vector that I can use to obtain the random point.
Problem Constraints and Known Details
The circle RoamArea has a radius of A and is considered centered at origin. The exclusion area has a radius of B, and its center is a distance C away from the center of RoamArea.
Your logic seems sound but the math you should check this Google Gemini AI code
Here is the prompt I used.
godot find a random point inside circle excluding another circle
extends Node2D
## Generates a uniform random point inside a main circle, excluding an inner area.
func get_random_point_excluding_circle(
main_center: Vector2,
main_radius: float,
exclude_center: Vector2,
exclude_radius: float
) -> Vector2:
# Safety check to avoid infinite loops if the exclusion completely covers the main circle
var dist_centers = main_center.distance_to(exclude_center)
if dist_centers + main_radius <= exclude_radius:
push_error("Exclusion circle completely covers the main circle!")
return main_center
while true:
# 1. Choose a random uniform direction
var angle = randf() * TWO_PI
# 2. Use sqrt() to ensure uniform spatial distribution across the circle area
var radius = main_radius * sqrt(randf())
# 3. Calculate candidate coordinates
var candidate_point = main_center + Vector2(cos(angle), sin(angle)) * radius
# 4. Accept the point only if it is outside the exclusion circle
if candidate_point.distance_to(exclude_center) >= exclude_radius:
return candidate_point
return main_center
The AI code you prompted for just polls for random points until one of them is not within the exclusion zone, the brute force method I described earlier. I want to avoid using this approach if I can as if the exclusion zone is big enough, a lot more time will be spent polling for a valid point.
What is the reason to avoid brute force method? Do you need to get hundreds of these random points in every frame?
If there is no actual performance reason to avoid the brute force overhead, I would do something like this:
loop X times:
select random point inside A
if point not inside B:
return point
# reduce area B's size and try again
make area B 30% smaller
loop Y times:
select random point inside A
if point not inside B:
return point
# quit trying and return any random point
select random point inside A
return point
The player will never notice that sometimes the NPC’s target point is closer to the previous point than it usually is.
I am currently using a brute force method for my purposes, but it bugs me that I could be using a better method. I do like your approach though, I did not consider shrinking the exclusion zone.
Even though the brute force method will likely suffice for my needs, I want to see this through in case someone else does need a more optimal solution to this specific problem .
I have found a way to implement the approach suggested by @silocoder
Step 1: Random Direction
The first step is to obtain the intersection points of the exclusion zone and the circle itself, which I did by adapting the logic discussed here. Using those points, a valid angle range is found, and from there a random direction. It is assumed that the center of the exclusion zone is always WITHIN the boundaries of the circle.
func _get_random_direction(
circle_center: Vector2,
exclusion_center: Vector2,
circle_radius: float,
exclusion_radius: float
) -> Vector2:
var v := exclusion_center - circle_center
var d := v.length()
# Rename relevant parameters for conciseness.
var r0 := circle_radius
var r1 := exclusion_radius
if d < abs(r0 - r1) or d > r0 + r1:
# Exclusion zone does not overlap boundaries of circle so any
# direction is valid. Assumes exclusion_center is within circle's
# area.
return Vector2.from_angle(randf() * TAU).normalized()
var u := v.normalized()
var x_vec := (pow(d, 2.0) - pow(r1, 2.0) + pow(r0, 2.0)) * u / (2 * d)
var u_perp := Vector2(u.y, -u.x)
var a_half := (
sqrt(
(-d + r1 - r0)
* (-d - r1 + r0)
* (-d + r1 + r0)
* (d + r0 + r1)
) / d * 0.5
)
var intersect_1 := x_vec - u_perp * a_half
var intersect_2 := x_vec + u_perp * a_half
var v1 := intersect_1 - exclusion_center
var v2 := intersect_2 - exclusion_center
var angle := v1.angle_to(v2)
# Want to get the value of the angle that points towards the center of
# circle. Negative angle points away from center.
if angle < 0.0:
angle += TAU
return v1.normalized().rotated(randf() * angle)
Step 2: Random Distance
Once a direction is found, the next step is to ray cast from the exclusion zone center and find the points where that ray intersects with the circle. Those intersection points can then be used to calculate the length which gives us the upper bound for the range (the lower bound being the radius of the exclusion zone). The logic was found here: Ray-Sphere Intersection
func _get_random_point_on_ray(
ray_start: Vector2,
ray_direction: Vector2,
exclusion_radius: float,
circle_center: Vector2,
circle_radius: float
) -> Vector2:
var L := ray_start - circle_center
var a := ray_direction.dot(ray_direction)
var b := 2.0 * ray_direction.dot(L)
var c := L.dot(L) - pow(circle_radius, 2.0)
var discriminent := pow(b, 2.0) - 4.0 * a * c
var max_dist: float
if discriminent < 0.0:
printerr("Cannot find random point in Circle.")
return ray_start
elif is_zero_approx(discriminent):
max_dist = -b / (2.0 * a)
else:
var s := 1.0 if b > 0 else -1.0
var q := (b + s * sqrt(discriminent)) / -2.0
var x0 := q / a
var x1 := c / q
max_dist = x0 if x0 > 0 else x1
return ray_direction * randf_range(exclusion_radius, max_dist) + ray_start
Solution in Action
This is an example of these functions at work, adapted for my project.
The BLUE CIRCLE is the area we are finding a random point in.
The RED CIRCLE is the area of the exclusion zone.
The WHITE LINE is the path to the found target.
The ORANGE LINE and PINK LINE denote the angle range when the exclusion zone intersects with the circle.
Note: The wolf starting outside the circle is unintended.
I’m interested in how the points are distributed in the calculated solution, but my math skills are lacking. Could you generate a few hundred/thousand points and draw them in the test program?
So, it turns out that there are some issues with my calculated solution.
I went ahead and created a test Node2D scene that displays points as they are drawn that uses this script
@tool
extends Node2D
const CIRCLE_VERTICES := 32
@export var radius: float = 5.0:
set(value):
radius = value
if is_node_ready():
_render_circle()
@export var exclusion_radius: float = 1.0
@export_range(1, 1000) var hundred_mult: int = 1
@onready var circle: Polygon2D = $Polygon2D
var _exclusion_center: Vector2
var _point_limit: int:
get():
return 100 * hundred_mult
var _count: int = 0
# Called when the node enters the scene tree for the first time.
func _ready() -> void:
_render_circle()
_exclusion_center = circle.global_position
func _process(_delta: float) -> void:
if Engine.is_editor_hint() or _count >= _point_limit:
return
_draw_point()
_count += 1
if _count >= _point_limit:
print("Finished!")
func _draw_point() -> void:
_render_point(_exclusion_center)
_exclusion_center = _get_random_point_on_ray(_get_random_direction())
func _render_circle() -> void:
var points: PackedVector2Array = []
points.resize(CIRCLE_VERTICES)
for i: int in CIRCLE_VERTICES:
points[i] = Vector2.RIGHT.rotated(TAU / CIRCLE_VERTICES * i) * radius
circle.polygon = points
circle.uv = points
circle.color = Color.WHITE
func _render_point(point_position: Vector2) -> void:
var point_polygon := Polygon2D.new()
circle.add_child(point_polygon)
var points: PackedVector2Array = [
Vector2(-1.0, 1.0),
Vector2(1.0, 1.0),
Vector2(1.0, -1.0),
Vector2(-1.0, -1.0)
]
point_polygon.polygon = points
point_polygon.uv = points
point_polygon.color = Color.NAVY_BLUE
point_polygon.global_position = point_position
func _get_random_direction() -> Vector2:
var v := _exclusion_center - circle.global_position
var d := v.length()
# Rename relevant parameters for conciseness.
var r0 := radius
var r1 := exclusion_radius
if d < abs(r0 - r1) or d > r0 + r1:
# Exclusion zone does not overlap boundaries of circle so any
# direction is valid. Assumes exclusion_center is within circle's
# area.
return Vector2.from_angle(randf() * TAU).normalized()
var u := v.normalized()
var x_vec := (pow(d, 2.0) - pow(r1, 2.0) + pow(r0, 2.0)) * u / (2 * d)
var u_perp := Vector2(u.y, -u.x)
var a_half := (
sqrt(
(-d + r1 - r0)
* (-d - r1 + r0)
* (-d + r1 + r0)
* (d + r0 + r1)
) / d * 0.5
)
var intersect_1 := x_vec - u_perp * a_half
var intersect_2 := x_vec + u_perp * a_half
var v1 := intersect_1 - _exclusion_center
var v2 := intersect_2 - _exclusion_center
var angle := v1.angle_to(v2)
# Want to get the value of the angle that points towards the center of
# circle. Negative angle points away from center.
if angle < 0.0:
angle += TAU
return v1.normalized().rotated(randf() * angle)
func _get_random_point_on_ray(ray_direction: Vector2) -> Vector2:
var L := _exclusion_center - circle.global_position
var a := ray_direction.dot(ray_direction)
var b := 2.0 * ray_direction.dot(L)
var c := L.dot(L) - pow(radius, 2.0)
var discriminent := pow(b, 2.0) - 4.0 * a * c
var max_dist: float
if discriminent < 0.0:
printerr("Cannot find random point in Circle.")
return _exclusion_center
elif is_zero_approx(discriminent):
max_dist = -b / (2.0 * a)
else:
var s := 1.0 if b > 0 else -1.0
var q := (b + s * sqrt(discriminent)) / -2.0
var x0 := q / a
var x1 := c / q
max_dist = x0 if x0 > 0 else x1
return ray_direction * randf_range(exclusion_radius, max_dist) + _exclusion_center
However, when the exclusion radius is big enough, points are drawn outside the area of the circle. Additionally, there are many instances where the random point is not found in _get_random_point_on_ray.
I have figured out what was wrong. I needed to offset the intersection points by the circle position. This is the updated _get_random_direction function.
func _get_random_direction() -> Vector2:
var v := _exclusion_center - circle.global_position
var d := v.length()
# Rename relevant parameters for conciseness.
var r0 := radius
var r1 := exclusion_radius
if d < abs(r0 - r1) or d > r0 + r1:
# Exclusion zone does not overlap boundaries of circle so any
# direction is valid. Assumes exclusion_center is within circle's
# area.
return Vector2.from_angle(randf() * TAU).normalized()
var u := v.normalized()
var x_vec := (pow(d, 2.0) - pow(r1, 2.0) + pow(r0, 2.0)) * u / (2 * d)
var u_perp := Vector2(u.y, -u.x)
var a_half := (
sqrt(
(-d + r1 - r0)
* (-d - r1 + r0)
* (-d + r1 + r0)
* (d + r0 + r1)
) / d * 0.5
)
var intersect_1 := x_vec - u_perp * a_half + circle.global_position
var intersect_2 := x_vec + u_perp * a_half + circle.global_position
var v1 := intersect_1 - _exclusion_center
var v2 := intersect_2 - _exclusion_center
var angle := v1.angle_to(v2)
# Want to get the value of the angle that points towards the center of
# circle. Negative angle points away from center.
if angle < 0.0:
angle += TAU
return v1.normalized().rotated(randf() * angle)
The first step is to obtain the intersection points of the exclusion zone and the circle itself. Using those points, a valid angle range is found, and from there a random direction. It is assumed that the center of the exclusion zone is always WITHIN the boundaries of the circle.
func _get_random_direction(
circle_center: Vector2,
exclusion_center: Vector2,
circle_radius: float,
exclusion_radius: float
) -> Vector2:
var v := exclusion_center - circle_center
var d := v.length()
# Rename relevant parameters for conciseness.
var r0 := circle_radius
var r1 := exclusion_radius
if d < abs(r0 - r1) or d > r0 + r1:
# Exclusion zone does not overlap boundaries of circle so any
# direction is valid. Assumes exclusion_center is within circle's
# area.
return Vector2.from_angle(randf() * TAU).normalized()
var u := v.normalized()
var x_vec := (pow(d, 2.0) - pow(r1, 2.0) + pow(r0, 2.0)) * u / (2 * d)
var u_perp := Vector2(u.y, -u.x)
var a_half := (
sqrt(
(-d + r1 - r0)
* (-d - r1 + r0)
* (-d + r1 + r0)
* (d + r0 + r1)
) / d * 0.5
)
# Offset intersections by circle center as they are originally considered
# set at origin.
var intersect_1 := x_vec - u_perp * a_half + circle_center
var intersect_2 := x_vec + u_perp * a_half + circle_center
var v1 := intersect_1 - exclusion_center
var v2 := intersect_2 - exclusion_center
var angle := v1.angle_to(v2)
# Want to get the value of the angle that points towards the center of
# circle. Negative angle points away from center.
if angle < 0.0:
angle += TAU
return v1.normalized().rotated(randf() * angle)
Step 2: Random Distance
Once a direction is found, the next step is to ray cast from the exclusion zone center and find the points where that ray intersects with the circle. Those intersection points can then be used to calculate the length which gives us the upper bound for the range (the lower bound being the radius of the exclusion zone).
func _get_random_point_on_ray(
ray_start: Vector2,
ray_direction: Vector2,
exclusion_radius: float,
circle_center: Vector2,
circle_radius: float
) -> Vector2:
var L := ray_start - circle_center
var a := ray_direction.dot(ray_direction)
var b := 2.0 * ray_direction.dot(L)
var c := L.dot(L) - pow(circle_radius, 2.0)
var discriminent := pow(b, 2.0) - 4.0 * a * c
var max_dist: float
if discriminent < 0.0:
printerr("Cannot find random point in Circle.")
return ray_start
elif is_zero_approx(discriminent):
max_dist = -b / (2.0 * a)
else:
var s := 1.0 if b > 0 else -1.0
var q := (b + s * sqrt(discriminent)) / -2.0
var x0 := q / a
var x1 := c / q
max_dist = x0 if x0 > 0 else x1
return ray_direction * randf_range(exclusion_radius, max_dist) + ray_start
Distribution Findings
These are samples of 5,000 points for exclusion zones of various sizes.
This method does not fully work when the exclusion zone radius is 0.0. It will occasionally poll a point that is outside the radius of the main circle.
.
