C# - Recursive Function Issue

Here's my function:

static Map AddFormation(Map _map, Tile tile, int x, int y, int length, 
    Random rand, Tile endTile = (Tile)Int32.MaxValue)
{
    //so a call to AddFormation without the endTile will work, if I don't want a border.
    if ((int)endTile == Int32.MaxValue) endTile = tile;

    if (x >= 0 && x < _map.Data.GetLength(0) && y >= 0 && y < _map.Data.GetLength(1))
    {
        if (_map.Data[x, y].Tile != tile)
        {
            if (length > 0)
            {
                _map.Data[x, y].Tile = tile;
                int newlength = length - 1;
                AddFormation(_map, tile, x, y - 1, newlength, rand, endTile); // ^
                AddFormation(_map, tile, x, y + 1, newlength, r开发者_高级运维and, endTile); // v
                AddFormation(_map, tile, x - 1, y, newlength, rand, endTile); // <-
                AddFormation(_map, tile, x + 1, y, newlength, rand, endTile); // ->

            }
            else
            {
                _map.Data[x, y].Tile = endTile;
            }
        }
    }

    return _map;
}

I have a Tile enum which is to make my life easier when working with the tiles. I have a Cell class which contains a Tile enum called "Tile" and other info (unimportant to this) The Map class contains a Cell[,] group called Data.

What I am trying to achieve is to create a block of the specific tile at a specific point, I will later incorporate Randomisation into this (so it wouldn't be just a diamond) but I took it out to see if that was the cause of my issue.

The problem is a call to this function always produces blocks taller than they are wide and I can't for the life of me see why..

I created a test function to see what happens if I use something like:

    public static int[,] Add(int[,] grid, int x, int y, int length, int value)
    {

        if (x >= 0 && y >= 0 && x < grid.GetLength(0) && y < grid.GetLength(1))
        {
            if(grid[x,y] != value)
            {
                if(length > 0)
                {
                    grid[x, y] = value;

                    Add(grid, x - 1, y, length - 1, value);
                    Add(grid, x + 1, y, length - 1, value);
                    Add(grid, x, y - 1, length - 1, value);
                    Add(grid, x, y + 1, length - 1, value);
                }
            }
        }

        return grid;
    }

Which seems to suffer from the same problem if you go big enough (5 produces a perfect diamond, 6 produces a strange shape and something like 11 even stranger)

Ok, after spending a long time on this (I do like recursion), here is partway to the solution (it may be hard to explain):

The problem is that you are allowing the "path" to backtrack along the cells that have already been allocated as endTiles. If you take a look at your first method, you make the search point go down straight after it has searched up. You simply need to remove that.

This is the code I am using (notice that it calls AddFormationAlt twice, once for going up, once for going down):

class Program
{
    static string left;
    static string right;

    static void Main(string[] args)
    {
        int size = 20;
        int sizem = size*2 + 1;
        Map m = new Map(new int[sizem,sizem]);
        AddFormationAlt(m, 1, size, size, size-1, 2);

        var l = left;
        var r = right;
    }

    private class Map
    {
        public int[,] Data { get; set; }

        public Map(int[,] data)
        {
            Data = data;
        }

        public string Print()
        {
            StringBuilder sb = new StringBuilder();

            for (int x = 0; x < Data.GetLength(0); x++)
            {
                for (int y = 0; y < Data.GetLength(1); y++)
                    sb.Append(Data[y, x] == 0 ? " " : Data[y,x] == 1 ? "." : "#");
                sb.AppendLine();
            }

            return sb.ToString();
        }
    }

    static void AddFormationAlt(Map _map, int tile, int x, int y, int length, int endTile)
    {
        // You may need to change the cloning method when you change the tiles from ints
        Map m1 = new Map((int[,])_map.Data.Clone());
        Map m2 = new Map((int[,])_map.Data.Clone());

        // Contains the left and right half of the Map you want, you need to join these together.
        Map aleft = AddFormationAlt(m1, true, tile, x, y, length, endTile);
        Map aright = AddFormationAlt(m2, false, tile, x, y + 1, length, endTile);

        left = aleft.Print();
        right = aright.Print();
    }

    static Map AddFormationAlt(Map _map, bool up, int tile, int x, int y, int length, int endTile)
    {
        if (x >= 0 && x < _map.Data.GetLength(0) && y >= 0 && y < _map.Data.GetLength(1))
        {
            if (_map.Data[y, x] != tile)
            {
                if (length > 0)
                {
                    _map.Data[y, x] = tile;
                    int newlength = length - 1;

                    // Either go 'up' or 'down'
                    if(up)
                        AddFormationAlt(_map, true, tile, x, y - 1, newlength, endTile); // ^
                    else
                        AddFormationAlt(_map, false, tile, x, y + 1, newlength, endTile); // v

                    AddFormationAlt(_map, up, tile, x - 1, y, newlength, endTile); // <-
                    AddFormationAlt(_map, up, tile, x + 1, y, newlength, endTile); // ->

                }
                else
                    _map.Data[y, x] = endTile;
            }
        }

        return _map;
    }
}

I changed all your Data[x, y] to Data[y, x] because that's how I usually store them and then it worked xD.

In aleft and aright you have the left half and the right half of the diamond you want in separate Maps, you need to join them together somehow (shouldn't be too hard for a clever guy like you :). left and right show the textual representation of Maps (note the overlap in the centre):

left:

             #              
            #.
           #..
          #...
         #....
        #.....
       #......
      #.......
     #........
    #.........
   #..........
  #...........
 #............
#.............
 #............
  #...........
   #..........
    #.........
     #........
      #.......
       #......
        #.....
         #....
          #...
           #..
            #.
             #              

right:

             #                      
             .#            
             ..#           
             ...#          
             ....#         
             .....#        
             ......#       
             .......#      
             ........#     
             .........#    
             ..........#   
             ...........#  
             ............# 
             .............#
             ............# 
             ...........#  
             ..........#   
             .........#    
             ........#     
             .......#      
             ......#       
             .....#        
             ....#         
             ...#          
             ..#           
             .#            
             #   

You need to clean this up and change all the classes back to your own ones. I hope this helps!

When you say:

if(grid[x,y] != value)

You're telling it to only continue down this "leg" if you don't run into any blocks that have already been set to this value. The problem is that once you get a long enough length, the "leg" going out the top of the starting point "spirals around" to the left and right, and so when the recursion finally comes back to the point where it starts trying to go out the left or right, there is already a square there and you return immediately.

It looks like you want to take the if(length > 0) and put it after the if(grid[x,y] != value) block, rather than inside of it. That way, you only "set" the value if it hasn't already been set, but you will continue until you reach the appropriate length.

Of course, since "branches" (i.e. if statements) take longer than "assignments" (i.e. setting a value in an array), you might as well just remove the if(grid[x,y] != value) entirely, and risk setting spots to the same value multiple times, because it's cheaper than comparing the current value.

if (x >= 0 && y >= 0 && x < grid.GetLength(0) && y < grid.GetLength(1))
{
    grid[x, y] = value;
    if(length > 0)
    {

        Add(grid, x - 1, y, length - 1, value);
        Add(grid, x + 1, y, length - 1, value);
        Add(grid, x, y - 1, length - 1, value);
        Add(grid, x, y + 1, length - 1, value);
    }
}

return grid;

Don't you want something like

 if(grid[x,y] != 0) // or whatever the initial value is

instead of

 if(grid[x,y] != value)

Otherwise, when you grow out, it will grow back to the seed point.