Reducing the number of verts on a path

Kequc

I'm using a implementation of the RDP algorithm to eliminate unnecessary verts on a given A* path. If you're not familiar with RDP there is a Wikipedia article about it.

https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Here's my implementation:

const CULL_THRESHOLD: = 1.0

static func _rdp(verts: Array) -> Array:
	if verts.size() <= 2: return verts
	var d_max: = 0.0
	var index: = 0
	for i in range(1, verts.size() - 1):
		var d: float = point_line_distance(verts[i], verts.front(), verts.back())
		if d <= d_max: continue
		index = i
		d_max = d
	if d_max < CULL_THRESHOLD:
		return [verts.front(), verts.back()]
	var path: Array = _rdp(verts.slice(0, index))
	path.pop_back()
	return path + _rdp(verts.slice(index, verts.size() - 1))

static func point_line_distance(point: Vector3, start: Vector3, end: Vector3) -> float:
	var n: float = abs((end.x - start.x) * (start.z - point.z) - (start.x - point.x) * (end.z - start.z))
	var d: float = sqrt(pow(end.x - start.x, 2) + pow(end.z - start.z, 2))
	return n / d

It works and makes my paths look quite a bit more organic and... sane. My question though is there are sometimes key points on paths that I wouldn't want this algorithm to remove. For example when traversing stairs, I've noted my actors sometimes approach the stairs from an angle and then get hung up on them.

One thing that might work is if I'm calculating point_line_distance on all three axis including y. But I haven't been able to really figure out how to do that in the function.

Calculating the third axis would mean that the point isn't eliminated if it's directly before or directly after an incline. Anyone have any ideas? I'd like not to have to remove this.

Kequc

An alternative I suppose would be to detect whether the path uses stairs and then cut the path up before and after using stairs.

I might have to do that anyway in case I ever want to implement elevators or similar. That might be a direction that makes more sense...

So, alternate question. Is there a built-in gdscript method that calculates the distance between a point and a line? That way I could at least eliminate the need to build my own point_line_distance method. Might be a slight optimisation.

Kequc

I mean I guess the simple solution involves a bit of refactoring in my point_line_distance as follows:

static func calc_distance(from: Vector3, point1: Vector3, point2: Vector3) -> float:
	if abs(from.y - point2.y) > 0.1: return INF
	var a: float = point1.z - point2.z;
	var b: float = point2.x - point1.x;
	var c: float = point1.x * point2.z - point2.x * point1.z;
	return abs(a * from.x + b * from.z + c) / sqrt(a * a + b * b);

Returning an infinite distance when there's been a height distance just forces it to care. That solves it, as long as I don't care about splitting up the path.

It's the simple solution.

Edit: Nah that doesn't work either, it doesn't force there to be a vert at the top of he stairs, I've got to just split up the paths.