Messy and experimental ASCII maze solver

msolve2.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

typedef struct
{
	int x, y;
	void *parent;
	
	char c;
	
	enum
	{
		wall,
		air,
		node,
		nodeEntrance,
		nodeExit,
		marker,
	} type;
	
} Node;

struct
{
	Node **nodes;
	int width, height;
	Node *exitNode, *entranceNode;
} map;

void mapLoad( const char *fname )
{
	FILE *f = NULL;
	int x = 0, y = 0;
	int c = 0, i = 0;
	Node *node;
	
	f = fopen( fname, "r" );
	if ( f ==  NULL )
	{
		fprintf( stderr, "cannot open file!\n" );
		exit( 1 );
	}
	
	map.width = 0;
	map.height = 1;
	
	while ( ( c = fgetc( f ) ) != EOF )
	{
		if ( (char) c == '\n' )
		{
			map.height++;
			if ( map.width < x ) map.width = x;
			x = 0;
		}
		else x++;
	}
	
	if ( x == 0 ) map.height--;
	
	if ( !map.width || !map.height )
	{
		fprintf( stderr, "there's no data!\n" );
		exit( 1 );
	} 
	
	map.nodes = calloc( map.width, sizeof( Node* ) );
	for ( i = 0; i < map.width; i++ )
		map.nodes[i] = calloc( map.height, sizeof( Node ) );
		
	fprintf( stderr, "width: %d, height: %d\n", map.width, map.height );
	
	rewind( f );
	
	x = y = 0;
	while ( ( c = fgetc( f ) ) != EOF )
	{
		node = &map.nodes[x][y];
		
		if ( (char) c == '\n' )
		{
			y++;
			x = 0;
		}
		else
		{
			switch ( (char) c )
			{
				case ' ':
					node->type = air;
					node->c = ' ';
					break;
					
				case 'S':
					node->type = nodeEntrance;
					node->c = 'S';
					map.entranceNode = node;
					break;
					
				case 'E':
					node->type = nodeExit;
					node->c = 'E';
					map.exitNode = node;
					break;
				
				default:
					node->type = wall;
					node->c = '#';
					break;
			}
			
			node->x = x;
			node->y = y;
			x++;
		}
	}
	
	fclose( f );
}

void adddoors( )
{
	int i;
	if ( map.entranceNode == NULL )
		for ( i = 0; i < map.width; i++ )
			if ( map.nodes[i][1].type == air )
			{
				map.nodes[i][0].type = nodeEntrance;
				map.nodes[i][0].c = 'S';
				map.entranceNode = &map.nodes[i][0];
				break;
			}
			
	if ( map.exitNode == NULL )
		for ( i = map.width - 1; i >= 0; i-- )
			if ( map.nodes[i][map.height-2].type == air )
			{
				map.nodes[i][map.height-1].type = nodeExit;
				map.nodes[i][map.height-1].c = 'E';
				map.exitNode = &map.nodes[i][map.height-1];
				break;
			}
}

void setupNodes( )
{
	int i, j;
	char l, r, u, d;
	int ln, rn, un, dn;
	
	for ( i = 0; i < map.width; i++ )
	{
		for ( j = 0; j < map.height; j++ )
		{
			switch ( map.nodes[i][j].type )
			{
				case air:
					l = r = u = d = 0;
					
					if ( i > 0 )
					{
						ln = map.nodes[i - 1][j].type;
						l |= ln == air;
						l |= ln == node;
						l |= ln == nodeEntrance;
						l |= ln == nodeExit;
					}
					
					if ( !l && i < map.width - 1 )
					{
						rn = map.nodes[i + 1][j].type;
						r |= rn == air;
						r |= rn == node;
						r |= rn == nodeEntrance;
						r |= rn == nodeExit;
					}
					
					if ( j > 0 )
					{
						un = map.nodes[i][j - 1].type;
						u |= un == air;
						u |= un == node;
						u |= un == nodeEntrance;
						u |= un == nodeExit;
					}
					
					if ( !u && j < map.height - 1 )
					{
						dn = map.nodes[i][j + 1].type;
						d |= dn == air;
						d |= dn == node;
						d |= dn == nodeEntrance;
						d |= dn == nodeExit;
					}		
					
					if ( ( ( l || r ) && ( u || d ) ) )
					{
						map.nodes[i][j].type = node;
						map.nodes[i][j].c = '.';
					}
					break;
					
				default:
					break;
			}
		}
	}
	
	map.entranceNode->type = node;
	map.entranceNode->parent = map.entranceNode;
	map.exitNode->type = node;
}


