[Vb.Net] Pathfinder

[dday9]

There has been a major update. See post #4.

I've been very interested in path finding for a while now and decided to make one myself.

Features:

• A panel that draws up a grid. The grid is determined by the NodeHeightCount, NodeWidthCount, and NodeSize.
• Fills up the nodes by calling the FillPath method
• Clears the path by calling the ClearPath method

Drawbacks:

• A very slow and brutal approach
• Doesn't allow for "Blocked" nodes

Plans:
I plan on studying some other methods of path finding such as the famous A* algorithm and adjusting my code accordingly.

Notes:
The way that the program works is it first checks if the current node we are on is the end, if it is, then exit out. Next it checks if we can move up/down or left/right based on where the end node is in relation to the current node. If so, then move accordingly.

Image:


Code:

Public Class Grid
    Inherits Windows.Forms.Panel

#Region "Node Properties"

    Private beginning_node As Point = New Point(0, 0)
    Public Property BeginningNode() As Point
        Get
            Return beginning_node
        End Get
        Set(ByVal value As Point)
            If value.X > nodes_left - 1 Then
                value.X = nodes_left - 1
                value.Y = value.Y
            ElseIf value.X < 0 Then
                value.X = 0
                value.Y = value.Y
            End If
            If value.Y > nodes_height - 1 Then
                value.Y = nodes_height - 1
            ElseIf value.Y < 0 Then
                value.Y = 0
            End If

            beginning_node = value : Me.Invalidate()
        End Set
    End Property

    Private end_node As Point = New Point(1, 1)
    Public Property EndNode() As Point
        Get
            Return end_node
        End Get
        Set(ByVal value As Point)
            If value.X > nodes_left - 1 Then
                value.X = nodes_left - 1
                value.Y = value.Y
            ElseIf value.X < 0 Then
                value.X = 0
                value.Y = value.Y
            End If
            If value.Y > nodes_height - 1 Then
                value.Y = nodes_height - 1
            ElseIf value.Y < 0 Then
                value.Y = 0
            End If

            If value = beginning_node Then value = New Point(1, 1)
            end_node = value : Me.Invalidate()
        End Set
    End Property

    Private _nodes As New List(Of Point)
    Public ReadOnly Property Nodes() As List(Of Point)
        Get
            Return _nodes
        End Get
    End Property

    Private node_default_color As Color = Me.BackColor
    <System.ComponentModel.Description("Node")> Public Property NodeDefaultColor() As Color
        Get
            Return node_default_color
        End Get
        Set(ByVal value As Color)
            node_default_color = value : Me.Invalidate()
        End Set
    End Property

    Private nodes_height As Integer = 12
    <System.ComponentModel.Description("Node")> Public Property NodeHeightCount() As Integer
        Get
            Return nodes_height
        End Get
        Set(ByVal value As Integer)
            If value < 1 Then value = 1
            nodes_height = value : Me.Invalidate()
        End Set
    End Property

    Private node_selected_color As Color = Me.BackColor
    <System.ComponentModel.Description("Node")> Public Property NodeSelectedColor() As Color
        Get
            Return node_selected_color
        End Get
        Set(ByVal value As Color)
            node_selected_color = value : Me.Invalidate()
        End Set
    End Property

    Private node_size As Size = New Size(25, 25)
    <System.ComponentModel.Description("Node")> Public Property NodeSize() As Size
        Get
            Return node_size
        End Get
        Set(ByVal value As Size)
            node_size = value : Me.Invalidate()
        End Set
    End Property

    Private nodes_left As Integer = 12
    <System.ComponentModel.Description("Node")> Public Property NodeWidthCount() As Integer
        Get
            Return nodes_left
        End Get
        Set(ByVal value As Integer)
            If value < 1 Then value = 1
            nodes_left = value : Me.Invalidate()
        End Set
    End Property

#End Region

