I have implemented an A-star implementation which gives a list of points for my RTS game agent to follow. However, the a-star algorithm i implemented is on the grid-based graph. the calculated path looks like stairs when player is moving diagonally. i want to make an algorithm that takes a path (list of Vector3 points) in input & smoothens them based on a given weight. it must be able to create smooth curves instead of jagged paths. it is allowed to make the points itself or to dissolve the points, all of these depending on the weight.
Path Simplification Algorithm
If you want to eliminate the “stairy” or “zigzag” pattern and focus on straight lines along the general direction of movement, a path simplification algorithm like the Ramer-Douglas-Peucker algorithm (RDP) is a better fit. This algorithm reduces a polyline (sequence of points) to a simplified version by keeping only the critical points that define the overall shape while discarding intermediate points causing the zigzag pattern.
Ramer-Douglas-Peucker Algorithm
This algorithm works as follows:
- Start with the first and last points of the path.
- Find the point farthest from the line connecting these two points.
- If the distance of this farthest point exceeds a threshold, it is kept, and the line is split at this point.
- Repeat recursively for the two new segments until no point exceeds the threshold. Here I used iterative approach instead so stack overflow problems don’t occur for large paths.
Following is the iterative version of the Ramer-Douglas-Peucker (RDP) algorithm. This version avoids recursion and uses a stack to manage the segments to be processed, which makes it more efficient for handling long paths.
GDScript RDP Algorithm Implementation (iterative approach)
# path simplification algorithm
# Simplifies a path by removing unnecessary points while preserving the general direction.
# Iterative version of the RDP algorithm.
# @param path: Array of Vector3 points (path from A* algorithm)
# @param tolerance: Minimum distance a point must have from the line to be kept
# @return Array of simplified Vector3 points
func simplify_path(path: Array, tolerance: float) -> Array:
if path.size() < 3:
return path # Cannot simplify if less than 3 points
var result = [] # Final simplified path
var stack = [] # Stack for segments to process
stack.append(Vector2(0, path.size() - 1)) # Start with the entire path
var markers = PackedInt32Array() # Marks points to keep (1 = keep, 0 = discard)
markers.resize(path.size())
# Mark the first and last points as kept
markers[0] = 1
markers[path.size() - 1] = 1
while stack.size() > 0:
var indices = stack.pop_back() # Get the current segment (start, end)
var start_index = indices.x
var end_index = indices.y
var max_distance = 0
var farthest_index = -1
# Find the point farthest from the line segment
for i in range(start_index + 1, end_index):
var distance = point_line_distance(path[i], path[start_index], path[end_index])
if distance > max_distance:
max_distance = distance
farthest_index = i
# If the farthest point exceeds the tolerance, keep it and add new segments
if max_distance > tolerance:
markers[farthest_index] = 1
stack.append(Vector2(start_index, farthest_index)) # Left segment
stack.append(Vector2(farthest_index, end_index)) # Right segment
# Collect the points marked as kept
for i in range(path.size()):
if markers[i] == 1:
result.append(path[i])
return result
# Calculates the perpendicular distance of a point from a line segment
# @param point: The point to measure distance from
# @param line_start: Start of the line segment
# @param line_end: End of the line segment
# @return The perpendicular distance
func point_line_distance(point: Vector3, line_start: Vector3, line_end: Vector3) -> float:
var line = line_end - line_start
var length_squared = line.length_squared()
if length_squared == 0:
return (point - line_start).length() # Line is a single point
# Projection of 'point' onto the line
var t = ((point - line_start).dot(line)) / length_squared
t = clamp(t, 0.0, 1.0) # Clamp to line segment bounds
var projection = line_start + t * line
return (point - projection).length()Usage
var path = [] # list of Vector3 points
var tolerance = 0.5 # how much simplification is needed
var simplified_path = simplify_path(path, tolerance)
# Move NPC along simplified pathThank you for reading <3