Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #Region "Path Finding"
- Public OpenList As New List(Of Node)
- Public ClosedList As New List(Of Node)
- Public Structure State
- Dim X, Y As Integer
- End Structure
- Public Class Node
- Public Self As State 'the location of this node
- Public Parent As Node 'the location of this nodes parent
- Public F, G, H As Integer
- Sub Clear()
- Self.X = 0
- Self.Y = 0
- Parent = Nothing
- F = 0
- G = 0
- H = 0
- End Sub
- Sub GetScores(TargetX As Integer, TargetY As Integer)
- Dim dx, dy As Integer
- 'Console.Title = "Parent : " & Parent.Self.X & "," & Parent.Self.Y & _
- ' "Target : " & TargetX & "," & TargetY
- dx = Self.X - Parent.Self.X
- dy = Self.Y - Parent.Self.Y
- 'check if movement type
- If dx = 1 And dy <> Self.Y Then
- G = 14 + Parent.G
- ElseIf dx = -1 And dy <> Self.Y Then
- G = 14 + Parent.G
- Else
- G = 10 + Parent.G
- End If
- 'block-method heuristic (vertical/horizontal movement only)
- dx = Math.Abs(TargetX - Self.X)
- dy = Math.Abs(TargetY - Self.Y)
- H = (dx + dy) * 10
- 'total score
- F = G + H
- 'Write(2, 2, "GetScores( )", ConsoleColor.Yellow)
- 'Write(2, 13, TargetX & "," & TargetY, ConsoleColor.Cyan)
- 'Write(4, 4, "G:", ConsoleColor.Yellow)
- 'Write(5, 4, "H:", ConsoleColor.Yellow)
- 'Write(6, 4, "F:", ConsoleColor.Yellow)
- 'Write(4, 7, G, ConsoleColor.Cyan)
- 'Write(5, 7, H, ConsoleColor.Cyan)
- 'Write(6, 7, F, ConsoleColor.Cyan)
- 'Console.ReadKey()
- 'Console.Clear()
- End Sub
- End Class
- Public Sub Path(StartX As Integer, StartY As Integer, _
- EndX As Integer, EndY As Integer)
- Dim CurrentX, CurrentY, CurrentG, intIndex As Integer
- Dim InList As Boolean = False
- Dim FirstNode As New Node
- 'the first node in the closed list is the starting position
- With FirstNode
- .Self.X = StartX
- .Self.Y = StartY
- .Parent = FirstNode
- .GetScores(EndX, EndY)
- End With
- ClosedList.Add(FirstNode)
- CurrentX = StartX
- CurrentY = StartY
- intIndex = 0
- Do While True
- Dim TempNode, LowNode As New Node
- With TempNode
- .Clear()
- .Self.X = CurrentX
- .Self.Y = CurrentY
- .G = CurrentG
- End With
- If CurrentX = EndX And CurrentY = EndY Then
- For Each Node In ClosedList
- 'output the path (backwards i think?)
- Write((intIndex + 2), 2, Node.Self.X, ConsoleColor.Green)
- Write((intIndex + 3), 2, Node.Self.Y, ConsoleColor.Green)
- intIndex = intIndex + 1
- Console.ReadKey()
- Console.Clear()
- Next
- Else
- 'add neighbors to the open list
- AddNeighbors(TempNode, EndX, EndY)
- 'find the lowest node
- LowNode.F = 999999
- Dim bChanged As Boolean = True 'tracks if there was a change or not
- Do While bChanged = True 'cycle through until you make NO changes.
- bChanged = False
- For Each Node In OpenList
- 'Write(2, 2, Node.F, ConsoleColor.Cyan)
- 'Write(2, 5, "vs", ConsoleColor.Yellow)
- ' Write(2, 8, LowNode.F, ConsoleColor.Cyan)
- If Node.F < LowNode.F Then
- LowNode = Node
- bChanged = True
- 'Write(3, 2, "Changed.", ConsoleColor.Green)
- End If
- 'Console.ReadKey()
- 'Console.Clear()
- Next
- Loop
- 'Write(2, 2, "Low Node", ConsoleColor.Yellow)
- 'With LowNode
- 'Write(4, 4, "X:", ConsoleColor.Yellow)
- 'Write(5, 4, "Y:", ConsoleColor.Yellow)
- 'Write(6, 4, "G:", ConsoleColor.Yellow)
- 'Write(7, 4, "H:", ConsoleColor.Yellow)
- 'Write(8, 4, "F:", ConsoleColor.Yellow)
- '
- 'Write(4, 7, .Self.X, ConsoleColor.Cyan)
- 'Write(5, 7, .Self.Y, ConsoleColor.Cyan)
- 'Write(6, 7, .G, ConsoleColor.Cyan)
- 'Write(7, 7, .H, ConsoleColor.Cyan)
- 'Write(8, 7, .F, ConsoleColor.Cyan)
- 'End With
- 'Console.ReadKey()
- 'Console.Clear()
- 'remove from open list
- OpenList.Remove(LowNode)
- 'check the closed list for this node
- For Each Node In ClosedList
- If Node.Self.X = LowNode.Self.X And Node.Self.Y = LowNode.Self.Y Then
- InList = True
- End If
- Next
- 'if its not in the list
- If Not InList Then
- 'add it to the list
- ClosedList.Add(LowNode)
- 'set next node info
- CurrentX = LowNode.Self.X
- CurrentY = LowNode.Self.Y
- CurrentG = LowNode.G
- End If
- End If
- '
- Loop
- End Sub
- 'adds the neighbors of a cell to the open list
- Public Sub AddNeighbors(ThisNode As Node, TargetX As Integer, TargetY As Integer)
- Dim InList As Boolean = False
- Dim X, Y As Integer
- X = ThisNode.Self.X
- Y = ThisNode.Self.Y
- For intX = -1 To 1
- For intY = -1 To 1
- 'skip intX=0,intY=0, it's always self, never a neighbour
- If intX = 0 And intY = 0 Then
- Continue For
- End If
- 'start by assuming a neighbour is not in the list until it is found
- InList = False
- 'if the node is inside the map boundries
- If Not (X + intX) < 0 Then
- If Not (Y + intY) < 0 Then
- Dim TempNode As New Node
- 'set positions
- TempNode.Self.X = X + intX
- TempNode.Self.Y = Y + intY
- 'assign parent node
- TempNode.Parent = ThisNode
- 'get this nodes scores
- TempNode.GetScores(TargetX, TargetY)
- 'check the closed list for this node
- For Each Node In ClosedList
- If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
- InList = True
- End If
- Next
- 'only check the open list if it wasn't in the closed list
- If Not InList Then
- For Each Node In OpenList
- 'if it's already in the list
- If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
- 'and it has a lower G score
- If TempNode.G < Node.G Then
- 'update values
- InList = True
- Node.G = TempNode.G
- Node.H = TempNode.H
- Node.F = TempNode.F
- Node.Parent = ThisNode 'this is new parent
- End If
- End If
- Next
- 'if its not in either list, add it to the open list
- If Not InList Then
- OpenList.Add(TempNode)
- End If
- End If
- End If
- End If
- Next
- Next
- End Sub
- #End Region
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement