How to connect and store post and walls and update when needed

[NinjoOnline]

I’m trying to create a wall placement system, and I need it to auto update when you place walls through walls, etc. to cut in a correct manner
So example, you place a wall, theres posts either side

And then place a perpendicular wall

It should know that said wall needs to split

But I can’t just look at pole positions and figure it out, as players could place walls like so

So my question is, how do I store this info in a manner that makes it easy to know what’s what?? I was thinking of having it something like

{
    ["Wall"] = {
        Pole1 = pole1.Position,
        Pole2 = pole2.Position,
    }
}

And then I can tell where said wall is, based on those 2 poles positions. But I’m unsure what else to really do from here

[ThanksRoBama (Emma)]

I’m actually working on a similar system at the moment

I use a 3D segment-segment intersection algorithm to find the intersection point between the placed wall and every other wall. This algorithm also lets you find out how far along each segment the intersection point is. So I just limit the placed wall to only to go the first existing wall that it intersects.

Here’s a great resource for 2D and 3D geometry algos: C++ Code TOC

although for this specific thing I based my code on this: Point, Line, Plane

And yeah I store walls in a similar manner to what you posted. I have wall objects and corner objects, and each object has a reference to it’s connected objects. So each wall has a list of corners that it’s connected to (always 2) and each corner has a list of walls that it’s connected to (1 or more). I keep around a list of every wall and a list of every corner, so when I want to check if the wall-being-placed or corner-being-placed is intersecting any existing walls I can just loop through them.

[NinjoOnline]

I think I’m gonna change my thought process a little, as I feared it’d be too hard for me to figure out that math myself. Instead of a solid wall being made, breaking them up into segments. That way when a wall is placed through like so there’s need for cutting.

This idea is unlikely to work with angled walls intersecting, so I’m gonna need to think about that too

I do want to stick with this segment idea if possible, as it’d allow for more customisation in the future

EDIT
scratch that idea. How’s this for storing objets?

-- Store the walls
	AllWalls[Wall1] = {
		[1] = Pole1,
		[2] = Pole2
	}
	
	AllWalls[Wall2] = {
		[1] = Pole1,
		[2] = Pole2
	}
	
	-- Store the poles and the walls they on
	if not AllPoles[Pole1] then
		AllPoles[Pole1] = {}
	end
	
	table.insert(AllPoles[Pole1], Wall1)
	table.insert(AllPoles[Pole1], Wall2)
	
	if not AllPoles[Pole2] then
		AllPoles[Pole2] = {}
	end

	table.insert(AllPoles[Pole2], Wall1)
	table.insert(AllPoles[Pole2], Wall2)

Unsure if I should store as positions or instances

[ThanksRoBama (Emma)]

Yeah no problem! I honestly haven’t studied the formulas to like really get them, just ported the code 1-to-1 and got some thing that works If you’re really curious about the math I could take another look and let you know how I understand it.

Here’s the code though if you just want to get it working. Feel free to use it in your own game projects, but please don’t distribute it in any other way. I’m planning on adapting the entirety of the original C++ library and releasing it here on the forums.

I’ve added some comments explaining what the functions do, but ask away if anything is unclear. You’ll want the one called segmentsIntersect and call it with two segments, one for each wall you want to find the intersection point between. It works in 3D, so two segments can miss each other even if they’re not parallel unlike in 2D. Just make sure they’re actually crossing E.g. make sure the Y component of each segment endpoint is 0 or at least the same.

--!nocheck
--Geom.lua

local SMALL_NUMBER = 10e-5 --For equality comparisons that work regardless of floating-point error

export type Plane = {
	Point: Vector3,
	Normal: Vector3,
}

export type Segment = {
	Point1: Vector3,
	Point2: Vector3,
}

export type Ray = {
	Point: Vector3,
	Direction: Vector3,
}

export type Line = {
	Point1: Vector3,
	Point2: Vector3,
}

--Returns the number of intersections and intersection point between a line segment and a plane
--0 if none, 1 if one, 2 if infinite (i.e. the segment lies in the plane, so any point on the segment is in the plane)
--An intersection point is only returned if there's exactly 1 intersection
function segmentPlaneIntersect(s: Segment, p: Plane): (number, Vector3?)
	local u = s.Point2 - s.Point1
	local w = s.Point1 - p.Point

	local D = p.Normal:Dot(u)
	local N = -p.Normal:Dot(w)

	if math.abs(D) < SMALL_NUMBER then --Parallel
		if N == 0 then --Segment in plane
			return 2, nil
		else --No intersection
			return 0, nil 
		end
	end

	local sI = N / D
	if sI < 0 or sI > 1 then -- No intersection
		return 0, nil
	end

	return 1, s.Point1 + sI * u
end


