[RESOLVED] reading cell values in an image

Hello everyone,

I would be so glad if you could help me on the following problem. I want to read the values of the 8 neighboring cells in an image as shown on the attached file. For example, the green cell is the home cell and it has 8 neighbors (cells from 1 to 8 as seen on the attached image). It will read all 8 neighboring cells then it will move one cell to right (now pixel 4 will be home pixel). Again it will read its neighboring cell values and then it will move to next pixel etc. It will continue till to the end (the last cell or pixel of the image). I would appreciate if you could help me on this..

Thanks in advance.

Well, the idea is to make two variables, homeX and homeY from where you will make different points for the neighbours. You read the colour from these neighbours.

Code:

---

        Dim img As Bitmap = New Bitmap(8, 8) 'load or set your image to use here
        Dim homeX As Integer = 1
        Dim homeY As Integer = 1
        For hX As Integer = homeX To img.Width - 2
            'to img.width - 2 so it stops at the second last pixel on the X - axis
            'also, the image must be at least 3 x 3 large
            'next step is to read the pixels around it
            'first make an array of points for all neighbours
            Dim neighbours(8) As Point
            neighbours(0) = New Point(hX - 1, homeY - 1) '1
            neighbours(1) = New Point(hX, homeY - 1) '2
            neighbours(2) = New Point(hX + 1, homeY - 1) '3
            neighbours(3) = New Point(hX + 1, homeY) '4
            neighbours(4) = New Point(hX + 1, homeY + 1) '5
            neighbours(5) = New Point(hX, homeY + 1) '6
            neighbours(6) = New Point(hX - 1, homeY + 1) '7
            neighbours(7) = New Point(hX - 1, homeY) '8
            'loop through all neighbours and read color (pixel)
            For Each neighbour As Point In neighbours
                Dim neighbourcolor As Color = img.GetPixel(neighbour.X, neighbour.Y)
                'perform operation on this color?
            Next
        Next

---

Make sure not to go outside of the image bounds, or it will crash. You could also check in the Y direction by adding another For loop for the Y values inside the current For loop.

Thank you, bergerkiller, for the code. It works if the program starts at (1,1) or it has 8 neighbor pixels but what if the image has, lets say, a size of 10x10?

I mean the program should always start from pixel location (0,0) which has only three neighbor pixels (one on the east, one on the southeast, one on the south), and should end at the last pixel location (10,10) if the image has a dimension of (10,10). The program should read only those three pixels and should not crash because there are not 8 neighbor pixels.

Thanks.

Well then you will have to check if the point is allowed (not -1 and not outside of the image width/height) and just loop from 0.0 - w.h.

Ok, let's get coding. :bigyello:

First of all, you will need two for loops, one in the X and one in the Y dimension:

Code:

---

        Dim IMG As Bitmap = New Bitmap(10, 10)
        For Y As Integer = 0 To IMG.Height - 1
            For X As Integer = 0 To IMG.Width - 1
                'Code for every pixel goes here
            Next
        Next

---

Then you need to know all of the neighbours that exist around this point. Tip: you could make a separate subroutine for this, and one for the "PointIsInImage" If statement line.

Code:

---

        Dim IMG As Bitmap = New Bitmap(10, 10)
        For Y As Integer = 0 To IMG.Height - 1
            For X As Integer = 0 To IMG.Width - 1
                Dim neighbours(8) As Point
                neighbours(0) = New Point(X - 1, Y - 1) '1
                neighbours(1) = New Point(X, Y - 1) '2
                neighbours(2) = New Point(X + 1, Y - 1) '3
                neighbours(3) = New Point(X + 1, Y) '4
                neighbours(4) = New Point(X + 1, Y + 1) '5
                neighbours(5) = New Point(X, Y + 1) '6
                neighbours(6) = New Point(X - 1, Y + 1) '7
                neighbours(7) = New Point(X - 1, Y) '8
                For Each neighbour As Point In neighbours
                    If neighbour.X >= 0 And neighbour.Y >= 0 And neighbour.X < IMG.Width And neighbour.Y < IMG.Height Then
                        'this neighbour exists, since it is inside of the image bounds.
                        Dim neighbourcolor As Color = IMG.GetPixel(neighbour.X, neighbour.Y)
                        'perform operation on this color?
                        'The neighbour X, Y and colour value and the base point X and Y are available for you to use.
                    End If
                Next
            Next
        Next

---

BTW: if you are going to use this on large images (50+ x 50+) it may take a while to loop through all the points and read the colour. In case you use this image as some sort of "color map" internally, you could better use an array with two dimensions:

