Sign in to follow this  
Followers 0
Linux

Path Finding Bot

4 posts in this topic

Hi all!

I created this code to find the best path between 2 point given by the user, using recursive function (the function CALC, calls itself inside)

The $field array is random( 0 = plain terrain, 99 = hilly terrain). This could reflect time or fuel used to travel that square. This is only an example. If you plan to use PathFinding you should also take a look at Toady Example HERE because the example I'm posting takes more time/iteractions.

This code can be improved to use GUI, User Selected Array, more speed, diagonal moves and other features.

ALLOWED TWEAKS:

You can change the size of the array, the starting point, End point, and $MaxSteps.

#cs ----------------------------------------------------------------------------
    
    AutoIt Version: 3.2.12.0
    Author:         Linux
    
    Script Function: This Script will find the best path from the starting point to the finish point, using recursive function
    
#ce ----------------------------------------------------------------------------
#include <array.au3>
Global $Field[12][12]
Global $StartPoint = "0/0" ; Upper Left
Global $Endpoint = "10/10" ; 
Global $MaxSteps = 100 ; this is used to speed up the pathfinding
Global $Max_x = UBound($Field, 1) - 1
Global $Max_y = UBound($Field, 2) - 1
Global $Lowest = 99*$Max_x * $Max_y, $LowestPath = ""
Global $TotalNodeschecked = 0, $TotalPaths = 0,$LastSec = @sec,$lastnodes = 0

For $node_y = 0 To $Max_y
    For $node_x = 0 To $Max_x
        $Field[$node_x][$node_y] = Floor(Random() * 99)+1 ; 0 = plain, 100 = hilly
        ;this can be time used, Fuel used or any other factor
    Next
Next
;_ArrayDisplay($Field, "FIELD CONFIGURATION")
Global $timer = TimerInit()
Local $_TempArray = StringSplit($StartPoint,"/")
Calc($StartPoint, 0, $Field[number($_TempArray[1])][number($_TempArray[2])],number($_TempArray[1]),number($_TempArray[2]))
If $LowestPath = "" Then
    ConsoleWrite("Path not found! Try a higher $MaxSteps Value!")
    Exit
EndIf
ConsoleWrite(@CRLF & "Time: " & Floor(TimerDiff($timer)) & " ms")
ConsoleWrite(@CRLF & "Total Nodes: " & $TotalNodeschecked)
ConsoleWrite(@CRLF & "Total Paths: " & $TotalPaths)
ConsoleWrite(@CRLF & "Lowest Total: " & $Lowest)
ConsoleWrite(@CRLF & "Lowest Path: " &@crlf &  $LowestPath)
_ArrayDisplay($Field, "FIELD CONFIGURATION")

Func Calc($Path, $Step, $Total,$Node_x,$node_y)
    $TotalNodeschecked += 1 ; DEBUG ONLY
    $Step += 1
    ;#cs ; DEBUG ONLY 
    If @sec <> $LastSec Then
        ConsoleWrite(@crlf & "Sec: " & @sec & " Nodes per second: " & $TotalNodeschecked - $lastnodes)
        if $LowestPath <> "" then ConsoleWrite (" Paths: " & $TotalPaths & " LowestTotal: " & $Lowest)
        $LastSec = @SEC
        $lastnodes = $TotalNodeschecked
    EndIf
    ;#ce
    $Total += $Field[$Node_x][$node_y] ; add the node value to the total.
    If $Step > $MaxSteps or $total >= $Lowest Then Return 0 ; Speed up code
    If $node_x & "/" & $node_y = $Endpoint Then ; Path Found! 
        $TotalPaths += 1 
        If $Lowest > $Total Then ;If its lower
            $LowestPath = $Path ; SAVE CURRENT PATH
            $Lowest = $Total
        EndIf
        Return 0
    EndIf
    ;GO Down
    If $node_x < $Max_x And Not StringInStr($Path, $node_x + 1 & "/" & $node_y) And $Total + $Field[$node_x + 1][$node_y] < $Lowest Then Calc($Path & " Down " & $node_x + 1 & "/" & $node_y, $Step, $Total, $node_x + 1, $node_y)
    ;GO Right
    If $node_y < $Max_y And Not StringInStr($Path, $node_x & "/" & $node_y + 1) And $Total + $Field[$node_x][$node_y + 1] < $Lowest Then Calc($Path & " Right " & $node_x & "/" & $node_y + 1, $Step, $Total, $node_x , $node_y + 1)
    ;GO up
    If $node_y > 0 And Not StringInStr($Path, $node_x & "/" & $node_y - 1) And $Total + $Field[$node_x][$node_y - 1] < $Lowest Then Calc($Path & " Up " & $node_x & "/" & $node_y - 1, $Step, $Total,$node_x ,$node_y - 1)
    ;Go Left
    If $node_x > 0 And Not StringInStr($Path, $node_x - 1 & "/" & $node_y) And $Total + $Field[$node_x - 1][$node_y] < $Lowest Then Calc($Path & " Left " & $node_x - 1 & "/" & $node_y, $Step, $Total,$node_x - 1, $node_y)
EndFunc   ;==>Calc

Feel free to post your comments/critics here


You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"

Share this post


Link to post
Share on other sites



#2 ·  Posted (edited)

Can you provide an example of it's use?

I'm not quite sure what this dose.

Never mind... I see the link to the example.

Is this the beginning of a Real Time Strategy AI engine?

Edited by Zinthose

--- TTFN

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

This code will generate an array 12x12, with numbers between 1 and 99. that number can reflect the time used for a bot to travel that square. Sometimes the shortest path, isnt the quickest path, and there is a longest/quicker path.

This code will generate the random field, and then find the FASTEST path between 2 points!

1- Open the code.

2- Run the code.

3-Wait for it to generate random field, and search the quickest path. The quickest path is the one with the lowest SUM of the squares it uses to travel from Start point to End point. The code will try all combos, but it will preffer the squares with the lowest values.

Edited by Linux

You can help! Donate to AutoIt! or, visit ClimatePREDICTION.netMy posts:Travian Bot Example (100+ servers) BETAHow to Host you code/app for free! (unlimited team number) (Public or Private)"Sir, we're surrounded!" "Excellent. We can attack in any direction!"

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