Why does recursive function return unexpected result?

Question

My program is:

var maze = MazeFactory.FromPattern(Patterns.Maze3, Patterns.WallSymbol);
var a = maze.GetElementAt(0, 1);
var b = maze.GetElementAt(12, 0);

var printer = new PathPrinter(ConsoleColor.Yellow, ConsoleColor.Gray, ConsoleColor.Black);

Console.WriteLine("Maze");
printer.Print(maze, Path.Empty, Console.CursorLeft, Console.CursorTop);

var ab = new PathFinder(maze, a, b).GetPaths();
var abPath = ab.OrderBy(p => p.Elements.Count()).First();
Console.WriteLine("A -> B");
printer.Print(maze, abPath, Console.CursorLeft, Console.CursorTop);

var ba = new PathFinder(maze, b, a).GetPaths();
var baPath = ba.OrderBy(p => p.Elements.Count()).First();
Console.WriteLine("B -> A");
printer.Print(maze, baPath, Console.CursorLeft, Console.CursorTop);

Output is:

I expect PathFinder.GetPaths() to return a collection of Paths so that I could take the shortest one, but the collection contains only one element.

Answer to any is welcome.

Why is that?
Why 'a to b' path and 'b to a' one are different?
Why is 'a to b' path so long?
How to get both paths the shortest and the same?

Note: I'm not looking for a new solution, just for fixing up this one.

Details:

I have a class MazeElement:

class MazeElement
{
    public bool IsPass { get; }
    public int X { get; }
    public int Y { get; }

    public MazeElement(int x, int y, bool isPass) => (X, Y, IsPass) = (x, y, isPass);
}

MazeElement instances can form a Maze:

class Maze
{
    public IReadOnlyList<IReadOnlyList<MazeElement>> Elements { get; }
    public int MaxY { get; }
    public int MaxX { get; }

    public Maze(MazeElement[][] elements) =>
        (Elements, MaxY, MaxX) =
            (elements, elements.Length - 1, elements[0].Length - 1);

    public MazeElement GetElementAt(int x, int y) =>
        0 <= x && x <= MaxX && 0 <= y && y <= MaxY ?
        Elements[y][x] :
        null;
}

and a Path:

class Path
{
    public IEnumerable<MazeElement> Elements { get; }
    public bool ReachedDestination { get; }

    public static Path Empty => new Path(new MazeElement[0], false);

    private Path(IEnumerable<MazeElement> elements, bool reachedDestination) => (Elements, ReachedDestination) = (elements, reachedDestination);

    public Path Continued(MazeElement next, bool reachedDestination) => new Path(new List<MazeElement>(Elements) { next }, reachedDestination);

    public static Path FromStart(MazeElement start) => new Path(new[] { start }, false);
}

I have a MazeFactory that can create a Maze from a set of strings:

static class MazeFactory
{
    public static Maze FromPattern(IEnumerable<string> pattern, char wallSymbol) =>
        new Maze(pattern.Select((line, y) => line.Select((c, x) => new MazeElement(x, y, c != wallSymbol)).ToArray()).ToArray());
}

and some such sets:

static class Patterns
{
    public static readonly char WallSymbol = '#';

    public static readonly IReadOnlyList<string> Maze1 = new[]
        {
            "#########################",
            "                      ###",
            "##################### # #",
            "#                     # #",
            "# ##################### #",
            "# #                     #",
            "# ##################### #",
            "#                       #",
            "####################### #"
        };
    public static readonly IReadOnlyList<string> Maze2 = new[]
        {
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         ",
            "                         "
        };
    public static readonly IReadOnlyList<string> Maze3 = new[]
        {
            "############ ############",
            "                      ###",
            "######## ############ # #",
            "#                     # #",
            "# ########## ######## # #",
            "# #                     #",
            "# ###### ############ # #",
            "#                       #",
            "####################### #"
        };
}

To display results I have a PathPrinter:

class PathPrinter
{
    private static readonly string mazeSymbol = "█";
    private static readonly string pathSymbol = "*";

    private readonly ConsoleColor wallColor;
    private readonly ConsoleColor passColor;
    private readonly ConsoleColor pathColor;

    public PathPrinter(ConsoleColor wallColor, ConsoleColor passColor, ConsoleColor pathColor) =>
        (this.wallColor, this.passColor, this.pathColor) = (wallColor, passColor, pathColor);

    public void Print(Maze maze, Path path, int x = -1, int y = -1)
    {
        x = x == -1 ? Console.CursorLeft : x;
        y = y == -1 ? Console.CursorTop : y;

        foreach (var line in maze.Elements)
            foreach (var e in line)
            {
                Console.SetCursorPosition(e.X + x, e.Y + y);
                Console.ForegroundColor = e.IsPass ? passColor : wallColor;
                Console.Write(mazeSymbol);
            }
        Console.ForegroundColor = pathColor;
        foreach (var e in path.Elements)
        {
            Console.SetCursorPosition(e.X + x, e.Y + y);
            Console.BackgroundColor = e.IsPass ? passColor : wallColor;
            Console.Write(pathSymbol);
        }
        Console.SetCursorPosition(0, maze.MaxY + y + 1);
        Console.ResetColor();
    }
}

Finally I have a PathFinder to find a path in a Maze:

class PathFinder
{
    private readonly Maze maze;
    private readonly MazeElement start;
    private readonly MazeElement end;
    private readonly Dictionary<MazeElement, bool> elementIsChecked;

    public PathFinder(Maze maze, MazeElement start, MazeElement end) =>
        (this.maze, this.start, this.end, elementIsChecked) =
        (maze, start, end, maze.Elements.SelectMany(i => i).ToDictionary(i => i, i => false));

    public Path[] GetPaths() => FindPath(Path.FromStart(start)).ToArray();

    private IEnumerable<Path> FindPath(Path path) =>
        GetContinuations(path).Where(next => next != null)
                              .SelectMany(next => next.ReachedDestination ? new[] { next } : FindPath(next));

    private IEnumerable<Path> GetContinuations(Path path)
    {
        var e = path.Elements.LastOrDefault();

        if (e == null)
            return new Path[] { null };

        return new[]
        {
            maze.GetElementAt(e.X, e.Y - 1),
            maze.GetElementAt(e.X, e.Y + 1),
            maze.GetElementAt(e.X - 1, e.Y),
            maze.GetElementAt(e.X + 1, e.Y)
        }
        .Where(i => i != null)
        .Select(i => GetContinuedPath(path, i));
    }

    private Path GetContinuedPath(Path path, MazeElement e)
    {
        if (e == null || elementIsChecked[e])
            return null;

        elementIsChecked[e] = true;

        if (e.IsPass)
            return path.Continued(e, e == end);

        return null;
    }
}

