ansaurus

Question

Answer 1

A:

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.

Lou Franco 2010-09-18 21:48:56

Answer 2

+1 A:

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;

StriplingWarrior 2010-09-18 22:08:47

The only problem then becomes it checks over all the ones it's been through and creates 4 new instances for each one, and then 4 more instances (as a recursive function should) but the extra calling of the function on values it's already done creates an incredible time difference because of all the calls :( For example if it expands one out, then one left or one left then one out it will check that cell twice. Any way I could stop it without it messing up?

Blam 2010-09-18 23:20:34

Yeah, Callum showed how you could stop it by only going in one direction at a time. You could also avoid recursion entirely by drawing consecutive diamonds in a simple "for" loop. It would be much simpler, and might give you better performance, too.

StriplingWarrior 2010-09-20 16:05:20

Answer 3

+1 A:

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!

Callum Rogers 2010-09-18 23:25:52

Just to show it does work: http://pastebin.com/v22GT1mt

Callum Rogers 2010-09-18 23:49:03

Thanks! What I did (which is probably bad) is simply call the function on the same map, but I made the one that goes down (x,y-1) so it would work properly. With the overlap it obviously would find it the tile as the one we're setting to and stop immediately. Again - Thanks.

Blam 2010-09-18 23:52:17

@Blam: Glad it helped, when I tried it on a single map it went all wrong, I got the answer in the end by trial and improvement.

Callum Rogers 2010-09-19 13:53:54

ansaurus

tags:

views:

answers:

C# - Recursive Function Issue.

related questions