Crawling 2D Maze/Matrix

Question

I'm trying to create a class that's able to 'crawl' through a generic 2D matrix. Crawling through a Bitmap (which can be viewed as a 2D Matrix of Colors) should yield the same result of a flood fill.

So the first thing I did was create a IMatrix (previous name was I2DMatrix. I renamed it since i don't intend to code a I3DMatrix) interface.

public interface IMatrix<T>
{
    int Width { get; }
    int Height { get; }

    void SetValue(int x, int y, T value);
    void SetValue(Point pt, T value);

    T GetValue(int x, int y);
    T GetValue(Point pt);
}

Then I created a abstract crawler for a genertic type T. Abstract so I don't have to worry creating 'how do I mark this place as already visited' and 'is this point crawlable' methods. The code for the Crawler is at the end of the post. It's somewhat polluted with comments, so here's a brief explanation of what's what.

• Protected non-abstract methods: are responsible for actually 'crawling' through the IMatrix. They rely heavily on IsValid(Point pt) and Mark(Pt), both abstract methods. If you override them to work with images in such way that Mark(Point pt) actually changes the color of the pixel at Pt and IsValid(Point pt) returns true whenever the color at Pt should be changed and false whenever it should not, then you'd have the flood fill effect previously mentioned.
• ValidArea property: used to create a boundary inside the IMatrix
• If you have any questions about the code, I'll update this list.

I'd like to have some help improving the Crawl(Point pt) method performance. From what I've read, I'm doing some unnecessary checking of points (as in checking points multiple times). But I don't know how I could improve it.

public abstract class Crawler<T>
{
    #region Fields
    /// <summary>
    /// The crawlable 2D grid.
    /// </summary>
    protected IMatrix<T> matrix;

    /// <summary>
    /// The width of the crawlable grid.
    /// </summary>
    protected int Width { get { return matrix.Width; } }

    /// <summary>
    /// The height of the crawlable grid.
    /// </summary>
    protected int Height { get { return matrix.Height; } }

    /// <summary>
    /// Used to 'jump' to walkable positions after the crawler is no longer able to move left or right, without having to backtrack.
    /// </summary>
    protected Stack<Point> upperRows { get; set; }

    /// <summary>
    /// Used to 'jump' to a walkable position after the crawler is no longer able to move left or right, without having to backtrack.
    /// </summary>
    protected Stack<Point> lowerRows { get; set; }

    /// <summary>
    /// Used to store the real valid area.
    /// </summary>
    protected Rectangle _validArea;

    /// <summary>
    /// A area within the crawlable area that further limits the moviment of the crawler.
    /// </summary>
    protected Rectangle ValidArea
    {
        get { return _validArea; }
        set
        {
            _validArea = value;
            _validArea.Intersect(new Rectangle(0, 0, matrix.Width, matrix.Height));
        }
    }

    #endregion

    /// <summary>
    /// Creates a object thats able to 'crawl' through a 2D grid, marking the spots it walked through.
    /// </summary>
    /// <param name="crawlableObject">The object to be crawled.</param>
    /// <param name="validArea">A area within the crawlable object, which further limits the crawlable area.</param>
    /// <param name="stackCapacity">The initial capcity of the stacks used to backtrack.    </param>
    protected Crawler(IMatrix<T> crawlableObject, System.Drawing.Rectangle validArea, int stackCapacity)
    {
        this.matrix = crawlableObject;

        this.ValidArea = validArea;

        this.upperRows = new Stack<Point>(stackCapacity);
        this.lowerRows = new Stack<Point>(stackCapacity);
    }

    /// <summary>
    /// Creates a object thats able to 'crawl' through a 2D grid, marking the spots it walked through.
    /// The valid area is equal to the area of the crawlawble object.
    /// The stackCapacity is guessed based on the dimensions of the crawlable area.
    /// </summary>
    /// <param name="crawlableObject"> The object to be crawled. </param>
    protected Crawler(IMatrix<T> crawlableObject)
        : this(crawlableObject,
               new Rectangle(0, 0, crawlableObject.Width, crawlableObject.Height),
               (int)(Math.Max(crawlableObject.Width, crawlableObject.Height) * Math.Sqrt(Math.Min(crawlableObject.Width, crawlableObject.Height))))
    { }

    #region Protected Abstract Methods

    /// <summary>
    /// Returns true if the Point with coordinates (x,y) should be walked.
    /// </summary>
    /// <param name="x">The x coordinate of the point.</param>
    /// <param name="y">The y coordinate of the point.</param>
    /// <returns></returns>
    protected abstract bool IsValid(int x, int y);

    /// <summary>
    /// Returns true if the Point pt should walked.
    /// </summary>
    /// <param name="pt">The point to be checked.</param>
    /// <returns></returns>
    protected bool IsValid(Point pt)
    {
        return IsValid(pt.X, pt.Y);
    }

    /// <summary>
    /// Marks the point with coordinates (x,y) as already walked through.
    /// </summary>
    /// <param name="x">The x coordinate of the point.</param>
    /// <param name="y">The y coordinate of the point.</param>
    protected abstract void Mark(int x, int y);


    /// <summary>
    /// Marks the Point pt as already walked through.
    /// </summary>
    /// <param name="pt">The point to be marked.</param>
    protected void Mark(Point pt)
    {
        Mark(pt.X, pt.Y);
    }

    /// <summary>
    /// Check if the point (pt.X, pt.Y + 1) should be walked. If it should, add it to the upperRows stack.
    /// </summary>
    /// <param name="pt">The point whose 'top' will be checked.</param>
    protected void CheckTop(Point pt)
    {
        pt.Y--;

        if (!IsValid(pt)) return;

        if (upperRows.Count == 0)
        {
            upperRows.Push(pt);
            return;
        }

        Point currentTop = upperRows.Pop();
        if (currentTop.Y == pt.Y && (Math.Abs(currentTop.X - pt.X) <= 1))
        {
            upperRows.Push(pt);
        }
        else
        {
            upperRows.Push(currentTop);
            upperRows.Push(pt);
        }
    }

    /// <summary>
    /// Check if the point (pt.X, pt.Y - 1) should be walked. If it should, add it to the lowerRows stack.
    /// </summary>
    /// <param name="pt">The point whose 'bot' will be checked.</param>
    protected void CheckBot(Point pt)
    {
        pt.Y++;

        if (!IsValid(pt)) return;

        if (lowerRows.Count == 0)
        {
            lowerRows.Push(pt);
            return;
        }

        Point currentBot = lowerRows.Pop();
        if (currentBot.Y == pt.Y && (Math.Abs(currentBot.X - pt.X) <= 1))
        {
            lowerRows.Push(pt);
        }
        else
        {
            lowerRows.Push(currentBot);
            lowerRows.Push(pt);
        }
    }

    /// <summary>
    /// Check if the point (pt.X + 1, pt.Y) should be walked through. If it should, move the crawler there and check its surroundings.
    /// </summary>
    /// <param name="pt">The point whose 'right' will be checked.</param>
    protected void CheckRight(Point pt)
    {
        pt.X++;
        while (IsValid(pt))
        {
            Mark(pt);
            CheckTop(pt);
            CheckBot(pt);
            pt.X++;
        }
    }

    /// <summary>
    /// Check if the point (pt.X - 1, pt.Y) should be walked through. If it should, move the crawler there and check its surroundings.
    /// </summary>
    /// <param name="pt">The point whose 'left' will be checked.</param>
    protected void CheckLeft(Point pt)
    {
        pt.X--;
        while (IsValid(pt))
        {
            Mark(pt);
            CheckTop(pt);
            CheckBot(pt);
            pt.X--;
        }
    }


    /// <summary>
    /// Checks if the point pt can be walked. If it can, mark it and check it's surroundings
    /// </summary>
    /// <param name="pt"></param>
    protected void CheckLocation(Point pt)
    {
        if (!IsValid(pt)) return;

        Mark(pt);
        CheckTop(pt);
        CheckBot(pt);
        CheckRight(pt);
        CheckLeft(pt);
    }

    #endregion

    /// <summary>
    /// This method will be called before the crawl. For performance reasons this isn't a event.
    /// </summary>
    protected abstract void PreCrawlMethods();

    /// <summary>
    /// This method will be called after the crawl. For performance reasons this isn't a event.
    /// </summary>
    protected abstract void PostCrawlMethods();


    /// <summary>
    /// Crawls through the CrawlableArea, starting from the startingPosition, until it reaches the limit of ValidArea,
    /// there are no more Valid points or it reaches the end of the CrawlableArea, whicheever comes first.
    /// The method that marks a Point as 'already walked through' must be overriden.
    /// The method that decide is a Point is a valid 'move position' must be overriden.
    /// </summary>
    /// <param name="startingPosition"></param>
    protected void Crawl(Point startingPosition)
    {
        PreCrawlMethods();

        CheckLocation(startingPosition);
        while (upperRows.Count > 0 || lowerRows.Count > 0)
        {
            if (upperRows.Count > 0)
            {
                CheckLocation(upperRows.Pop());
            }
            if (lowerRows.Count > 0)
            {
                CheckLocation(lowerRows.Pop());
            }
        }

        PostCrawlMethods();
    }
}

Answer 1

This is really very good in my opinion. I like your use of interfaces, and an abstract base class seems to be the right design choice to me.

The double checks here bother me a little bit though.

    while (upperRows.Count > 0 || lowerRows.Count > 0)
    {
        if (upperRows.Count > 0)
        {
            CheckLocation(upperRows.Pop());
        }
        if (lowerRows.Count > 0)
        {
            CheckLocation(lowerRows.Pop());
        }
    }

Unfortunately, I don't see a way to do it that wouldn't add an extra loop and given a loop would be much more inefficient than accessing the property repeatedly, I think it's good.

---

Properties should be PascalCased. You have a couple that are camelCased here.

protected Stack<Point> upperRows { get; set; }

/// <summary>
/// Used to 'jump' to a walkable position after the crawler is no longer able to move left or right, without having to backtrack.
/// </summary>
protected Stack<Point> lowerRows { get; set; }

---

CheckLeft, CheckRight, etc. make sense, but this one's name could be better IMO.

/// <summary>
/// Check if the point (pt.X, pt.Y - 1) should be walked. If it should, add it to the lowerRows stack.
/// </summary>
/// <param name="pt">The point whose 'bot' will be checked.</param>
protected void CheckBot(Point pt)

The doc comment seems to be at odds with the name CheckBot. I would expect this to check on the current location of the crawler. Which, on further inspection, is exactly what it does. So, the comment is a bit misleading. It's not obvious what this method does by either its name or comment.

---

The doc comments are great to have by the way. Did you know that you can reference types in them?

/// Check if the <see cref="Point" /> (pt.X + 1, pt.Y) should be walked through. If it should, move the crawler there and check its surroundings.

• Recommended doc comment tags
• see tag example

Answer 2

C# lets us define indexers. This would be an appropriate use case:

public interface IMatrix<T>
{
    void SetValue(int x, int y, T value);
    void SetValue(Point pt, T value);

    T GetValue(int x, int y);
    T GetValue(Point pt);
}

These 4 getter/setters should just be 2 get/set indexers.

public interface IMatrix<T>
{
    T this[Point pt] { get; set; }
    T this[int x, int y] { get; set; }
}

^{only relevant members included in snippets}