Sign in to follow this  
Followers 0
furrycow

Calculating paths in an Array

5 posts in this topic

#1 ·  Posted (edited)

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...

#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 by furrycow

Instant Lockerz Invite - www.instantlockerzinvite.co.uk

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

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 by dani

Share this post


Link to post
Share on other sites

furrycow,

Here is my take on what you want: :(

$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


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

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 by JRowe

Share this post


Link to post
Share on other sites

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!


Instant Lockerz Invite - www.instantlockerzinvite.co.uk

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0