Node based path-finding

[HezkoreParticipant]

I’m trying to figure out a simple way to do node based path-finding, but my math skills are terrible so it’s proven to be a bit too hard for me.
This is what I’ve got so far, it has no path-finding code.
Could someone point me in the right direction here, or help me out with some example?
At line 375 is where the path-finding code would go.

Monkey

#Import "<std>" #Import "<mojo>" #Import "<mojox>" Using std.. Using mojo.. Using mojox.. Class MyWindow Extends Window Global pathPlaceStep:Int Method New() Super.New("Simple Mojo Gui App",640,480,WindowFlags.Resizable) Node.camera.X=640/2 Node.camera.Y=480/2 For Local i:Int=0 Until 25 New Node(Rnd(-640,640),Rnd(-480,480)) Next ClearColor=Color.DarkGrey ClearEnabled=True End Method OnRender(canvas:Canvas) Override App.RequestRender() canvas.DrawText("Click & Drag to Move node",0,0) canvas.DrawText("Ctrl & Drag to Link node",0,15) canvas.DrawText("Shift & Click to Insta-Link node",0,15*2) canvas.DrawText("Alt & Click to Remove node",0,15*3) canvas.DrawText("W,A,S,D to Move camera",0,15*4) canvas.DrawText("Numpad Minus to Remove node",0,15*5) canvas.DrawText("Numpad Plus to Add node",0,15*6) If Self.pathPlaceStep Then canvas.DrawText("Space to Place path end",0,15*7) Else canvas.DrawText("Space to Place path start",0,15*7) Endif If Keyboard.KeyDown(Key.W) Then Node.camera.Y+=2 If Keyboard.KeyDown(Key.S) Then Node.camera.Y-=2 If Keyboard.KeyDown(Key.A) Then Node.camera.X+=2 If Keyboard.KeyDown(Key.D) Then Node.camera.X-=2 If Keyboard.KeyHit(Key.KeypadPlus) Then New Node(Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y,Node.selectedNode) Node.selectedNode=Node.lastAddedNode Endif If Keyboard.KeyHit(Key.KeypadMinus) Then If Node.selectedNode Then Node.selectedNode.Remove() Else Node.MouseNode() If Node.lastMouseNode Then Node.lastMouseNode.Remove() Endif Endif If Keyboard.KeyHit(Key.Space) Then If Self.pathPlaceStep then Self.pathPlaceStep=0 Node.FindPath(Node.pathStartPos.x,Node.pathStartPos.y,Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) Else Node.ClearPath() Self.pathPlaceStep=1 Node.pathStartPos=New Vec2f(Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) Node.pathEndPos=New Vec2f(Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) endif Endif Node.Update() Node.Draw(canvas) If Node.dragLink Or Node.moveNode Then If SwapInterval<>0 Then SwapInterval=0 Else If SwapInterval<>1 Then SwapInterval=1 Endif End End Function Main() New AppInstance New MyWindow App.Run() End Class Node Global list:List<Node> Global path:List<Node> Global camera:Vec2f Global selectedNode:Node Global lastMouseNode:Node Global lastAddedNode:Node Global lastCloseNode:Node Global dragLink:Bool Global moveNode:Bool Global pathStartNode:Node Global pathEndNode:Node Global pathStartPos:Vec2f Global pathEndPos:Vec2f Field id:Int Field x:Float Field y:Float Field links:List<Node> Field color:Color Field size:Int=12 Method New(x:Float,y:Float,link:Node=Null) If Not Node.list Then Node.list=New List<Node> If Not Node.path Then Node.path=New List<Node> 'Find unique ID for node Local n:Node Local freeId:Int Local checkId:Int Repeat freeId=checkId For n=Eachin Node.list If n.id=checkId Then 'RETRY!! freeId=-1 Exit Endif Next checkId+=1 Until freeId>=0 Self.id=freeId Self.x=x Self.y=y If Not Self.links Then Self.links=New List<Node> If link Then Self.AddLink(link) Node.lastAddedNode=Self Node.list.AddLast(self) End Method MouseHover:Bool() If Mouse.X-Node.camera.X>=Self.x-Self.size/2 And Mouse.Y-Node.camera.Y>=Self.y-Self.size/2 Then If Mouse.X-Node.camera.X<=Self.x+Self.size/2 And Mouse.Y-Node.camera.Y<=Self.y+Self.size/2 Return True Endif End Return False End Method AddLink(node:Node) If Not node Then Print "No link node!" Return Endif 'Check if self If Self=node Then Print "Link node is self!" Return Endif 'Check if link already exists Local n:Node For n=Eachin node.links If n=Self Then Print "Link already exists!" Return Endif Next For n=Eachin Self.links If n=node Then Print "Link already exists!" Return Endif Next node.links.AddLast(Self) Self.links.AddLast(node) End Method RemoveLink(node:Node) Self.links.Remove(node) node.links.Remove(Self) End Method Remove() If Node.selectedNode=Self Then Node.selectedNode=Null If Node.lastMouseNode=Self Then Node.lastMouseNode=Null If Node.lastAddedNode=Self Then Node.lastAddedNode=Null If Node.lastCloseNode=Self Then Node.lastCloseNode=Null If Self.links Then For Local n:Node=Eachin Self.links n.RemoveLink(Self) Next Endif Node.list.Remove(Self) End Function MouseNode:Node() Node.lastMouseNode=Null For Local n:Node=Eachin Node.list If n.MouseHover() Then Node.lastMouseNode=n Return Node.lastMouseNode Endif Next Return Null End Function NodeClose:Node(x:Float,y:Float) Node.lastCloseNode=Null Local dx:Float Local dy:Float Local dist:Float Local bestDist:Float For Local n:Node=Eachin Node.list dx=x-n.x dy=y-n.y dist=Sqrt(dx*dx + dy*dy) If Not Node.lastCloseNode Or dist<bestDist Then bestDist=dist Node.lastCloseNode=n Endif Next Return Node.lastCloseNode End Function NodeId:Node(id:int) For Local n:Node=Eachin Node.list If n.id=id Then Return n Next Return Null End Function Update() For Local n:Node=Eachin Node.list If Node.selectedNode = n Then n.color=Color.Green Else n.color=Color.Orange Endif Next If Mouse.ButtonHit(MouseButton.Left) Then Node.MouseNode() If Node.selectedNode Then If Not Node.lastMouseNode Then Node.selectedNode=Null Else If Node.selectedNode=Node.lastMouseNode Then If Keyboard.KeyDown(Key.LeftControl) Or Keyboard.KeyDown(Key.RightControl) Then Node.dragLink=True Else Node.moveNode=True Endif Else If Keyboard.KeyDown(Key.LeftShift) Or Keyboard.KeyDown(Key.RightShift) Then Node.selectedNode.AddLink(Node.lastMouseNode) Else If Keyboard.KeyDown(Key.LeftAlt) Or Keyboard.KeyDown(Key.RightAlt) Then Node.selectedNode.RemoveLink(Node.lastMouseNode) Else Node.selectedNode=Node.lastMouseNode Endif Endif Endif Endif Else Node.selectedNode=Node.lastMouseNode Endif Else If Mouse.ButtonDown(MouseButton.Left) Then If Node.dragLink Then Node.MouseNode() If Node.lastMouseNode And Node.lastMouseNode<>Node.selectedNode Then Node.lastMouseNode.color=Color.Blue Endif Endif If Node.moveNode Then Node.selectedNode.x=Mouse.X-Node.camera.X Node.selectedNode.y=Mouse.Y-Node.camera.Y Endif Else If Node.dragLink Then If Node.lastMouseNode Then Node.selectedNode.AddLink(Node.lastMouseNode) Node.dragLink=False Endif If Node.moveNode Then Node.moveNode=False Endif Endif Endif End Function Draw(canvas:Canvas) canvas.Translate(Node.camera.X,Node.camera.Y) Local n:Node Local n2:Node canvas.LineSmoothing=True canvas.LineWidth=3 'Draw links For n=Eachin Node.list canvas.Color=Color.Blue For n2=Eachin n.links canvas.DrawLine(n.x,n.y,n2.x,n2.y) Next Next 'Draw nodes For n=Eachin Node.list canvas.Color=n.color canvas.DrawOval(Int(n.x-n.size/2),Int(n.y-n.size/2),n.size,n.size) canvas.Color=Color.White canvas.DrawText(n.id,n.x,n.y,0.5,0.5) Next 'Draw dragging line If Node.dragLink Then canvas.Color=Color.Blue canvas.DrawLine(selectedNode.x,selectedNode.y,Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) Endif 'Draw path canvas.Color=Color.Puce If Node.path.Count()<=0 Then canvas.DrawLine(Node.pathStartPos.X,Node.pathStartPos.Y,Node.pathEndPos.X,Node.pathEndPos.Y) Else canvas.DrawLine(Node.pathStartPos.X,Node.pathStartPos.Y,Node.path.First.x,Node.path.First.y) Local lastNode:Node=Node.path.First For n=Eachin Node.path If lastNode=n Then Continue canvas.DrawLine(n.x,n.y,lastNode.x,lastNode.y) lastNode=n Next canvas.DrawLine(Node.pathEndPos.X,Node.pathEndPos.Y,Node.path.Last.x,Node.path.Last.y) Endif canvas.Color=Color.Pink canvas.DrawText("S",Int(Node.pathStartPos.X),Int(Node.pathStartPos.Y),0.5,0.5) If Int(Node.pathStartPos.X)<>Int(Node.pathEndPos.X) And Int(Node.pathStartPos.Y)<>Int(Node.pathEndPos.Y) then canvas.DrawText("E",Int(Node.pathEndPos.X),Int(Node.pathEndPos.Y),0.5,0.5) Endif End Function ClearPath() Node.path.Clear() End Function FindPath(startX:Float,startY:Float,endX:Float,endY:Float) ClearPath() Node.pathStartNode=Node.NodeClose(startX,startY) Node.pathEndNode=Node.NodeClose(endX,endX) Node.pathStartPos.X=startX Node.pathStartPos.Y=startY Node.pathEndPos.X=endX Node.pathEndPos.Y=endY 'Super pathfinding code here... 'Just add some random path for now Node.path.AddLast(Node.NodeId(8)) Node.path.AddLast(Node.NodeId(5)) Node.path.AddLast(Node.NodeId(11)) Node.path.AddLast(Node.NodeId(17)) Node.path.AddLast(Node.NodeId(0)) 'Print path For Local n:Node=Eachin Node.path Print n.id Next End End

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388

