Advertisement
Guest User

getting close

a guest
Oct 9th, 2012
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
VB.NET 5.86 KB | None | 0 0
  1. #Region "Path Finding"
  2.  
  3.     Public OpenList As New List(Of Node)
  4.     Public ClosedList As New List(Of Node)
  5.  
  6.     Public Structure State
  7.         Dim X, Y As Integer
  8.     End Structure
  9.  
  10.     Public Class Node
  11.  
  12.         Public Self As State 'the location of this node
  13.         Public Parent As Node  'the location of this nodes parent
  14.         Public F, G, H As Integer
  15.  
  16.         Sub Clear()
  17.             Self.X = 0
  18.             Self.Y = 0
  19.             Parent = Nothing
  20.             F = 0
  21.             G = 0
  22.             H = 0
  23.         End Sub
  24.  
  25.         Sub GetScores(TargetX As Integer, TargetY As Integer)
  26.  
  27.             Dim dx, dy As Integer
  28.  
  29.             dx = Self.X - Parent.Self.X
  30.             dy = Self.Y - Parent.Self.Y
  31.  
  32.             'check if movement type
  33.             If dx = 1 And dy <> Self.Y Then
  34.                 G = 14 + Parent.G
  35.             ElseIf dx = -1 And dy <> Self.Y Then
  36.                 G = 14 + Parent.G
  37.             Else
  38.                 G = 10 + Parent.G
  39.             End If
  40.  
  41.             'block-method heuristic (vertical/horizontal movement only)
  42.             dx = Math.Abs(TargetX - Self.X)
  43.             dy = Math.Abs(TargetY - Self.Y)
  44.  
  45.             H = (dx + dy) * 10
  46.  
  47.             'total score
  48.             F = G + H
  49.  
  50.         End Sub
  51.  
  52.     End Class
  53.  
  54.     Public Sub Path(StartX As Integer, StartY As Integer, _
  55.                     EndX As Integer, EndY As Integer)
  56.  
  57.         Dim CurrentX, CurrentY, intIndex As Integer
  58.         Dim InList As Boolean = False
  59.         Dim TempNode, LowNode As New Node
  60.  
  61.         'the first node in the closed list is the starting position
  62.         With TempNode
  63.             .self.x = StartX
  64.             .self.y = StartY
  65.             .parent = TempNode
  66.             .GetScores(EndX, EndY)
  67.         End With
  68.  
  69.         ClosedList.Add(TempNode)
  70.  
  71.         CurrentX = StartX
  72.         CurrentY = StartY
  73.  
  74.         intIndex = 0
  75.  
  76.         Do While True
  77.  
  78.             If CurrentX = EndX And CurrentY = EndY Then
  79.  
  80.                 For Each Node In ClosedList
  81.  
  82.                     'output the path (backwards i think?)
  83.                     Write((intIndex + 2), 2, Node.Self.X, ConsoleColor.Green)
  84.                     Write((intIndex + 3), 2, Node.Self.Y, ConsoleColor.Green)
  85.  
  86.                     intIndex = intIndex + 1
  87.  
  88.                     Console.ReadKey()
  89.                     Console.Clear()
  90.  
  91.                 Next
  92.  
  93.             Else
  94.  
  95.                 'update tempnode to match the current x,y
  96.                 With TempNode
  97.                     .Clear()
  98.                     .Self.X = CurrentX
  99.                     .Self.Y = CurrentY
  100.                 End With
  101.  
  102.                 'add neighbors to the open list
  103.                 AddNeighbors(TempNode, EndX, EndY)
  104.  
  105.                 'find the lowest node
  106.                 LowNode.F = 999999
  107.  
  108.                 For Each Node In OpenList
  109.                     If Node.F < LowNode.F Then
  110.                         LowNode = Node
  111.                     End If
  112.                 Next
  113.  
  114.                 'remove from open list
  115.                 OpenList.Remove(LowNode)
  116.  
  117.                 'check the closed list for this node
  118.                 For Each Node In ClosedList
  119.                     If Node.Self.X = LowNode.Self.X And Node.Self.Y = LowNode.Self.Y Then
  120.                         InList = True
  121.                     End If
  122.                 Next
  123.  
  124.                 'if its not in the list
  125.                 If Not InList Then
  126.  
  127.                     With LowNode
  128.                         Write(2, 2, .Self.X & "," & .Self.Y, ConsoleColor.Green)
  129.                         Write(3, 2, .F, ConsoleColor.Green)
  130.                         Console.ReadKey()
  131.                         Console.Clear()
  132.                     End With
  133.  
  134.                     'add it to the list
  135.                     ClosedList.Add(LowNode)
  136.  
  137.                     'set this node as the current node
  138.                     CurrentX = LowNode.Self.X
  139.                     CurrentY = LowNode.Self.Y
  140.  
  141.                 End If
  142.  
  143.             End If
  144.             '
  145.         Loop
  146.  
  147.     End Sub
  148.  
  149.     'adds the neighbors of a cell to the open list
  150.     Public Sub AddNeighbors(ThisNode As Node, TargetX As Integer, TargetY As Integer)
  151.  
  152.         Dim TempNode As New Node
  153.         Dim LowNode As New Node
  154.         Dim InList As Boolean = False
  155.  
  156.         Dim X, Y As Integer
  157.  
  158.         X = ThisNode.Self.X
  159.         Y = ThisNode.Self.Y
  160.  
  161.         For intX = -1 To 1
  162.             For intY = -1 To 1
  163.  
  164.                 'if the node is inside the map boundries
  165.                 If Not (X + intX) < 0 Then
  166.                     If Not (Y + intY) < 0 Then
  167.  
  168.                         'set positions
  169.                         TempNode.Self.x = X + intX
  170.                         TempNode.Self.y = Y + intY
  171.  
  172.                         'assign parent node
  173.                         TempNode.Parent = ThisNode
  174.  
  175.                         'get this nodes scores
  176.                         TempNode.GetScores(TargetX, TargetY)
  177.  
  178.                         'check the other two lists for this node
  179.                         For Each Node In OpenList
  180.                             If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
  181.                                 InList = True
  182.                             End If
  183.                         Next
  184.  
  185.                         'check the other two lists for this node
  186.                         For Each Node In ClosedList
  187.                             If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
  188.                                 InList = True
  189.                             End If
  190.                         Next
  191.  
  192.                         'add to the next open list if it's not already in either list
  193.                         If Not InList Then
  194.                             OpenList.Add(TempNode)
  195.                         End If
  196.  
  197.                     End If
  198.                 End If
  199.  
  200.             Next
  201.         Next
  202.  
  203.  
  204.     End Sub
  205.  
  206. #End Region
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement