sub follow_paths {
    my ($x_s,$y_s,$s_s,$paths,$regs) = @_;
    
    my $branches = $paths->[$x_s][$y_s][$s_s];
                        
    unless (defined $branches) {
        # pad endpoint (base case)}
        return [[[$x_s,$y_s,$s_s,'pad']]];
    }
                            
    if (exists $regs->{$x_s}{$y_s}{$s_s}) {
        # register endpoint (base case)
        return [[[$x_s,$y_s,$s_s,'reg']]];
    }
                        
    my @current;
    foreach my $branch (@$branches) {
        my $branch_paths = follow_paths(@$branch,$paths,$regs);
        push @current, map { unshift @$_, [$x_s,$y_s,$s_s]; $_ }
                       @$branch_paths;
    }
    return \@current;
}