#Region "Methods"

    Public Sub FindPath()
        'Clear existing points
        Call ClearPath()

        'Get a start node
        Dim start_node As Point = beginning_node

        'Get if the path is to the left or to the rigth
        Dim horizontal_movement As Direction
        'Get if the path is to the up or to the down
        Dim vertical_movement As Direction

        If beginning_node.X < end_node.X Then
            horizontal_movement = Direction.Right
        ElseIf beginning_node.X > end_node.X Then
            horizontal_movement = Direction.Left
        Else
            horizontal_movement = Direction.None
        End If

        If beginning_node.Y < end_node.Y Then
            vertical_movement = Direction.Down
        ElseIf beginning_node.Y > end_node.Y Then
            vertical_movement = Direction.Up
        Else
            vertical_movement = Direction.None
        End If

        'If vertical movement or horizontal movement is nothing then we either move only up or only down
        If horizontal_movement = Direction.None Then
            Dim _step As Integer = 1
            If vertical_movement = Direction.Up Then
                _step = -_step
            End If

            For i As Integer = beginning_node.Y To end_node.Y Step _step
                _nodes.Add(New Point(beginning_node.X, i))
            Next
        ElseIf vertical_movement = Direction.None Then
            Dim _step As Integer = 1
            If horizontal_movement = Direction.Left Then
                _step = -_step
            End If

            For i As Integer = beginning_node.X To end_node.X Step _step
                _nodes.Add(New Point(i, beginning_node.Y))
            Next
        Else
            Dim temp_nodes As New List(Of Point)
            temp_nodes.Add(New Point(beginning_node.X, beginning_node.Y))

            Do Until horizontal_movement = Direction.None AndAlso vertical_movement = Direction.None
                Dim current_node As Point = temp_nodes.Item(temp_nodes.Count - 1)

                If current_node = end_node Then
                    horizontal_movement = Direction.None
                    vertical_movement = Direction.None
                Else
                    If current_node.X < end_node.X Then
                        horizontal_movement = Direction.Right
                    ElseIf current_node.X > end_node.X Then
                        horizontal_movement = Direction.Left
                    Else
                        horizontal_movement = Direction.None
                    End If

                    If current_node.Y < end_node.Y Then
                        vertical_movement = Direction.Down
                    ElseIf current_node.Y > end_node.Y Then
                        vertical_movement = Direction.Up
                    Else
                        vertical_movement = Direction.None
                    End If

                End If

                If horizontal_movement = Direction.Right Then
                    current_node = New Point(current_node.X + 1, current_node.Y)
                ElseIf horizontal_movement = Direction.Left Then
                    current_node = New Point(current_node.X - 1, current_node.Y)
                End If

                If vertical_movement = Direction.Down Then
                    current_node = New Point(current_node.X, current_node.Y + 1)
                ElseIf vertical_movement = Direction.Up Then
                    current_node = New Point(current_node.X, current_node.Y - 1)
                End If

                temp_nodes.Add(New Point(current_node.X, current_node.Y))

            Loop

            _nodes = temp_nodes

        End If

        Me.Invalidate()
    End Sub

    Public Sub ClearPath()
        _nodes.Clear()
        Me.Invalidate()
    End Sub

#End Region

    Protected Overrides Sub OnPaint(e As System.Windows.Forms.PaintEventArgs)
        MyBase.OnPaint(e)

        For x As Integer = 0 To nodes_left - 1
            For y As Integer = 0 To nodes_height - 1
                Dim pt As New Point(x, y)
                If pt = beginning_node OrElse _
                    pt = end_node OrElse _
                    _nodes.Contains(pt) Then

                    e.Graphics.FillRectangle(New SolidBrush(node_selected_color), New Rectangle(New Point(pt.X * node_size.Width, pt.Y * node_size.Height), node_size))
                Else
                    e.Graphics.FillRectangle(New SolidBrush(node_default_color), New Rectangle(New Point(pt.X * node_size.Width, pt.Y * node_size.Height), node_size))
                End If
                e.Graphics.DrawRectangle(Pens.Black, New Rectangle(New Point(pt.X * node_size.Width, pt.Y * node_size.Height), node_size))
            Next
        Next

        For Each node As Point In _nodes
            e.Graphics.FillRectangle(New SolidBrush(node_selected_color), New Rectangle(New Point(node.X * node_size.Width, node.Y * node_size.Height), node_size))
            e.Graphics.DrawRectangle(Pens.Black, New Rectangle(New Point(node.X * node_size.Width, node.Y * node_size.Height), node_size))
        Next
    End Sub

    Private Enum Direction
        Up
        Down
        Left
        Right
        None
    End Enum

