Generating mazes

In an attempt to create a video game, I came across the problem of creating a maze (see figure).

Like in most games you need to go from point A to point B via a number of corridors.

Now my problem was to find a good algorithm to create mazes, and after some research on the Internet I found several of them (see wikipedia for an explanantion) .

My first attempt was to use the simpelst algorithm , being the Depth-first search algorithm.

The algorithm goes as follows :

1, Initialize a grid full of walls
2, Start at a particular cell and call it the "exit."
3, Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.

So to implement this , I'll developed a recursive method (uses more memory and in a later state I can use a stack to avoid recursion).

In objective-C the implementation looks like this (very premature source code of the maze creation program (with animated GUI) can be downloaded here) :

step 1 : Initialize a grid

for ( x = 0 ; x <>
{

for ( y = 0 ; y <>
{
cell = [MazeCell fullCell] ;
[cell x: x ] ;
[cell y: y] ;
[maze atX: x atY: y put: cell]
}
}

A MazeCell is an object that contains four 'wall's' (a wall is here a BOOL that is true or false dending on the fact if the wall is their or not.

Step 2 : the actual generation of the maze

- (void) walkCells: (MazeCell *) aCell
{
int x ;
int y ;

NSMutableSet *neighbors ;
MazeCell *cell1 ;
NSEnumerator *enumerator ;

[aCell visited: YES] ;


x = [aCell x];
y = [aCell y];

neighbors = [NSMutableSet set] ;
if ( x > 0 ) [neighbors addObject: [maze atX: (x-1) atY: y ]] ;

if ( y > 0 ) [neighbors addObject: [maze atX: (x) atY: (y-1) ]] ;

if ( x <>

if ( y <>


enumerator = [ neighbors objectEnumerator] ;

while ( (cell1 = [enumerator nextObject] ) != nil )
{

if ( [cell1 visited] == NO )
{
if ( [cell1 x] == (x-1) )
{
[cell1 rightWall: NO] ;
[aCell leftWall: NO] ;
}

if ( [cell1 x] == (x+1) )
{
[aCell rightWall: NO] ;
[cell1 leftWall: NO] ;
}
if ( [cell1 y] == (y-1) )
{
[cell1 upWall: NO] ;
[aCell downWall: NO] ;
}

if ( [cell1 y] == (y+1) )
{
[aCell upWall: NO] ;
[cell1 downWall: NO] ;
}


[self walkCells: cell1] ;

}
}


}


A little explanation is needed here , in the beginning of the method you see that I build a list of the neighbours of cell.
Now it is important that the list is build in a random order, so therefor I use a NSMutableSet as datastructure. The position in the set depends on the hash that is generated for the object that is inserted.
In my case these objects are of type MazeCell.
So the trick to get them in random order was to implement the hash method on MazeCell and this hash method just returns a random number.

Drawing in views : background in custom views

Sometimes it could be usefull to have a background image in view instead of a color. For example if we want to have a texture in a view.

In the following example I draw a 'wall' as the background of a view :


The texture I want to apply to my view is the following :



Now its very easy to define this as a texture, you just create a new color , and not just a color but a colorpattern :

Step 1 : find the texture in my resources

NSString* fileName = [[NSBundle mainBundle] pathForResource: @"wall" ofType:@"jpg"];

NSURL* url = [NSURL fileURLWithPath: fileName];

Step 2 : upload the image from the URL
background = [[NSImage alloc] initWithContentsOfURL: url];

Step 3 : define a new color

color = [NSColor colorWithPatternImage:background ] ;
[color set] ;

Step 4 : fill the background
NSRectFill( [self bounds] ) ;

Note that you need to implement this code also in the drawRect: method, to ensure that each time your view get's redrawn that the background is drawn also.

Saving data to files

In some circumstances you want to save data to disk, in some cases you will use a database for that. But if you need , for example, to save the highscores of a game then a database will be a bit overkill.

In that case you can use core data, so lets look at a small example of how this works.
(Consider you already have an application in which you want to include a mechanism to save data).

Step 1 : add a data model

In XCode , you open the file assistant (via File>New File) and select 'data model'



Once you defined the data model , you'll get something like this :


I already added an Entity called HighScores , you add the entity via the menuitem (Design>Data Model>Add Entity).
I a same fashion you can add attributes to the entity (Desgin>Data Model>Add Attribute).
In my case I just defined 3 attributes : name,rank and score.

So this is all their is to define a datamodel (of course this is a very simple datamodel).
Now we need some coding to save information to the datamodel (and to file).

Step 2 : datastore identification

First we need to define in which file we will store the information :

NSError *error ; // this is for error reporting ; see later

NSURL *url = [NSURL fileURLWithPath:@"/Users/Herman/file.xml"];

Step 3 : define the datamodel we will use (= the datamodel in the project)

NSArray *bundles = [NSArray arrayWithObject:[NSBundle mainBundle]];

NSManagedObjectModel *model = [NSManagedObjectModel mergedModelFromBundles:bundles];

Step 4 : associate the datamodel with the datastore (= the file) via a coordinator

NSPersistentStoreCoordinator *coordinator = [[NSPersistentStoreCoordinator alloc] initWithManagedObjectModel:model];
[coordinator addPersistentStoreWithType:NSXMLStoreType configuration:nil URL:url options: nil error:&error];

Step 5 : Get the context

context = [[NSManagedObjectContext alloc] init];
[context setPersistentStoreCoordinator: coordinator];

Step 6 : Save some data to the file

NSManagedObject *score = [NSEntityDescription insertNewObjectForEntityForName:@"HighScores" inManagedObjectContext:context];
[score setValue:@"bla bla" forKey:@"name"] ;
[score setValue:[NSNumber numberWithInt: 100] forKey:@"score"] ;
[score setValue:[NSNumber numberWithInt: 1] forKey:@"rank"] ;
[context save: &error ] ;

Et voila, we have a simple way of saving data to a file.
In a next message I'll discuss how to retrieve data and do some more complex queries on files.

Drawing in views: rectangles

When you want to draw a rectangle (or fill one), you basically have 2 choices :

1. You want absolute performance and less accuracy then you can use the functions defined in NSGraphics.h (NSFrameRect, NSRectFill etc).

2. You need absolute accuracy and don't care so much about performance then you can use the methods defined in NSBezierPath.

(the reason why the NSBezierPath is less performant is explained in this article ).

The following code extract is from a drawRect: method of a custom view :
It shows the different methods of drawing and filling a rectangle.

NSBezierPath *aPath ;

NSBezierPath *myPath ;

// reset the bounds
[self setBounds: NSMakeRect(0,0,1000,1000)] ;

//---------------------------------
//1. filling rectangles
//---------------------------------
[[NSColor grayColor] set] ;

// convenience method for filling a rectangle
// less precise , but good performance
// C functions defined in NSGraphics.h
NSRectFill( rect ) ;

// filling a rectangle using a class method of NSBezierPath
[NSBezierPath fillRect: NSMakeRect( 0,500,75,75) ] ;


// filling a rectangle using an instance method of NSBezierPath
// this usefull if you want to do additional drawing in that path
myPath = [NSBezierPath new] ;
[myPath appendBezierPathWithRect: NSMakeRect ( 600,0,80,80) ] ;
[myPath fill] ;


// -----------------------------
//2. drawing a rectangle
//------------------------------

[[NSColor redColor] set ] ;

// drawing a rectangle using a class method of NSBezierPath
[NSBezierPath strokeRect: NSMakeRect( 500,500,80,80 ) ] ;

// drawing a rectangle using an instance method of NSBezierPath
// this usefull if you want to do additional drawing in that path
[[NSColor greenColor] set ] ;
aPath = [NSBezierPath bezierPathWithRect: NSMakeRect( 450,600,100,100) ] ;
[aPath stroke] ;


// absolute performance, less precise
// C functions defined in NSGraphics.h
NSFrameRectWithWidth( NSMakeRect( 700,700,70,70), 10 ) ;

NSFrameRect( NSMakeRect( 0,700,80,80 ) );