Skip to content

anonymous /gist:4741606

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Challenge 119 - objective C for Mac OS - command line
//
// Maze.h
// 119 maze shortest path
//
#import <Foundation/Foundation.h>
#define NOT_DEFINED -1
// These are valid maze inputs
#define START_ROOM 'S'
#define END_ROOM 'E'
#define WALL 'W'
#define ROOM '.'
@interface Maze : NSObject
{
int size; // the maze will be a size x size grid
int startNode; // node number where maze begins
int endNode; // node number where maze ends
NSMutableArray *maze; // our maze stored in an single array vs 2 dimension array
}
- (id) init;
- (id) initWithSize: (int) s;
- (void) addNode: (char) c;
- (void) displayMaze;
- (void) computeH;
+ (int) isValidRoom: (char) c;
- (int) isShortPath;
@property (nonatomic) int size;
@property (nonatomic) int startNode;
@property (nonatomic) int endNode;
@property (strong) NSMutableArray *maze;
@end
//
// Maze.m
// 119 maze shortest path
//
#import "Maze.h"
#import "MazeNode.h"
@implementation Maze
// create set/get accessors
@synthesize size, startNode, endNode, maze;
- (id) init
{
self = [super init];
if (self)
{
self = [self initWithSize: 0];
[self setStartNode: NOT_DEFINED];
[self setEndNode: NOT_DEFINED];
}
return self;
}
- (id) initWithSize: (int) s
{
self = [super init];
if (self)
{
[self setSize:s];
[self setStartNode: NOT_DEFINED];
[self setEndNode: NOT_DEFINED];
}
return self;
}
+ (int) isValidRoom: (char) c
{
switch (c) {
case START_ROOM:
case END_ROOM:
case WALL:
case ROOM:
return TRUE;
default:
return FALSE;
}
}
- (void) addNode: (char) c
{
MazeNode *node = nil;
node = [[MazeNode alloc] initWithNode: c];
if (!maze) {
maze = [[NSMutableArray alloc] init];
}
[maze addObject: node];
// set room number to current index in the maze array
[node setRoomNumber: (int) ([maze count] - 1)];
if (c == START_ROOM)
{
[self setStartNode: (int) ([maze count] -1)];
}
if (c == END_ROOM)
{
[self setEndNode: (int) ([maze count] -1)];
}
}
- (void) displayMaze
{
MazeNode *node = nil;
int n;
int c = 0;
printf("\n");
for (n = 0; n < ([self size] * [self size]); n++)
{
c++;
node = [maze objectAtIndex: n];
if (node) {
printf("%c", [node room]);
if (c == [self size])
{
printf("\n");
c = 0;
}
} else {
printf("?");
}
}
}
// compute H value using a simple manhattan heuristic of distance away
- (void) computeH
{
int beginCol;
int beginRow;
int endCol;
int endRow;
int deltaCol;
int deltaRow;
int nodeNum;
int h;
NSMutableArray *m = [self maze];
MazeNode *n;
endCol = [self endNode] % [self size] + 1;
endRow = [self endNode] / [self size] + 1;
// To compute H our heuristic for distance from cell to end we have to find the
// distance. So I convert the nodenumber (array location) into a row/col pairs
// and take the delta and add it together. Essentially that is how many squares
// from the node to the end node.
//
// so for example a 3x3 grid would have 9 elements in it
// 1 2 3 col/row
// [0] [1] [2] 1
// [3] [4] [5] 2
// [6] [7] [8] 3
//
// to get column from nodenumber you just take the nodenumber and modulus grid size + 1
// to get row from the nodenumber you just take the nodenumber and divide grid size + 1
//
// then I subract (I think I could have done an absolute vs conditional but it works)
// populate all nodes with the H value to the end node for A * algorithm.
for (nodeNum = 0; nodeNum < [m count]; nodeNum++)
{
n = [m objectAtIndex:nodeNum];
if (nodeNum == [self endNode])
{
h = 0;
}
else
{
beginCol = nodeNum % [self size] + 1;
beginRow = nodeNum / [self size] + 1;
(beginCol > endCol) ? deltaCol = beginCol - endCol : endCol - beginCol;
(beginRow > endRow) ? deltaRow = beginRow - endRow : endRow - beginRow;
h = deltaCol + deltaRow;
}
[n setH: h];
[n setG: 1];
[n setF: (h + 1)];
}
}
// Main Shortest Path check using A* Algorithm
- (int) isShortPath
{
NSMutableArray *closed = [[NSMutableArray alloc] initWithObjects: nil];
NSMutableArray *open = nil;
NSMutableArray *neighbor = [[NSMutableArray alloc] initWithObjects: nil];
NSSortDescriptor *byLowF = [NSSortDescriptor sortDescriptorWithKey: @"f" ascending: YES];
MazeNode *node = nil;
int tentativeG = 0;
int current;
int n;
int found;
int i;
if ([self startNode] == NOT_DEFINED ||
[self endNode] == NOT_DEFINED)
{
printf("False - no start/end room\n");
return 0;
}
//
// A* Algorithm - okay lets find a path
//
// populate H for the A* Algorithm
[self computeH];
// zero G at the start room
current = [self startNode];
node = [[self maze] objectAtIndex:current];
[node setG: 0];
// calculate F for current room f = g + h
[node setF: ([node g] + [node h])];
open = [[NSMutableArray alloc] initWithObjects: node, nil];
// while the open set is not empty
while ([open count] > 0)
{
// sort the open set by lowest F to find the current room to handle.
[open sortUsingDescriptors: [NSArray arrayWithObjects: byLowF, nil]];
// first node in open is the current room we want to handle with lowest F value
node = [open objectAtIndex: 0];
current = [node roomNumber];
if (current == [self endNode])
{
// found end of the maze -- we can return true/false
//
// return number of rooms in path since this is a positive number
// more than 0 it will be considered true.
//
// F value of the end room should now have the distance.
return [[[self maze] objectAtIndex:current] f];
}
// pop the current room from open and put it on closed
[open removeObjectAtIndex: 0];
[closed addObject: node];
// north -- calculate by subtracting size
n = current - [self size];
if (n > 0) // if n < 0 there is no valid north
{
if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
{
// okay we have a north neighbor that is not a wall add to neighbor queue
[neighbor addObject: [[self maze] objectAtIndex: n]];
}
}
// south -- calculate by adding size
n = current + [self size];
if (n < (size * size)) // if we go more/equal to size * size we went south too far
{
if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
{
// okay we have a south neighbor that is not a wall add to neighbor queue
[neighbor addObject: [[self maze] objectAtIndex: n]];
}
}
// west -- calculate by subtracting 1
n = current - 1;
if (n >= 0 && (current / [self size] == n / [self size])) // make sure still on same row
{
if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
{
// okay we have a west neighbor that is not a wall add to neighbnor queue
[neighbor addObject: [[self maze] objectAtIndex:n]];
}
}
// east -- calculate by adding + 1
n = current + 1;
if (n < [self size] * [self size] && current / [self size] == n / [self size]) // make sure still on same row
{
if ([[[self maze] objectAtIndex: n] room] != 'W') // room is not a wall
{
// okay we have a east neighbor that is not a wall add to neighbor queue
[neighbor addObject: [[self maze] objectAtIndex: n]];
}
}
// now we walk the neighbor queue/array and handle every neighbor.
// if the neighbor is closed - do nothing
// otherwise
while ([neighbor count] > 0)
{
// check to see if neighbor is in the closed queue
i = 0;
found = 0;
while (i < [closed count])
{
if ([[closed objectAtIndex: i] roomNumber] == [[neighbor objectAtIndex:0] roomNumber]) {
found = 1;
break;
}
i++;
}
if (found)
{
[neighbor removeObjectAtIndex: 0];
}
else
{
tentativeG = [node g] + 1;
// if neighbor is not in the open set and the tentative g <= neighbor's g
// then we need to adjust f, g and push on open set
i = 0;
found = 0;
while (i < [open count])
{
if ([[open objectAtIndex: i] roomNumber] == [[neighbor objectAtIndex:0] roomNumber]) {
found = 1;
break;
}
i++;
}
if (!found || tentativeG <= [[neighbor objectAtIndex:0] g])
{
// update the g, f and prev room of the neighbor
[[neighbor objectAtIndex:0] setG: tentativeG];
[[neighbor objectAtIndex:0] setF: (tentativeG + [[neighbor objectAtIndex: 0] h])];
[[neighbor objectAtIndex:0] setPrevRoom: current];
// if neighbor is not in the open set -- push it on
if (!found)
{
[open addObject: [neighbor objectAtIndex:0]];
}
}
// pop the current neighbor as we handled it.
[neighbor removeObjectAtIndex: 0];
} // if else
} // while we still have neighbors to process
} // while open has rooms
// return a FAILURE -- if we get this far we did not find the end room we exhausted a search -- just return failed
return FALSE;
}
@end
//
// MazeNode.h
// 119 maze shortest path
//
#import <Foundation/Foundation.h>
#import "Maze.h"
@interface MazeNode : NSObject
{
int roomNumber; // index into the single dimension array
int g; // movement cost
int h; // heuristic cost to get to end
int f; // f = g+h
int prevRoom; // room previous to this one on shortest path
char room; // room type
}
- (void) displayRoom;
- (id) init;
- (id) initWithNode: (char) c;
@property (nonatomic) int roomNumber;
@property (nonatomic) int g;
@property (nonatomic) int h;
@property (nonatomic) int f;
@property (nonatomic) char room;
@property (nonatomic) int prevRoom;
@end
//
// MazeNode.m
// 119 maze shortest path
//
#import "MazeNode.h"
@implementation MazeNode
@synthesize roomNumber, g, h, f, room, prevRoom;
- (id) init
{
return [self initWithNode: ROOM];
}
- (id) initWithNode: (char) c
{
self = [super init];
if (self) {
[self setG: 0];
[self setH: 0];
[self setF: 0];
[self setRoom: c];
}
return self;
}
- (void) displayRoom
{
printf("[%c]Room Number[%d] F[%d] = G[%d] + H[%d]\n",
[self room],
[self roomNumber],
[self f],
[self g],
[self h]);
}
@end
//
// main.m
// 119 maze shortest path
//
#import <Foundation/Foundation.h>
#import "Maze.h"
#import "MazeNode.h"
int main(int argc, const char * argv[])
{
@autoreleasepool {
int size = 0;
int row;
int col;
int nodeNum;
char room;
char enterKey;
int answer;
Maze *maze = nil;
printf("Enter Size (n) for a NxN Maze-->");
scanf("%d", &size);
if (size > 0) // read in rest of the maze
{
maze = [[Maze alloc] initWithSize: size]; // alloc a new maze;
if (maze)
{
nodeNum = 0;
for (row = 0; row < size; row++ )
{
scanf("%c", &enterKey);
for (col = 0; col < size; col++)
{
scanf("%c", &room);
if ([Maze isValidRoom: room])
{
[maze addNode: room];
}
else
{
printf("Error not a valid room type!\n");
return 1;
}
}
}
// [maze displayMaze];
}
else
{
printf("Error!! Could not allocate and create a maze/n");
return 1;
}
}
else // error message non-decimal, 0 or negative number entered
{
printf("\nError!!! Please enter a valid maze size!\n\n");
return 1;
}
// do we have a short path?
answer = [maze isShortPath];
if (answer)
{
printf("TRUE, %d\n", answer);
}
else
{
printf("FALSE\n");
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.