End Class

[bensonsearch]

So this would be used for say a game sprite finding a path to food on the other side right? interesting, i always wonder how things like this are done.

[dday9]

This is really a brute force method and doesn't allow for blocked nodes, but it's a start. I want to learn the A*(pronounced "A Star") algorithm which is the foundation of path finding in game programming.

[dday9]

UPDATE!

Here is a major update in the Path Finding. I've created my version of the Dijkstra Algorithm in Vb.Net.

Features

1. A control that draws up a grid.
2. There are a start and end node. I reference those as Cap Nodes.
3. You can also add blocked nodes where the path may not pass through.
4. Fills up the nodes by calling the GetPath method
5. Clears the path by calling the ClearPath method

Drawbacks:
Dijkstra's algorithm fails if there is a negative edge weight. In the hypothetical situation where Nodes A, B, and C form a connected undirected graph with edges AB = 3, AC = 4, and BC = −2, the optimal path from A to C costs 1, and the optimal path from A to B costs 2. Dijkstra's Algorithm starting from A will first examine B, as that is the closest. It will assign a cost of 3 to it, and mark it closed, meaning that its cost will never be reevaluated. Therefore, Dijkstra's cannot evaluate negative edge weights. However, since for many practical purposes there will never be a negative edgeweight, Dijkstra's algorithm is largely suitable for the purpose of pathfinding. Found here.

Code:

Public Class Dijkstra
    Inherits System.Windows.Forms.Control

#Region "Properties"

    Private bColor As Color
    <System.ComponentModel.Description("Gets/Sets the fill color of nodes that are impassable.")> _
    Public Property BlockedColor() As Color
        Get
            Return bColor
        End Get
        Set(ByVal value As Color)
            bColor = value : Me.Invalidate()
        End Set
    End Property

    Private bNodes As List(Of Rectangle)
    <System.ComponentModel.Description("Gets/Sets the collection of nodes that are impassable.")> _
    Public Property BlockedNodes() As List(Of Rectangle)
        Get
            Return bNodes
        End Get
        Set(ByVal value As List(Of Rectangle))
            bNodes = value : Me.Invalidate()
        End Set
    End Property

    Private cColor As Color
    <System.ComponentModel.Description("Gets/Sets the fill color of the beginning and end nodes.")> _
    Public Property CapColor() As Color
        Get
            Return cColor
        End Get
        Set(ByVal value As Color)
            cColor = value : Me.Invalidate()
        End Set
    End Property

    Private eNode As Rectangle
    <System.ComponentModel.Description("Gets/Sets the node at the end of the path.")> _
    Public Property EndNode() As Rectangle
        Get
            Return eNode
        End Get
        Set(ByVal value As Rectangle)
            eNode = value : Me.Invalidate()
        End Set
    End Property

    Private n As List(Of Rectangle)
    <System.ComponentModel.Description("Gets all the nodes in the grid.")> _
    Public ReadOnly Property Nodes() As List(Of Rectangle)
        Get
            Return n
        End Get
    End Property

    Private nSize As Size
    <System.ComponentModel.Description("Gets/Sets the size of the nodes in the grid.")> _
    Public Property NodeSize() As Size
        Get
            Return nSize
        End Get
        Set(ByVal value As Size)
            nSize = value : Me.Invalidate()
        End Set
    End Property

    Private pColor As Color
    <System.ComponentModel.Description("Gets the color of the collection of nodes that make up the path.")> _
    Public Property PathColor() As Color
        Get
            Return pColor
        End Get
        Set(ByVal value As Color)
            pColor = value : Me.Invalidate()
        End Set
    End Property

    Private pNodes As List(Of Rectangle)
    <System.ComponentModel.Description("Gets the collection of nodes that make up the path using Dijkstra Algorithm.")> _
    Public ReadOnly Property PathNodes() As List(Of Rectangle)
        Get
            Return pNodes
        End Get
    End Property

    Private sNode As Rectangle
    <System.ComponentModel.Description("Gets/Sets the node at the beginning of the path.")> _
    Public Property StartNode() As Rectangle
        Get
            Return sNode
        End Get
        Set(ByVal value As Rectangle)
            sNode = value : Me.Invalidate()
        End Set
    End Property

