Android Question Quiz "Is there a path ?"

Informatix

Informatix

Expert
Licensed User
Longtime User
Hello,

I'd like to submit a quiz to the fellow members of this forum:
In a grid of 20x20, that you can see as a graph where each cell is connected to the four adjacent cells (no diagonals), there's a certain amount of blocked cells that creates a maze (or an empty crosswords grid). Your algorithm has to determine if there's a path between 2 cells of this grid (2 nodes of this graph).
The goal is to write the fastest algorithm and to beat mine. It's more a quiz about optimization with B4A than a quiz about algorithms (you should quickly find with Google a suitable algorithm for this). And the path has not to be the shortest one nor stored for a later use (only the answer to the question matters).

I'll give an answer of course and I'll explain my own code if there are participants to this quiz. Note that's not complicated at all and if you write more than 100 lines of code, you're probably doing something too complex and too slow. Simplicity is the key. No external library is allowed.

I join to this post a B4A project that you can use to create the maze and benchmark your attempts. It uses the NanoTime library to time your code (because DateTime.now is not accurate enough; 1 millisecond is too much ;)).
I will compare all submitted algo to my own algo ASAP.

Example of solution found in 0.09 ms on a Moto G (SS is the starting cell and DD the destination):
B4X: 
XX..XX............XXXX....XX......XX..XX
XXXXXX....XX......XX........XX......XX..
XX....XX..XXXXXX........DDXX....XXXX....
..XX....XXXX....XX......[][]XX..XX......
XX..XXXX....XXXX....XXXX..[]..XXXXXXXX..
..XX..XX..XX..XXXX..XX..XX[]XXXX........
....XX......XX......XXXX[][]..XX..XX..XX
......XX............XX[][]......XX......
..XXXX..XXXXXX....XX[][]..XXXX..XX......
XX..XX........XXXX[][]XX..........XX..XX
................[][]....XXXX..XX........
XX..XXXXXXXX....[]..XX..XX......XXXXXX..
..XX............[]XX......XX..XXXX......
XXXXXXXXXXXXXXXX[][]XXXXXXXX..XX..XX....
......XX..........[]..........XXXX..XXXX
XXXXXX..XX..XX....[]XX..XX..XX..........
XX......XX........[]XXXX........XXXX....
..XX........XXXXXXSSXXXX..XX....XXXX....
..XX....XX..XXXX......XXXX..XX....XX....
XX........XX......XX..XX..XX............
 

Attachments

  • QuizProject.zip
    6.5 KB · Views: 437
Last edited:
Sort by date Sort by votes
RandomCoder

RandomCoder

Well-Known Member
Licensed User
Longtime User
Well here's my attempt which is no where near as neat or condensed as the recursive code you guys have produced. I thought there would be some gains storing the alternate routes and sensibly selecting from the list but it seems that the creation of the list and managing of the list just adds another bottleneck. And probably its got a lot to do with my implementation.
B4X: 
Galaxy S3
----- TOTAL -----
Sum algo DFS = 18.323 ms / Worst = 0.217 ms
Sum algo RandomCoder = 13.89 ms / Worst = 0.213 ms
** Activity (main) Pause, UserClosed = true **


Nexus 7 (2013)
----- TOTAL -----
Sum algo DFS = 6.592 ms / Worst = 0.072 ms
Sum algo RandomCoder = 5.518 ms / Worst = 0.085 ms
** Activity (main) Pause, UserClosed = true **

B4X: 
Sub PathFinder()
    'Initialisations
    For X = 0 To SizeX - 1
        For Y = 0 To SizeY - 1
            Visited(X, Y) = Blocked(X, Y)
        Next
    Next
    ' Alternative routes (stored as X * Y)
    Dim AltPointer As Int = -1
    Dim Alternate(100) As Int

    ' Current X, Y position in maze
    Dim PosX As Int = StartX
    Dim PosY As Int = StartY

    ' Loop until destination found or Exit if impassable
    Do Until PosX = DestX And PosY = DestY
        Dim Up, Down, Left, Right As Boolean ' Possible paths
        Dim X_Dist As Int ' Distance from current position to Dest in X
        Dim Y_Dist As Int ' Distance from current position to Dest in Y
       
        Dim Count As Int  = 0 ' Number of possible paths
        Dim Pref_X As Int = 0 ' -1=Up, 0=Center, +1=Down
        Dim Pref_Y As Int = 0 ' -1=Left, 0=Center, +1=Right
        Dim Pref As Int   = 0 ' -1=Vertical, 1=Horizontal

        ' Set current position as visited and reset count
        Visited(PosX, PosY) = True
        Count = 0
       
        ' Determine prefered direction
        X_Dist = DestX - PosX
        Y_Dist = DestY - PosY
        Pref_X = Direction(X_Dist) ' -1=Up, 0=Center, +1=Down
        Pref_Y = Direction(Y_Dist) ' -1=Left, 0=Center, +1=Right
   
        ' Horizontal or vertical preference (which is the furthest)
        If Abs(X_Dist) > Abs(Y_Dist) Then
            Pref = -1 ' Vertical movement preferable
        Else
            Pref = 1  ' Horizontal movement preferable
        End If
   
        ' Determine which paths are free
        ' Check Up
        If PosX > 0 And Visited(PosX - 1, PosY) = False Then
            Up = True
            Count = Count + 1
        End If
        ' Check Down
        If PosX < SizeX - 1 And Visited(PosX + 1, PosY) = False Then
            Down = True
            Count = Count + 1
        End If
        ' Check left
        If PosY > 0 And Visited(PosX, PosY - 1) = False Then
            Left = True
            Count = Count + 1
        End If
        ' Check Right
        If PosY < SizeY - 1 And Visited(PosX, PosY + 1) = False Then
            Right = True
            Count = Count + 1
        End If

        ' Decide on action to take
        If Count = 0 Then ' No path available, check for alternatives
            If AltPointer >= 0 Then
                ' Load last path that had other possible paths (NB. Could do with making smarter!)
                PosX = Floor(Alternate(AltPointer)/SizeX)
                PosY = Alternate(AltPointer) Mod SizeY
                AltPointer = AltPointer - 1
            Else
                ' No more paths exist, abort!
                Exit
            End If
        Else
            If Count > 1 Then ' If alternative paths exist, store position for later use if required
                AltPointer = AltPointer + 1
                Alternate(AltPointer) = PosX * PosY ' store position as X * Y
            End If

            If Pref <= 0 Then ' If vertical movement prefered
                ' Check if vertical travel in prefered direction is possible
                If Pref_X = -1 And Up Then
                    PosX = PosX - 1
                Else If Pref_X = 1 And Down Then
                    PosX = PosX + 1
                ' If preferred direction not available is it possible to move toward target horizontally
                Else If Pref_Y = -1 And Left Then
                    PosY = PosY - 1
                Else If Pref_Y = 1 And Right Then
                    PosY = PosY + 1
                ' Failing that go in which ever direction is free!
                Else If Up Or Down Or Left Or Right Then
                    If Up Then
                        PosX = PosX - 1
                    Else If Down Then
                        PosX = PosX + 1
                    Else If Left Then
                        PosY = PosY - 1
                    Else If Right Then
                        PosY = PosY + 1
                    End If
                End If
            Else ' If horizontal movement prefered
                ' Check if horizontal travel in prefered direction is possible
                If Pref_Y = -1 And Left Then
                    PosY = PosY - 1
                Else If Pref_Y = 1 And Right Then
                    PosY = PosY + 1
                ' If preferred direction not available is it possible to move toward target vertically
                Else If Pref_X = -1 And Up Then
                    PosX = PosX - 1
                Else If Pref_X = 1 And Down Then
                    PosX = PosX + 1
                ' Failing that go in which ever direction is free!
                Else If Up Or Down Or Left Or Right Then
                    If Up Then
                        PosX = PosX - 1
                    Else If Down Then
                        PosX = PosX + 1
                    Else If Left Then
                        PosY = PosY - 1
                    Else If Right Then
                        PosY = PosY + 1
                    End If
                End If
            End If
        End If
       
    Loop
End Sub

Sub Direction(Dist As Int) As Int
    If Dist > 0 Then
        Return 1
    Else If Dist < 0 Then
        Return -1
    Else
        Return 0
    End If
 

Attachments

  • Quiz_RC.zip
    8.3 KB · Views: 338
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
cimperia said:
OK, I have cleaned up the Algo. It looks pretty ugly and repetitive but I have found out that it was the only way to extract the max speed out of it. I used to populate an array with values (EAST, WEST ...) according to the decisions made and later on iterate it but it was taking too long.
Click to expand...
Excellent work ! Your code is very close to mine. On the first run, it got a better time than mine so I looked at the differences. I changed two things in my code: I replaced the two Abs() by conditions (I suggested this change in this thread but did not do it for my own code) and I can confirm that Abs is very slow, then I changed the way how the Found value is set (now I set it in the main loop as you do). I think that change does not make a difference, contrary to Abs, but it seemed to me more fair for a comparison. With these changes, my code regained the first place but congratulations anyway !!!
 
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
RandomCoder said:
Well here's my attempt which is no where near as neat or condensed as the recursive code you guys have produced. I thought there would be some gains storing the alternate routes and sensibly selecting from the list but it seems that the creation of the list and managing of the list just adds another bottleneck. And probably its got a lot to do with my implementation.
B4X: 
Galaxy S3
----- TOTAL -----
Sum algo DFS = 18.323 ms / Worst = 0.217 ms
Sum algo RandomCoder = 13.89 ms / Worst = 0.213 ms
** Activity (main) Pause, UserClosed = true **


Nexus 7 (2013)
----- TOTAL -----
Sum algo DFS = 6.592 ms / Worst = 0.072 ms
Sum algo RandomCoder = 5.518 ms / Worst = 0.085 ms
** Activity (main) Pause, UserClosed = true **

B4X: 
Sub PathFinder()
    'Initialisations
    For X = 0 To SizeX - 1
        For Y = 0 To SizeY - 1
            Visited(X, Y) = Blocked(X, Y)
        Next
    Next
    ' Alternative routes (stored as X * Y)
    Dim AltPointer As Int = -1
    Dim Alternate(100) As Int

    ' Current X, Y position in maze
    Dim PosX As Int = StartX
    Dim PosY As Int = StartY

    ' Loop until destination found or Exit if impassable
    Do Until PosX = DestX And PosY = DestY
        Dim Up, Down, Left, Right As Boolean ' Possible paths
        Dim X_Dist As Int ' Distance from current position to Dest in X
        Dim Y_Dist As Int ' Distance from current position to Dest in Y
     
        Dim Count As Int  = 0 ' Number of possible paths
        Dim Pref_X As Int = 0 ' -1=Up, 0=Center, +1=Down
        Dim Pref_Y As Int = 0 ' -1=Left, 0=Center, +1=Right
        Dim Pref As Int   = 0 ' -1=Vertical, 1=Horizontal

        ' Set current position as visited and reset count
        Visited(PosX, PosY) = True
        Count = 0
     
        ' Determine prefered direction
        X_Dist = DestX - PosX
        Y_Dist = DestY - PosY
        Pref_X = Direction(X_Dist) ' -1=Up, 0=Center, +1=Down
        Pref_Y = Direction(Y_Dist) ' -1=Left, 0=Center, +1=Right
 
        ' Horizontal or vertical preference (which is the furthest)
        If Abs(X_Dist) > Abs(Y_Dist) Then
            Pref = -1 ' Vertical movement preferable
        Else
            Pref = 1  ' Horizontal movement preferable
        End If
 
        ' Determine which paths are free
        ' Check Up
        If PosX > 0 And Visited(PosX - 1, PosY) = False Then
            Up = True
            Count = Count + 1
        End If
        ' Check Down
        If PosX < SizeX - 1 And Visited(PosX + 1, PosY) = False Then
            Down = True
            Count = Count + 1
        End If
        ' Check left
        If PosY > 0 And Visited(PosX, PosY - 1) = False Then
            Left = True
            Count = Count + 1
        End If
        ' Check Right
        If PosY < SizeY - 1 And Visited(PosX, PosY + 1) = False Then
            Right = True
            Count = Count + 1
        End If

        ' Decide on action to take
        If Count = 0 Then ' No path available, check for alternatives
            If AltPointer >= 0 Then
                ' Load last path that had other possible paths (NB. Could do with making smarter!)
                PosX = Floor(Alternate(AltPointer)/SizeX)
                PosY = Alternate(AltPointer) Mod SizeY
                AltPointer = AltPointer - 1
            Else
                ' No more paths exist, abort!
                Exit
            End If
        Else
            If Count > 1 Then ' If alternative paths exist, store position for later use if required
                AltPointer = AltPointer + 1
                Alternate(AltPointer) = PosX * PosY ' store position as X * Y
            End If

            If Pref <= 0 Then ' If vertical movement prefered
                ' Check if vertical travel in prefered direction is possible
                If Pref_X = -1 And Up Then
                    PosX = PosX - 1
                Else If Pref_X = 1 And Down Then
                    PosX = PosX + 1
                ' If preferred direction not available is it possible to move toward target horizontally
                Else If Pref_Y = -1 And Left Then
                    PosY = PosY - 1
                Else If Pref_Y = 1 And Right Then
                    PosY = PosY + 1
                ' Failing that go in which ever direction is free!
                Else If Up Or Down Or Left Or Right Then
                    If Up Then
                        PosX = PosX - 1
                    Else If Down Then
                        PosX = PosX + 1
                    Else If Left Then
                        PosY = PosY - 1
                    Else If Right Then
                        PosY = PosY + 1
                    End If
                End If
            Else ' If horizontal movement prefered
                ' Check if horizontal travel in prefered direction is possible
                If Pref_Y = -1 And Left Then
                    PosY = PosY - 1
                Else If Pref_Y = 1 And Right Then
                    PosY = PosY + 1
                ' If preferred direction not available is it possible to move toward target vertically
                Else If Pref_X = -1 And Up Then
                    PosX = PosX - 1
                Else If Pref_X = 1 And Down Then
                    PosX = PosX + 1
                ' Failing that go in which ever direction is free!
                Else If Up Or Down Or Left Or Right Then
                    If Up Then
                        PosX = PosX - 1
                    Else If Down Then
                        PosX = PosX + 1
                    Else If Left Then
                        PosY = PosY - 1
                    Else If Right Then
                        PosY = PosY + 1
                    End If
                End If
            End If
        End If
     
    Loop
End Sub

Sub Direction(Dist As Int) As Int
    If Dist > 0 Then
        Return 1
    Else If Dist < 0 Then
        Return -1
    Else
        Return 0
    End If
Click to expand...
I didn't look very closely at your code but there's a problem somewhere as the number of found paths is different from what is expected.
See these different benchmarks:
----- TOTAL -----
Sum algo DFS = 17.997 ms / Worst = 0.263 ms
Found=178
Sum algo FLM (simple) = 9.686 ms / Worst = 0.13 ms
Found=178
Sum algo FLM (advanced) = 7.256 ms / Worst = 0.116 ms
Found=178
Sum algo Cimperia's ZoomIn = 8.319 ms / Worst = 0.237 ms
Found=178
Sum algo RandomCoder's algo = 15.664 ms / Worst = 0.423 ms
Found=176

----- TOTAL -----
Sum algo DFS = 18.678 ms / Worst = 0.211 ms
Found=184
Sum algo FLM (simple) = 9.079 ms / Worst = 0.079 ms
Found=184
Sum algo FLM (advanced) = 6.93 ms / Worst = 0.097 ms
Found=184
Sum algo Cimperia's ZoomIn = 8.218 ms / Worst = 0.251 ms
Found=184
Sum algo RandomCoder's algo = 15.187 ms / Worst = 0.191 ms
Found=166

----- TOTAL -----
Sum algo DFS = 18.944 ms / Worst = 0.215 ms
Found=175
Sum algo FLM (simple) = 9.916 ms / Worst = 0.15 ms
Found=175
Sum algo FLM (advanced) = 7.483 ms / Worst = 0.163 ms
Found=175
Sum algo Cimperia's ZoomIn = 8.907 ms / Worst = 0.254 ms
Found=175
Sum algo RandomCoder's algo = 12.955 ms / Worst = 0.262 ms
Found=167
 
Last edited:
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
I'm on vacation and until September I will be far from my computer so I won't be able to compare or run anything. That's why I decided to convert my code to a library (alt+5) and to share the library. Anyone can do its own comparisons now. I will explain in September the two algorithms of this library (one of them is extremely simple) and I will publish the entire code of the class behind the library.
 

Attachments

  • QuizBenchmark+JavaLib.zip
    13.2 KB · Views: 318
Upvote 0
RandomCoder

RandomCoder

Well-Known Member
Licensed User
Longtime User
Informatix said:
I didn't look very closely at your code but there's a problem somewhere as the number of found paths is different from what is expected.
Click to expand...
Typical, I must have broken something with all the changes I've made. I'll see if I can work out what before you get back. Have a good vacation @Informatix
 
Upvote 0
S

sorex

Expert
Licensed User
Longtime User
amazing that all these if's would even lead to something faster than the dfs method knowing that the guessed decision might lead to a dead end.
 
Upvote 0
RandomCoder

RandomCoder

Well-Known Member
Licensed User
Longtime User
I've found the fault during my lunch break. It was the way I stored and recalled alternative routes. Originally I had two arrays one for X and one for Y but this required twice as much memory and seemed to add another slow down. therefore I combined X and Y into one value and stored this. but did so in a rush and without properly checking the result. I blame it on tiered eyes :D

This modification now gives the correct results.
B4X: 
' Decide on action to take
        If Count = 0 Then ' No path available, check for alternatives
            If AltPointer >= 0 Then
                ' Load last path that had other possible paths (NB. Could do with making smarter!)
                PosX = Floor(Alternate(AltPointer)/SizeX)
                PosY = Alternate(AltPointer) Mod SizeX
                AltPointer = AltPointer - 1
            Else
                ' No more paths exist, abort!
                Exit
            End If
        Else
            If Count > 1 Then ' If alternative paths exist, store position for later use if required
                AltPointer = AltPointer + 1
                Alternate(AltPointer) = PosX * SizeX + PosY ' store position as X & Y
            End If
........
.......

I'll continue playing to see if I can now make this more recursive, i.e. turn the Do Until into a subroutine.
 
Upvote 0
cimperia

cimperia

Active Member
Licensed User
Longtime User
Informatix said:
With these changes, my code regained the first place
Click to expand...

Champagne, my modified algo is the new king of the hill :) And no it was not a one off ;)- it's on every run!

EDIT: Added the Sub.
The improvement is nearly only due to replacing all Not(Blocked(,)) with If Blocked(,) = False. Simple change that has a dramatic effect. Obviously, if the basic DFS code was modified this way, its performance would improve as well.

B4X: 
Sum algo DFS  = 17.792 ms / Worst = 0.217ms (Found Time=13.479 | Not Found Time=4.314)
Found=175
Sum algo FLM (advanced)  = 8.047 ms / Worst = 0.131ms  (Found Time=4.031 | Not Found Time=4.015)
Found=175
Sum algo Cimperias ZoomIn  = 6.755 ms / Worst = 0.151ms  (Found Time=3.133 | Not Found Time=3.622)
Found=175

B4X: 
Sub ZoomIn (x As Int, y As Int) As Boolean 

   'Accept Case - we found the destination
   If x = DestX And y = DestY Then
     Visited(x, y) = True
     Return True
   End If
   
  'Reject Case - we hit a block|wall Or our path
  If Blocked(x, y) Or Visited(x, y) Then Return False 
  Visited(x, y) = True

       dx = DestX - x
       dy = DestY - y

       If dx < 0 Then dxa = -dx Else dxa = dx
       If dy < 0 Then dya = -dy Else dya = dy
       'version: 1 'i = x < 0 ? -x : x; -- version: 2 'i = (x ^ (x >> 31)) - (x >> 31);
     
       If (dxa > dya) Then ' Move along the X axis
         If dx > 0 Then     ' Try East first
   '         Order(0) = EAST
           If x < SizeX -1 And Blocked(x+1, y) = False Then
             If ZoomIn(x+1, y) Then Return True
           End If       
           If dy >= 0 Then
   '           Order(1) = SOUTH
             If y < SizeY - 1 And Blocked(x, y+1) = False Then
               If ZoomIn(x, y+1) Then Return True
             End If
   '           Order(2) = NORTH
             If y > 0 And Blocked(x, y-1) = False Then
               If ZoomIn(x, y-1) Then Return True
             End If             
           Else
   '           Order(1) = NORTH
             If Y > 0 And Blocked(x, y-1) = False Then
               If ZoomIn(x, y-1) Then Return True
             End If 
   '           Order(2) = SOUTH   
             If y < SizeY - 1 And Blocked(x, y+1) = False Then
               If ZoomIn(x, y+1) Then Return True
             End If
           End If
   '         Order(3) = WEST
           If x > 0 And Blocked(x-1, y) = False Then
             If ZoomIn(x-1, y) Then Return True
           End If 
         Else                ' Try West first
   '         Order(0) = WEST
           If x > 0 And Blocked(x-1, y) = False Then
             If ZoomIn(x-1, y) Then Return True
           End If         
           If dy >= 0 Then
   '           Order(1) = SOUTH
             If y < SizeY - 1 And Blocked(x, y+1) = False Then
               If ZoomIn(x, y+1) Then Return True
             End If
   '           Order(2) = NORTH
             If Y > 0 And Blocked(x, y-1) = False Then
               If ZoomIn(x, y-1) Then Return True
             End If             
           Else
   '           Order(1) = NORTH
             If Y > 0 And Blocked(x, y-1) = False Then
               If ZoomIn(x, y-1) Then Return True
             End If 
   '           Order(2) = SOUTH   
             If y < SizeY - 1 And Blocked(x, y+1) = False Then
               If ZoomIn(x, y+1) Then Return True
             End If
           End If
   '         Order(3) = EAST 
           If x < SizeX -1 And Blocked(x+1, y) = False Then
             If ZoomIn(x+1, y) Then Return True
           End If       
         End If   
       Else                ' Move along the Y axis
         If dy > 0 Then     ' Try South first 
   '         Order(0) = SOUTH
           If y < SizeY - 1 And Blocked(x, y+1) = False Then
             If ZoomIn(x, y+1) Then Return True
           End If
           If dx < 0 Then
   '           Order(1) = WEST
             If X > 0 And Blocked(x-1, y) = False Then
               If ZoomIn(x-1, y) Then Return True
             End If
   '           Order(2) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False Then
               If ZoomIn(x+1, y) Then Return True
             End If
           Else
   '           Order(1) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False Then
               If ZoomIn(x+1, y) Then Return True
             End If
   '           Order(2) = WEST     
             If X > 0 And Blocked(x-1, y) = False Then
               If ZoomIn(x-1, y) Then Return True
             End If 
           End If
   '         Order(3) = NORTH 
           If Y > 0 And Blocked(x, y-1) = False Then
             If ZoomIn(x, y-1) Then Return True
           End If     
         Else  ' Try North first
   '         Order(0) = NORTH
           If Y > 0 And Blocked(x, y-1) = False Then
             If ZoomIn(x, y-1) Then Return True
           End If       
           If dx < 0 Then
   '           Order(1) = WEST
             If X > 0 And Blocked(x-1, y) = False Then
               If ZoomIn(x-1, y) Then Return True
             End If
   '           Order(2) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False Then
               If ZoomIn(x+1, y) Then Return True
             End If
           Else
   '           Order(1) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False Then
               If ZoomIn(x+1, y) Then Return True
             End If
   '           Order(2) = WEST     
             If X > 0 And Blocked(x-1, y) = False Then
               If ZoomIn(x-1, y) Then Return True
             End If 
           End If
   '         Order(3) = SOUTH   
           If y < SizeY - 1 And Blocked(x, y+1) = False Then
             If ZoomIn(x, y+1) Then Return True
           End If   
         End If 
       End If
     
       'Deadend - this location can't be part of path
       Return False
