Jump to content
Sign in to follow this  
Acanis

Optimal route calculation

Recommended Posts

Hey, I'm trying to figure out what my algorithm has to look like so that I can reach a certain number of targets from a starting point and go back again with a minimum number of steps.
I found Dijkstra and A*, but I don't know if it's too complex for this problem and how to start correctly with the AutoIt implementation.

Can you please help me or give me a hint?

My code so far:

#include <Array.au3>

Dim $aArray[20][20] ; x/y

Local $aHome[1][2] = [[8, 9]] ; Array starts with 0, so 7/8 in $aArray
Local $aTargets[6][2] = [[7, 11], [8, 12], [9, 7], [7, 5], [10, 10], [5, 9]]

;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ******4*************
;~ ********************
;~ ********3***********
;~ ********************
;~ ****6**H************
;~ *********5**********
;~ ******1*************
;~ *******2************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
;~ ********************
; Find an algorithm that calculates the optimal way to run from a coordinate to x (3 / 4) targets in a Cartesian coordinate system and to end back at the initial coordinate.

; Test Distance Home -> Target 1 (8/9 to 7/11)
Dim $aTarget[1][2] = [[$aTargets[0][0], $aTargets[0][1]]]
ConsoleWrite("Test Home -> Target 1: " & (getDistance($aHome, $aTarget) = 2) & @CRLF)


Func getDistance($aHome, $aTarget)
    Local $aX = $aHome[0][0], $aY = $aHome[0][1], $bX = $aTarget[0][0], $bY = $aTarget[0][1]
    Local $iDist = Min(Abs($aX - $bX), Abs($aY - $bY))

    $aX += $aX > $bX ? -$iDist : $iDist
    $aY += $aY > $bY ? -$iDist : $iDist

    Return $iDist + Abs($aX - $bX) + Abs($aY - $bY)
EndFunc

Func getCoordInArray($aArray)
    Dim $aArray2[1][2] = [[$aArray[0] - 1, $aArray[1] -1]]

    Return $aArray2
EndFunc

Func Min($a, $b)
    Return $a < $b ? $a : $b
EndFunc

Thank you

Share this post


Link to post
Share on other sites

You may wish to study the TSP example here.

Alternatively, you can ask an amoeba.

Edited by RTFC

Share this post


Link to post
Share on other sites
1 hour ago, RTFC said:

You may wish to study the TSP example here.

Alternatively, you can ask an amoeba.

Thank you - looks good. I try to understand the TSP example, even its different, because I dont want to go to "every city". I have to say, that its not easy to understand the script (for me^^), you use a lot of Globals and even if its just 300 lines (and I can skip/delete the GUI), I feel a little overwhelmed. But I try to follow this puls. :)

I like the idea behind Simulated Annealing. Iam just a little inexperienced^^.

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  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...