void linkNode( Node *n )
{
	int x, y;
	
	//n->c = 'o';
	x = n->x + 1;
	y = n->y;
	
	for (; x < map.width; x++ )
	{
		if ( map.nodes[x][y].type == wall ) break;
		if ( map.nodes[x][y].type == node )
		{
			if ( map.nodes[x][y].parent != NULL ) break;
			map.nodes[x][y].parent = n;
			linkNode( &map.nodes[x][y] );
		}
	}
	
	x = n->x;
	y = n->y + 1;
			
	for (; y < map.height; y++ )
	{
		if ( map.nodes[x][y].type == wall ) break;
		if ( map.nodes[x][y].type == node )
		{
			if ( map.nodes[x][y].parent != NULL ) break;
			map.nodes[x][y].parent = n;
			linkNode( &map.nodes[x][y] );
		}
	}
	
	x = n->x - 1;
	y = n->y;
	
	for (; x >= 0; x-- )
	{
		if ( map.nodes[x][y].type == wall ) break;
		if ( map.nodes[x][y].type == node )
		{
			if ( map.nodes[x][y].parent != NULL ) break;
			map.nodes[x][y].parent = n;
			linkNode( &map.nodes[x][y] );
		}
	}
		
	x = n->x;
	y = n->y - 1;
		
	for (; y >= 0; y-- )
	{
		if ( map.nodes[x][y].type == wall ) break;
		if ( map.nodes[x][y].type == node )
		{
			if ( map.nodes[x][y].parent != NULL ) break;
			map.nodes[x][y].parent = n;
			linkNode( &map.nodes[x][y] );
		}
	}
}

void mapDraw( )
{
	int i, j;
	char *col;

	for ( i = 0; i < map.height; i++ )
	{
		for ( j = 0; j < map.width; j++ )
		{
			switch ( map.nodes[j][i].type )
			{
				case node:
					col = "3";
					break;
					
				case marker:
					col = "1;1";
					break;
					
				default:
					col = "7";
					break;
								}
			printf( "\x1b[3%sm%c\x1b[0m", col, map.nodes[j][i].c );
		}
		printf( "\n" );
	}
}

void printNodeInf( Node *n )
{
	fprintf( stderr, \
	"node %p\n" \
	"\tx: %d\n" \
	"\ty: %d\n" \
	"\tparent: %p\n" \
	"\ttype: %d\n" \
	"\tchar: %c\n" \
	, n, n->x, n->y, n->parent, n->type, n->c );
}

long markPath( Node *n )
{
	if ( n == NULL ) return 0;
	
	//printNodeInf( n );
	n->type = marker;
	n->c = '+';
	
	if ( n->parent == n ) return 0;
	return markPath( n->parent ) + 1;
}


int main( int argc, char **argv )
{
	if ( argc < 2 )
	{
		fprintf( stderr, "specify filename!\n" );
		exit( 1 );	
	}
	
	mapLoad( argv[1] );
	adddoors( );
	
	struct timeval t0, t1, t;
	gettimeofday( &t0, NULL );
	setupNodes( );
	linkNode( map.entranceNode );
	gettimeofday( &t1, NULL );
	timersub( &t1, &t0, &t );
	long hops = markPath( map.exitNode );
	fprintf( stderr, "hops: %ld\n", hops );
	fprintf( stderr, "elapsed: %ld.%06lds\n", (long) t.tv_sec, (long) t.tv_usec );
	mapDraw( );
}