#Import "<std>" #Import "<mojo>" #Import "<mojox>"   Using std.. Using mojo.. Using mojox..   Class MyWindow Extends Window Global pathPlaceStep:Int Method New() Super.New("Simple Mojo Gui App",640,480,WindowFlags.Resizable) Node.camera.X=640/2 Node.camera.Y=480/2 For Local i:Int=0 Until 25 New Node(Rnd(-640,640),Rnd(-480,480)) Next ClearColor=Color.DarkGrey ClearEnabled=True End Method OnRender(canvas:Canvas) Override App.RequestRender() canvas.DrawText("Click & Drag to Move node",0,0) canvas.DrawText("Ctrl & Drag to Link node",0,15) canvas.DrawText("Shift & Click to Insta-Link node",0,15*2) canvas.DrawText("Alt & Click to Remove node",0,15*3) canvas.DrawText("W,A,S,D to Move camera",0,15*4) canvas.DrawText("Numpad Minus to Remove node",0,15*5) canvas.DrawText("Numpad Plus to Add node",0,15*6) If Self.pathPlaceStep Then canvas.DrawText("Space to Place path end",0,15*7) Else canvas.DrawText("Space to Place path start",0,15*7) Endif If Keyboard.KeyDown(Key.W) Then Node.camera.Y+=2 If Keyboard.KeyDown(Key.S) Then Node.camera.Y-=2 If Keyboard.KeyDown(Key.A) Then Node.camera.X+=2 If Keyboard.KeyDown(Key.D) Then Node.camera.X-=2 If Keyboard.KeyHit(Key.KeypadPlus) Then New Node(Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y,Node.selectedNode) Node.selectedNode=Node.lastAddedNode Endif If Keyboard.KeyHit(Key.KeypadMinus) Then If Node.selectedNode Then Node.selectedNode.Remove() Else Node.MouseNode() If Node.lastMouseNode Then Node.lastMouseNode.Remove() Endif Endif If Keyboard.KeyHit(Key.Space) Then If Self.pathPlaceStep then Self.pathPlaceStep=0 Node.FindPath(Node.pathStartPos.x,Node.pathStartPos.y,Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) Else Node.ClearPath() Self.pathPlaceStep=1 Node.pathStartPos=New Vec2f(Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) Node.pathEndPos=New Vec2f(Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) endif Endif Node.Update() Node.Draw(canvas) If Node.dragLink Or Node.moveNode Then If SwapInterval<>0 Then SwapInterval=0 Else If SwapInterval<>1 Then SwapInterval=1 Endif End End   Function Main() New AppInstance New MyWindow App.Run() End   Class Node Global list:List<Node> Global path:List<Node> Global camera:Vec2f Global selectedNode:Node Global lastMouseNode:Node Global lastAddedNode:Node Global lastCloseNode:Node Global dragLink:Bool Global moveNode:Bool Global pathStartNode:Node Global pathEndNode:Node Global pathStartPos:Vec2f Global pathEndPos:Vec2f Field id:Int Field x:Float Field y:Float Field links:List<Node> Field color:Color Field size:Int=12 Method New(x:Float,y:Float,link:Node=Null) If Not Node.list Then Node.list=New List<Node> If Not Node.path Then Node.path=New List<Node> 'Find unique ID for node Local n:Node Local freeId:Int Local checkId:Int Repeat freeId=checkId For n=Eachin Node.list If n.id=checkId Then 'RETRY!! freeId=-1 Exit Endif Next checkId+=1 Until freeId>=0 Self.id=freeId Self.x=x Self.y=y If Not Self.links Then Self.links=New List<Node> If link Then Self.AddLink(link) Node.lastAddedNode=Self Node.list.AddLast(self) End Method MouseHover:Bool() If Mouse.X-Node.camera.X>=Self.x-Self.size/2 And Mouse.Y-Node.camera.Y>=Self.y-Self.size/2 Then If Mouse.X-Node.camera.X<=Self.x+Self.size/2 And Mouse.Y-Node.camera.Y<=Self.y+Self.size/2 Return True Endif End Return False End Method AddLink(node:Node) If Not node Then Print "No link node!" Return Endif 'Check if self If Self=node Then Print "Link node is self!" Return Endif 'Check if link already exists Local n:Node For n=Eachin node.links If n=Self Then Print "Link already exists!" Return Endif Next For n=Eachin Self.links If n=node Then Print "Link already exists!" Return Endif Next node.links.AddLast(Self) Self.links.AddLast(node) End Method RemoveLink(node:Node) Self.links.Remove(node) node.links.Remove(Self) End Method Remove() If Node.selectedNode=Self Then Node.selectedNode=Null If Node.lastMouseNode=Self Then Node.lastMouseNode=Null If Node.lastAddedNode=Self Then Node.lastAddedNode=Null If Node.lastCloseNode=Self Then Node.lastCloseNode=Null If Self.links Then For Local n:Node=Eachin Self.links n.RemoveLink(Self) Next Endif Node.list.Remove(Self) End Function MouseNode:Node() Node.lastMouseNode=Null For Local n:Node=Eachin Node.list If n.MouseHover() Then Node.lastMouseNode=n Return Node.lastMouseNode Endif Next Return Null End Function NodeClose:Node(x:Float,y:Float) Node.lastCloseNode=Null Local dx:Float Local dy:Float Local dist:Float Local bestDist:Float For Local n:Node=Eachin Node.list dx=x-n.x dy=y-n.y dist=Sqrt(dx*dx + dy*dy) If Not Node.lastCloseNode Or dist<bestDist Then bestDist=dist Node.lastCloseNode=n Endif Next Return Node.lastCloseNode End Function NodeId:Node(id:int) For Local n:Node=Eachin Node.list If n.id=id Then Return n Next Return Null End Function Update() For Local n:Node=Eachin Node.list If Node.selectedNode = n Then n.color=Color.Green Else n.color=Color.Orange Endif Next If Mouse.ButtonHit(MouseButton.Left) Then Node.MouseNode() If Node.selectedNode Then If Not Node.lastMouseNode Then Node.selectedNode=Null Else If Node.selectedNode=Node.lastMouseNode Then If Keyboard.KeyDown(Key.LeftControl) Or Keyboard.KeyDown(Key.RightControl) Then Node.dragLink=True Else Node.moveNode=True Endif Else If Keyboard.KeyDown(Key.LeftShift) Or Keyboard.KeyDown(Key.RightShift) Then Node.selectedNode.AddLink(Node.lastMouseNode) Else If Keyboard.KeyDown(Key.LeftAlt) Or Keyboard.KeyDown(Key.RightAlt) Then Node.selectedNode.RemoveLink(Node.lastMouseNode) Else Node.selectedNode=Node.lastMouseNode Endif Endif Endif Endif Else Node.selectedNode=Node.lastMouseNode Endif Else If Mouse.ButtonDown(MouseButton.Left) Then If Node.dragLink Then Node.MouseNode() If Node.lastMouseNode And Node.lastMouseNode<>Node.selectedNode Then Node.lastMouseNode.color=Color.Blue Endif Endif If Node.moveNode Then Node.selectedNode.x=Mouse.X-Node.camera.X Node.selectedNode.y=Mouse.Y-Node.camera.Y Endif Else If Node.dragLink Then If Node.lastMouseNode Then Node.selectedNode.AddLink(Node.lastMouseNode) Node.dragLink=False Endif If Node.moveNode Then Node.moveNode=False Endif Endif Endif End Function Draw(canvas:Canvas) canvas.Translate(Node.camera.X,Node.camera.Y) Local n:Node Local n2:Node canvas.LineSmoothing=True canvas.LineWidth=3 'Draw links For n=Eachin Node.list canvas.Color=Color.Blue For n2=Eachin n.links canvas.DrawLine(n.x,n.y,n2.x,n2.y) Next Next 'Draw nodes For n=Eachin Node.list canvas.Color=n.color canvas.DrawOval(Int(n.x-n.size/2),Int(n.y-n.size/2),n.size,n.size) canvas.Color=Color.White canvas.DrawText(n.id,n.x,n.y,0.5,0.5) Next 'Draw dragging line If Node.dragLink Then canvas.Color=Color.Blue canvas.DrawLine(selectedNode.x,selectedNode.y,Mouse.X-Node.camera.X,Mouse.Y-Node.camera.Y) Endif 'Draw path canvas.Color=Color.Puce If Node.path.Count()<=0 Then canvas.DrawLine(Node.pathStartPos.X,Node.pathStartPos.Y,Node.pathEndPos.X,Node.pathEndPos.Y) Else canvas.DrawLine(Node.pathStartPos.X,Node.pathStartPos.Y,Node.path.First.x,Node.path.First.y) Local lastNode:Node=Node.path.First For n=Eachin Node.path If lastNode=n Then Continue canvas.DrawLine(n.x,n.y,lastNode.x,lastNode.y) lastNode=n Next canvas.DrawLine(Node.pathEndPos.X,Node.pathEndPos.Y,Node.path.Last.x,Node.path.Last.y) Endif canvas.Color=Color.Pink canvas.DrawText("S",Int(Node.pathStartPos.X),Int(Node.pathStartPos.Y),0.5,0.5) If Int(Node.pathStartPos.X)<>Int(Node.pathEndPos.X) And Int(Node.pathStartPos.Y)<>Int(Node.pathEndPos.Y) then canvas.DrawText("E",Int(Node.pathEndPos.X),Int(Node.pathEndPos.Y),0.5,0.5) Endif End Function ClearPath() Node.path.Clear() End Function FindPath(startX:Float,startY:Float,endX:Float,endY:Float) ClearPath() Node.pathStartNode=Node.NodeClose(startX,startY) Node.pathEndNode=Node.NodeClose(endX,endX) Node.pathStartPos.X=startX Node.pathStartPos.Y=startY Node.pathEndPos.X=endX Node.pathEndPos.Y=endY 'Super pathfinding code here... 'Just add some random path for now Node.path.AddLast(Node.NodeId(8)) Node.path.AddLast(Node.NodeId(5)) Node.path.AddLast(Node.NodeId(11)) Node.path.AddLast(Node.NodeId(17)) Node.path.AddLast(Node.NodeId(0)) 'Print path For Local n:Node=Eachin Node.path Print n.id Next End End

[nerobotParticipant]

Need to know finding rules. At least, can we go to the end point directly without nodes if end is near to start?

My version:

1. Go through all nodes and find nearest point to the end by calculating minimal total distance:
   • total = dist(start,node[i])+dist(node[i],end)
   • so we get nodeX, store it to the  path-list
   • note, that end point should be in this check as any other nodes
2. Goto (2) but replacing ‘start’ with our ‘nodeX’. Until the nearest node will be ‘end’ point.

In specific case there will be only start and end points as result if any other node have longer distance.

[Mark SiblyKeymaster]

I think there’s a node/pathfinding demo in blitzmax!

[impixiParticipant]

I think there’s a node/pathfinding demo in blitzmax!

samples/aaronkoolen/AStar/astar_demo.bmx?

EDIT: Removed possibly incorrect info.

@hezkore: I’m not sure I understand your requirements. Do you want to calculate the most efficient route through a set of given nodes?

[HezkoreParticipant]

@impixi Yep!
I want to place a bunch of nodes and then set one of them as the start node and one as the ending node.
Then I want a list of the nodes that are needed to go by in order to get to the ending node.

I’ve started to translate some Monkey X code I’ve found, but it’s tricky heh.

[HezkoreParticipant]

Here’s a translated example.
Click to place a few nodes, then drag a line between the nodes.
Hover over a node and press S to place the path start.
Do the same but press G to place the path goal.
Press Enter to calculate the path.

Original code: http://www.monkey-x.com/Community/posts.php?topic=2155

Monkey

#Import "<std>" #Import "<mojo>" Using std.. Using mojo.. Const PATHNODE_RADIUS:Int=12 Global START_NODE:PathNode Global GOAL_NODE:PathNode Class MyWindow Extends Window 'stores mouse positions Field mx:Int Field my:Int 'bool to detect mouse pressing Field mousePressed:Int 'stores clicked nodes Field node1:PathNode Field node2:PathNode 'stores found path Field foundPath:Path Field foundTime:Int Method New(title:String="Simple mojo app",width:Int=640,height:Int=480,flags:WindowFlags=Null) Super.New(title,width,height,flags ) End Method OnRender(canvas:Canvas) Override App.RequestRender() OnUpdate() 'draws mouse line If mousePressed = 1 If Mouse.X<>mx Or Mouse.Y<>my canvas.DrawLine(mx, my, Mouse.X, Mouse.Y) Endif Endif 'draws node network PathNode.DrawLinks(canvas) PathNode.DrawNodes(canvas) 'draws path If foundPath<>Null canvas.Color=Color.White canvas.DrawText(foundPath.PrintPath() + " " + foundTime + "ms", 10, 0) Endif End Method OnUpdate() 'finds a path If Keyboard.KeyHit(Key.Enter) 'sets up pathfinding routing foundPath = Null PathFind.Setup( START_NODE, GOAL_NODE ) 'starts pathfinding foundTime = Millisecs() Local result : Bool = PathFind.FindPath() foundTime = Millisecs() - foundTime 'stores found path If result = True Then foundPath = PathFind.pathList.First Endif 'sets start node If Keyboard.KeyHit(Key.S) Local test : PathNode = PathNode.Touch( Mouse.X, Mouse.Y ) If test <> Null Then START_NODE = test Endif 'sets goal node If Keyboard.KeyHit(Key.G) Local test : PathNode = PathNode.Touch( Mouse.X, Mouse.Y ) If test <> Null Then GOAL_NODE = test Endif 'handles mouse If Mouse.ButtonDown(MouseButton.Left) 'store initial mouse click location (used to detect mouse movement) If mousePressed = 0 'grab mouse position mx = Mouse.X my = Mouse.Y 'grab clicked node if any node1 = PathNode.Touch( mx, my ) Endif 'mouse has been pressed mousePressed = 1 Endif If Not Mouse.ButtonDown(MouseButton.Left) And mousePressed = 1 'if we didnt click a path node If node1 = Null 'if the mouse position has not changed since we first clicked If Mouse.X = mx And Mouse.Y = my 'create a path node PathNode.Create(mx, my) 'position has moved so we have dragged an invisible line Else 'use the mouse path to find intersecting nodes and links and remove them PathNode.RemoveIntersectingNodes(mx,my,Mouse.X, Mouse.Y) PathNode.RemoveIntersectingLinks(mx,my,Mouse.X, Mouse.Y) Endif 'if we did click inside a node Else 'grab clicked node if any node2 = PathNode.Touch( Mouse.X, Mouse.Y ) 'check if we intersected with another node If node2<>Null And node2<>node1 'create a link node1.Link( node2 ) Endif Endif 'reset mouse mousePressed = 0 node1 = Null Endif End End Function Main() New AppInstance New MyWindow App.Run() End Class Path Field nodes:List<PathNode> Field travelledDistance:Float Field underestimate:Float Method New() Self.nodes=New List<PathNode> End Method Copy:Path() Local this:Path=New Path For Local n:PathNode=Eachin Self.nodes this.nodes.AddLast(n) Next this.travelledDistance=Self.travelledDistance Return this End Method CalculateUnderestimate:Float( goal : PathNode ) If goal = Null Then Return 0 Self.underestimate=nodes.Last.Distance( goal.x, goal.y ) Return Self.underestimate End Method PrintPath:String() Local output:String For Local this:PathNode = Eachin Self.nodes output=output + String( this.id ) If this<>Self.nodes.Last output+=" -> " Endif Next Return output End Function Create:Path( start : PathNode ) Local this:Path = New Path this.nodes.AddLast( start ) Return this End End 'extends the list Class PathfindList Extends List<Path> 'compares score value Method Compare:Int(a:Path,b:Path ) If a.travelledDistance+a.underestimate>b.travelledDistance+b.underestimate Then Return 1 If a.travelledDistance+a.underestimate<b.travelledDistance+b.underestimate Then Return -1 Return 0 End End 'static pathfind class Class PathFind Global start:PathNode Global goal:PathNode Global pathList:PathfindList=New PathfindList 'sets up the pathfinding Function Setup(node1:PathNode, node2:PathNode) start=node1 goal=node2 pathList.Clear() pathList.AddLast(Path.Create(start)) pathList.First.CalculateUnderestimate(node2) End 'finds a path Function FindPath:Bool() Repeat 'if pathList is empty then exit If Not pathList Or pathList.Count()=0 Then Return False 'if first path ends at goal then we have found our path If pathList.First.nodes.Last = goal Then Return True 'extract the first path Local firstPath:Path=pathList.RemoveFirst() 'extend path to all neighbours creating x new paths For Local neighbour:PathLink=Eachin firstPath.nodes.Last.linked 'copy path Local newPath:Path = firstPath.Copy() 'get the neighbour node Local newNode:PathNode = neighbour.linkedNode 'reject if loop For Local child:PathNode = Eachin newPath.nodes If child=newNode newPath=Null Exit Endif Next 'if newPath is null we found a loop If newPath 'add new node and travel cost newPath.nodes.AddLast( newNode ) newPath.travelledDistance = newPath.travelledDistance + neighbour.cost Endif 'For all paths that End at the same node, keep only the shortest one. If newPath<>Null For Local shortPath:Path=Eachin pathList 'if ends in the same node If shortPath.nodes.Last=newNode 'keep the shortest If shortPath.travelledDistance <= newPath.travelledDistance newPath = Null Exit Else pathList.RemoveEach( shortPath ) Exit Endif Endif Next Endif 'if we still have a valid new path add it to the list If newPath <> Null pathList.AddLast( newPath ) newPath.CalculateUnderestimate( goal ) Endif Next 'Sort all paths by total underestimate, shortest first. pathList.Sort(True) Forever Return False End End Class PathLink Field linkedNode:PathNode Field cost:Float Function Create:PathLink(node1:PathNode, node2:PathNode) Local this:PathLink=New PathLink this.linkedNode=node2 this.cost=node1.Distance(node2.x, node2.y) Return this End End Class PathNode Global nodeCount:Int Global nodeList:List<PathNode> Field nodeId:List<PathNode>.Node Field id:Int Field x:Int Field y:Int Field linked:List<PathLink> 'links two nodes Method Link(other:PathNode) 'if same node then exit If other = Self Then Return 'if link already exists then exit For Local this:PathLink=Eachin Self.linked If this.linkedNode=other Then Return Next 'create links other.linked.AddLast(PathLink.Create(other,Self)) Self.linked.AddLast(PathLink.Create(Self,other)) End 'draws node, coloured to indicate start/goal Method Draw(canvas:Canvas) canvas.Color=Color.White canvas.DrawOval(Self.x - PATHNODE_RADIUS, Self.y - PATHNODE_RADIUS, PATHNODE_RADIUS * 2, PATHNODE_RADIUS * 2) canvas.Color=Color.Black If GOAL_NODE=Self Then canvas.Color=Color.Red If START_NODE=Self Then canvas.Color=Color.Green canvas.DrawOval(Self.x - PATHNODE_RADIUS + 1, Self.y - PATHNODE_RADIUS + 1, PATHNODE_RADIUS * 2 - 2, PATHNODE_RADIUS * 2 - 2) canvas.Color=Color.White canvas.DrawText(Self.id, Self.x, Self.y, 0.5, 0.5) End 'draws a line to all linked nodes Method DrawLinked(canvas:Canvas) canvas.Color=Color.White For Local this:PathLink = Eachin Self.linked canvas.DrawLine(Self.x, Self.y, this.linkedNode.x, this.linkedNode.y) Next End Method 'returns distance from self to point x, y Method Distance:Float(px:Int, py:Int) Local dx:Int=px-Self.x Local dy:Int=py-Self.y Return Sqrt(dx*dx+dy*dy) End Method Function Create:PathNode(px:Int, py:Int) If Not nodeList Then nodeList=New List<PathNode> nodeCount=nodeCount+1 Local this:PathNode=New PathNode ' 'Find unique ID for node Local n:PathNode Local freeId:Int Local checkId:Int Repeat freeId=checkId For n=Eachin nodeList If n.id=checkId Then 'RETRY!! freeId=-1 Exit Endif Next checkId+=1 Until freeId>=0 this.id=freeId this.x=px this.y=py this.nodeId=nodeList.AddLast(this) this.linked=New List<PathLink> Return this End Function Function DrawNodes(canvas:Canvas) If Not nodeList Or nodeList.Count()=0 Then Return For Local this:PathNode=Eachin nodeList this.Draw(canvas) Next End Function DrawLinks(canvas:Canvas) If Not nodeList Or nodeList.Count()=0 Then Return For Local this : PathNode = Eachin nodeList this.DrawLinked(canvas) Next End Function Touch:PathNode(px:Int, py:Int) If Not nodeList Or nodeList.Count()=0 Then Return Null 'loop all nodes and return if we are inside For Local this:PathNode=Eachin nodeList If this.Distance(px,py)<PATHNODE_RADIUS Return this Endif Next Return Null End Function RemoveIntersectingNodes(x1:Int, y1:Int, x2:Int, y2:Int) If Not nodeList Then Return For Local this:PathNode=Eachin nodeList 'if line is intersecting the node If DistanceToLineSegment( x1, y1, x2, y2, this.x, this.y ) <= PATHNODE_RADIUS 'find all linked nodes to this one For Local link : PathLink = Eachin this.linked 'loop all of their links and remove link to this Local testNode : PathNode = link.linkedNode For Local rLink : PathLink = Eachin testNode.linked If rLink.linkedNode = this testNode.linked.RemoveEach( rLink ) Exit Endif Next Next 'remove the node this.nodeId.Remove() Endif Next End Function RemoveIntersectingLinks(x1:Int, y1:Int, x2:Int, y2:Int) If Not nodeList Then Return 'cycle all nodes For Local this:PathNode=Eachin nodeList 'cycle all links For Local link:PathLink=Eachin this.linked 'if the line intersects the link If Intersect(x1,y1,x2,y2,this.x,this.y,link.linkedNode.x,link.linkedNode.y ) 'remove the link this.linked.RemoveEach( link ) 'check and remove link from other node For Local rLink:PathLink=Eachin link.linkedNode.linked If rLink.linkedNode=this link.linkedNode.linked.RemoveEach(rLink) Exit Endif Next Endif Next Next End End ' 2D math functions by Jasu 'http://blitzbasic.com/codearcs/codearcs.php?code=2180 Function Intersect:Int(x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, x4:Float, y4:Float) ' This Function returns True If lines x1,y1,x2,y2 And x3,y3,x4,y4 intersect at some point. Return (Orientation(x1, y1, x2, y2, x3, y3) <> Orientation(x1, y1, x2, y2, x4, y4)) And (Orientation(x3, y3, x4, y4, x1, y1) <> Orientation(x3, y3, x4, y4, x2, y2)) End Function Orientation:Int(x1:Float,y1:Float, x2:Float,y2:Float, Px:Float,Py:Float) ' Linear determinant of the 3 points. ' This Function returns the orientation of px,py on line x1,y1,x2,y2. ' Look from x2,y2 To the direction of x1,y1. ' If px,py is on the right, Function returns +1 ' If px,py is on the left, Function returns -1 ' If px,py is directly ahead Or behind, Function returns 0 Return Sgn((x2-x1)*(Py-y1)-(Px-x1)*(y2-y1)) End Function DistanceToLineSegment:Float(x1:Float, y1:Float, x2:Float, y2:Float, Px:Float, Py:Float) ' This Function calculates the distance between a line segment And a point. ' So this Function is useful To determine If line intersects a circle. ' To also determine the point on the line x1,y1,x2,y2 which is the closest To px,py , use Function NearestPointInLine# Local Dx : Float Local Dy : Float Local Ratio : Float If (x1 = x2) And (y1 = y2) Then Return Sqrt( (Px-x1)*(Px-x1)+(Py-y1)*(Py-y1) ) Else Dx = x2 - x1 Dy = y2 - y1 Ratio = ((Px - x1) * Dx + (Py - y1) * Dy) / (Dx * Dx + Dy * Dy) If Ratio < 0 Then Return Sqrt( (Px-x1)*(Px-x1)+(Py-y1)*(Py-y1) ) Elseif Ratio > 1 Then Return Sqrt( (Px-x2)*(Px-x2)+(Py-y2)*(Py-y2) ) Else Return Sqrt((Px - ((1 - Ratio) * x1 + Ratio * x2))*(Px - ((1 - Ratio) * x1 + Ratio * x2))+(Py - ((1 - Ratio) * y1 + Ratio * y2))*(Py - ((1 - Ratio) * y1 + Ratio * y2))) Endif Endif End

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500

