Advertisement
Guest User

A* Added checks

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