home *** CD-ROM | disk | FTP | other *** search
/ Planet Source Code Jumbo …e CD Visual Basic 1 to 7 / 5_2007-2008.ISO / data / Zips / Blank_Engi2067755272007.psc / BlankEngine / BE_AI_Dijkstra.bas next >
BASIC Source File  |  2007-03-29  |  12KB  |  242 lines
  1. Attribute VB_Name = "BE_AI_Dijkstra"
  2. '//
  3. '// BE_AI_Dijkstra handles the Dijkstra Artifical Inteligence Path Finding Algorithm
  4. '//
  5.  
  6. Private Declare Function GetTickCount Lib "kernel32" () As Long
  7.  
  8. Public Type NodePoint
  9.     X As Single
  10.     Y As Single
  11.     Z As Single
  12. End Type
  13.  
  14. Public Type TreeNode
  15.     CurrNode As Long                    'Current node
  16.     NextNode(0 To 3) As Long            'up to 4 attached nodes
  17.     Dist(0 To 3) As Double              'distance between these nodes
  18.     VisitNumber As Long                 'What number this node was visited
  19.     Distance As Double                  'Current distance at point
  20.     TmpVar As Double                    'Temp for story distance
  21.     Weight As Single                    'Added weight (distance) to a distance
  22. End Type
  23.  
  24. Public NodeList() As NodePoint
  25. Public nNodes As Long
  26. Public TreeNodeList() As TreeNode
  27. Public nPathList As Long
  28. Public PathList() As Long
  29.  
  30. Public Sub BE_AI_DIJKSTRA_ADD_NODE(X As Single, Y As Single, Z As Single)
  31. '// Add to the nodelist
  32.     nNodes = nNodes + 1
  33.     ReDim Preserve NodeList(0 To nNodes - 1) As NodePoint
  34.     NodeList(nNodes - 1).X = X
  35.     NodeList(nNodes - 1).Y = Y
  36.     NodeList(nNodes - 1).Z = Z
  37. End Sub
  38.  
  39. Public Sub BE_AI_DIJKSTRA_ADD_TREENODE(Index As Long, NextNode1 As Long, NextNode2 As Long, NextNode3 As Long, NextNode4 As Long, Weight As Single)
  40. '// Add to the treenode list
  41.     ReDim Preserve TreeNodeList(0 To nNodes - 1) As TreeNode
  42.     TreeNodeList(Index).CurrNode = Index
  43.     TreeNodeList(Index).NextNode(0) = NextNode1
  44.     TreeNodeList(Index).NextNode(1) = NextNode2
  45.     TreeNodeList(Index).NextNode(2) = NextNode3
  46.     TreeNodeList(Index).NextNode(3) = NextNode4
  47.     TreeNodeList(Index).Weight = Weight
  48.     If (Not TreeNodeList(Index).NextNode(0) = -1) Then
  49.         TreeNodeList(Index).Dist(0) = BE_VERTEX_FIND_VECTOR_DISTANCE(BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).CurrNode).X, NodeList(TreeNodeList(Index).CurrNode).Y, NodeList(TreeNodeList(Index).CurrNode).X) _
  50.                  , BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).NextNode(0)).X, NodeList(TreeNodeList(Index).NextNode(0)).Y, NodeList(TreeNodeList(Index).NextNode(0)).Z)) * Weight
  51.     End If
  52.     If (Not TreeNodeList(Index).NextNode(1) = -1) Then
  53.         TreeNodeList(Index).Dist(1) = BE_VERTEX_FIND_VECTOR_DISTANCE(BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).CurrNode).X, NodeList(TreeNodeList(Index).CurrNode).Y, NodeList(TreeNodeList(Index).CurrNode).X) _
  54.                  , BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).NextNode(1)).X, NodeList(TreeNodeList(Index).NextNode(1)).Y, NodeList(TreeNodeList(Index).NextNode(1)).Z)) * Weight
  55.     End If
  56.     If (Not TreeNodeList(Index).NextNode(2) = -1) Then
  57.         TreeNodeList(Index).Dist(2) = BE_VERTEX_FIND_VECTOR_DISTANCE(BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).CurrNode).X, NodeList(TreeNodeList(Index).CurrNode).Y, NodeList(TreeNodeList(Index).CurrNode).X) _
  58.                  , BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).NextNode(2)).X, NodeList(TreeNodeList(Index).NextNode(2)).Y, NodeList(TreeNodeList(Index).NextNode(2)).Z)) * Weight
  59.     End If
  60.     If (Not TreeNodeList(Index).NextNode(3) = -1) Then
  61.         TreeNodeList(Index).Dist(3) = BE_VERTEX_FIND_VECTOR_DISTANCE(BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).CurrNode).X, NodeList(TreeNodeList(Index).CurrNode).Y, NodeList(TreeNodeList(Index).CurrNode).X) _
  62.                  , BE_VERTEX_MAKE_VECTOR(NodeList(TreeNodeList(Index).NextNode(3)).X, NodeList(TreeNodeList(Index).NextNode(3)).Y, NodeList(TreeNodeList(Index).NextNode(3)).Z)) * Weight
  63.     End If
  64. End Sub
  65.  
  66. Public Function BE_AI_DIJKSTRA_PATHFIND(NodeSrc As Long, NodeDest As Long) As Boolean
  67. '// find the path between 2 nodes
  68. On Error GoTo Err
  69.  
  70. Dim i As Long, bRun As Boolean, CurrentVisitNumber As Long
  71. Dim CurrNode As Long, LowestNodeFound As Long, LowestValFound As Double
  72.     
  73.     If (NodeSrc = NodeDest) Then
  74.         'we are already there!
  75.         nPathList = 2
  76.         ReDim PathList(2) As Long
  77.         PathList(1) = NodeSrc
  78.         PathList(2) = NodeDest
  79.         BE_AI_DIJKSTRA_PATHFIND = True
  80.         Exit Function
  81.     End If
  82.     
  83.     'setup data
  84.     For i = 0 To nNodes - 1
  85.         TreeNodeList(i).VisitNumber = -1
  86.         TreeNodeList(i).Distance = -1
  87.         TreeNodeList(i).TmpVar = 99999
  88.     Next i
  89.     
  90.     'setup 1st var
  91.     TreeNodeList(NodeSrc).VisitNumber = 1
  92.     CurrentVisitNumber = 1
  93.     CurrNode = NodeSrc
  94.     TreeNodeList(NodeSrc).Distance = 0
  95.     TreeNodeList(NodeSrc).TmpVar = 0
  96.     
  97.     Do While (Not bRun)
  98.         'go through each node the current node touches
  99.         If Not (TreeNodeList(CurrNode).NextNode(0) = -1) Then TreeNodeList(TreeNodeList(CurrNode).NextNode(0)).TmpVar = BE_AI_DIJKSTRA_MIN(TreeNodeList(CurrNode).Dist(0) + TreeNodeList(CurrNode).Distance, TreeNodeList(TreeNodeList(CurrNode).NextNode(0)).TmpVar / 1)
  100.         If Not (TreeNodeList(CurrNode).NextNode(1) = -1) Then TreeNodeList(TreeNodeList(CurrNode).NextNode(1)).TmpVar = BE_AI_DIJKSTRA_MIN(TreeNodeList(CurrNode).Dist(1) + TreeNodeList(CurrNode).Distance, TreeNodeList(TreeNodeList(CurrNode).NextNode(1)).TmpVar / 1)
  101.         If Not (TreeNodeList(CurrNode).NextNode(2) = -1) Then TreeNodeList(TreeNodeList(CurrNode).NextNode(2)).TmpVar = BE_AI_DIJKSTRA_MIN(TreeNodeList(CurrNode).Dist(2) + TreeNodeList(CurrNode).Distance, TreeNodeList(TreeNodeList(CurrNode).NextNode(2)).TmpVar / 1)
  102.         If Not (TreeNodeList(CurrNode).NextNode(3) = -1) Then TreeNodeList(TreeNodeList(CurrNode).NextNode(3)).TmpVar = BE_AI_DIJKSTRA_MIN(TreeNodeList(CurrNode).Dist(3) + TreeNodeList(CurrNode).Distance, TreeNodeList(TreeNodeList(CurrNode).NextNode(3)).TmpVar / 1)
  103.         
  104.         'find the lowest temp var
  105.         LowestValFound = 100999
  106.         For i = 0 To nNodes - 1
  107.             If (TreeNodeList(i).TmpVar <= LowestValFound) And (TreeNodeList(i).TmpVar >= 0) And (TreeNodeList(i).VisitNumber < 0) Then
  108.                 'we have found a lower value
  109.                 LowestValFound = TreeNodeList(i).TmpVar
  110.                 LowestNodeFound = i
  111.             End If
  112.         Next i
  113.         
  114.         'mark node as next visit node and set distance
  115.         CurrentVisitNumber = CurrentVisitNumber + 1
  116.         TreeNodeList(LowestNodeFound).VisitNumber = CurrentVisitNumber
  117.         TreeNodeList(LowestNodeFound).Distance = TreeNodeList(LowestNodeFound).TmpVar
  118.         CurrNode = LowestNodeFound
  119.         
  120.         'if this node is not the destination then continue
  121.         If (CurrNode = NodeDest) Then
  122.             bRun = True
  123.         End If
  124.     Loop
  125.     
  126.     'setup vars
  127.     bRun = False
  128.     CurrNode = NodeDest
  129.     Dim lngTimeTaken As Long
  130.     lngtimetake = GetTickCount()
  131.     nPathList = 1
  132.     ReDim PathList(nPathList) As Long
  133.     PathList(1) = NodeDest
  134.     
  135.     Do While (Not bRun)
  136.         'check to see that currnode isnt the start
  137.         If (CurrNode = NodeSrc) Then
  138.             bRun = True
  139.             GoTo SkipToEnd:
  140.         ElseIf (GetTickCount - lngtimetake > 1000) Then
  141.             'break after 1 second of not finding path
  142.             bRun = True
  143.             BE_AI_DIJKSTRA_PATHFIND = False
  144.             Exit Function
  145.         End If
  146.         
  147.         'scan through each node visited
  148.          If (TreeNodeList(CurrNode).NextNode(0) >= 0) Then '//Only if there is a node in this direction
  149.             If (TreeNodeList(TreeNodeList(CurrNode).NextNode(0)).VisitNumber >= 0) Then
  150.                 '//Only if we visited this node...
  151.                 If TreeNodeList(CurrNode).Distance - TreeNodeList(TreeNodeList(CurrNode).NextNode(0)).Distance <= TreeNodeList(CurrNode).Dist(0) Then
  152.                     'NextNode(0) is part of the route home
  153.                     nPathList = nPathList + 1
  154.                     ReDim Preserve PathList(nPathList) As Long
  155.                     PathList(nPathList) = TreeNodeList(CurrNode).NextNode(0)
  156.                     CurrNode = TreeNodeList(CurrNode).NextNode(0)
  157.                     GoTo SkipToEnd:
  158.                 End If
  159.             End If
  160.         End If
  161.             
  162.         If (TreeNodeList(CurrNode).NextNode(1) >= 0) Then  '//Only if there is a node in this direction
  163.             If (TreeNodeList(TreeNodeList(CurrNode).NextNode(1)).VisitNumber >= 0) Then
  164.                 '//Only if we visited this node...
  165.                 If TreeNodeList(CurrNode).Distance - TreeNodeList(TreeNodeList(CurrNode).NextNode(1)).Distance <= TreeNodeList(CurrNode).Dist(1) Then
  166.                     'NextNode(1) is part of the route home
  167.                     nPathList = nPathList + 1
  168.                     ReDim Preserve PathList(nPathList) As Long
  169.                     PathList(nPathList) = TreeNodeList(CurrNode).NextNode(1)
  170.                     CurrNode = TreeNodeList(CurrNode).NextNode(1)
  171.                     GoTo SkipToEnd:
  172.                 End If
  173.             End If
  174.         End If
  175.             
  176.         If (TreeNodeList(CurrNode).NextNode(2) >= 0) Then  '//Only if there is a node in this direction
  177.             If (TreeNodeList(TreeNodeList(CurrNode).NextNode(2)).VisitNumber >= 0) Then
  178.                 '//Only if we visited this node...
  179.                 If TreeNodeList(CurrNode).Distance - TreeNodeList(TreeNodeList(CurrNode).NextNode(2)).Distance <= TreeNodeList(CurrNode).Dist(2) Then
  180.                     'NextNode(2) is part of the route home
  181.                     nPathList = nPathList + 1
  182.                     ReDim Preserve PathList(nPathList) As Long
  183.                     PathList(nPathList) = TreeNodeList(CurrNode).NextNode(2)
  184.                     CurrNode = TreeNodeList(CurrNode).NextNode(2)
  185.                     GoTo SkipToEnd:
  186.                 End If
  187.             End If
  188.         End If
  189.             
  190.         If (TreeNodeList(CurrNode).NextNode(3) >= 0) Then  '//Only if there is a node in this direction
  191.             If (TreeNodeList(TreeNodeList(CurrNode).NextNode(3)).VisitNumber >= 0) Then
  192.                 '//Only if we visited this node...
  193.                 If TreeNodeList(CurrNode).Distance - TreeNodeList(TreeNodeList(CurrNode).NextNode(3)).Distance >= TreeNodeList(CurrNode).Dist(3) Then
  194.                     'NextNode(3) is part of the route home
  195.                     nPathList = nPathList + 1
  196.                     ReDim Preserve PathList(nPathList) As Long
  197.                     PathList(nPathList) = TreeNodeList(CurrNode).NextNode(3)
  198.                     CurrNode = TreeNodeList(CurrNode).NextNode(3)
  199.                     GoTo SkipToEnd:
  200.                 End If
  201.             End If
  202.         End If
  203.         
  204. 'skips to the loop
  205. SkipToEnd:
  206.     Loop
  207.     
  208.     'finally reverse the array to find the path
  209.     Dim TmpArray() As Long
  210.     ReDim TmpArray(nPathList) As Long
  211.     
  212.     For i = nPathList To 1 Step -1
  213.         TmpArray(i) = PathList(((nPathList - i) + 1))
  214.     Next i
  215.     
  216.     For i = 1 To nPathList
  217.         PathList(i) = TmpArray(i)
  218.     Next i
  219.     
  220.     'exit
  221.     BE_AI_DIJKSTRA_PATHFIND = True
  222.     Exit Function
  223.     
  224. Err:
  225. 'send to logger
  226.     Logger.BE_LOGGER_SAVE_LOG "Error[" & Err.Number & "] " & Err.Source & "{BE_AI_DIJKSTRA_PATHFIND} : " & Err.Description, App.Path & "\Log.txt"
  227. End Function
  228.  
  229. Public Function BE_AI_DIJKSTRA_INTERPOLATE(Src As Single, dest As Single, Value As Single) As Single
  230. '// Interpolate the distance between start and finish
  231.     BE_AI_DIJKSTRA_INTERPOLATE = (dest * Value) + Src * (1# - Value)
  232. End Function
  233.  
  234. Public Function BE_AI_DIJKSTRA_MIN(v1 As Single, v2 As Single) As Single
  235. '// Returns the smaller number
  236.     If (v1 < v2) Then
  237.         BE_AI_DIJKSTRA_MIN = v1
  238.     Else
  239.         BE_AI_DIJKSTRA_MIN = v2
  240.     End If
  241. End Function
  242.