#Import "<std>" #Import "<mojo>" Using std.. Using mojo..   Const PATHNODE_RADIUS:Int=12   Global START_NODE:PathNode Global GOAL_NODE:PathNode   Class MyWindow Extends Window 'stores mouse positions Field mx:Int Field my:Int 'bool to detect mouse pressing Field mousePressed:Int 'stores clicked nodes Field node1:PathNode Field node2:PathNode 'stores found path Field foundPath:Path Field foundTime:Int Method New(title:String="Simple mojo app",width:Int=640,height:Int=480,flags:WindowFlags=Null) Super.New(title,width,height,flags ) End Method OnRender(canvas:Canvas) Override App.RequestRender() OnUpdate() 'draws mouse line If mousePressed = 1 If Mouse.X<>mx Or Mouse.Y<>my canvas.DrawLine(mx, my, Mouse.X, Mouse.Y) Endif Endif 'draws node network PathNode.DrawLinks(canvas) PathNode.DrawNodes(canvas) 'draws path If foundPath<>Null canvas.Color=Color.White canvas.DrawText(foundPath.PrintPath() + "    " + foundTime + "ms", 10, 0) Endif End Method OnUpdate() 'finds a path If Keyboard.KeyHit(Key.Enter) 'sets up pathfinding routing foundPath = Null PathFind.Setup( START_NODE, GOAL_NODE ) 'starts pathfinding foundTime = Millisecs() Local result : Bool = PathFind.FindPath() foundTime = Millisecs() - foundTime 'stores found path If result = True Then foundPath = PathFind.pathList.First Endif 'sets start node If Keyboard.KeyHit(Key.S) Local test : PathNode = PathNode.Touch( Mouse.X, Mouse.Y ) If test <> Null Then START_NODE = test Endif 'sets goal node If Keyboard.KeyHit(Key.G) Local test : PathNode = PathNode.Touch( Mouse.X, Mouse.Y ) If test <> Null Then GOAL_NODE = test Endif 'handles mouse If Mouse.ButtonDown(MouseButton.Left) 'store initial mouse click location (used to detect mouse movement) If mousePressed = 0 'grab mouse position mx = Mouse.X my = Mouse.Y 'grab clicked node if any node1 = PathNode.Touch( mx, my ) Endif 'mouse has been pressed mousePressed = 1 Endif If Not Mouse.ButtonDown(MouseButton.Left) And mousePressed = 1 'if we didnt click a path node If node1 = Null 'if the mouse position has not changed since we first clicked If Mouse.X = mx And Mouse.Y = my 'create a path node PathNode.Create(mx, my) 'position has moved so we have dragged an invisible line Else 'use the mouse path to find intersecting nodes and links and remove them PathNode.RemoveIntersectingNodes(mx,my,Mouse.X, Mouse.Y) PathNode.RemoveIntersectingLinks(mx,my,Mouse.X, Mouse.Y) Endif   'if we did click inside a node Else 'grab clicked node if any node2 = PathNode.Touch( Mouse.X, Mouse.Y ) 'check if we intersected with another node If node2<>Null And node2<>node1 'create a link node1.Link( node2 ) Endif Endif 'reset mouse mousePressed = 0 node1 = Null Endif End End   Function Main() New AppInstance New MyWindow App.Run() End   Class Path Field nodes:List<PathNode> Field travelledDistance:Float Field underestimate:Float Method New() Self.nodes=New List<PathNode> End Method Copy:Path() Local this:Path=New Path For Local n:PathNode=Eachin Self.nodes this.nodes.AddLast(n) Next this.travelledDistance=Self.travelledDistance Return this End Method CalculateUnderestimate:Float( goal : PathNode ) If goal = Null Then Return 0 Self.underestimate=nodes.Last.Distance( goal.x, goal.y ) Return Self.underestimate End Method PrintPath:String() Local output:String For Local this:PathNode = Eachin Self.nodes output=output + String( this.id ) If this<>Self.nodes.Last output+=" -> " Endif Next Return output End Function Create:Path( start : PathNode ) Local this:Path = New Path this.nodes.AddLast( start ) Return this End End   'extends the list Class PathfindList Extends List<Path> 'compares score value Method Compare:Int(a:Path,b:Path ) If a.travelledDistance+a.underestimate>b.travelledDistance+b.underestimate Then Return 1 If a.travelledDistance+a.underestimate<b.travelledDistance+b.underestimate Then Return -1 Return 0 End End   'static pathfind class Class PathFind Global start:PathNode Global goal:PathNode Global pathList:PathfindList=New PathfindList 'sets up the pathfinding Function Setup(node1:PathNode, node2:PathNode) start=node1 goal=node2 pathList.Clear() pathList.AddLast(Path.Create(start)) pathList.First.CalculateUnderestimate(node2) End 'finds a path Function FindPath:Bool() Repeat 'if pathList is empty then exit If Not pathList Or pathList.Count()=0 Then Return False 'if first path ends at goal then we have found our path If pathList.First.nodes.Last = goal Then Return True 'extract the first path Local firstPath:Path=pathList.RemoveFirst() 'extend path to all neighbours creating x new paths For Local neighbour:PathLink=Eachin firstPath.nodes.Last.linked 'copy path Local newPath:Path = firstPath.Copy() 'get the neighbour node Local newNode:PathNode = neighbour.linkedNode 'reject if loop For Local child:PathNode = Eachin newPath.nodes If child=newNode newPath=Null Exit Endif Next 'if newPath is null we found a loop If newPath 'add new node and travel cost newPath.nodes.AddLast( newNode ) newPath.travelledDistance = newPath.travelledDistance + neighbour.cost Endif 'For all paths that End at the same node, keep only the shortest one. If newPath<>Null For Local shortPath:Path=Eachin pathList 'if ends in the same node If shortPath.nodes.Last=newNode 'keep the shortest If shortPath.travelledDistance <= newPath.travelledDistance newPath = Null Exit Else pathList.RemoveEach( shortPath ) Exit Endif Endif Next Endif 'if we still have a valid new path add it to the list If newPath <> Null pathList.AddLast( newPath ) newPath.CalculateUnderestimate( goal ) Endif   Next 'Sort all paths by total underestimate, shortest first. pathList.Sort(True) Forever Return False End End   Class PathLink Field linkedNode:PathNode Field cost:Float Function Create:PathLink(node1:PathNode, node2:PathNode) Local this:PathLink=New PathLink this.linkedNode=node2 this.cost=node1.Distance(node2.x, node2.y) Return this End End   Class PathNode Global nodeCount:Int Global nodeList:List<PathNode> Field nodeId:List<PathNode>.Node Field id:Int Field x:Int Field y:Int Field linked:List<PathLink> 'links two nodes Method Link(other:PathNode) 'if same node then exit If other = Self Then Return 'if link already exists then exit For Local this:PathLink=Eachin Self.linked If this.linkedNode=other Then Return Next 'create links other.linked.AddLast(PathLink.Create(other,Self)) Self.linked.AddLast(PathLink.Create(Self,other)) End 'draws node, coloured to indicate start/goal Method Draw(canvas:Canvas) canvas.Color=Color.White canvas.DrawOval(Self.x - PATHNODE_RADIUS, Self.y - PATHNODE_RADIUS, PATHNODE_RADIUS * 2, PATHNODE_RADIUS * 2) canvas.Color=Color.Black If GOAL_NODE=Self Then canvas.Color=Color.Red If START_NODE=Self Then canvas.Color=Color.Green canvas.DrawOval(Self.x - PATHNODE_RADIUS + 1, Self.y - PATHNODE_RADIUS + 1, PATHNODE_RADIUS * 2 - 2, PATHNODE_RADIUS * 2 - 2) canvas.Color=Color.White canvas.DrawText(Self.id, Self.x, Self.y, 0.5, 0.5) End 'draws a line to all linked nodes Method DrawLinked(canvas:Canvas) canvas.Color=Color.White For Local this:PathLink = Eachin Self.linked canvas.DrawLine(Self.x, Self.y, this.linkedNode.x, this.linkedNode.y) Next End Method 'returns distance from self to point x, y Method Distance:Float(px:Int, py:Int) Local dx:Int=px-Self.x Local dy:Int=py-Self.y Return Sqrt(dx*dx+dy*dy) End Method Function Create:PathNode(px:Int, py:Int) If Not nodeList Then nodeList=New List<PathNode> nodeCount=nodeCount+1 Local this:PathNode=New PathNode ' 'Find unique ID for node Local n:PathNode Local freeId:Int Local checkId:Int Repeat freeId=checkId For n=Eachin nodeList If n.id=checkId Then 'RETRY!! freeId=-1 Exit Endif Next checkId+=1 Until freeId>=0 this.id=freeId this.x=px this.y=py this.nodeId=nodeList.AddLast(this) this.linked=New List<PathLink> Return this End Function Function DrawNodes(canvas:Canvas) If Not nodeList Or nodeList.Count()=0 Then Return For Local this:PathNode=Eachin nodeList this.Draw(canvas) Next End Function DrawLinks(canvas:Canvas) If Not nodeList Or nodeList.Count()=0 Then Return For Local this : PathNode = Eachin nodeList this.DrawLinked(canvas) Next End Function Touch:PathNode(px:Int, py:Int) If Not nodeList Or nodeList.Count()=0 Then Return Null 'loop all nodes and return if we are inside For Local this:PathNode=Eachin nodeList If this.Distance(px,py)<PATHNODE_RADIUS Return this Endif Next Return Null End Function RemoveIntersectingNodes(x1:Int, y1:Int, x2:Int, y2:Int) If Not nodeList Then Return For Local this:PathNode=Eachin nodeList 'if line is intersecting the node If DistanceToLineSegment( x1, y1, x2, y2, this.x, this.y ) <= PATHNODE_RADIUS 'find all linked nodes to this one For Local link : PathLink = Eachin this.linked   'loop all of their links and remove link to this Local testNode : PathNode = link.linkedNode For Local rLink : PathLink = Eachin testNode.linked If rLink.linkedNode = this testNode.linked.RemoveEach( rLink ) Exit Endif Next Next 'remove the node this.nodeId.Remove() Endif Next End Function RemoveIntersectingLinks(x1:Int, y1:Int, x2:Int, y2:Int) If Not nodeList Then Return 'cycle all nodes For Local this:PathNode=Eachin nodeList 'cycle all links For Local link:PathLink=Eachin this.linked 'if the line intersects the link If Intersect(x1,y1,x2,y2,this.x,this.y,link.linkedNode.x,link.linkedNode.y )   'remove the link this.linked.RemoveEach( link )   'check and remove link from other node For Local rLink:PathLink=Eachin link.linkedNode.linked If rLink.linkedNode=this link.linkedNode.linked.RemoveEach(rLink) Exit Endif Next Endif Next Next End End   ' 2D math functions by Jasu 'http://blitzbasic.com/codearcs/codearcs.php?code=2180   Function Intersect:Int(x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, x4:Float, y4:Float) ' This Function returns True If lines x1,y1,x2,y2 And x3,y3,x4,y4 intersect at some point. Return (Orientation(x1, y1, x2, y2, x3, y3) <> Orientation(x1, y1, x2, y2, x4, y4)) And (Orientation(x3, y3, x4, y4, x1, y1) <> Orientation(x3, y3, x4, y4, x2, y2)) End   Function Orientation:Int(x1:Float,y1:Float, x2:Float,y2:Float, Px:Float,Py:Float) ' Linear determinant of the 3 points. ' This Function returns the orientation of px,py on line x1,y1,x2,y2. ' Look from x2,y2 To the direction of x1,y1. ' If px,py is on the right, Function returns +1 ' If px,py is on the left, Function returns -1 ' If px,py is directly ahead Or behind, Function returns 0 Return Sgn((x2-x1)*(Py-y1)-(Px-x1)*(y2-y1)) End   Function DistanceToLineSegment:Float(x1:Float, y1:Float, x2:Float, y2:Float, Px:Float, Py:Float) ' This Function calculates the distance between a line segment And a point. ' So this Function is useful To determine If line intersects a circle. ' To also determine the point on the line x1,y1,x2,y2 which is the closest To px,py , use Function NearestPointInLine# Local Dx : Float Local Dy : Float Local Ratio : Float If (x1 = x2) And (y1 = y2) Then Return Sqrt( (Px-x1)*(Px-x1)+(Py-y1)*(Py-y1) ) Else Dx = x2 - x1 Dy = y2 - y1 Ratio = ((Px - x1) * Dx + (Py - y1) * Dy) / (Dx * Dx + Dy * Dy) If Ratio < 0 Then Return Sqrt( (Px-x1)*(Px-x1)+(Py-y1)*(Py-y1) ) Elseif Ratio > 1 Then Return Sqrt( (Px-x2)*(Px-x2)+(Py-y2)*(Py-y2) ) Else Return Sqrt((Px - ((1 - Ratio) * x1 + Ratio * x2))*(Px - ((1 - Ratio) * x1 + Ratio * x2))+(Py - ((1 - Ratio) * y1 + Ratio * y2))*(Py - ((1 - Ratio) * y1 + Ratio * y2))) Endif Endif End

[Author]

Posts