End Sub
 
Last edited:
Upvote 0
cimperia

cimperia

Active Member
Licensed User
Longtime User
I think I have managed to squeeze a tiny bit more performance with another small modification. In any case I find the code easier to read.

I don't think I can go any further than that - as I have run out of ideas.

Results
B4X: 
----- TOTAL -----
Sum algo DFS  = 15.67 ms / Worst = 0.194ms  (Found Time=12.877 | Not Found Time=2.793)
Found=174
Sum algo FLM (advanced)  = 6.474 ms / Worst = 0.084ms  (Found Time=3.593 | Not Found Time=2.881)
Found=174
Sum algo Cimperias ZoomIn  = 4.85 ms / Worst = 0.148ms  (Found Time=2.408 | Not Found Time=2.442)
Found=174
Sum algo Cimperias ZoomIn2  = 4.737 ms / Worst = 0.141ms  (Found Time=2.356 | Not Found Time=2.382)
Found=174

----- TOTAL -----
Sum algo DFS  = 16.408 ms / Worst = 0.19ms  (Found Time=13.209 | Not Found Time=3.199)
Found=183
Sum algo FLM (advanced)  = 6.864 ms / Worst = 0.085ms  (Found Time=3.962 | Not Found Time=2.902)
Found=183
Sum algo Cimperias ZoomIn  = 5.756 ms / Worst = 0.162ms  (Found Time=2.923 | Not Found Time=2.833)
Found=183
Sum algo Cimperias ZoomIn2  = 5.646 ms / Worst = 0.162ms  (Found Time=2.868 | Not Found Time=2.779)
Found=183

----- TOTAL -----
Sum algo DFS  = 15.343 ms / Worst = 0.193ms (Found Time=11.384 | Not Found Time=3.959)
Found=170
Sum algo FLM (advanced)  = 7.038 ms / Worst = 0.087ms  (Found Time=3.569 | Not Found Time=3.47)
Found=170
Sum algo Cimperias ZoomIn  = 5.947 ms / Worst = 0.145ms  (Found Time=2.524 | Not Found Time=3.422)
Found=170
Sum algo Cimperias ZoomIn2  = 5.836 ms / Worst = 0.142ms  (Found Time=2.487 | Not Found Time=3.349)
Found=170

----- TOTAL -----
Sum algo DFS  = 15.588 ms / Worst = 0.178ms (Found Time=12.253 | Not Found Time=3.335)
Found=180
Sum algo FLM (advanced)  = 6.874 ms / Worst = 0.082ms  (Found Time=3.682 | Not Found Time=3.191)
Found=180
Sum algo Cimperias ZoomIn  = 5.35 ms / Worst = 0.131ms  (Found Time=2.413 | Not Found Time=2.937)
Found=180
Sum algo Cimperias ZoomIn2  = 5.322 ms / Worst = 0.131ms  (Found Time=2.405 | Not Found Time=2.917)
Found=180

Sub
B4X: 
Sub ZoomIn2 (x As Int, y As Int) As Boolean    
'     counter = counter + 1

       'Accept Case - we found the Destination
       If x = DestX And y = DestY Then
         Visited(x, y) = True
         Return True
       End If

       'Reject Case - we hit a block|wall Or our path 
       If Blocked(x, y) Or Visited(x, y) Then Return False  
       Visited(x, y) = True

       dx = DestX - x
       dy = DestY - y

       If dx < 0 Then dxa = -dx Else dxa = dx
       If dy < 0 Then dya = -dy Else dya = dy
       'version: 1 'i = x < 0 ? -x : x; -- version: 2 'i = (x ^ (x >> 31)) - (x >> 31);
      
       If (dxa > dya) Then ' Move along the X axis
         If dx > 0 Then     ' Try East first
   '         Order(0) = EAST
           If x < SizeX -1 And Blocked(x+1, y) = False And ZoomIn2(x+1, y) Then Return True      
           If dy >= 0 Then
   '           Order(1) = SOUTH
             If y < SizeY - 1 And Blocked(x, y+1) = False And ZoomIn2(x, y+1) Then Return True
   '           Order(2) = NORTH
             If y > 0 And Blocked(x, y-1) = False And ZoomIn2(x, y-1) Then Return True            
           Else
   '           Order(1) = NORTH
             If Y > 0 And Blocked(x, y-1) = False And ZoomIn2(x, y-1) Then Return True  
   '           Order(2) = SOUTH    
             If y < SizeY - 1 And Blocked(x, y+1) = False And ZoomIn2(x, y+1) Then Return True
           End If
   '         Order(3) = WEST
           If x > 0 And Blocked(x-1, y) = False And ZoomIn2(x-1, y) Then Return True
         Else                ' Try West first
   '         Order(0) = WEST
           If x > 0 And Blocked(x-1, y) = False And ZoomIn2(x-1, y) Then Return True          
           If dy >= 0 Then
   '           Order(1) = SOUTH
             If y < SizeY - 1 And Blocked(x, y+1) = False And ZoomIn2(x, y+1) Then Return True
   '           Order(2) = NORTH
             If Y > 0 And Blocked(x, y-1) = False And ZoomIn2(x, y-1) Then Return True            
           Else
   '           Order(1) = NORTH
             If Y > 0 And Blocked(x, y-1) = False And ZoomIn2(x, y-1) Then Return True
   '           Order(2) = SOUTH    
             If y < SizeY - 1 And Blocked(x, y+1) = False And ZoomIn2(x, y+1) Then Return True
           End If
   '         Order(3) = EAST  
           If x < SizeX -1 And Blocked(x+1, y) = False And ZoomIn2(x+1, y) Then Return True      
         End If    
       Else                ' Move along the Y axis
         If dy > 0 Then     ' Try South first  
   '         Order(0) = SOUTH
           If y < SizeY - 1 And Blocked(x, y+1) = False And ZoomIn2(x, y+1) Then Return True
           If dx < 0 Then
   '           Order(1) = WEST
             If X > 0 And Blocked(x-1, y) = False And ZoomIn2(x-1, y) Then Return True
   '           Order(2) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False And ZoomIn2(x+1, y) Then Return True
           Else
   '           Order(1) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False And ZoomIn2(x+1, y) Then Return True
   '           Order(2) = WEST      
             If X > 0 And Blocked(x-1, y) = False And ZoomIn2(x-1, y) Then Return True
           End If
   '         Order(3) = NORTH  
           If Y > 0 And Blocked(x, y-1) = False And ZoomIn2(x, y-1) Then Return True      
         Else  ' Try North first
   '         Order(0) = NORTH
           If Y > 0 And Blocked(x, y-1) = False And ZoomIn2(x, y-1) Then Return True      
           If dx < 0 Then
   '           Order(1) = WEST
             If X > 0 And Blocked(x-1, y) = False And ZoomIn2(x-1, y) Then Return True
   '           Order(2) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False And ZoomIn2(x+1, y) Then Return True
           Else
   '           Order(1) = EAST
             If x < SizeX -1 And Blocked(x+1, y) = False And ZoomIn2(x+1, y) Then Return True
   '           Order(2) = WEST      
             If X > 0 And Blocked(x-1, y) = False And ZoomIn2(x-1, y) Then Return True  
           End If
   '         Order(3) = SOUTH    
           If y < SizeY - 1 And Blocked(x, y+1) = False And ZoomIn2(x, y+1) Then Return True    
         End If  
       End If
      
       'Deadend - this location can't be part of path
       Return False
