Advertisement
Guest User

Finally

a guest
Oct 10th, 2012
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
VB.NET 8.63 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.             'Console.Title = "Parent : " & Parent.Self.X & "," & Parent.Self.Y & _
  30.             '                "Target : " & TargetX & "," & TargetY
  31.  
  32.             dx = Self.X - Parent.Self.X
  33.             dy = Self.Y - Parent.Self.Y
  34.  
  35.             'check if movement type
  36.             If dx = 1 And dy <> Self.Y Then
  37.                 G = 14 + Parent.G
  38.             ElseIf dx = -1 And dy <> Self.Y Then
  39.                 G = 14 + Parent.G
  40.             Else
  41.                 G = 10 + Parent.G
  42.             End If
  43.  
  44.             'block-method heuristic (vertical/horizontal movement only)
  45.             dx = Math.Abs(TargetX - Self.X)
  46.             dy = Math.Abs(TargetY - Self.Y)
  47.  
  48.             H = (dx + dy) * 10
  49.  
  50.             'total score
  51.             F = G + H
  52.  
  53.             'Write(2, 2, "GetScores(       )", ConsoleColor.Yellow)
  54.             'Write(2, 13, TargetX & "," & TargetY, ConsoleColor.Cyan)
  55.  
  56.             'Write(4, 4, "G:", ConsoleColor.Yellow)
  57.             'Write(5, 4, "H:", ConsoleColor.Yellow)
  58.             'Write(6, 4, "F:", ConsoleColor.Yellow)
  59.  
  60.             'Write(4, 7, G, ConsoleColor.Cyan)
  61.             'Write(5, 7, H, ConsoleColor.Cyan)
  62.             'Write(6, 7, F, ConsoleColor.Cyan)
  63.  
  64.             'Console.ReadKey()
  65.             'Console.Clear()
  66.  
  67.         End Sub
  68.  
  69.     End Class
  70.  
  71.     Public Sub Path(StartX As Integer, StartY As Integer, _
  72.                     EndX As Integer, EndY As Integer)
  73.  
  74.         Dim CurrentX, CurrentY, CurrentG, intIndex As Integer
  75.         Dim InList As Boolean = False
  76.         Dim FirstNode As New Node
  77.  
  78.         'the first node in the closed list is the starting position
  79.         With FirstNode
  80.             .Self.X = StartX
  81.             .Self.Y = StartY
  82.             .Parent = FirstNode
  83.             .GetScores(EndX, EndY)
  84.         End With
  85.  
  86.         ClosedList.Add(FirstNode)
  87.  
  88.         CurrentX = StartX
  89.         CurrentY = StartY
  90.  
  91.         intIndex = 0
  92.  
  93.         Do While True
  94.  
  95.             Dim TempNode, LowNode As New Node
  96.  
  97.             With TempNode
  98.                 .Clear()
  99.                 .Self.X = CurrentX
  100.                 .Self.Y = CurrentY
  101.                 .G = CurrentG
  102.             End With
  103.  
  104.             If CurrentX = EndX And CurrentY = EndY Then
  105.  
  106.                 For Each Node In ClosedList
  107.  
  108.                     'output the path (backwards i think?)
  109.                     Write((intIndex + 2), 2, Node.Self.X, ConsoleColor.Green)
  110.                     Write((intIndex + 3), 2, Node.Self.Y, ConsoleColor.Green)
  111.  
  112.                     intIndex = intIndex + 1
  113.  
  114.                     Console.ReadKey()
  115.                     Console.Clear()
  116.  
  117.                 Next
  118.  
  119.             Else
  120.  
  121.                 'add neighbors to the open list
  122.                 AddNeighbors(TempNode, EndX, EndY)
  123.  
  124.                 'find the lowest node
  125.                 LowNode.F = 999999
  126.  
  127.                 Dim bChanged As Boolean = True 'tracks if there was a change or not
  128.  
  129.                 Do While bChanged = True 'cycle through until you make NO changes.
  130.  
  131.                     bChanged = False
  132.  
  133.                     For Each Node In OpenList
  134.  
  135.                         'Write(2, 2, Node.F, ConsoleColor.Cyan)
  136.                         'Write(2, 5, "vs", ConsoleColor.Yellow)
  137.                         ' Write(2, 8, LowNode.F, ConsoleColor.Cyan)
  138.  
  139.                         If Node.F < LowNode.F Then
  140.                             LowNode = Node
  141.                             bChanged = True
  142.                             'Write(3, 2, "Changed.", ConsoleColor.Green)
  143.                         End If
  144.                         'Console.ReadKey()
  145.                         'Console.Clear()
  146.                     Next
  147.  
  148.                 Loop
  149.  
  150.                 'Write(2, 2, "Low Node", ConsoleColor.Yellow)
  151.  
  152.                 'With LowNode
  153.                 'Write(4, 4, "X:", ConsoleColor.Yellow)
  154.                 'Write(5, 4, "Y:", ConsoleColor.Yellow)
  155.                 'Write(6, 4, "G:", ConsoleColor.Yellow)
  156.                 'Write(7, 4, "H:", ConsoleColor.Yellow)
  157.                 'Write(8, 4, "F:", ConsoleColor.Yellow)
  158.                 '
  159.                 'Write(4, 7, .Self.X, ConsoleColor.Cyan)
  160.                 'Write(5, 7, .Self.Y, ConsoleColor.Cyan)
  161.                 'Write(6, 7, .G, ConsoleColor.Cyan)
  162.                 'Write(7, 7, .H, ConsoleColor.Cyan)
  163.                 'Write(8, 7, .F, ConsoleColor.Cyan)
  164.                 'End With
  165.  
  166.                 'Console.ReadKey()
  167.                 'Console.Clear()
  168.  
  169.                 'remove from open list
  170.                 OpenList.Remove(LowNode)
  171.  
  172.                 'check the closed list for this node
  173.                 For Each Node In ClosedList
  174.                     If Node.Self.X = LowNode.Self.X And Node.Self.Y = LowNode.Self.Y Then
  175.                         InList = True
  176.                     End If
  177.                 Next
  178.  
  179.                 'if its not in the list
  180.                 If Not InList Then
  181.  
  182.                     'add it to the list
  183.                     ClosedList.Add(LowNode)
  184.  
  185.                     'set next node info
  186.                     CurrentX = LowNode.Self.X
  187.                     CurrentY = LowNode.Self.Y
  188.                     CurrentG = LowNode.G
  189.  
  190.                 End If
  191.  
  192.             End If
  193.             '
  194.         Loop
  195.  
  196.     End Sub
  197.  
  198.     'adds the neighbors of a cell to the open list
  199.     Public Sub AddNeighbors(ThisNode As Node, TargetX As Integer, TargetY As Integer)
  200.  
  201.         Dim InList As Boolean = False
  202.  
  203.         Dim X, Y As Integer
  204.  
  205.         X = ThisNode.Self.X
  206.         Y = ThisNode.Self.Y
  207.  
  208.         For intX = -1 To 1
  209.             For intY = -1 To 1
  210.  
  211.                 'skip intX=0,intY=0, it's always self, never a neighbour
  212.                 If intX = 0 And intY = 0 Then
  213.                     Continue For
  214.                 End If
  215.  
  216.                 'start by assuming a neighbour is not in the list until it is found
  217.                 InList = False
  218.  
  219.                 'if the node is inside the map boundries
  220.                 If Not (X + intX) < 0 Then
  221.                     If Not (Y + intY) < 0 Then
  222.  
  223.                         Dim TempNode As New Node
  224.  
  225.                         'set positions
  226.                         TempNode.Self.X = X + intX
  227.                         TempNode.Self.Y = Y + intY
  228.  
  229.                         'assign parent node
  230.                         TempNode.Parent = ThisNode
  231.  
  232.                         'get this nodes scores
  233.                         TempNode.GetScores(TargetX, TargetY)
  234.  
  235.                         'check the closed list for this node
  236.                         For Each Node In ClosedList
  237.                             If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
  238.                                 InList = True
  239.                             End If
  240.                         Next
  241.  
  242.                         'only check the open list if it wasn't in the closed list
  243.                         If Not InList Then
  244.  
  245.                             For Each Node In OpenList
  246.  
  247.                                 'if it's already in the list
  248.                                 If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
  249.  
  250.                                     'and it has a lower G score
  251.                                     If TempNode.G < Node.G Then
  252.  
  253.                                         'update values
  254.                                         InList = True
  255.                                         Node.G = TempNode.G
  256.                                         Node.H = TempNode.H
  257.                                         Node.F = TempNode.F
  258.                                         Node.Parent = ThisNode  'this is new parent
  259.                                     End If
  260.  
  261.                                 End If
  262.  
  263.                             Next
  264.  
  265.                             'if its not in either list, add it to the open list
  266.                             If Not InList Then
  267.                                 OpenList.Add(TempNode)
  268.                             End If
  269.  
  270.                         End If
  271.  
  272.                     End If
  273.  
  274.                 End If
  275.  
  276.             Next
  277.  
  278.         Next
  279.  
  280.     End Sub
  281.  
  282. #End Region
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement