Hello everyone,

I found a pretty good maze solver. If you click this link : https://scratch.mit.edu/projects/147094127/#editor you will get to the project of Harakou.
Im really interested in this algorithm but the problem is that I dont understand the script of the solver sprite.
It would be really nice if someone could help me to understand the script step by step.
I already know the algorithm. The project uses the depth-first algorithm but like I said I dont really understand the script of the solver sprite.

Thank you for your help
Generator98

What are you having trouble with? DFS_R is clearly doing a standard recursive search of every available next step.

gtoal wrote:

What are you having trouble with? DFS_R is clearly doing a standard recursive search of every available next step.

I dont understand the calculations in map edges and DFS_R, next to this I dont understand the block with the genMatrix.

I know maybe this algorithm is very basic but I want to understand it, I'm sorry if I'm not that fast.

Thank you for your help
Generator98

Hello?

You should possibly ask the creator of the project what it means because it's hard to understand code that isn't your own. That's why they've put comments in some of the scripts for other people to understand it easier.

Generator98 wrote:

Hello?

Not here every day,

OK, here's the code. Ask specific querstions, I'll try to explain if I can.

define map edges
genMatrix :: custom
go to x: (-175) y: (-171)
set [i v] to [0]
repeat (35) 
  change [i v] by (1)
  set [j v] to [0]
  repeat (34) 
    change [j v] by (1)
    change x by (10)
    if <not <touching color [#000] ?>> then 
      replace item (((35) * ((i) - (1))) + (j)) of [adjacency v] with ((item (((35) * ((i) - (1))) + (j)) of [adjacency v] :: list) + (100))
      replace item ((((35) * ((i) - (1))) + (j)) + (1)) of [adjacency v] with ((item ((((35) * ((i) - (1))) + (j)) + (1)) of [adjacency v] :: list) + (1))
    end
  end
  change y by (10)
  set x to (-175)
end
go to x: (-171) y: (-165)
set [i v] to [0]
repeat (34) 
  change [i v] by (1)
  set [j v] to [0]
  repeat (35) 
    change [j v] by (1)
    if <not <touching color [#000] ?>> then 
      replace item (((35) * ((i) - (1))) + (j)) of [adjacency v] with ((item (((35) * ((i) - (1))) + (j)) of [adjacency v] :: list) + (1000))
      replace item (((35) * (i)) + (j)) of [adjacency v] with ((item (((35) * (i)) + (j)) of [adjacency v] :: list) + (10))
    end
    change x by (10)
  end
  change y by (10)
  set x to (-171)
end

define DFS_R (x) (y) (lastx) (lasty)
stackPush :: custom
add (x) to [pathX v]
add (y) to [pathY v]
if <(demonstrate) = [1]> then 
  set pen color to [#76ff56]
  go to x: ((-170) + ((10) * ((lastx) - (1)))) y: ((-170) + ((10) * ((lasty) - (1))))
  pen down
  glide (0.1) secs to x: ((-170) + ((10) * ((x) - (1)))) y: ((-170) + ((10) * ((y) - (1))))
  pen up
end
if <<(x) = [35]> and <(y) = [35]>> then 
  set [done v] to [1]
  stop [this script v]
else 
  set [currentindex v] to (((35) * ((y) - (1))) + (x))
  set [currentnode v] to (item (currentindex) of [adjacency v] :: list)
  if <(letter (1) of (currentnode)) = [2]> then 
    replace item ((currentindex) + (35)) of [adjacency v] with ((item ((currentindex) + (35)) of [adjacency v] :: list) - (10))
    DFS_R (x) ((y) + (1)) (x) (y) :: custom
    if <(done) = [1]> then 
      stop [this script v]
    end
  end
  if <(letter (2) of (currentnode)) = [2]> then 
    replace item ((currentindex) + (1)) of [adjacency v] with ((item ((currentindex) + (1)) of [adjacency v] :: list) - (1))
    DFS_R ((x) + (1)) (y) (x) (y) :: custom
    if <(done) = [1]> then 
      stop [this script v]
    end
  end
  if <(letter (3) of (currentnode)) = [2]> then 
    replace item ((currentindex) - (35)) of [adjacency v] with ((item ((currentindex) - (35)) of [adjacency v] :: list) - (1000))
    DFS_R (x) ((y) - (1)) (x) (y) :: custom
    if <(done) = [1]> then 
      stop [this script v]
    end
  end
  if <(letter (4) of (currentnode)) = [2]> then 
    replace item ((currentindex) - (1)) of [adjacency v] with ((item ((currentindex) - (1)) of [adjacency v] :: list) - (100))
    DFS_R ((x) - (1)) (y) (x) (y) :: custom
    if <(done) = [1]> then 
      stop [this script v]
    end
  end
end
delete (last v) of [pathX v]
delete (last v) of [pathY v]
if <(demonstrate) = [1]> then 
  set pen color to [#2ca5e2]
  change pen shade by (30)
  pen down
  glide (0.1) secs to x: ((-170) + ((10) * ((lastx) - (1)))) y: ((-170) + ((10) * ((lasty) - (1))))
  pen up
end
stackPop :: custom

I dont understand the calculations at all.. like * 35 or - 170

Generator98 wrote:

I dont understand the calculations at all.. like * 35 or - 170

Scratch doesn't have the 2d arrays you would normally use to represent a maze, so he's using a 1d array and mapping x and y indexes to a single index. So maze[1][1] is array[1]; maze[1][2] is array[2] etc. Once you get to the next row, you discover that maze[2][1] is array[36]. So multiply x by 35 and add y. It's complicated a little because scratch arrays start at 1 rather than 0.

The -170 is just positioning the drawing of the maze on the screen where he wants it.