Circuit schematic wire layout algo?

Blitz3D Forums/Blitz3D Programming/Circuit schematic wire layout algo?

octothorpe

(Posted 2006) [#1]

I'm making a digital logic simulator just for fun and my wires are currently single quads stretched between the contact points of my components. In good circuit schematics, wires are usually composed of several segments, drawn horizontally and vertically, and (most importantly) do not overlap components.

Does anyone know of an algorithm (or any ideas at all) I can use to determine how to lay out my wires between arbitrarily positioned contact points on arbitrarily positioned components? I'm thinking a function which uses trial-and-error checking for collisions with components, then returns a list of x,y coordinates for the coords of the segments that will make up a wire.

Here are some examples of some rather tricky circuit schematics: http://images.google.com/images?q=jk%20flip%20flop

And here is my work-in-progress simulator. Right-click the "switches" on the left to toggle their state and watch the gates flip their logic states. You can add and remove wires by left clicking and move components by left dragging. To change the gates you're playing with, you'll need to modify the top of the program (create_component() calls) - feel free to remove all the code responsible for adding wires (create_wire() calls) in the initialization: you can add wires while you're running the program. The circuit depicted is a JK Flip Flop: a single bit of memory composed of four NAND gates.

Const INFINITY# = 99999.0^99999.0 

Const WIRE_RADIUS# = .05

Type wire
	Field entity
	Field conpoint1.conpoint
	Field conpoint2.conpoint
	Field conpoint1_node.listC_node
	Field conpoint2_node.listC_node
End Type

Type conpoint
	Field class$
	Field entity
	Field parent.component
	Field target.conpoint
	Field wire_list.listC
	Field logic_state
End Type

Type component
	Field class$
	Field entity
	Field conpoint_list.listC ; todo: should this be a hash table instead?
End Type

;--------------------------------------------------------------

Include "../common/listC.bb" ; <a href="http://blitzbasic.com/codearcs/codearcs.php?code=1438" target="_blank">http://blitzbasic.com/codearcs/codearcs.php?code=1438</a>

;--------------------------------------------------------------

Graphics3D 800, 600, 32, 0
camera = CreateCamera()
CameraZoom(camera, 1.6)
PositionEntity(camera, 0, 0, -20)
light = CreateLight()
TurnEntity(light, 20, 20, 0)

Global wire_brush = CreateBrush() ; har har
BrushColor(wire_brush, 255, 255, 255)
BrushFX(wire_brush, 1) ; 1=fullbright

s1.component = create_component("switch", -6,  2)
s2.component = create_component("switch", -6, -2)
n1.component = create_component("nand",   -2,  2)
n2.component = create_component("nand",   -2, -2)
n3.component = create_component("nand",    2,  2)
n4.component = create_component("nand",    2, -2)
o1.component = create_component("motor",   6,  2)
o2.component = create_component("motor",   6, -2)

create_wire(get_conpoint_by_index(s1, 0), get_conpoint_by_index(n1, 1))
create_wire(get_conpoint_by_index(s2, 0), get_conpoint_by_index(n2, 0))
create_wire(get_conpoint_by_index(n1, 2), get_conpoint_by_index(n3, 1))
create_wire(get_conpoint_by_index(n2, 2), get_conpoint_by_index(n4, 0))
create_wire(get_conpoint_by_index(n3, 2), get_conpoint_by_index(n4, 1))
update_logic() ; grumble grumble: fix nasty feedback loop in jk flip flop
create_wire(get_conpoint_by_index(n4, 2), get_conpoint_by_index(n3, 0))
create_wire(get_conpoint_by_index(n3, 2), get_conpoint_by_index(n2, 1))
create_wire(get_conpoint_by_index(n4, 2), get_conpoint_by_index(n1, 0))
create_wire(get_conpoint_by_index(n3, 2), get_conpoint_by_index(o1, 0))
create_wire(get_conpoint_by_index(n4, 2), get_conpoint_by_index(o2, 0))

Local game_state$ = "free"
Local drag_component.component = Null
Local drag_offset_x, drag_offset_y
Local connection_start.conpoint = Null

While Not KeyHit(1)
	mx = MouseX() : my = MouseY()

	; get mouseover component
	Local mouseover_component.component = Null
	Local mouseover_conpoint.conpoint = Null
	CameraPick(camera, mx, my)
	Local mouseover_entity = PickedEntity()
	If mouseover_entity <> 0 Then
		If Left$(EntityName(mouseover_entity), 10) = "COMPONENT_" Then
			mouseover_component = Object.component(Mid$(EntityName(mouseover_entity), 11))
		ElseIf Left$(EntityName(mouseover_entity), 9) = "CONPOINT_" Then
			mouseover_conpoint = Object.conpoint(Mid$(EntityName(mouseover_entity), 10))
			;mouseover_component = mouseover_conpoint\parent
		EndIf
	EndIf

	mh1 = MouseHit(1)
	mh2 = MouseHit(2)
	Select game_state$
		Case "free"
			; drag positon of components with left mouse button on component
			If MouseDown(1) And mouseover_component <> Null Then
				game_state$ = "drag"
				drag_component = mouseover_component
				; TODO: there must be a better way than cameraproject!!
				CameraProject(camera, EntityX(mouseover_component\entity), EntityY(mouseover_component\entity), EntityZ(mouseover_component\entity))
				drag_offset_x = ProjectedX() - mx
				drag_offset_y = ProjectedY() - my
			; toggle switches with right mouse button on component
			ElseIf mh2 And mouseover_component <> Null Then
				If mouseover_component\class = "switch" Then
					output_conpoint.conpoint = Object.conpoint(mouseover_component\conpoint_list\first_node\value)
					output_conpoint\logic_state = Not(output_conpoint\logic_state)
				EndIf
			; start a wire connection with left mouse button on conpoint
			ElseIf mh1 And mouseover_conpoint <> Null Then
				game_state$ = "connect"
				connection_start = mouseover_conpoint
			; destroy all wires with right mouse button on conpoint
			ElseIf mh2 And mouseover_conpoint <> Null Then
				; for doomed_wire.wire = each mouseover_conpoint\wire_list
				it.listC_iter = list_iterator_begin(mouseover_conpoint\wire_list)
				While list_iterator_next(it)
					doomed_wire.wire = Object.wire(list_iterator_get(it))
					remove_wire(doomed_wire)
				Wend
			EndIf
		Case "drag"
			PositionEntityFrom2D(camera, drag_component\entity, mx + drag_offset_x, my + drag_offset_y, 20, 1.6)

			; for affected_conpoint.conpoint = each drag_component\conpoint_list
			it.listC_iter = list_iterator_begin(drag_component\conpoint_list)
			While list_iterator_next(it)
				affected_conpoint.conpoint = Object.conpoint(list_iterator_get(it))
				; for affected_wire.wire = each affected_conpoint\wire_list
				it2.listC_iter = list_iterator_begin(affected_conpoint\wire_list)
				While list_iterator_next(it2)
					affected_wire.wire = Object.wire(list_iterator_get(it2))
					update_wire(affected_wire)
				Wend
			Wend

			If MouseDown(1) = False Then
				game_state$ = "free"
			EndIf
		Case "connect"
			If mh1 Then
				game_state$ = "free"

				hot_conpoint.conpoint = mouseover_conpoint
				If hot_conpoint = Null Then hot_conpoint = find_nearest_conpoint(mouseover_component, connection_start\class)
				If hot_conpoint <> Null Then
					If hot_conpoint\class <> connection_start\class Then
					
						; lastly, make sure the "input" conpoint doesn't have a connection already
						If hot_conpoint\class = "input" Then
							input_conpoint.conpoint = hot_conpoint
						Else
							input_conpoint.conpoint = connection_start
						EndIf
						If list_count(input_conpoint\wire_list) = 0 Then

							create_wire(connection_start, hot_conpoint)
						EndIf
					EndIf
				EndIf
			EndIf
	End Select
	
	update_logic()
	
	RenderWorld
	Text 0, 0, game_state$
	Flip
Wend
End

;--------------------------------------------------------------

Function create_component.component(class$, x#=0, y#=0)
	c.component = New component
	c\conpoint_list = list_new()
	c\class = class$
	c\entity = CreateCube()
	NameEntity(c\entity, "COMPONENT_"+Handle(c))
	PositionEntity(c\entity, x, y, 0)
	EntityPickMode(c\entity, 2)
	ScaleEntity(c\entity, 1, 1, 1)
	
	Select c\class
		Case "switch"
			EntityColor(c\entity,   0, 255, 255)
			inputs = 0 : outputs = 1
		Case "motor"
			EntityColor(c\entity,   0,   0, 255)
			inputs = 1 : outputs = 0
		Case "and"
			EntityColor(c\entity, 255, 255,   0)
			inputs = 2 : outputs = 1
		Case "or"
			EntityColor(c\entity,   0, 255,   0)
			inputs = 2 : outputs = 1
		Case "nand"
			EntityColor(c\entity, 127, 127,   0)
			inputs = 2 : outputs = 1
		Case "nor"
			EntityColor(c\entity,   0, 127,   0)
			inputs = 2 : outputs = 1
		Case "not"
			EntityColor(c\entity, 255,   0,   0)
			inputs = 1 : outputs = 1
	End Select
	
	If inputs = 1 Then
		;c\input1 = create_conpoint(c, "input", -1, 0)
		add_conpoint(c, "input", -1, 0)
	ElseIf inputs = 2 Then
		;c\input1 = create_conpoint(c, "input", -1, -.5)
		;c\input2 = create_conpoint(c, "input", -1, +.5)
		add_conpoint(c, "input", -1, -.5)
		add_conpoint(c, "input", -1, +.5)
	EndIf

	If outputs = 1 Then
		;c\output = create_conpoint(c, "output", 1, 0)
		add_conpoint(c, "output", 1, 0)
	EndIf
	
	Return c
End Function

Function add_conpoint.conpoint(parent.component, class$, x#=0, y#=0, z#=0)
	cp.conpoint = New conpoint
	cp\wire_list = list_new()
	cp\class = class$
	cp\parent = parent

	cp\entity = CreateSphere(8, parent\entity)
	NameEntity(cp\entity, "CONPOINT_"+Handle(cp))
	PositionEntity(cp\entity, x, y, z)
	EntityPickMode(cp\entity, 2)
	EntityColor(cp\entity, 255, 255, 255)
	ScaleEntity(cp\entity, .3, .3, .3)

	list_push(parent\conpoint_list, Handle(cp))
	Return cp
End Function

Function find_nearest_conpoint.conpoint(mouseover_component.component, disallowed_conpoint_class$)
	Local nearest_conpoint.conpoint = Null
	If mouseover_component <> Null Then
		Local sample_pivot = CreatePivot()
		PositionEntity(sample_pivot, PickedX(), PickedY(), PickedZ())
		Local smallest_distance# = INFINITY
		
		; for this_conpoint.conpoint = each mouseover_component\conpoint_list
		it.listC_iter = list_iterator_begin(mouseover_component\conpoint_list)
		While list_iterator_next(it)
			this_conpoint.conpoint = Object.conpoint(list_iterator_get(it))

			If this_conpoint\class$ <> disallowed_conpoint_class$ Then

				d# = EntityDistance(sample_pivot, this_conpoint\entity)
				If d < smallest_distance Then
					smallest_distance = d
					nearest_conpoint = this_conpoint
				EndIf
			EndIf
		Wend
		
		FreeEntity(samplepivot)
	EndIf
	Return nearest_conpoint
End Function

Function get_conpoint_by_index.conpoint(c.component, index%)
	; negative indexes reference elements in reverse order
	Return Object.conpoint(list_node_get_value(list_find_node_by_position(c\conpoint_list, index)))
End Function

Function create_wire.wire(conpoint1.conpoint, conpoint2.conpoint)
	If conpoint1\class = "output" Then temp.conpoint=conpoint1:conpoint1=conpoint2:conpoint2=temp

	w.wire = New wire
	w\conpoint1 = conpoint1
	w\conpoint2 = conpoint2
	
	w\conpoint1_node = list_push(conpoint1\wire_list, Handle(w))
	w\conpoint2_node = list_push(conpoint2\wire_list, Handle(w))

	w\entity = CreateMesh()
	s = CreateSurface(w\entity, wire_brush)
	v1 = AddVertex(s, 0, 0, 0, 0, 1)
	v2 = AddVertex(s, 0, 0, 0, 0, 0)
	v3 = AddVertex(s, 0, 0, 0, 1, 0)
	v4 = AddVertex(s, 0, 0, 0, 1, 1)
	AddTriangle(s, v1, v2, v3)
	AddTriangle(s, v1, v3, v4)

	update_wire(w)
	
	Return w
End Function

Function remove_wire(w.wire)
	FreeEntity(w\entity)
	list_remove_node(w\conpoint1_node)
	list_remove_node(w\conpoint2_node)
	Delete w
End Function

Function update_wire(w.wire)
	cp1x# = EntityX(w\conpoint1\entity, True)
	cp1y# = EntityY(w\conpoint1\entity, True)
	cp1z# = EntityZ(w\conpoint1\entity, True)
	cp2x# = EntityX(w\conpoint2\entity, True)
	cp2y# = EntityY(w\conpoint2\entity, True)
	cp2z# = EntityZ(w\conpoint2\entity, True)

	ang# = ATan2(cp2y - cp1y, cp2x - cp1x)

	x1# = cp1x + Cos(ang-90)*WIRE_RADIUS
	y1# = cp1y + Sin(ang-90)*WIRE_RADIUS
	z1# = cp1z
	x2# = cp1x + Cos(ang+90)*WIRE_RADIUS
	y2# = cp1y + Sin(ang+90)*WIRE_RADIUS
	z2# = cp1z
	x3# = cp2x + Cos(ang+90)*WIRE_RADIUS
	y3# = cp2y + Sin(ang+90)*WIRE_RADIUS
	z3# = cp2z
	x4# = cp2x + Cos(ang-90)*WIRE_RADIUS
	y4# = cp2y + Sin(ang-90)*WIRE_RADIUS
	z4# = cp2z

	s = GetSurface(w\entity, 1)
	VertexCoords(s, 0, x1, y1, z1)
	VertexCoords(s, 1, x2, y2, z2)
	VertexCoords(s, 2, x3, y3, z3)
	VertexCoords(s, 3, x4, y4, z4)
End Function

Function PositionEntityFrom2D(cam,entity,x2d#,y2d#,height#=0,camZoom#=1)
	gw=GraphicsWidth()
	gh=GraphicsHeight()
	x#=-((gw/2)-x2d)
	y#=(gh/2)-y2d
	parent=GetParent(entity)
	EntityParent entity,cam
	z#=Abs(EntityZ(entity))
	div#=(gw/(2/camzoom))/z
	x=x/div
	y=y/div
	
	TFormPoint x,y,z,cam,0
	y3d#=TFormedY()
	x3d#=TFormedX()
	z3d#=TFormedZ()
	EntityParent entity,parent
	PositionEntity entity,x3d,y3d,z3d
End Function

Function update_logic()
	For c.component = Each component
		Select c\class
			Case "and"
				input1.conpoint = get_conpoint_by_index(c, 0)
				input2.conpoint = get_conpoint_by_index(c, 1)
				output.conpoint = get_conpoint_by_index(c, -1)
				output\logic_state = input1\logic_state And input2\logic_state
			Case "nand"
				input1.conpoint = get_conpoint_by_index(c, 0)
				input2.conpoint = get_conpoint_by_index(c, 1)
				output.conpoint = get_conpoint_by_index(c, -1)
				output\logic_state = Not(input1\logic_state And input2\logic_state)
			Case "or"
				input1.conpoint = get_conpoint_by_index(c, 0)
				input2.conpoint = get_conpoint_by_index(c, 1)
				output.conpoint = get_conpoint_by_index(c, -1)
				output\logic_state = input1\logic_state Or input2\logic_state
			Case "nor"
				input1.conpoint = get_conpoint_by_index(c, 0)
				input2.conpoint = get_conpoint_by_index(c, 1)
				output.conpoint = get_conpoint_by_index(c, -1)
				output\logic_state = Not(input1\logic_state Or input2\logic_state)
			Case "not"
				input1.conpoint = get_conpoint_by_index(c, 0)
				output.conpoint = get_conpoint_by_index(c, -1)
				output\logic_state = Not(input1\logic_state)
		End Select
	Next
	
	For cp.conpoint = Each conpoint
		If cp\class = "output" Then
			; for connected_wire.wire = each cp\wire_list
			it.listC_iter = list_iterator_begin(cp\wire_list)
			While list_iterator_next(it)
				connected_wire.wire = Object.wire(list_iterator_get(it))
				If cp = connected_wire\conpoint1 Then
					target_conpoint.conpoint = connected_wire\conpoint2
				Else
					target_conpoint.conpoint = connected_wire\conpoint1
				EndIf
				If target_conpoint\class = "input" Then
					target_conpoint\logic_state = cp\logic_state
				EndIf
			Wend
		EndIf
	Next

	For cp.conpoint = Each conpoint
		If cp\logic_state Then
			EntityColor(cp\entity, 255,   0,   0)
		Else
			EntityColor(cp\entity,   0,   0, 255)
		EndIf
	Next
End Function

WolRon

(Posted 2006) [#2]

Haven't checked out your code (mostly due to not bothering to download the include file), but wouldn't laying out all of your components on some sort of grid help to determine where you can/can't lay down circuit connections?

Dreamora

(Posted 2006) [#3]

You might check google or more programming related pages for "scan line algorithms" which are what normally is used on geometric problems to find a solution. They are suited especially for your situation where you are looking for wire layout.

big10p

(Posted 2006) [#4]

Not sure exactly what you want, but doesn't this just boil down to 2D pathfinding? Would a modified A* algo do the job?