#End Region

#Region "Methods"

    Private Function CalculateHScore(ByVal node As Rectangle) As Integer
        'Manhattan method
        Dim h As Integer = (Me.EndNode.X - node.X) \ 25 + (Me.EndNode.Y - node.Y) \ 25
        If h < 0 Then
            h = -h
        End If
        Return h
    End Function

    <System.ComponentModel.Description("Clears the PathNodes property.")> _
    Public Sub ClearPath()
        If pNodes IsNot Nothing Then
            pNodes.Clear()
            Me.Invalidate()
        End If
    End Sub

    <System.ComponentModel.Description("Gets the nodes that make up the PathNodes property and draws the nodes too.")> _
    Public Sub GetPath()
        pNodes = New List(Of Rectangle)

        'The algorithm begins with a start node and an open set of candidate nodes
        Dim openSet As List(Of List(Of Rectangle)) = New List(Of List(Of Rectangle))

        'Add a new list with just the start node
        openSet.AddRange(NewNodeList(Nothing))

        'Loop until the path is populated or there are no other paths available
        Do
            Dim possibleWinners As List(Of List(Of Rectangle)) = New List(Of List(Of Rectangle))
            For i As Integer = openSet.Count - 1 To 0 Step -1
                If HitBlocked(openSet.Item(i).Last) OrElse HitWall(openSet.Item(i).Last) Then
                    openSet.RemoveAt(i)
                ElseIf HitEnd(openSet.Item(i).Last) Then
                    possibleWinners.Add(openSet.Item(i))
                Else
                    openSet.AddRange(NewNodeList(openSet.Item(i)))
                    openSet.RemoveAt(i)
                End If

                If possibleWinners.Count > 0 Then
                    Dim winner As List(Of Rectangle) = Nothing
                    For Each win As List(Of Rectangle) In possibleWinners
                        If winner IsNot Nothing Then
                            If win.Count < winner.Count Then
                                winner = win
                            End If
                        Else
                            winner = win
                        End If
                    Next

                    pNodes = winner
                End If
            Next
        Loop Until pNodes.Count > 0 OrElse openSet.Count = 0

        Me.Invalidate()
    End Sub

    Private Function HitBlocked(ByVal node As Rectangle) As Boolean
        Return bNodes.Contains(node)
    End Function

    Private Function HitWall(ByVal node As Rectangle) As Boolean
        If node.Left < 0 Then
            Return True
        ElseIf node.Right > Me.Width Then
            Return True
        ElseIf node.Top < 0 Then
            Return True
        ElseIf node.Bottom > Me.Height Then
            Return True
        Else
            Return False
        End If
    End Function

    Private Function HitEnd(ByVal node As Rectangle) As Boolean
        Return node = eNode
    End Function

    Private Function NewNodeList(ByVal priorList As List(Of Rectangle)) As List(Of Rectangle)()
        Dim foo As List(Of List(Of Rectangle)) = New List(Of List(Of Rectangle))

        If priorList IsNot Nothing Then
            Dim lastRect As Rectangle = priorList.Last
            'Get the surrounding nodes.
            'UL = Upper Left
            'UT = Upper Top
            'UR = Upper Right
            'ML = Middle Left
            'MR = Middle Right
            'LL = Lower Left
            'LB = Lower Bottom
            'LR = Lower Right
            Dim ulRect As Rectangle = New Rectangle(lastRect.X - nSize.Width, lastRect.Y - nSize.Height, nSize.Width, nSize.Height)
            Dim utRect As Rectangle = New Rectangle(lastRect.X, lastRect.Y - nSize.Height, nSize.Width, nSize.Height)
            Dim urRect As Rectangle = New Rectangle(lastRect.X + nSize.Width, lastRect.Y - nSize.Height, nSize.Width, nSize.Height)
            Dim mlRect As Rectangle = New Rectangle(lastRect.X - nSize.Width, lastRect.Y, nSize.Width, nSize.Height)
            Dim mrRect As Rectangle = New Rectangle(lastRect.X + nSize.Width, lastRect.Y, nSize.Width, nSize.Height)
            Dim llRect As Rectangle = New Rectangle(lastRect.X - nSize.Width, lastRect.Y + nSize.Height, nSize.Width, nSize.Height)
            Dim lbRect As Rectangle = New Rectangle(lastRect.X, lastRect.Y + nSize.Height, nSize.Width, nSize.Height)
            Dim lrRect As Rectangle = New Rectangle(lastRect.X + nSize.Width, lastRect.Y + nSize.Height, nSize.Width, nSize.Height)


            If priorList.Contains(ulRect) = False AndAlso HitBlocked(ulRect) = False AndAlso HitWall(ulRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(ulRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(ulRect)
                foo.Add(n)
            End If
            If priorList.Contains(utRect) = False AndAlso HitBlocked(utRect) = False AndAlso HitWall(utRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(utRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(utRect)
                foo.Add(n)
            End If
            If priorList.Contains(urRect) = False AndAlso HitBlocked(urRect) = False AndAlso HitWall(urRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(urRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(urRect)
                foo.Add(n)
            End If
            If priorList.Contains(mlRect) = False AndAlso HitBlocked(mlRect) = False AndAlso HitWall(mlRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(mlRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(mlRect)
                foo.Add(n)
            End If
            If priorList.Contains(mrRect) = False AndAlso HitBlocked(mrRect) = False AndAlso HitWall(mrRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(mrRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(mrRect)
                foo.Add(n)
            End If
            If priorList.Contains(llRect) = False AndAlso HitBlocked(llRect) = False AndAlso HitWall(llRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(llRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(llRect)
                foo.Add(n)
            End If
            If priorList.Contains(lbRect) = False AndAlso HitBlocked(lbRect) = False AndAlso HitWall(lbRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(lbRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(lbRect)
                foo.Add(n)
            End If
            If priorList.Contains(lrRect) = False AndAlso HitBlocked(lrRect) = False AndAlso HitWall(lrRect) = False AndAlso Me.CalculateHScore(lastRect) > Me.CalculateHScore(lrRect) Then
                Dim n As List(Of Rectangle) = New List(Of Rectangle)
                n.AddRange(priorList)
                n.Add(lrRect)
                foo.Add(n)
            End If
        Else
            Dim n As List(Of Rectangle) = New List(Of Rectangle)
            n.Add(sNode)
            foo.Add(n)
        End If

        Return foo.ToArray
    End Function

#End Region

#Region "Events"

    Protected Overrides Sub OnPaint(ByVal e As System.Windows.Forms.PaintEventArgs)
        MyBase.OnPaint(e)

        Using rBrush As SolidBrush = New SolidBrush(bColor)
            Using gBrush As SolidBrush = New SolidBrush(pColor)
                Using cBrush As SolidBrush = New SolidBrush(cColor)
                    Using bPen As Pen = New Pen(Color.Black, 1)
                        For Each r As Rectangle In n
                            If bNodes.Contains(r) Then
                                e.Graphics.FillRectangle(rBrush, r)
                            ElseIf pNodes IsNot Nothing AndAlso pNodes.Contains(r) AndAlso r <> sNode AndAlso r <> eNode Then
                                e.Graphics.FillRectangle(gBrush, r)
                            ElseIf r = sNode OrElse r = eNode Then
                                e.Graphics.FillRectangle(cBrush, r)
                            End If
                            e.Graphics.DrawRectangle(bPen, r)
                        Next
                    End Using
                End Using
            End Using
        End Using

    End Sub

    Private Sub Dijkstra_SizeChanged(ByVal sender As Object, ByVal e As System.EventArgs) Handles Me.SizeChanged
        n.Clear()
        For x As Integer = 0 To Me.Width - nSize.Width Step nSize.Width
            For y As Integer = 0 To Me.Height - nSize.Height Step nSize.Height
                n.Add(New Rectangle(New Point(x, y), nSize))
            Next
        Next
    End Sub

#End Region

#Region "New Constructors"

    Public Sub New()
        bColor = Color.Red
        bNodes = New List(Of Rectangle)
        cColor = Color.Blue
        nSize = New Size(25, 25)
        eNode = New Rectangle(0, 0, nSize.Width, nSize.Height)
        pColor = Color.Green
        sNode = New Rectangle(0, 0, nSize.Width, nSize.Height)
        n = New List(Of Rectangle)
    End Sub

#End Region

End Class

Image:

[dday9]

Here is the code I used in my Form in the image above for the Dijkstra algorithm(to much for the last post):

Option Strict On
Option Explicit On
Public Class Form1

    Private selectingBlocked As Boolean
    Private selectingEnd As Boolean
    Private selectingStart As Boolean

    Private Sub btnStart_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnStart.Click
        selectingBlocked = False
        selectingEnd = False
        selectingStart = True
        Dijkstra1.Cursor = Cursors.Cross
    End Sub

    Private Sub btnEnd_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnEnd.Click
        selectingBlocked = False
        selectingEnd = True
        selectingStart = False
        Dijkstra1.Cursor = Cursors.Cross
    End Sub

    Private Sub btnBlocked_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnBlocked.Click
        selectingBlocked = True
        selectingEnd = False
        selectingStart = False
        Dijkstra1.Cursor = Cursors.Cross
    End Sub

    Private Sub btnClear_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnClear.Click
        Dijkstra1.ClearPath()
    End Sub

    Private Sub btnFind_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnFind.Click
        Dijkstra1.GetPath()
    End Sub

    Private Sub Dijkstra1_MouseClick(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles Dijkstra1.MouseClick
        Dim x As Integer = e.Location.X
        Dim y As Integer = e.Location.Y

        Dim selectedNode As Rectangle

        For Each r As Rectangle In Dijkstra1.Nodes
            If r.IntersectsWith(New Rectangle(x, y, 1, 1)) Then
                selectedNode = r
                Exit For
            End If
        Next

        If selectingEnd = True Then
            Dijkstra1.EndNode = selectedNode
        ElseIf selectingStart = True Then
            Dijkstra1.StartNode = selectedNode
        ElseIf selectingBlocked Then
            If Dijkstra1.BlockedNodes.Contains(selectedNode) = False Then
                Dijkstra1.BlockedNodes.Add(selectedNode)
                Dijkstra1.Invalidate()
            Else
                Dijkstra1.BlockedNodes.Remove(selectedNode)
                Dijkstra1.Invalidate()
            End If
        End If
    End Sub

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        selectingBlocked = False
        selectingEnd = False
        selectingStart = False
        selectingBlocked = False
    End Sub

End Class

[dclamp]

*Choose*

[dday9]

Choose?