Did you step through with a debugger? Did you write unit tests to help you validate correct behavior as you built your algorithm? If not, I recommend doing both of those things. — Daniel Mann
– Daniel Mann, Commented May 4, 2019 at 17:04
@Daniel Mann, I did testing. For example with a maze in the question. Path 'a to b' fails (it really leads from a to b, but it's too long), though path 'b to a' passes. I tried debugging, but it gave me only a headache because of recursion. — CSDev
– CSDev, Commented May 4, 2019 at 17:15
If you can't follow and reason about the code you just wrote, then you need to write unit tests. If you don't know what unit testing is, read up on it. — Daniel Mann
– Daniel Mann, Commented May 4, 2019 at 18:39
The code is a bit confusing to me so I might be missing it but I can't see the part which is supposed to ensure that the shortest path is chosen rather than the first found. — Stilgar
– Stilgar, Commented May 4, 2019 at 19:11
@Stilgar it looks like he is doing this in his main function with ab.OrderBy(p => p.Elements.Count()).First() — symbiont
– symbiont, Commented May 4, 2019 at 19:39

symbiont · Accepted Answer · 2019-05-05 07:42:02Z

5

You are using a Depth-First-Search in the function FindPath and also marking all points you come across as elementIsChecked, the first time you encounter them. Once marked you aren't looking at those points anymore.

But because you are using a Depth-First-Search, you could end up encountering a point while you are completing a long path. Then, once it's marked as elementIsChecked, the other paths don't get to use that point anymore. A long path ends up blocking subsequent shorter paths.

The reason that it took the long path in from A->B, is that you gave priority to these directions in the function PathFinder.GetContinuations: up, down, left, right. At (8,1) it chose down because right has a lower priotiy. (Using conditional breakpoints saves a lot of headaches)

So the only points you actually can't visit again are the points already on the path. A simple fix is to get rid of PathFinder.elementIsChecked and in PathFinder.GetContinuedPath replace:

if (e == null || elementIsChecked[e])

with

if (e == null || path.Elements.Contains(e))

Each path then continues until it blocks itself. it's not efficient but i guess that's the easy fix.

You should probably be using Breadth-First-Search and expand in all possible directions like a ripple in a pond at the same rate and stop expanding once you reach your destination

edited May 5, 2019 at 7:42

answered May 4, 2019 at 22:07

symbiont

1,6173 gold badges22 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

CSDev Over a year ago

thank you for paying attention and getting into my problem. I found a bit different solution myself (see Solved section in the question), but yours is good too. Take my upvote.

CSDev · Accepted Answer · 2019-06-20 07:27:12Z

Since I have my own answer I decided to post it properly.

@symbiont's answer still remains the accepted one.

Like @symbiont I found out the reason why I always get a collection that contains a single element. But I decided that was OK. So I changed

public Path[] GetPath() => FindPath(Path.FromStart(start)).ToArray();

to

public Path GetPath() => FindPath(Path.FromStart(start)).SingleOrDefault() ?? Path.Empty;

Then I concentrated on the direction priority problem which I discovered too. I came up with forcing the algorithm to prefer shorter ways by changing

private IEnumerable<Path> GetContinuations(Path path)
{
    var e = path.Elements.LastOrDefault();

    if (e == null)
        return new Path[] { null };

    return new[]
    {
        maze.GetElementAt(e.X, e.Y - 1),
        maze.GetElementAt(e.X, e.Y + 1),
        maze.GetElementAt(e.X - 1, e.Y),
        maze.GetElementAt(e.X + 1, e.Y)
    }
    .Where(i => i != null)
    .Select(i => GetContinuedPath(path, i));
}

to

private IEnumerable<Path> GetContinuations(Path path)
{
    var e = path.Elements.LastOrDefault();

    if (e == null)
        return new Path[] { null };

    return new[]
    {
        maze.GetElementAt(e.X, e.Y - 1),
        maze.GetElementAt(e.X, e.Y + 1),
        maze.GetElementAt(e.X - 1, e.Y),
        maze.GetElementAt(e.X + 1, e.Y)
    }
    .Where(i => i != null)
    .OrderBy(i => Math.Sqrt(Math.Pow(end.X - i.X, 2) + Math.Pow(end.Y - i.Y, 2)))
    .Select(i => GetContinuedPath(path, i));
}

So I changed my program to

var maze = MazeFactory.FromPattern(Patterns.Maze3, Patterns.WallSymbol);
var a = maze.GetElementAt(0, 1);
var b = maze.GetElementAt(12, 0);

var printer = new PathPrinter(ConsoleColor.Yellow, ConsoleColor.Gray, ConsoleColor.Black);

Console.WriteLine("Maze");
printer.Print(maze, Path.Empty);

Console.WriteLine("A -> B");
printer.Print(maze, new PathFinder(maze, a, b).GetPath());

Console.WriteLine("B -> A");
printer.Print(maze, new PathFinder(maze, b, a).GetPath());

And got the expected output:

Collectives™ on Stack Overflow

Why does recursive function return unexpected result?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related