End Sub
 
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
cimperia said:
Champagne, my modified algo is the new king of the hill :)
Click to expand...
Congratulations !!!
I have also an idea for my code but I'll be able to test it only when I'm back. My code uses an array of bytes because it's very convenient for my game, but for the quiz, I have not the same constraints and could gain some speed by using the Blocked and Visited arrays as is.
 
Upvote 0
cimperia

cimperia

Active Member
Licensed User
Longtime User
Informatix said:
Congratulations !!!
Click to expand...

Thanks but I don't think I'll stay on my perch for very long ;)

Informatix said:
I have also an idea for my code but I'll be able to test it only when I'm back. My code uses an array of bytes because it's very convenient for my game, but for the quiz, I have not the same constraints and could gain some speed by using the Blocked and Visited arrays as is.
Click to expand...

I am looking forward to that...

I gave up on some early solutions as I had to populate arrays and it was really time consuming. If the quiz were “Is there a path, Yes or No?” with no requirement of storing the path, then I have a solution which beats my best efforts to date: it uses my algo ZoomIn but does away with the Visited array as it is not used and instead sets Blocked to True wherever Visited(x,y) = True was used. In other words the original array gets overwritten: the fewer checks, the better performance. But, as the benchmark relies on testing the same array multiple times, I have to repopulate the array afresh at every iteration. Even with this handicap, it comes second in the table of results given below. Its name is ZoomIn2 in the results given below which are typical of the timings I usually get on my mobile.

OK:

Some further results. I have modified DFS so as to use Blocked(x,y) = False instead of Not(Blocked(x,y)) and named it DFS2.

As expected DFS2 is now much faster than DFS and the time gain of FLM and ZoomIn does not look so impressive anymore.

It's also obvious that DFS2's Not Found Time will be extremely difficult to emulate, as it is a given that the number of visited cells, when there is no path, will be the same by the algos presented so far. DFS2, not having to make any "decision", is bound to be faster.

Basically, FLM and ZoomIn will usually beat DFS2 when a path exists, but if the likelihood of finding a path decreases then DFS2 will win on the long run.

In your benchmark out of 300 mazes, there is always a majority of them where a path exists with an average split of 170/130. This is disadvantageous for DFS.

When I tried to improve my own algo (ZoomIn), I was trying to reduce the Not Found Time, because, when a Path is available, my original algo is very competitive but dreadful when no path exists. What I noticed, and is still the case, is that FLM is very performant when there is No Path. What bugs me as well is that FLM's Worst time is always inferior to ZoomIn's. I am very curious to find out why, but it'll have to wait...

B4X: 
----- TOTAL -----
Sum algo DFS..................= 15.553 ms / Worst = 0.177ms  (Found Time=11.7 | Not Found Time=3.854)
Found=168
Sum algo DFS2................ =  9.914 ms / Worst = 0.117ms  (Found Time=7.26 | Not Found Time=2.655)

Sum algo FLM (advanced)...... =  7.149 ms / Worst = 0.136ms  (Found Time=3.427 | Not Found Time=3.722)

Sum algo Cimperias ZoomIn.....=  5.708 ms / Worst = 0.15ms  (Found Time=2.268 | Not Found Time=3.44)

Sum algo Cimperias ZoomIn2....=  6.321 ms / Worst = 0.146ms  (Found Time=2.922 | Not Found Time=3.399)
 
Last edited:
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
cimperia said:
Thanks but I don't think I'll stay on my perch for very long ;)



I am looking forward to that...

I gave up on some early solutions as I had to populate arrays and it was really time consuming. If the quiz were “Is there a path, Yes or No?” with no requirement of storing the path, then I have a solution which beats my best efforts to date: it uses my algo ZoomIn but does away with the Visited array as it is not used and instead sets Blocked to True wherever Visited(x,y) = True was used. In other words the original array gets overwritten: the fewer checks, the better performance. But, as the benchmark relies on testing the same array multiple times, I have to repopulate the array afresh at every iteration. Even with this handicap, it comes second in the table of results given below. Its name is ZoomIn2 in the results given below which are typical of the timings I usually get on my mobile.

OK:

Some further results. I have modified DFS so as to use Blocked(x,y) = False instead of Not(Blocked(x,y)) and named it DFS2.

As expected DFS2 is now much faster than DFS and the time gain of FLM and ZoomIn does not look so impressive anymore.

It's also obvious that DFS2's Not Found Time will be extremely difficult to emulate, as it is a given that the number of visited cells, when there is no path, will be the same by the algos presented so far. DFS2, not having to make any "decision", is bound to be faster.

Basically, FLM and ZoomIn will usually beat DFS2 when a path exists, but if the likelihood of finding a path decreases then DFS2 will win on the long run.

In your benchmark out of 300 mazes, there is always a majority of them where a path exists with an average split of 170/130. This is disadvantageous for DFS.

When I tried to improve my own algo (ZoomIn), I was trying to reduce the Not Found Time, because, when a Path is available, my original algo is very competitive but dreadful when no path exists. What I noticed, and is still the case, is that FLM is very performant when there is No Path. What bugs me as well is that FLM's Worst time is always inferior to ZoomIn's. I am very curious to find out why, but it'll have to wait...

