Calculating paths in an Array

[furrycow]

Hey, so i have an array -> 10x6

Filled with random numbers between 1 and 9 so it COULD look something like this:

1 4 6 8 4 3 2 3 9 5

6 8 5 2 3 6 8 7 7 1

3 2 6 7 8 3 2 1 5 6

3 7 5 6 3 4 9 1 2 2

5 3 7 6 8 9 3 4 2 1

4 7 5 3 2 1 8 8 6 5

And what i want to do is try and find the shortest path (only travelling vertically and horizontally) to the nearest SAME number.

So, starting with the top left, "1", i want to find the nearest "1" to $array[0][0], which in this case would be $array[2][7] (the number in BOLD).

Would it be better to search every possible combination of moves, eg. look up, down, left, right one element in the array from the starting number, if it cant find it then try two...(but then when should it start looking around corners??)...or would it be better to _ArraySearch() for the nearest number, and work out the path from there...IT IS THE PATH I AM INTERESTED IN!!

So here is a very basic example which just tells you when there is a match with the number, ONE element around it, (above, below, left, right)...so i am really looking for a more complex version of this...a version that has the ability to look further than one square around it, and look for number around corners, so just like when it says, "Match RIGHT" for an equal element to the right of it, it would say, "Match RIGHT (3), BELOW (2)", for an element that was 3 to the right and two down...i hope i am, 1. not babbling, 2. making sense!! Heres the example i have done so far...

expandcollapse popup

#include <Array.au3>

Global $array[6][10]


For $x=0 To 9

    For $y=0 To 5

        $array[$y][$x]=Random(1,9,1) ;Just fills the Array with random numbers

    Next

Next

For $a = 0 To 9

        For $b = 0 To 5

        $TargetTILE=$array[$b][$a]
        ;If the RANDOM NUMBER in $array[$b][$a] equals any of the numbers around it then it will state where the number is
        If $a+1<9 And $array[$b][$a+1]=$TargetTILE Then
        Msgbox(0,"TARGET: "&$TargetTILE&" X: "&$a&" Y: "&$b,"Match RIGHT")
        _ArrayDisplay($array)
        EndIf
        If $b+1<5 And $array[$b+1][$a]=$TargetTILE Then
        Msgbox(0,"TARGET: "&$TargetTILE&" X: "&$a&" Y: "&$b,"Match BELOW")
        _ArrayDisplay($array)
        EndIf
        If $a-1>-1 And $array[$b][$a-1]=$TargetTILE Then
        Msgbox(0,"TARGET: "&$TargetTILE&" X: "&$a&" Y: "&$b,"Match LEFT")
        _ArrayDisplay($array)
        EndIf
        If $b-1>-1 And $array[$b-1][$a]=$TargetTILE Then
        Msgbox(0,"TARGET: "&$TargetTILE&" X: "&$a&" Y: "&$b,"Match ABOVE")
        _ArrayDisplay($array)
        EndIf

        Next

Next

Any help GREATLY appriciated!! Thanks.

Edited March 16, 2010 by furrycow

[dani]

As you can only travel horizontally and vertically, I think (I could be wrong of course) the shortest distance is always simply Abs(y2-y1) + Abs(x2-x1). If that really is the case -- and I am pretty 99% sure it is --, the solution would be using _ArraySearch and then just do the calculation

Edited March 16, 2010 by dani

[Melba23]

furrycow,

Here is my take on what you want:

expandcollapse popup

$iDim_X = 10
$iDim_Y = 6

Global $aArray[$iDim_Y][$iDim_X] = [ _
[1, 4, 6, 8, 4, 3, 2, 3, 9, 5], _
[6, 8, 5, 2, 3, 6, 8, 7, 7, 1], _
[3, 2, 6, 7, 8, 3, 2, 1, 5, 6], _
[3, 7, 5, 6, 3, 4, 9, 1, 2, 2], _
[5, 3, 7, 6, 8, 9, 3, 4, 2, 1], _
[4, 7, 5, 3, 2, 1, 8, 8, 6, 5]]
;0  1  2  3  4  5  6  7  8  9 = X coords,  Y coords are vertical 0 to 5

$sStart = "7,2"

$aIndex = StringSplit($sStart, ",")
$iValue = $aArray[Number($aIndex[2])][Number($aIndex[1])]
ConsoleWrite($iValue & " @ " & $aIndex[1] & " - " & $aIndex[2] & @CRLF)

$iX_Pos = $aIndex[1]
$iY_Pos = $aIndex[2]
$iLowest = $iDim_X + $iDim_Y

For $y = 0 To $iDim_Y - 1

    For $x = 0 To $iDim_X - 1

        If $x = $aIndex[1] And $y = $aIndex[2] Then ContinueLoop

        If $aArray[$y][$x] = $iValue Then
            $iY = Abs($y - Number($aIndex[2]))
            $iX = Abs($x - Number($aIndex[1]))
            $iScore = $iY + $iX
            If $iScore < $iLowest Then
                $iLowest = $iScore
                $iX_Pos = $x
                $iY_Pos = $y
            EndIf
        EndIf
    Next
Next

ConsoleWrite("Value " & $iValue & " - Nearest SAME number found at " & $iX_Pos & "x" & $iY_Pos & " = " & $iLowest & " moves away" & @CRLF)

M23

[JRowe]

You're looking for the A* algorithm. There was an implementation in AutoIt 2 years ago.

http://www.autoitscript.com/forum/index.php?showtopic=47161&st=0

I don't know what you'll have to do to update this, but it should be exactly what you want. It will give you the an optimal path across 2 dimensions.

Edited March 16, 2010 by JRowe

[furrycow]

I havent got time tonight to try them out, but JRowe, just having a quick little gander at your suggestion, and reading through the post...THAT SOUNDS EXACTLY WHAT I WANT!! - What a find, Thanks!!!

Thanks to you both for your time Melba and dani as well, i'll try them out tomorrow!