Code:

---

        Dim colormap(10, 10) As Color
        colormap(0, 0) = Color.Black

---

Thank you, bergerkiller, for your help. It worked smoothly. What if I want the program should check its neighbors values and should select the largest value which will be the next host and then the program will continue to check this new hosts neighbor values and it will select the pixel that has the largest among 8 neighbors and this will continue like that. This way the program will not have to check each and every pixel of the image. It will follow the path of cells that have largest values.

Thanks again for all the help you have provided so far...

Should it check the surrounding pixels' value based on the home pixel?
You can navigate through a path of highest values, but the risk exists it ends up in a loop which never ends...

What is the main purpose; finding the pixel (point) in the image that has the highest color value, or to make some sort of pixel map navigation?

EDIT

Already got this, inside the do-loop you can use the current point

Code:

---

    Public Sub routine()
        Dim IMG As New Bitmap(10, 10)
        Dim currentPoint As New Point(0, 0) 'point to start from
        Dim previousPoints As New List(Of Point) 'previous points, these are not allowed to navigate to
        'Now a do-loop
        Do
            Dim p As Point = GetPointHighestNeighbour(IMG, currentPoint, previousPoints)
            If IsNothing(p) Then
                'found the end of the path, time to quit
                Exit Do
            Else
                currentPoint = p
                previousPoints.Add(currentPoint)
            End If
        Loop
    End Sub

    Public Function GetPointHighestNeighbour(ByVal IMG As Bitmap, ByVal P As Point, ByVal skipPoints As List(Of Point)) As Point
        'IMG is the image used for the colors and bounds
        'P is the point to check the neighbours of
        'skipPoints is a collection of points which are not allowed as return point
        Dim neighbours(8) As Point
        neighbours(0) = New Point(P.X - 1, P.Y - 1) '1
        neighbours(1) = New Point(P.X, P.Y - 1) '2
        neighbours(2) = New Point(P.X + 1, P.Y - 1) '3
        neighbours(3) = New Point(P.X + 1, P.Y) '4
        neighbours(4) = New Point(P.X + 1, P.Y + 1) '5
        neighbours(5) = New Point(P.X, P.Y + 1) '6
        neighbours(6) = New Point(P.X - 1, P.Y + 1) '7
        neighbours(7) = New Point(P.X - 1, P.Y) '8
        Dim highestpoint As Point
        Dim highestcolor As Integer = -1 'make sure the first point is higher
        For Each neighbour As Point In neighbours
            If Not skipPoints.Contains(neighbour) Then
                If neighbour.X >= 0 And neighbour.Y >= 0 And neighbour.X < IMG.Width And neighbour.Y < IMG.Height Then
                    Dim c As Color = IMG.GetPixel(neighbour.X, neighbour.Y)
                    Dim cvalue As Integer = c.A + c.R + c.G + c.B
                    If cvalue > highestcolor Then
                        'new highest colour found
                        highestpoint = neighbour 'set a new return point
                        highestcolor = cvalue 'set a new max for the following points
                    End If
                End If
            End If
        Next
        Return highestpoint
    End Function

---

Hi bergerkiller... You are so right about the never ending loop. I was trying to do something similar the A* (pathfinding) algorithm but I now know that it makes no sense. Do you have an idea about the shortest path algorithm? I have read about A* algorithm and according to that algorithm the diagonal moves cost 14, and normal north-south or east-west moves cost 10. Lets say starting point is (0,0) and ending point (4,4) in an 8x8 pixel image... I do not know how I could code to calculate the shortest path from (0,0) to (4,4)... It starts searching the 8 neighboring pixels of the starting point (0,0) and this is ok with your help of course. But how could the program would know that the southeast pixel of the (0,0) which is located at (1,1) should be selected... I just hope you could have an idea...

Thanks..

Wow, spot on. :bigyello:

Yep, pathfinding is very hard in this case. It kind of depends of the complexity of the image pixel data used. Any ways, like any path finding type, there are two ways:
- get all possible routes and choose the shortest (time consuming!)
- check for every available neighbour if it is closest to the destination. If so, move on.

I'd go for the second way, since way 1 is very hard to make. (separating the pathways)

Ok, I'll give it a go. :D

To do this, you need a few things:
- an image that has either accessible (white) or not-accessible (black) pixels
- a function that returns accessible points to travel to
- a function that returns the closest point of a list of points
- a list of already travelled points to prevent looping around

It looks bit like the first and second post, but now you return all available points that have a white pixel:

Code:

---

    Public Function GetAccessiblePoints(ByVal IMG As Bitmap, ByVal P As Point, ByVal skipPoints As List(Of Point)) As List(Of Point)
        'IMG is the image used for the colors and bounds
        'P is the point to check the neighbours of
        'skipPoint is the point which is not allowed as return point, can be set to nothing
        Dim neighbours(8) As Point
        neighbours(0) = New Point(P.X - 1, P.Y - 1) '1
        neighbours(1) = New Point(P.X, P.Y - 1) '2
        neighbours(2) = New Point(P.X + 1, P.Y - 1) '3
        neighbours(3) = New Point(P.X + 1, P.Y) '4
        neighbours(4) = New Point(P.X + 1, P.Y + 1) '5
        neighbours(5) = New Point(P.X, P.Y + 1) '6
        neighbours(6) = New Point(P.X - 1, P.Y + 1) '7
        neighbours(7) = New Point(P.X - 1, P.Y) '8
        'check for each point if it exists and add to (return) array if the pixel is white
        Dim rpoints As New List(Of Point)
        For Each neighbour As Point In neighbours
            If Not skipPoints.Contains(neighbour) Then
                If neighbour.X >= 0 And neighbour.Y >= 0 And neighbour.X < IMG.Width And neighbour.Y < IMG.Height Then
                    Dim c As Color = IMG.GetPixel(neighbour.X, neighbour.Y)
                    If c.R = 255 And c.G = 255 And c.B = 255 Then rpoints.Add(neighbour)
                End If
            End If
        Next
        Return rpoints
    End Function

---

Now you need to get the point that is closest to the destination:

Code:

---

    Public Function GetDistance(ByVal Point1 As Point, ByVal Point2 As Point) As Double
        Return Math.Sqrt((Point1.X - Point2.X) ^ 2 + (Point1.Y - Point2.Y) ^ 2)
    End Function
    Public Function GetNearestPoint(ByVal Points As List(Of Point), ByVal Destination As Point) As Point
        Dim rval As Point
        Dim smallestdistance As Double = Double.MaxValue
        For Each p As Point In Points
            Dim distance As Double = GetDistance(p, Destination) 'get the distance between two points (Pythagoras Theorem)
            If distance < smallestdistance Then
                rval = p 'set new minimum point
                smallestdistance = distance 'update new minimum
            End If
        Next
        Return rval
    End Function

---

And a function that uses there functions in a loop:

Code:

---

    Public Sub routine()
        Dim IMG As New Bitmap(10, 10)
        Dim currentPoint As New Point(0, 0) 'point to start from
        Dim destPoint As New Point(4, 6) 'point to go to
        Dim previousPoints As New List(Of Point) 'previous points, these are not allowed to navigate to
        'Now a do-loop
        Do
            Dim p As List(Of Point) = GetAccessiblePoints(IMG, currentPoint, previousPoints)
            Dim nearestpoint As Point = GetNearestPoint(p, destPoint)
            If IsNothing(nearestpoint) Then
                'found the end of the path, time to quit
                Exit Do
            ElseIf nearestpoint = destPoint Then
                'traveled to the destination, huray!
                MsgBox("I found the destination.", MsgBoxStyle.Information)
            Else
                'move on
                currentPoint = nearestpoint
                previousPoints.Add(currentPoint)
            End If
        Loop
    End Sub

---

It should work, but only in a somewhat understandable fashion. For example, if there is a curve it could end up in the corner and walk around in there, or eat itself up like in the snake game.
If the path consists of a line, this will not happen. It will just move on, since there is only one (good) pixel to go to.

EDIT

Wow, it does work. I made my form draw the path image and a red line between current point and destination, it nicely goes to the destination! :D
But yeah, with a bulge of 2x2 in it it runs around and ends up "eating itself". You could increase the logic a few steps ahead. For example, you can make a function that returns how many steps he needed to travel to a certain point. Then you check during every step which neighbour has the least steps. Or even more advanced, you make it recursive and basically do EVERY POSSIBLE ROUTE POSSIBLE. But yeah, it's not the most efficient way. :P

Thank you, bergerkiller... I guess you are using the hypotenuse rule to find the shortest path, am I right?

I guess so yes, it checks for all neighbour pixels if it is nearest to the destination. If so, move on.

You can go for the "hardcore" way, as I like to call it. Then you calculate every possible path. For example, from every neighbour you do for every neighbour you do for every neighbour etc. A single or a few times it will manage to find the destination. In that case, it stops all running routines and uses this path.

It uses recursive functions, therefore it will be pretty slow. Let's say, about 2000 iterations for a 10x10 bitmap? :bigyello:

EDIT

Something like this, only needs a better-built "previous points" system:

Code:

---

    Public prevpoints As New List(Of Point)
    Public destination As New Point(10, 10)
    Public Function FindDestinationPath(ByVal startpoint As Point) As List(Of Point)
        If startpoint = destination Then Return prevpoints
        prevpoints.Add(startpoint)
        For Each neighbour As Point In GetAccessiblePoints(IMG, startpoint, prevpoints)
            Dim res As List(Of Point) = FindDestinationPath(neighbour)
            If Not IsNothing(res) Then Return res
        Next
        Return Nothing
    End Function

---

The idea is to make it travel every single path possible, and check if the destination is reached. If so, pass the result path back and make all for loops behind it stop and return the new path. This will eventually get the good path back to the surface.

You could also make it add the path to an array of paths, and finally check the amount of steps (point) required for every path. Then choose the shortest.

Working with lists for a single path could mess up the code easily, try to place your "path list" into a class called "Path" :thumb:
Also, every iteration has to know of a certain path. Every level up has a different path, this means different variables. Instead of using paths (they can take up a lot of resources) you can pass the previous point to every function, and, if the result is true, make every underlying control add it's own path to the return array. This would reduce the size a lot.

Code:

---

    Public destination As New Point(10, 10)
    Public result As New List(Of Point)
    Public Function FindDestinationPath(ByVal startpoint As Point) As Boolean
        If startpoint = destination Then Return True 'Pass message that destination is reached
        For Each neighbour As Point In GetAccessiblePoints(IMG, startpoint, New List(Of Point))
            If FindDestinationPath(neighbour) Then
                result.Insert(0, neighbour) 'Add own point to path array, add at 0 since the order is inverted
                Return True
            End If
        Next
        Return False
    End Function

---

But now, no "previous points" are stored. (That's why I used the Path way at first, it is the same as previous points)

As you can see, many solutions are possible, it just needs some debugging and optimization. ;)

Thank you, bergerkiller, for your help. I appreciate it, but I couldn't make it work. How could you make it draw a red line between start and end points?

Using a graphics object. Upon every update you do, you make the graphics object clear itself and draw the image (IMG) and a line:

Code:

---

        Dim g As Graphics = PictureBox1.CreateGraphics
        g.DrawImage(IMG, New Point(0, 0))
        g.DrawLine(Pens.Red, currentPoint.X, currentPoint.Y, destPoint.X, destPoint.Y)

---

Preferably you would keep the graphics object global or handle it in the OnPaint event of the picturebox.

And yes, my previous post about getting all paths is left untested, so you will probably have to change how it calls itself. (passing a new list array, cloned, containing the previous points and own point.)

Thanks bergerkiller. It draws the path but the do loop never ends.

I have inserted following code

Code:

---

Dim g As Graphics = PictureBox1.CreateGraphics
        g.DrawImage(IMG, New Point(0, 0))
        g.DrawLine(Pens.Red, currentPoint.X, currentPoint.Y, destPoint.X, destPoint.Y)

---

in sub routine before the do loop and I think the path draws red line just because of this code and not because of the search algorithm that checks each neighbor. I have also tried with some "unwalkable" black pixels but it just draws a straight red line over the black pixels. Where do you think I am doing wrong? Thanks.

Hehe nothing went wrong in your drawing function, it does what it does, it draws a line from start to end.

If you want to track the entire path, pass the "previous points" of the function to the g.DrawLines (Pens.Red , points)

Reason for infinite loop: no "previous points" are stored for every function. Since it is recursive, I recommend using classes instead of functions.

For example: class pathway containing a point and a reference to it's parent. This way you can recursively check back and go all the way back.
Achem, code:

Code:

