Archive for March, 2012

Manipulating doublearrays – an extension method

Thursday, March 22nd, 2012
arraymanipulations

I’ve been fiddling around with returning JSON from an Asp.net MVC solution and getting it in Jquery using the $.getJSON method. Unfortunately – when the default JSON serializer in .net serializes my doublearrays it takes the values of the first column first, then the next column, etc. I would like it to serialize it as one row, then the next, etc.

I am aware that this is default behavior and that I could just populate the doublearray with rows as columns and vice versa, but I find it more intuitive to be able to refer to the first indexer in an array as x and the second as y, like this:

byte[,] data = new byte[3,3];
int x = 2;
int y = 1;
data[x,y] = 1;

Therefore I created a little extension method for manipulating doublearrays. You may find it helpful if you need to rotate an array, or swap values vertically or horizontally.

You can perform multiple operations by chaining the manipulations.

This is how you use it:

byte[,] data = new byte[3,3];
byte[,] manipulatedData =data.GetManipulatedCopy(ArrayManipulation.RotateClockwise);

Download Vs2010 project

Download Class file

Here is the complete class:

using System;

// Class with extensionmethods to manipulate doublearrays with
// Jakob Krarup (www.xnafan.net)
// Use, alter and redistribute this code freely,
// but please leave this comment

namespace ArrayManipulation
{

    /// <summary>
    /// Defines how to manipulate an array
    /// </summary>
    public enum ArrayManipulation
    {
        /// <summary>
        /// Moves all values around the array clockwise
        /// </summary>
        RotateClockwise,

        /// <summary>
        /// Moves all values around the array counterclockwise
        /// </summary>
        RotateCounterClockwise,

        /// <summary>
        /// Swaps all values from the top to bottom and vice-versa
        /// </summary>
        FlipTopToBottom,

        /// <summary>
        /// Swaps all values from left to right and vice-versa
        /// </summary>
        FlipRightToLeft
    }

    public static class ArrayExtensions
    {

        /// <summary>
        /// Implements easy doublearray manipulations
        /// </summary>
        /// <typeparam name="T">The type of the values in the array</typeparam>
        /// <param name="matrix">The doublearray</param>
        /// <param name="manipulation">How to manipulate the array</param>
        /// <returns>A copy of the array with the values as ordered</returns>
        public static T[,] GetManipulatedCopy<T>(this T[,] matrix, ArrayManipulation manipulation)
        {
            int width = matrix.GetLength(0);
            int height = matrix.GetLength(1);
            T[,] ret = null;
            switch (manipulation)
            {
                //if we are rotating the matrix,
                //we need to swap width and height sizes
                case ArrayManipulation.RotateClockwise:
                case ArrayManipulation.RotateCounterClockwise:
                    ret = new T[height, width];
                    break;

                //otherwise we create an array with the same size
                case ArrayManipulation.FlipTopToBottom:
                case ArrayManipulation.FlipRightToLeft:
                    ret = new T[width, height];
                    break;
                default:
                    throw new ArgumentOutOfRangeException("Invalid manipulation : " + manipulation);
            }

            //for all values in the source matrix...
            for (int y = 0; y < height; ++y)
            {
                for (int x = 0; x < width; ++x)
                {
                    //copy the values to the new array
                    //choosing position depending on the wanted manipulation
                    switch (manipulation)
                    {
                        case ArrayManipulation.RotateCounterClockwise:
                            ret[y, width - x - 1] = matrix[x, y];
                            break;
                        case ArrayManipulation.RotateClockwise:
                            ret[height - y - 1, x] = matrix[x, y];
                            break;
                        case ArrayManipulation.FlipTopToBottom:
                            ret[x, height - 1 - y] = matrix[x, y];
                            break;
                        case ArrayManipulation.FlipRightToLeft:
                            ret[width - 1 - x, y] = matrix[x, y];
                            break;
                    }
                }
            }

            //return the new array
            return ret;
        }
    }
}

Searchwords for Google: extensionmethod, rotate double arrays, manipulate two-dimensional, twodimensional arrays, non-jagged

Maze creation in C#

Saturday, March 17th, 2012

maze_19x19

A small maze generator for use in .net.

