Finding a line-line intersection has a well documented solution, and while the equation might look complicated it is really simple enough to not warrant a library to solve.
In python it might look like this:
# line is a tuple of two Vector2 (the two end points of the line)
def line_length(line:tuple):
a = Vector2(line[0])
b = Vector2(line[1])
return (b - a).length()
# line is a tuple of two Vector2 (the two end points of the line)
def line_contains_point(line:tuple, point:Vector2):
a = line[0]
b = line[1]
if a == point or b == point:
return True
l = line_length(line)
a_to_point = point - a
b_to_point = point - b
return a_to_point.length() <= l and b_to_point.length() <= l
# line_to_check is a tuple of two Vector2 (the two end points of the line)
# line_to_check_against is a tuple of two Vector2 (the two end points of the line)
def find_line_intersection(line_to_check:tuple, line_to_check_against:tuple):
x1 = line_to_check[0].x
y1 = line_to_check[0].y
x2 = line_to_check[1].x
y2 = line_to_check[1].y
x3 = line_to_check_against[0].x
y3 = line_to_check_against[0].y
x4 = line_to_check_against[1].x
y4 = line_to_check_against[1].y
denominator = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4)
if denominator == 0:
return (True, None)
xNominator = (x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4)
yNominator = (x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4)
px = xNominator / denominator
py = yNominator / denominator
point = Vector2(px, py)
on_line = line_contains_point(line_to_check, point) and line_contains_point(line_to_check_against, point)
return (on_line is not None and on_line, point)
An algorithm that creates a path that does not intersects with itself simple enough to create, as all it has to do is to check the new line to see if it intersects with any of the previous lines:
lines[0]: line starting at (x:0, y:0) and ending at (x:0, y:1)
for i: 1 to m:
possible_angles = -90 to 90 in random order
for random_angle in possible_angle
new_line: new line starting at the end of lines[i-1] forming and angle = random_angle
between new_line and and lines[i]
if not intersects(new_line,lines)
lines[i]: new_line
break
What is harder is to find an algorithm that never "wraps in" on itself to the point where there is no next line that does not intersect an existing line.
But this can potentially be solved by detecting that state, and in those cases remove a number of path segments and then trying again.
This sort of solution gets progressively slower as the max length of the path goes up, but depending on your use-case it could work.
In the above example I manually add a segment on a key-press to slow the process down, I also reduce the path manually when it's stuck in a loop, but that would just be a matter of saying if stuck remove N number of segments.
Full python source for the above example:
import random
import pygame
from pygame.math import Vector2
pygame.init()
screen = pygame.display.set_mode((400, 300))
should_run = True
# line is a tuple of two Vector2 (the two end points of the line)
def line_length(line:tuple):
a = Vector2(line[0])
b = Vector2(line[1])
return (b - a).length()
# line is a tuple of two Vector2 (the two end points of the line)
def line_contains_point(line:tuple, point:Vector2):
a = line[0]
b = line[1]
if a == point or b == point:
return True
l = line_length(line)
a_to_point = point - a
b_to_point = point - b
return a_to_point.length() <= l and b_to_point.length() <= l
# line_to_check is a tuple of two Vector2 (the two end points of the line)
# line_to_check_against is a tuple of two Vector2 (the two end points of the line)
def find_line_intersection(line_to_check:tuple, line_to_check_against:tuple):
x1 = line_to_check[0].x
y1 = line_to_check[0].y
x2 = line_to_check[1].x
y2 = line_to_check[1].y
x3 = line_to_check_against[0].x
y3 = line_to_check_against[0].y
x4 = line_to_check_against[1].x
y4 = line_to_check_against[1].y
denominator = (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4)
if denominator == 0:
return (True, None)
xNominator = (x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4)
yNominator = (x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4)
px = xNominator / denominator
py = yNominator / denominator
point = Vector2(px, py)
on_line = line_contains_point(line_to_check, point) and line_contains_point(line_to_check_against, point)
return (on_line is not None and on_line, point)
def extend_path(path:list, line_length:float):
from_point = path[-1]
to_point = Vector2()
possible_angles = list(range(-90, 90, 1))
random.shuffle(possible_angles)
last_direction = (path[-1] - path[-2]) if len(path) > 1 else Vector2(line_length, 0)
while len(possible_angles) > 0:
angle = possible_angles.pop(0)
to_point = from_point + last_direction.rotate(angle)
path.append(to_point)
if check_if_path_is_valid(path):
return True
path.pop()
return False
def check_if_path_is_valid(path:list):
lines = []
for index in range(1, len(path)):
lines.append( (path[index - 1], path[index]))
for line in lines:
for index in range(1, len(path)):
other_line = (path[index - 1], path[index])
intersects_on_line, intersection_point = find_line_intersection(line, other_line)
if other_line != line and intersects_on_line:
if intersection_point != line[0] and intersection_point != line[1]:
return False
return True
point = Vector2(200, 150)
path = [ point ]
mouse_position = Vector2()
extend_path(path, 16)
while should_run:
screen.fill((10, 20, 40))
# Build two-point segments from path
lines = []
for index in range(1, len(path)):
lines.append( (path[index - 1], path[index]))
for line in lines:
pygame.draw.line(screen, (40, 80, 160), line[0], line[1])
pygame.display.flip()
for events in pygame.event.get():
if events.type == pygame.KEYDOWN:
if events.key == pygame.K_w:
if not extend_path(path, 16):
path.pop()
if events.key == pygame.K_q:
path = [ point ]
if events.key == pygame.K_e:
path.pop()
if events.type == pygame.MOUSEMOTION:
mouse_position = pygame.mouse.get_pos()
if events.type == pygame.QUIT:
should_run = False