--Returns the number of intersections and intersection point between a ray and a plane
--0 if none, 1 if one, 2 if infinite (i.e. the segment lies in the plane, so any point on the ray is in the plane)
--An intersection point is only returned if there's exactly 1 intersection
function rayPlaneIntersect(r: Ray, p: Plane): (number, Vector3?)
	local u = r.Direction
	local w = r.Point - p.Point

	local D = p.Normal:Dot(u)
	local N = -p.Normal:Dot(w)

	if math.abs(D) < 10e-5 then --Parallel
		if N == 0 then --Segment in plane
			return 2, nil
		else --No intersection
			return 0, nil 
		end
	end

	local sI = N / D
	if sI < 0 then -- No intersection
		return 0, nil
	end

	return 1, r.Point + sI * u
end

--Returns the shortest line segment between two lines.
--Additionally returns how far along each line the endpoints of said segment are, as a fraction of the vector from each line's Point1 to it's Point2.
function linesShortestSegment(a: Line, b: Line): (Segment, number, number)
	--From http://paulbourke.net/geometry/pointlineplane/linelineintersect.m
	local p1, p2, p3, p4 = a.Point1, a.Point2, b.Point1, b.Point2
	
	local p13 = p1 - p3
	local p21 = p2 - p1
	local p43 = p4 - p3
	
	local d1343 = p13.X * p43.X + p13.Y * p43.Y + p13.Z * p43.Z
	local d4321 = p43.X * p21.X + p43.Y * p21.Y + p43.Z * p21.Z
	local d1321 = p13.X * p21.X + p13.Y * p21.Y + p13.Z * p21.Z
	local d4343 = p43.X * p43.X + p43.Y * p43.Y + p43.Z * p43.Z
	local d2121 = p21.X * p21.X + p21.Y * p21.Y + p21.Z * p21.Z

	
	local mu_a = (d1343 * d4321 - d1321 * d4343) / (d2121 * d4343 - d4321 * d4321)
	local mu_b = (d1343 + d4321 * mu_a) / d4343
	
	local pa = p1 + mu_a * p21
	local pb = p3 + mu_b * p43
	
	return {
		Point1 = pa,
		Point2 = pb,
	}, mu_a, mu_b
end

--Returns the intersection point between two lines.
--Additionally returns how far along each line the intersection point is, as a fraction of the vector from each line's Point1 to it's Point2.
function linesIntersect(a: Line, b: Line): (Vector3?, number?, number?)
	local difference, mu_a, mu_b = linesShortestSegment(a, b)
	
	if (difference.Point2 - difference.Point1).Magnitude <= SMALL_NUMBER then
		return difference.Point1, mu_a, mu_b
	end
	
	return
end

--Returns the intersection point between two line segments.
--Additionally returns how far along each segment the intersection point is, as a fraction of the vector from each segments's Point1 to it's Point2.
function segmentsIntersect(a: Segment, b: Segment): (Vector3?, number?, number?)
	local difference, mu_a, mu_b = linesShortestSegment(a, b)
	
	if mu_a >= 0 and mu_a <= 1 and mu_b >= 0 and mu_b <= 1 then
		if (difference.Point2 - difference.Point1).Magnitude <= SMALL_NUMBER then
			if (difference.Point2 - difference.Point1).Magnitude <= SMALL_NUMBER then
				return difference.Point1, mu_a, mu_b
			end
		end
	end
	
	return
end

--Returns a projected onto b
--See https://en.wikipedia.org/wiki/Vector_projection
function project(a: Vector3, b: Vector3): Vector3
	return b * (a:Dot(b)) / (b:Dot(b))
end

--Returns whether a point is on a line segment (within some small error)
--Additionally returns how far along the segment the point is, as a fraction of the vector from the segment's Point1 to it's Point2.
function isPointOnSegment(p: Vector3, s: Segment): (boolean, number?)
	local p1p = p - s.Point1
	local p12 = s.Point2 - s.Point1
	local mu = p1p:Dot(p12) / p12:Dot(p12) --Progress along s of (p projected onto s)

	if mu < 0 or mu > 1 then --Off the ends of the segment
		return false, mu
	end 

	local pOnS = s.Point1 + mu * p12 --p projected onto s
	local d = (p - pOnS).Magnitude

	if d > SMALL_NUMBER then --Too far from segment
		return false, mu
	end

	return true, mu
end

--Returns whether a point is on a line (within some small error)
--Additionally returns how far along the line the point is, as a fraction of the vector from the line's Point1 to it's Point2.
function isPointOnLine(p: Vector3, l: Line): (boolean, number?)
	local p1p = p - l.Point1
	local p12 = l.Point2 - l.Point1
	local mu = p1p:Dot(p12) / p12:Dot(p12) --Progress along s of (p projected onto s)

	local pOnS = l.Point1 + mu * p12 --p projected onto s
	local d = (p - pOnS).Magnitude

	if d > SMALL_NUMBER then --Too far from segment
		return false, mu
	end

	return true, mu
end

return {
	segmentPlaneIntersect = segmentPlaneIntersect,
	rayPlaneIntersect = rayPlaneIntersect,
	linesShortestSegment = linesShortestSegment,
	linesIntersect = linesIntersect,
	segmentsIntersect = segmentsIntersect,
	isPointOnSegment = isPointOnSegment,
	isPointOnLine = isPointOnLine
}