I am currently in the process of learning how to code 3D graphics in XNA 4.0.  It’s a lot of fun – and I’ve gotten pretty far with just boxes covered by different textures. However I thought that it would be fun to have a small mazegame – where you’re running around as a bewildered labrat inside the maze. For that I would need to have a random maze generated each time.
So I Googled around, found some tips, and coded a mazegenerator.

After that I took the time to comment the code  and wrap it up. So if you don’t care about the inner workings, you can just add a reference to my DLL and get mazes like this:

//get a MazeCreator ready to make 9x9 mazes that start at 1,1
MazeCreator creator = new MazeCreator(9, 9, new Point(1, 1));
byte[,] maze1 = creator.CreateMaze();
byte[,] maze2 = creator.CreateMaze();
byte[,] maze3 = creator.CreateMaze();

Update - thanks to the anonymous commenter below, you can now get the point in the maze furthest from the starting point:)

If you want to know where the position in the maze that is furthest from the starting point is, you can ask the MazeCreator object after you have created the maze:

//get a MazeCreator ready to make 9x9 mazes that start at 1,1
MazeCreator creator = new MazeCreator(9, 9, new Point(1, 1));
byte[,] maze1 = creator.CreateMaze();
Point furthestPosition = creator.FurthestPoint;

Basics of maze creation

The basic algorithm of creating a maze is as follows (pseudocode)

Start at a valid starting point in the maze - then:
as long as there are still tiles to try
{
  excavate the square we are on
  get all valid neighbors for the curent tile
  if there are any interesting looking neighbors to branch off to(*)
  {
    remember the current tile, by putting it in a list of potential branch-offs (stack)
    move on to a random of the neighboring tiles
  }
  else
  {
    we are at a dead-end
    toss this tile out, thereby returning to the previous tile in the stack
  }
}

 

(*) and they are valid for whatever rules you have for your maze

(Longer writeup here: http://en.wikipedia.org/wiki/Maze_generation_algorithm)

Take a look at the animated gifs on this page, and try to follow along with the steps. I have chosen to use complete tiles for walls, but you could as well have neighboring tiles with a thin wall between in your own implementation.

The MazeCreator also has a MazeChanged event that signals every time a new tile has been excavated. This makes it easy to monitor the progress, either by inspecting the Maze property (byte[,]) or by calling the maze’s ToString representation:

image

LEGEND

X = wall

.  = tile which still needs to be checked

0 = tile being excavated

* = the point furthest from the beginning

[space] = tile which is done (no more neighbors to check)

The animated gif above was created by using gOODiDEA’s NGif component – here you can see that I subscribe to the event MazeChanged and add a new Bitmap to the AnimatedGifEncoder for every new tile excavated in the maze:

//create mazes of sizes 11 through 22
for (int size = 10; size < 12; size ++ )
{

    //make a new mazecreator
    _creator = new MazeCreator(size, size, new Point(1, 1));

    //figure out a savepath with a logical name containing width and height
    string gifPath = string.Format("c:\\maze_{0:00}x{0:00}.gif", size);

    //output status to console
    Console.WriteLine("Creating " + gifPath);

    //subscribe to the mazechanged event
    //to get a fresh bitmap on every new tile excavated
    _creator.MazeChanged += new EventHandler<PointEventArgs>(CreatorMazeChanged);

    //create the animated GIF
    _gifEncoder = new AnimatedGifEncoder();
    _gifEncoder.SetDelay(100);  //in milliseconds
    _gifEncoder.SetRepeat(0);   //yes - repeat (-1 is NO)
    _gifEncoder.SetQuality(1); //for generating palette - 1 is best, but slowest
    _gifEncoder.Start(gifPath); //where to save the maze
    var maze = _creator.CreateMaze();   //create a maze
    _gifEncoder.Finish();               //end
                
    //show the animated gif    
    Process.Start(gifPath);
    Console.WriteLine("Furthest point: " + _creator.FurthestPoint);
}

Class diagram and code

Here you can download the project which displays how to use the MazeGenerator, and see the public members of the MazeCreator. If you only want random mazes and don’t care for anything else, just grab the zipped DLL.

image

 Code with sample project

 Just the DLL

 Just the MazeCreator.cs (right-click and choose “Save as…” to save)

More sample mazes  Smiley

11 x 11 maze_11x11           13 x 13 maze_13x13          15 x 15 maze_15x15

image