B4X: 
----- TOTAL -----
Sum algo DFS..................= 15.553 ms / Worst = 0.177ms  (Found Time=11.7 | Not Found Time=3.854)
Found=168
Sum algo DFS2................ =  9.914 ms / Worst = 0.117ms  (Found Time=7.26 | Not Found Time=2.655)

Sum algo FLM (advanced)...... =  7.149 ms / Worst = 0.136ms  (Found Time=3.427 | Not Found Time=3.722)

Sum algo Cimperias ZoomIn.....=  5.708 ms / Worst = 0.15ms  (Found Time=2.268 | Not Found Time=3.44)

Sum algo Cimperias ZoomIn2....=  6.321 ms / Worst = 0.146ms  (Found Time=2.922 | Not Found Time=3.399)
Click to expand...
I'm back and I'm afraid that you lost your crown... :) Using only the Blocked and Visited arrays, and not the array of bytes needed for my game, is a great improvement.
I will publish my tutorial tomorrow.
 
Upvote 0
cimperia

cimperia

Active Member
Licensed User
Longtime User
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
Here's the class code and the generated library that I will explain tomorrow. I made a variant of my code using a single-dimensional array. The result is almost the same despite the added computations:
----- TOTAL -----
Sum algo DFS = 10.88 ms / Worst = 0.179 ms
Found=170
Sum algo FLM (simple) = 8.03 ms / Worst = 0.139 ms
Found=170
Sum algo FLM (advanced MDA) = 5.282 ms / Worst = 0.166 ms
Found=170
Sum algo FLM (advanced SDA) = 5.323 ms / Worst = 0.197 ms
Found=170
Sum algo Cimperia's ZoomIn2 = 6.781 ms / Worst = 0.214 ms
Found=170

----- TOTAL -----
Sum algo DFS = 11.496 ms / Worst = 0.117 ms
Found=176
Sum algo FLM (simple) = 8.409 ms / Worst = 0.093 ms
Found=176
Sum algo FLM (advanced MDA) = 5.001 ms / Worst = 0.092 ms
Found=176
Sum algo FLM (advanced SDA) = 5.073 ms / Worst = 0.1 ms
Found=176
Sum algo Cimperia's ZoomIn2 = 6.462 ms / Worst = 0.15 ms
Found=176
 

Attachments

  • Quiz_with_lib.zip
    16.2 KB · Views: 330
Upvote 0
cimperia

cimperia

Active Member
Licensed User
Longtime User
I had a go at tuning my own algo so as to attain the same level of performance as Informatix's. I have modified the code so that is uses the changes that I judge significant in Informatix's code, ie the use of local vars, the look-ahead check against Visited(,) and some pre-computation for the array coordinates. Additionally I have added a tweak here or there.

At this point, it's more a collective exercise in trying to squeeze a tiny bit more performance out of the algo - as Informatix's algo incorporates my own enhancements - than a "competition".

Here are the results on my low spec phone. I shall run the code on a much faster device later on... I have modified the code main loop so that it logs only each run's cumulative results and so that it runs 10 times in a row (takes a few minutes to run). My implementation seems to have an edge, however as the differences are so small, I am not sure whether they are significant.

B4X: 
** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
----- TOTAL -----
Sum algo DFS = 12.128 ms / Worst = 0.211 ms
  Found=169
Sum algo FLM (simple) = 9.59 ms / Worst = 0.167 ms
  Found=169
Sum algo FLM (advanced MDA) = 6.239 ms / Worst = 0.222 ms
  Found=169
Sum algo FLM (advanced SDA) = 6.182 ms / Worst = 0.256 ms
  Found=169
Sum algo Cimperia's ZoomIn2 = 5.99 ms / Worst = 0.191 ms
  Found=169
----- TOTAL -----
Sum algo DFS = 13.594 ms / Worst = 0.226 ms
  Found=178
Sum algo FLM (simple) = 9.336 ms / Worst = 0.125 ms
  Found=178
Sum algo FLM (advanced MDA) = 6.031 ms / Worst = 0.174 ms
  Found=178
Sum algo FLM (advanced SDA) = 5.974 ms / Worst = 0.148 ms
  Found=178
Sum algo Cimperia's ZoomIn2 = 5.727 ms / Worst = 0.152 ms
  Found=178
----- TOTAL -----
Sum algo DFS = 10.771 ms / Worst = 0.206 ms
  Found=174
Sum algo FLM (simple) = 7.64 ms / Worst = 0.189 ms
  Found=174
Sum algo FLM (advanced MDA) = 5.168 ms / Worst = 0.115 ms
  Found=174
Sum algo FLM (advanced SDA) = 5.28 ms / Worst = 0.137 ms
  Found=174
Sum algo Cimperia's ZoomIn2 = 5.141 ms / Worst = 0.157 ms
  Found=174
----- TOTAL -----
Sum algo DFS = 9.773 ms / Worst = 0.103 ms
  Found=162
Sum algo FLM (simple) = 7.451 ms / Worst = 0.101 ms
  Found=162
Sum algo FLM (advanced MDA) = 4.261 ms / Worst = 0.101 ms
  Found=162
Sum algo FLM (advanced SDA) = 4.193 ms / Worst = 0.109 ms
  Found=162
Sum algo Cimperia's ZoomIn2 = 4.053 ms / Worst = 0.095 ms
  Found=162
----- TOTAL -----
Sum algo DFS = 10.403 ms / Worst = 0.188 ms
  Found=173
Sum algo FLM (simple) = 7.286 ms / Worst = 0.085 ms
  Found=173
Sum algo FLM (advanced MDA) = 4.81 ms / Worst = 0.138 ms
  Found=173
Sum algo FLM (advanced SDA) = 4.755 ms / Worst = 0.122 ms
  Found=173
Sum algo Cimperia's ZoomIn2 = 4.617 ms / Worst = 0.1 ms
  Found=173
----- TOTAL -----
Sum algo DFS = 10.212 ms / Worst = 0.11 ms
  Found=165
Sum algo FLM (simple) = 6.911 ms / Worst = 0.081 ms
  Found=165
Sum algo FLM (advanced MDA) = 4.657 ms / Worst = 0.089 ms
  Found=165
Sum algo FLM (advanced SDA) = 4.575 ms / Worst = 0.096 ms
  Found=165
Sum algo Cimperia's ZoomIn2 = 4.449 ms / Worst = 0.088 ms
  Found=165
----- TOTAL -----
Sum algo DFS = 9.92 ms / Worst = 0.127 ms
  Found=177
Sum algo FLM (simple) = 6.785 ms / Worst = 0.095 ms
  Found=177
Sum algo FLM (advanced MDA) = 4.491 ms / Worst = 0.082 ms
  Found=177
Sum algo FLM (advanced SDA) = 4.466 ms / Worst = 0.089 ms
  Found=177
Sum algo Cimperia's ZoomIn2 = 4.231 ms / Worst = 0.093 ms
  Found=177
----- TOTAL -----
Sum algo DFS = 9.675 ms / Worst = 0.111 ms
  Found=165
Sum algo FLM (simple) = 7.155 ms / Worst = 0.087 ms
  Found=165
Sum algo FLM (advanced MDA) = 4.813 ms / Worst = 0.096 ms
  Found=165
Sum algo FLM (advanced SDA) = 4.771 ms / Worst = 0.099 ms
  Found=165
Sum algo Cimperia's ZoomIn2 = 4.605 ms / Worst = 0.092 ms
  Found=165
----- TOTAL -----
Sum algo DFS = 9.899 ms / Worst = 0.104 ms
  Found=179