---

    Public Class PathPoint
        Sub New(ByVal startpoint As Point, ByVal IMG As Bitmap)
            Me.Location = startpoint
            Me.Parent = Nothing
            Me.IMG = IMG
        End Sub
        Public Location As Point
        Public Parent As PathPoint
        Public IMG As Bitmap
        Public Function GetPreviousPoints() As List(Of Point)
            'recursively go back until there is no parent (=root)
            'insert at 0 so the last added point (=first point)
            Dim rval As New List(Of Point)
            Dim p As PathPoint = Me
            Do While Not IsNothing(p)
                rval.Insert(0, p.Location)
                p = p.Parent
            Loop
            Return rval
        End Function
        Public Function GetPath(ByVal destination As Point) As List(Of Point)
            If destination = Me.Location Then Return GetPreviousPoints() 'We got a result :)
            Dim neighbours(8) As Point
            neighbours(0) = New Point(Me.Location.X - 1, Me.Location.Y - 1) '1
            neighbours(1) = New Point(Me.Location.X, Me.Location.Y - 1) '2
            neighbours(2) = New Point(Me.Location.X + 1, Me.Location.Y - 1) '3
            neighbours(3) = New Point(Me.Location.X + 1, Me.Location.Y) '4
            neighbours(4) = New Point(Me.Location.X + 1, Me.Location.Y + 1) '5
            neighbours(5) = New Point(Me.Location.X, Me.Location.Y + 1) '6
            neighbours(6) = New Point(Me.Location.X - 1, Me.Location.Y + 1) '7
            neighbours(7) = New Point(Me.Location.X - 1, Me.Location.Y) '8
            For Each neighbour As Point In neighbours
                'Check bounds
                If neighbour.X >= 0 And neighbour.Y >= 0 And neighbour.X < IMG.Width And neighbour.Y < IMG.Height Then
                    'Check if not yet added
                    If Not GetPreviousPoints().Contains(neighbour) Then
                        Dim c As Color = IMG.GetPixel(neighbour.X, neighbour.Y)
                        If c.R = 255 And c.G = 255 And c.B = 255 Then
                            'accessible point
                            'make a new instance and perform same operation
                            Dim childpoint As New PathPoint(neighbour, Me.IMG)
                            childpoint.Parent = Me
                            Dim rval As List(Of Point) = childpoint.GetPath(destination) 'execute new point
                            If Not IsNothing(rval) Then
                                'We got a result! pass it back to underlying functions
                                Return rval
                            End If
                        End If
                    End If
                End If
            Next
            Return Nothing 'no result :(
        End Function
    End Class

---

This is tested, and, I must admit, pretty sick. In less than half a second it found the path in my 20x20 image! :eek:

Call it with (in my case, 17/16 is the destination):

Code:

---

        Dim pathway As New PathPoint(New Point(0, 0), IMG)
        Dim points As Point() = pathway.GetPath(New Point(17, 16)).ToArray

        'draw line displaying path
        Dim g As Graphics = PictureBox1.CreateGraphics
        g.DrawImage(IMG, New Point(0, 0))
        g.DrawLines(Pens.Red, points)
        g.Dispose()

---

Of course it is now simply just returning the first found path, if the image was pure white it would return a quite strange path. You can add a "length check" with the rval list, for example, to compare returned values on length (choose smallest) and return the smallest.

EDIT

I'm testing that but it takes infinitely long...
This time made it draw the new points to the form as soon it was found...there were infinite combinations possible, which explains the long time...

EDIT 2

For the best value possible, you would have to do this differently I guess...you would have to somehow check if a point to dest was processed before, and if so, use that point instead of regenerating it. It takes ages to do the path, even if there are only 2 points with 8 possible routes...

I'll work it out a little more, since I am interested. Going to add an array of "processed points", to prevent regeneration which is unneeded.

EDIT 3 (awesomeness)

I worked it out, and it is incredible how fast it is!

Code:

