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.
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