Sum algo FLM (simple) = 6.978 ms / Worst = 0.082 ms
  Found=179
Sum algo FLM (advanced MDA) = 4.143 ms / Worst = 0.086 ms
  Found=179
Sum algo FLM (advanced SDA) = 4.06 ms / Worst = 0.091 ms
  Found=179
Sum algo Cimperia's ZoomIn2 = 4.03 ms / Worst = 0.081 ms
  Found=179
----- TOTAL -----
Sum algo DFS = 9.304 ms / Worst = 0.108 ms
  Found=168
Sum algo FLM (simple) = 6.793 ms / Worst = 0.083 ms
  Found=168
Sum algo FLM (advanced MDA) = 4.353 ms / Worst = 0.097 ms
  Found=168
Sum algo FLM (advanced SDA) = 4.283 ms / Worst = 0.103 ms
  Found=168
Sum algo Cimperia's ZoomIn2 = 4.116 ms / Worst = 0.094 ms
  Found=168
** Activity (main) Pause, UserClosed = true **
 
Last edited:
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
While writing my tutorial I realized there was a bias in the benchmark (not all relative positions were tested) and that my SDA code was not fully optimized. I fixed that and the new SDA algo proves to be faster, with a significant improvement:
Sum algo SolveMaze_FLMAlgo = 10.097 ms / Worst = 0.149 ms
Found=369
Sum algo SolveMaze_FLMAlgo_SDA = 8.365 ms / Worst = 0.089 ms
Found=369
---
Sum algo SolveMaze_FLMAlgo = 10.277 ms / Worst = 0.12 ms
Found=358
Sum algo SolveMaze_FLMAlgo_SDA = 8.617 ms / Worst = 0.095 ms
Found=358

I will update the tutorial today or tomorrow.
 
Upvote 0
cimperia

cimperia

Active Member
Licensed User
Longtime User
Wow, great.

I actually thought that using a Single Dimensional Array would be quicker, but when I ran my tests on my early implementations, the results were disappointing - as I mentioned it in one of my previous posts.

I forgot all about it afterwards.

I have a question. In your game, does the array flmBlocked, or its equivalent, gets repopulated anew and so it is possible to overwrite it? If it is the case, then you can do without Visited(,) and the algo will run between 20 and 40 % faster on my mobile.

Edit: Actually, reviewing the results I posted here, the implementation was very promising, I simply forgot about it ;)
 
Last edited:
Upvote 0
Informatix

Informatix

Expert
Licensed User
Longtime User
cimperia said:
Wow, great.

I actually thought that using a Single Dimensional Array would be quicker, but when I ran my tests on my early implementations, the results were disappointing - as I mentioned it in one of my previous posts.

I forgot all about it afterwards.

I have a question. In your game, does the array flmBlocked, or its equivalent, gets repopulated anew and so it is possible to overwrite it? If it is the case, then you can do without Visited(,) and the algo will run between 20 and 40 % faster on my mobile.
Click to expand...
In my game, I create an array of bytes each time I need to find an alternate path. It's the only array used by the algorithm. I cannot use an existing array because my obstacles are stored in an array with a different coordinate system (I use three different layers for navigation). I have to convert all positions in the selected area and store a byte to indicate the presence of an obstacle. The byte value can also be set to indicate that the cell was visited so only one array is required. The use of this array is not for performance, just for convenience. The overhead of its creation counterbalances probably the benefit of having a single array.
 
Upvote 0
cimperia

cimperia

Active Member
Licensed User
Longtime User
Informatix said:
In my game, I create an array of bytes each time I need to find an alternate path. It's the only array used by the algorithm. I cannot use an existing array because my obstacles are stored in an array with a different coordinate system (I use three different layers for navigation). I have to convert all positions in the selected area and store a byte to indicate the presence of an obstacle. The byte value can also be set to indicate that the cell was visited so only one array is required. The use of this array is not for performance, just for convenience. The overhead of its creation counterbalances probably the benefit of having a single array.
Click to expand...

I had some time to ponder on this today...

OK, I understand. In that case I think it would be good to test different type of arrays. I've always believed that in Java arrays of Int were generally more performant. I put this belief to the test.

To even things out, as I did not want to penalize any algo by array copying/converting, in the Initialize method, I've set up master arrays of Int and Byte so that my functions can make a copy from them on every iteration, instead of copying from Blocked(,) as the latter would be very costly. The FLM SDA algo's code is the one posted in the tutorial.

B4X: 
Public Sub Initialize(....)
  ...
  Dim i As Int
   For Y = 0 To flmSizeY - 1
     For X = 0 To flmSizeX - 1
         If flmBlocked(X, Y) Then i = 1 Else i = 0
         BlockedInt( (flmSizeX * Y) + X ) = i
         BlockedByte( (flmSizeX * Y) + X ) = i   'implicit casting
     Next
   Next

The results are interesting. On a fast device Arrays of Int have definitely the edge, on a slow device not so much, but there's no performance penalty (just some minor memory penalty (X4) if the array is small, as it is the case in a 20X20 grid).

10 runs back to back:
Fast device with lots of memory
B4X: 
** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
----- TOTAL -----
Sum algo DFS = 7.202 ms / Worst = 0.109 ms
  Found=175
Sum algo FLM (advanced SDA) = 2.653 ms / Worst = 0.109 ms
  Found=175
Sum algo ......ZoomInSDAInt = 2.303 ms / Worst = 0.092 ms
  Found=175
Sum algo .....ZoomInSDAByte = 2.883 ms / Worst = 0.094 ms
  Found=175
----- TOTAL -----
Sum algo DFS = 5.338 ms / Worst = 0.059 ms
  Found=178
Sum algo FLM (advanced SDA) = 1.687 ms / Worst = 0.045 ms
  Found=178
Sum algo ......ZoomInSDAInt = 1.356 ms / Worst = 0.027 ms
  Found=178
Sum algo .....ZoomInSDAByte = 1.868 ms / Worst = 0.028 ms
  Found=178
----- TOTAL -----
Sum algo DFS = 4.838 ms / Worst = 0.057 ms
  Found=173
Sum algo FLM (advanced SDA) = 1.614 ms / Worst = 0.042 ms
  Found=173
Sum algo ......ZoomInSDAInt = 1.29 ms / Worst = 0.026 ms
  Found=173
Sum algo .....ZoomInSDAByte = 1.81 ms / Worst = 0.027 ms
  Found=173
----- TOTAL -----
Sum algo DFS = 5.55 ms / Worst = 0.059 ms
  Found=182
Sum algo FLM (advanced SDA) = 1.636 ms / Worst = 0.04 ms
  Found=182
Sum algo ......ZoomInSDAInt = 1.321 ms / Worst = 0.024 ms
  Found=182
Sum algo .....ZoomInSDAByte = 1.867 ms / Worst = 0.026 ms
  Found=182
----- TOTAL -----
Sum algo DFS = 5.197 ms / Worst = 0.054 ms
  Found=178
Sum algo FLM (advanced SDA) = 1.659 ms / Worst = 0.038 ms
  Found=178
Sum algo ......ZoomInSDAInt = 1.307 ms / Worst = 0.022 ms
  Found=178
Sum algo .....ZoomInSDAByte = 1.817 ms / Worst = 0.024 ms
  Found=178
----- TOTAL -----
Sum algo DFS = 5.083 ms / Worst = 0.056 ms
  Found=176
