1

Lately I've been stuck on an algorithm for "exploring a grid". I want to paint all moves that are valid within a certain part of a grid based on a starting square that could be anywhere on the grid. My original plan was to use recursive split off in 4 directions marking grids until it either reached a boundary or the move limit. An exploring "branch" cannot move diagonally:

*note: arrows do not represent occurrence in stack, they are there for visualizing the concept of the algorithm

enter image description here

private void Explore(byte moves, byte row, char col) {
        if (row >= Grid[0].Count || col >= Grid.Count || row + col + 2 > moves) {//var < 0 handled b/c byte b = 0; (byte)(b-1) == 255
            return;
        }
        Grid[row][col].color = ...;//mark it

        if (Grid[row + 1][col + 1] == notVisited) Explore((byte) (moves - 1), (byte)(row + 1), (char) (col + 1));
        if (Grid[row - 1][col + 1]== notVisited) Explore((byte)(moves - 1), (byte)(row - 1), (char) (col + 1));
        if (Grid[row - 1][col - 1] == notVisited) Explore((byte)(moves - 1), (byte)(row - 1), (char) (col - 1));
        if (Grid[row + 1][col - 1] == notVisited) Explore((byte)(moves - 1), (byte)(row + 1), (char) (col - 1));
    }

I know this algorithm doesn't work b/c I did a quick runnable sample here where the algorithm gets stuck between values until it triggers a Runtime error.

So at this point:

  1. Is recursion still a possibility (switch to iterative)?

  2. Is there a better alternative algorithm to this problem?

  3. Is my algorithm close, but needs a few tweaks?

Bennett Yeo
  • 819
  • 2
  • 14
  • 28
  • 1
    Are you familiar with either A-star or Dijkstra's shortest-path algorithms? – Pieter Geerkens May 27 '15 at 04:39
  • 1
    if you can move in all 4 directions in every point you will get lot's of cycles (for example left->right->left->right-> ...) so there are infinitely many paths - so first thing is you will remove cycles. The next thing is that you should indeed be only interested in the shortest path (yeah A* is the thing) – Random Dev May 27 '15 at 05:09
  • @PieterGeerkens I'm looking to "traverse" all possible paths, not just the best. – Bennett Yeo May 27 '15 at 14:27

2 Answers2

1

You seem to be looking to implement depth-first search. The wiki article even provides some pseudo code which you can use to implement the algorithm.

Note that this will mark all reachable squares, but will not print out all (redundant) moves unless you modify the algorithm.

H W
  • 2,556
  • 3
  • 21
  • 45
  • The depth/breath first algorithms are very close to what I'm doing, and they do it iteratively, which is going to be faster than my recursive based solution. – Bennett Yeo May 28 '15 at 14:46
  • For information on dfs/bfs: http://stackoverflow.com/questions/687731/breadth-first-vs-depth-first – Bennett Yeo Jun 01 '15 at 14:35
1

The idea for searching should work fine, but the reason the code does not work is because it is checking for the diagonals. 

if (Grid[row + 1][col + 1] == notVisited)
if (Grid[row - 1][col + 1]== notVisited) 
if (Grid[row - 1][col - 1] == notVisited) 
if (Grid[row + 1][col - 1] == notVisited)

I think you mean: 

if (Grid[row + 1][col] == notVisited)
if (Grid[row - 1][col]== notVisited) 
if (Grid[row][col + 1] == notVisited) 
if (Grid[row][col - 1] == notVisited)

For the questions:

1: Recursion is fine. Iterative would be faster, but it won't make too much of a difference.

2: There are probably tons different ways to do it, but the current method should be fine.

3: Besides changing those four conditionals, this condition 

|| row + col + 2 > moves)

might cause the program to act strangely depending on where it is put. The moves parameter will not be the same for all recursion paths, so it's likely that most times the program will paint the entire grid. Other than that, the program should run fine.

Blubber
  • 1,375
  • 1
  • 15
  • 32