I made the iterator version.

I changed the names of just about everything so I could keep things straight in my head. Feel free to change them back.

I changed the param order too. I tend to put the structure on which I am operating on the left, like $self is. It was also more convenient internally. Feel free to change that back too.

use strict;
use warnings;


sub build_and_pop {
   my ($stack) = @_;
   my $path = [ map $_->[0], @$stack ];
   pop @$stack;
   return $path;
}


sub find_paths {
   my ($tree, $regs) = splice(@_, 0, 2);

   my @stack = ( [ [ @_ ], 0 ] );

   return sub {
      for (;;) {
         return if !@stack;

         our   ($node, $idx);
         local (*node, *idx) = map \$_, @{ $stack[-1] };

         # $node can be a reference into $tree,
         # so don't modify @$node.

         my ($x_s, $y_s, $s_s) = @$node;
         my $children = $tree->[$x_s][$y_s][$s_s];

         if (!$idx) {
            if (!defined $children) {
               # pad endpoint (base case)}
               $node = [ $x_s, $y_s, $s_s, 'pad' ];
               return build_and_pop(\@stack);
            }
                            
            if (exists $regs->{$x_s}{$y_s}{$s_s}) {
               # register endpoint (base case)
               $node = [ $x_s, $y_s, $s_s, 'reg' ];
               return build_and_pop(\@stack);
            }
         }                        

         if ($idx > $#$children) {
            pop @stack;
         } else {
            my $child = $children->[$idx++];
            push @stack, [ $child, 0 ];
         }
      }
   };
}
[download]

my $regs;

$regs->{1}{0}{0} = 1;

my $tree;

$tree->[0][0][0] = [
   [ 3, 0, 0 ],
];
 
$tree->[0][1][0] = [
   [ 0, 2, 0 ],
];

$tree->[1][0][0] = [
   [ 0, 3, 0 ],
];
 
$tree->[3][0][0] = [
   [ 0, 1, 0 ],
   [ 1, 0, 0 ],
];
[download]

my $iter = find_paths($tree, $regs, 3,0,0);

while (my ($route) = $iter->()) {
   for my $node (@$route) {
      print(join(',', @$node), "\n");
   }
   print("\n");
}
[download]