---

    Public Class PointPath
        Private processedpoints As New List(Of Point)
        Private processedpointpath As New List(Of List(Of Point))
        Sub New(ByVal IMG As Bitmap)
            Me.IMG = IMG
        End Sub
        Public IMG As Bitmap
        Public Function GetPath(ByVal StartPoint As Point, ByVal DestPoint As Point) As List(Of Point)
            processedpointpath.Clear()
            processedpoints.Clear()
            Dim p As New PathPoint(StartPoint, Me.IMG, Me)
            Return p.GetPath(DestPoint)
        End Function
        Private Class PathPoint
            Sub New(ByVal startpoint As Point, ByVal IMG As Bitmap, ByVal root As PointPath)
                Me.Location = startpoint
                Me.Parent = Nothing
                Me.IMG = IMG
                Me.Root = root
            End Sub
            Public Location As Point
            Public Root As PointPath
            Public Parent As PathPoint
            Public IMG As Bitmap
            Public Function GetPreviousPoints() As List(Of Point)
                'recursively go back until there is no parent (=root)
                'insert at 0 so the last added point (=first point)
                Dim rval As New List(Of Point)
                Dim p As PathPoint = Me
                Do While Not IsNothing(p)
                    rval.Insert(0, p.Location)
                    p = p.Parent
                Loop
                Return rval
            End Function
            Public Function GetPath(ByVal destination As Point) As List(Of Point)
                Dim index As Integer = Root.processedpoints.IndexOf(Me.Location)
                If index <> -1 Then
                    'this is already done, return finished result
                    Return Root.processedpointpath(index)
                Else
                    If destination = Me.Location Then Return GetPreviousPoints() 'We got a result :)
                    Dim neighbours(8) As Point
                    neighbours(0) = New Point(Me.Location.X - 1, Me.Location.Y - 1) '1
                    neighbours(1) = New Point(Me.Location.X, Me.Location.Y - 1) '2
                    neighbours(2) = New Point(Me.Location.X + 1, Me.Location.Y - 1) '3
                    neighbours(3) = New Point(Me.Location.X + 1, Me.Location.Y) '4
                    neighbours(4) = New Point(Me.Location.X + 1, Me.Location.Y + 1) '5
                    neighbours(5) = New Point(Me.Location.X, Me.Location.Y + 1) '6
                    neighbours(6) = New Point(Me.Location.X - 1, Me.Location.Y + 1) '7
                    neighbours(7) = New Point(Me.Location.X - 1, Me.Location.Y) '8
                    Dim rval As List(Of Point) = Nothing
                    Dim count As Integer = Integer.MaxValue
                    Dim newrval As List(Of Point)
                    For Each neighbour As Point In neighbours
                        'Check bounds
                        If neighbour.X >= 0 And neighbour.Y >= 0 And neighbour.X < IMG.Width And neighbour.Y < IMG.Height Then
                            'Check if not yet added
                            If Not GetPreviousPoints().Contains(neighbour) Then
                                Dim c As Color = IMG.GetPixel(neighbour.X, neighbour.Y)
                                If c.R = 255 And c.G = 255 And c.B = 255 Then
                                    'accessible point
                                    'make a new instance and perform same operation
                                    Dim childpoint As New PathPoint(neighbour, Me.IMG, Me.Root)
                                    childpoint.Parent = Me
                                    newrval = childpoint.GetPath(destination) 'execute new point
                                    If Not IsNothing(newrval) Then
                                        'We got a result! pass it back to underlying functions
                                        If newrval.Count < count Then
                                            rval = newrval
                                            count = rval.Count
                                        End If
                                    End If
                                End If
                            End If
                        End If
                    Next
                    'add to "processed" array
                    Root.processedpoints.Add(Me.Location)
                    Root.processedpointpath.Add(rval)
                    Return rval
                End If
            End Function
        End Class
    End Class

---

Code:

---

        Dim path As New PointPath(IMG)
        Dim points() As Point = path.GetPath(New Point(0, 0), New Point(17, 16)).ToArray

        'draw line displaying path
        Dim g As Graphics = PictureBox1.CreateGraphics
        g.ScaleTransform(10, 10)
        g.DrawImage(IMG, New Point(0, 0))
        g.DrawLines(Pens.Red, points)
        g.Dispose()

---

Code is a bit complicated, so I'll try to explain it:
First, a new instance of "PointPath" is made. In there, the image is set in the constructor. Then, you call the "getpath" function. All this does is create a new instance of "PathPoint" and referencing itself as the root and the image and start point. Then, the PathPoint GetPath is called with the destpoint.

Now it gets complicated: It first checks if the point was already processed by using the Root.processedpoints list. If it is added already, it returns the value. Else, it generated a new value. It recursively calls the GetPath function from a new instance (with self as parent) of PathPoint.

See it as running a lot of neighbour checkers in a recursive patern, thereby checking every available point it can get to. Using a count check it chooses the list with the least points.

Auch my head, can't believe I actually coded this beast in under an hour! :sick:

http://i708.photobucket.com/albums/w...0-40-41288.png
http://i708.photobucket.com/albums/w...20-37-2387.png

Hi bergerkiller. I am glad that you got it workin but I got NullReferenceException error :)

Code:

---

Dim newIMG As New Bitmap(PictureBox1.Image.Width, PictureBox1.Image.Height)
        Dim path As New PointPath(newIMG)
        Dim points() As Point = path.GetPath(New Point(0, 0), New Point(17, 16)).ToArray 'NullReferenceException error thrown on this line

        'draw line displaying path
        Dim g As Graphics = PictureBox1.CreateGraphics
        g.ScaleTransform(PictureBox1.Image.Width, PictureBox1.Image.Height)
        g.DrawImage(newIMG, New Point(0, 0))
        g.DrawLines(Pens.Red, points)
        g.Dispose()

---

Then it failed to find a path, and it returned nothing. You can't call the function of nothing, so an error is thrown.

Make sure your destination is accessible, and not in the black area. :thumb:

EDIT

BTW: if this was for a game, the game would load up the image and generate "pathways", basically lots of points linking to each other.
After generation, you can then, for example, get the point from all generated points and make it look for a way, by using it's children, to go to the destination.
Due to every function containing a return list, a stack overflow exception is likely to occur.