Sum algo FLM (advanced SDA) = 1.683 ms / Worst = 0.035 ms
  Found=176
Sum algo ......ZoomInSDAInt = 1.347 ms / Worst = 0.021 ms
  Found=176
Sum algo .....ZoomInSDAByte = 1.857 ms / Worst = 0.023 ms
  Found=176
----- TOTAL -----
Sum algo DFS = 5.275 ms / Worst = 0.058 ms
  Found=176
Sum algo FLM (advanced SDA) = 1.519 ms / Worst = 0.043 ms
  Found=176
Sum algo ......ZoomInSDAInt = 1.248 ms / Worst = 0.025 ms
  Found=176
Sum algo .....ZoomInSDAByte = 1.763 ms / Worst = 0.026 ms
  Found=176
----- TOTAL -----
Sum algo DFS = 5.301 ms / Worst = 0.055 ms
  Found=172
Sum algo FLM (advanced SDA) = 1.732 ms / Worst = 0.042 ms
  Found=172
Sum algo ......ZoomInSDAInt = 1.374 ms / Worst = 0.025 ms
  Found=172
Sum algo .....ZoomInSDAByte = 1.867 ms / Worst = 0.027 ms
  Found=172
----- TOTAL -----
Sum algo DFS = 5.03 ms / Worst = 0.05 ms
  Found=172
Sum algo FLM (advanced SDA) = 1.537 ms / Worst = 0.038 ms
  Found=172
Sum algo ......ZoomInSDAInt = 1.262 ms / Worst = 0.022 ms
  Found=172
Sum algo .....ZoomInSDAByte = 1.763 ms / Worst = 0.023 ms
  Found=172
----- TOTAL -----
Sum algo DFS = 5.462 ms / Worst = 0.057 ms
  Found=167
Sum algo FLM (advanced SDA) = 1.624 ms / Worst = 0.03 ms
  Found=167
Sum algo ......ZoomInSDAInt = 1.317 ms / Worst = 0.021 ms
  Found=167
Sum algo .....ZoomInSDAByte = 1.823 ms / Worst = 0.02 ms
  Found=167
** Activity (main) Pause, UserClosed = true **


Slow device with little memory
B4X: 
** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
----- TOTAL -----
Sum algo DFS = 14.118 ms / Worst = 0.219 ms
  Found=178
Sum algo FLM (advanced SDA) = 5.268 ms / Worst = 0.198 ms
  Found=178
Sum algo ......ZoomInSDAInt = 5.124 ms / Worst = 0.143 ms
  Found=178
Sum algo .....ZoomInSDAByte = 5.077 ms / Worst = 0.167 ms
  Found=178
----- TOTAL -----
Sum algo DFS = 9.683 ms / Worst = 0.112 ms
  Found=173
Sum algo FLM (advanced SDA) = 3.424 ms / Worst = 0.102 ms
  Found=173
Sum algo ......ZoomInSDAInt = 3.527 ms / Worst = 0.077 ms
  Found=173
Sum algo .....ZoomInSDAByte = 3.502 ms / Worst = 0.088 ms
  Found=173
----- TOTAL -----
Sum algo DFS = 9.637 ms / Worst = 0.107 ms
  Found=171
Sum algo FLM (advanced SDA) = 3.504 ms / Worst = 0.085 ms
  Found=171
Sum algo ......ZoomInSDAInt = 3.458 ms / Worst = 0.071 ms
  Found=171
Sum algo .....ZoomInSDAByte = 3.444 ms / Worst = 0.068 ms
  Found=171
----- TOTAL -----
Sum algo DFS = 10.11 ms / Worst = 0.108 ms
  Found=175
Sum algo FLM (advanced SDA) = 3.713 ms / Worst = 0.088 ms
  Found=175
Sum algo ......ZoomInSDAInt = 3.641 ms / Worst = 0.067 ms
  Found=175
Sum algo .....ZoomInSDAByte = 3.65 ms / Worst = 0.067 ms
  Found=175
----- TOTAL -----
Sum algo DFS = 10.353 ms / Worst = 0.108 ms
  Found=169
Sum algo FLM (advanced SDA) = 3.764 ms / Worst = 0.089 ms
  Found=169
Sum algo ......ZoomInSDAInt = 3.655 ms / Worst = 0.068 ms
  Found=169
Sum algo .....ZoomInSDAByte = 3.698 ms / Worst = 0.079 ms
  Found=169
----- TOTAL -----
Sum algo DFS = 9.994 ms / Worst = 0.107 ms
  Found=168
Sum algo FLM (advanced SDA) = 3.872 ms / Worst = 0.1 ms
  Found=168
Sum algo ......ZoomInSDAInt = 3.726 ms / Worst = 0.075 ms
  Found=168
Sum algo .....ZoomInSDAByte = 3.75 ms / Worst = 0.075 ms
  Found=168
----- TOTAL -----
Sum algo DFS = 9.412 ms / Worst = 0.107 ms
  Found=175
Sum algo FLM (advanced SDA) = 3.455 ms / Worst = 0.062 ms
  Found=175
Sum algo ......ZoomInSDAInt = 3.412 ms / Worst = 0.048 ms
  Found=175
Sum algo .....ZoomInSDAByte = 3.42 ms / Worst = 0.048 ms
  Found=175
----- TOTAL -----
Sum algo DFS = 9.45 ms / Worst = 0.104 ms
  Found=185
Sum algo FLM (advanced SDA) = 3.225 ms / Worst = 0.076 ms
  Found=185
Sum algo ......ZoomInSDAInt = 3.302 ms / Worst = 0.057 ms
  Found=185
Sum algo .....ZoomInSDAByte = 3.319 ms / Worst = 0.056 ms
  Found=185
----- TOTAL -----
Sum algo DFS = 10.252 ms / Worst = 0.108 ms
  Found=189
Sum algo FLM (advanced SDA) = 3.297 ms / Worst = 0.085 ms
  Found=189
Sum algo ......ZoomInSDAInt = 3.296 ms / Worst = 0.065 ms
  Found=189
Sum algo .....ZoomInSDAByte = 3.305 ms / Worst = 0.064 ms
  Found=189
----- TOTAL -----
Sum algo DFS = 9.717 ms / Worst = 0.11 ms
  Found=167
Sum algo FLM (advanced SDA) = 3.664 ms / Worst = 0.096 ms
  Found=167
Sum algo ......ZoomInSDAInt = 3.544 ms / Worst = 0.073 ms
  Found=167
Sum algo .....ZoomInSDAByte = 3.569 ms / Worst = 0.072 ms
  Found=167
** Activity (main) Pause, UserClosed = true **
 
Last edited:
Upvote 0
You must log in or register to reply here.

Similar Threads

William Lancee
  • Article
B4J Code Snippet [B4X] Dijkstra's Algorithm for Finding the Shortest Path Through a Connected Graph.
Replies
18
Views
3K
PABLO2013
PABLO2013
max123
  • Article
Android Code Snippet [algorithm] First post. Map a value from one range to another range. The simple way.
Replies
0
Views
3K
max123
max123
peacemaker
  • Question
Android Question trace routing code
Replies
0
Views
699
peacemaker
peacemaker
NeoTechni
  • Question
Android Question Is there a way to extract points from a path?
Replies
4
Views
882
NeoTechni
NeoTechni
NeoTechni
  • Question
Android Question How to test if a point is inside a path?
Replies
4
Views
1K
Erel
Erel
Top