Sow, if you are working on "path finding" for a game, you can better use something like this:

vb Code:

Public Class PathFindingData
        Sub New(ByVal PathImage As Bitmap)
            'load all accessible points here
            Dim temp(PathImage.Width - 1, PathImage.Height - 1) As PathWay
            For x As Integer = 0 To PathImage.Width - 1
                For y As Integer = 0 To PathImage.Height - 1
                    temp(x, y) = New PathWay(New Point(x, y), GetPointAccesible(PathImage, x, y))
                Next
            Next
            'generate neighbours
            Me.PathWays = New List(Of PathWay)
            Dim neighbours(8) As Point
            Dim p As PathWay
            For x As Integer = 0 To PathImage.Width - 1
                For y As Integer = 0 To PathImage.Height - 1
                    p = temp(x, y)
                    If p.accessible Then
                        neighbours(0) = New Point(x - 1, y - 1) '1
                        neighbours(1) = New Point(x, y - 1) '2
                        neighbours(2) = New Point(x + 1, y - 1) '3
                        neighbours(3) = New Point(x + 1, y) '4
                        neighbours(4) = New Point(x + 1, y + 1) '5
                        neighbours(5) = New Point(x, y + 1) '6
                        neighbours(6) = New Point(x - 1, y + 1) '7
                        neighbours(7) = New Point(x - 1, y) '8 
                        For Each neighbour As Point In neighbours
                            If neighbour.X >= 0 And neighbour.Y >= 0 And neighbour.X < PathImage.Width And neighbour.Y < PathImage.Height Then
                                If temp(neighbour.X, neighbour.Y).accessible Then
                                    p.neighbours.Add(temp(neighbour.X, neighbour.Y))
                                End If
                            End If
                        Next
                        Me.PathWays.Add(p)
                    End If
                Next
            Next
        End Sub
        Private Function GetPointAccesible(ByVal IMG As Bitmap, ByVal x As Integer, ByVal y As Integer) As Boolean
            Dim c As Color = IMG.GetPixel(x, y)
            If c.R = 255 And c.G = 255 And c.B = 255 Then Return True
            Return False
        End Function
        Public PathWays As List(Of PathWay)
        Public Class PathWay
            Sub New(ByVal location As Point, Optional ByVal accesible As Boolean = True)
                Me.location = location
                Me.accessible = accesible
                Me.neighbours = New List(Of PathWay)
            End Sub
            Public location As Point
            Public neighbours As List(Of PathWay)
            Public accessible As Boolean
        End Class
        Public Function GetPathWay(ByVal location As Point) As PathWay
            For Each p As PathWay In PathWays
                If p.location = location Then Return p
            Next
            Return Nothing
        End Function
    End Class

Reading a pixel from an image takes longer than looping through points in memory. By pre-loading your path finding data performance will significantly improve, especially if you need to get different paths from one image. Pre-loading of my 1800x1800 image (maze) took around 25 seconds...not much compared to 3240000 pixels to read. :D

Update: used a 2-dimensional array to first store ANY point, and then generating neighbours by using this array. If the point was accessible, it gets added to a list. This list is used later on.

If you want to find a path, you first seek for the begin point by looping through the collection and getting the begin point "PathWay".
Finally (not yet added), it will go from child to child until it finds the destination. Instead of every function containing a list, you pass an index in this list of what point you're in.

As you see, I'm also quite interested in this. Never done path finding before...it's a nice challenge. :D

Thank you so much for your help, bergerkiller. This is not for a game... I am just trying to find the optimum path...

Well, I got to the end of .NET's limits. :(

I tried to make every possible variable in the recursive functions global or own-class added, but still it gives a stack overflow on:

Code:

---

For Each Me.tempneighbour In Me.neighbours

---

There is no way I could limit function variable creation here, so I guess I can not use recursive functions on VERY large images.

I'll try to get everything done in a single function; no recursion. Hopefully it will work. :bigyello:

EDIT

Nope, the "current step buffer" index went outside of the bounds of 1000000....that explains the stack overflow a bit...

EDIT 2

Found a bug that occurs in both the "no preload" and "with preload" version. As soon the "white line" gets wider than 1 pixel, it starts to "eat up" points around it, hindering future tries because it was already "processed"...

This is the preload version:

Code:

---

    Public Class PathFindingData
        Sub New(ByVal PathImage As Bitmap)
            'load all accessible points here
            Dim temp(PathImage.Width - 1, PathImage.Height - 1) As PathWay
            For x As Integer = 0 To PathImage.Width - 1
                For y As Integer = 0 To PathImage.Height - 1
                    temp(x, y) = New PathWay(New Point(x, y), GetPointAccesible(PathImage, x, y))
                Next
            Next
            'generate neighbours
            Me.PathWays = New List(Of PathWay)
            Dim neighbours(8) As Point
            Dim p As PathWay
            For x As Integer = 0 To PathImage.Width - 1
                For y As Integer = 0 To PathImage.Height - 1
                    p = temp(x, y)
                    If p.accessible Then
                        neighbours(0) = New Point(x - 1, y - 1) '1
                        neighbours(1) = New Point(x, y - 1) '2
                        neighbours(2) = New Point(x + 1, y - 1) '3
                        neighbours(3) = New Point(x + 1, y) '4
                        neighbours(4) = New Point(x + 1, y + 1) '5
                        neighbours(5) = New Point(x, y + 1) '6
                        neighbours(6) = New Point(x - 1, y + 1) '7
                        neighbours(7) = New Point(x - 1, y) '8
                        For Each neighbour As Point In neighbours
                            If neighbour.X >= 0 And neighbour.Y >= 0 And neighbour.X < PathImage.Width And neighbour.Y < PathImage.Height Then
                                If temp(neighbour.X, neighbour.Y).accessible Then
                                    p.neighbours.Add(temp(neighbour.X, neighbour.Y))
                                End If
                            End If
                        Next
                        Me.PathWays.Add(p)
                    End If
                Next
            Next
        End Sub
        Private Function GetPointAccesible(ByVal IMG As Bitmap, ByVal x As Integer, ByVal y As Integer) As Boolean
            Dim c As Color = IMG.GetPixel(x, y)
            If c.R = 255 And c.G = 255 And c.B = 255 Then Return True
            Return False
        End Function
        Private PathWays As List(Of PathWay)
        Public Function GetPath(ByVal startpoint As Point, ByVal endpoint As Point) As Point()
            'reset
            Dim begin As PathWay = Nothing
            For Each p As PathWay In Me.PathWays
                p.processed = False
                p.foundpath = Nothing
                If p.location = startpoint Then begin = p
            Next
            If IsNothing(begin) Then Return Nothing 'invalid starting point
            If begin.GetPaths(endpoint) Then
                Return begin.foundpath.ToArray
            Else
                Return Nothing
            End If
        End Function
        Private Class PathWay
            Sub New(ByVal location As Point, Optional ByVal accesible As Boolean = True)
                Me.location = location
                Me.accessible = accesible
                Me.neighbours = New List(Of PathWay)
            End Sub
            Public location As Point
            Public neighbours As List(Of PathWay)
            Public accessible As Boolean 'used when loading image data
            Public processed As Boolean 'used when getting a path (prevent infinite loop)
            Public foundpath As List(Of Point) 'smallest path returned by this function, also to prevent infinite loop
            Private tempneighbour As PathWay
            Public Function GetPaths(ByRef destination As Point) As Boolean
                If Me.processed = False Then
                    'generate shortest path found
                    Me.processed = True
                    Try
                        If Me.location = destination Then
                            'we found the destination!
                            Me.foundpath = New List(Of Point)
                            Me.foundpath.Add(Me.location)
                        Else
                            For Each Me.tempneighbour In Me.neighbours
                                If tempneighbour.GetPaths(destination) Then
                                    'my neighbour got to the destination
                                    If IsNothing(Me.foundpath) Then Me.foundpath = New List(Of Point)
                                    If Me.foundpath.Count = 0 OrElse Me.foundpath.Count > tempneighbour.foundpath.Count Then
                                        'set my foundpath to this path, but add my own point
                                        Me.foundpath = tempneighbour.foundpath
                                        Me.foundpath.Add(Me.location)
                                    End If
                                End If
                            Next
                        End If
                    Catch
                    End Try
                End If
                Return Not IsNothing(Me.foundpath) 'return whether I got a path to the destination (relative to self)
            End Function
        End Class
    End Class

---

Code:

---

        Dim data As New PathFindingData(IMG) 'loading can take a while
        Dim points() As Point = data.GetPath(New Point(2, 2), New Point(48, 48))
        If IsNothing(points) Then
            MsgBox("no path found")
        Else
            'draw line displaying path
            Dim g As Graphics = PictureBox1.CreateGraphics
            g.ScaleTransform(10, 10)
            g.DrawImage(IMG, New Point(0, 0))
            g.DrawLines(Pens.Red, points)
            g.Dispose()
        End If

---