Interesting Challenge

[simplezz]

So recently I came across an interesting puzzle. Having never done any pathfinding before, I knocked up a tentative solution. I based it on Dijkstra's algorithm. Though I soon realised that it was insufficient for the puzzle's search space parameters.

Unless I'm misunderstanding it, it (Dijkstra's) appears to radiate out from the source based on the smallest distance aggregate of the current vertex and its descendants (adjacents). That didn't seem to fit with this particular puzzle due to the fact that the distance between nodes in the graph is constant (1). I tweaked it somewhat by calculating the distance to the target instead. This means that descendants have a sense of direction.

I'm not sure how effective it would be at processing larger graphs, but it does currently solve the examples provided. I'm also interested in how it can be improved. The wiki seems to suggest that a fibonacci heap might decrease its runtime cost. Does anyone have any experience or insight they might be willing to share regarding efficiencies and whether or not Dijkstra's is right for this particular problem.

#include <stdlib.h>
#include <stdio.h>

typedef unsigned char byte;

/* prototypes */
int 
findPath(const int, const int, const int, const int, const byte*, const int, const int, int*, int);
/* -- */

void
printPath(int* path, int length) {
	printf("--------------\nLength: %i\n", length);
	while (length--)
		printf("%i\n", *path++);
}	

void 
test1() {
	byte map[] = {	1,1,1,1,
			0,1,0,1,
			0,1,1,1};
	int outBuffer[12];

	int hops = findPath(0, 0, 1, 2, map, 4, 3, outBuffer, 12);
	printPath(outBuffer, hops);
}	
void 
test2() {
	byte map[] = {	0,0,1,
			0,1,1,
			1,0,1};
	int outBuffer[7];

	int hops = findPath(2, 0, 0, 2, map, 3, 3, outBuffer, 7);
	printPath(outBuffer, hops);
}	

int
main(int argc, char** argv) {
	test1();
	test2();
	return EXIT_SUCCESS;
}

typedef struct {
	int x;
	int y;
} Point;	

static inline int
pointDiff(const Point* a, const Point* b) {
	return abs(a->x - b->x) + abs(a->y - b->y);
}	

typedef enum {True=1, False=0} Boolean;

/* forward declares */
typedef struct _AdjacentLink AdjacentLink;
typedef struct _Node Node;
/* -- */
typedef struct _Node {
	Point		vector; 
	int		indice;
	int		distance;
	AdjacentLink*	adjacents;
	Node*		prev;
} Node;

typedef struct _NodeLink NodeLink;
typedef struct _NodeLink {
	Node*	  node;
	NodeLink* prev;
	NodeLink* next;
} NodeLink;	
typedef struct _AdjacentLink {
	Node** 	 	node;
	AdjacentLink*	next;
} AdjacentLink;	

NodeLink* 
newNodeLink(NodeLink* head, Node* node) {
	NodeLink* link = malloc(sizeof(NodeLink));
	link->node = node;
	link->next = head;
	link->prev = NULL;
	if (NULL != head)
		head->prev = link;
	return link;
}
NodeLink*
removeNodeLink(NodeLink* link, NodeLink* head) {
	NodeLink* prev = link->prev;
	NodeLink* next = link->next;
	
	if(NULL != prev)
		prev->next = next; 
	else
		head = next;
	if(NULL != next)
		next->prev = prev;

	free(link);

	return head;	
}

AdjacentLink* 
newAdjacentLink(AdjacentLink* head, Node** node) {
	AdjacentLink* link = malloc(sizeof(AdjacentLink));
	link->node = node;
	link->next = head;
	return link;
}	
static inline Boolean 
hasAdjacents(Node* n) {
	return NULL != n->adjacents;
}	
typedef struct {
	int height;
	int width;
} Bounds;	

static inline int
pointToGridIndice(const Point *p, int gridWidth) {
	return p->y * gridWidth + p->x;
}	

#define CLOSED	   0
#define EDGE_COUNT 4	
static const Point edges[EDGE_COUNT] = {
	{-1,0},{1,0},{0,-1},{0,1}
};	
static inline Boolean
isBounded(int value, int limit) {
	return -1 != value && value < limit;
}

typedef struct {
	int	  size;
	Node**	  nodes;
	NodeLink* unvisited;
} Graph;

#define INFINITY 0x10000000

/* construct search graph with tentative distances 
 * returns graph node count */
int
buildGraph(const Bounds* b, const byte* grid, Graph** outGraph) {
	int count = 0;
	int x, y, indice;
	
	Graph* graph	= malloc(sizeof(Graph));
	graph->size	= b->height * b->width;
	graph->nodes	= malloc(graph->size * sizeof(Node*));
	graph->unvisited= NULL;

	/* initialise node set */
	for (y = 0, indice = 0; y < b->height; y++) {
		for (x = 0; x < b->width; x++, indice++) {
			graph->nodes[indice] = NULL;
			if (CLOSED == grid[indice])
				continue;
	
			Node* n = malloc(sizeof(Node));
			graph->nodes[indice] = n;
			n->vector.x = x;
			n->vector.y = y;
			n->indice   = indice;
			n->distance = INFINITY;
			n->adjacents= NULL;
			
			/* build adjacents */
			int i;		
			for(i = 0; i < EDGE_COUNT; i++) {
				Point edge = {n->vector.x + edges[i].x, n->vector.y + edges[i].y};
				if (isBounded(edge.x, b->width) && isBounded(edge.y, b->height)) {
					int adjacentIndice = pointToGridIndice(&edge, b->width);
					if (CLOSED != grid[adjacentIndice])
						n->adjacents = newAdjacentLink(n->adjacents, graph->nodes + adjacentIndice);
				}					
			}
				
			graph->unvisited = newNodeLink(graph->unvisited, n);		
			count++;
		}			
	}

	*outGraph = graph;
	return count;
}	

void
setStartPoint(Graph* graph, const Point* start, const Point* target, const Bounds* b) {
	graph->nodes[pointToGridIndice(start, b->width)]->distance = pointDiff(start, target);
}

NodeLink*
minUnvisited(NodeLink* set) {
	NodeLink* link	= set;
	NodeLink* best	= NULL;
	int distance	= INFINITY;

	while(NULL != link) {
		Node* n = link->node;
		if (distance > n->distance) {
			distance = n->distance;
			best 	 = link;		
		}			
		link = link->next;
	}

	return best;	
}
Boolean
isUnvisited(NodeLink* set, Node* test) {
	NodeLink* link = set;
	while(NULL != link) {
		if (test == link->node)
			return True;
		link = link->next;
	}		
	return False;		
}

Node*
planOptimalPath(Graph* graph, const Point* target, const Bounds* b) {
	NodeLink* link;
	Node*	  goal = graph->nodes[pointToGridIndice(target, b->width)];

	while(NULL != graph->unvisited) {
		link = minUnvisited(graph->unvisited);
		if (NULL == link)
			return NULL;
		Node* unvisited = link->node;
		if (goal == unvisited)
			return unvisited;
		graph->unvisited = removeNodeLink(link, graph->unvisited);

		AdjacentLink *al = unvisited->adjacents;
		while(NULL != al)  {
			if(isUnvisited(graph->unvisited, *al->node)) {
				Node* adjacent 	   = *al->node; 
				adjacent->distance = pointDiff(&adjacent->vector, target);
				adjacent->prev 	   = unvisited;
			}				
			al = al->next;
		}		
	}
	
	return NULL;		
}	

int
getOptimalPath(Node* target, int* outPath, int maxPath) {
	int  hops  = 0;
	Node *iter = target;
	
	/* todo: add to path stack or reverse outPath for correct source..goal order */
	while(NULL != iter && maxPath > hops) {
		outPath[hops] = iter->indice;
		hops++;
		iter = iter->prev;
	}
	
	return hops;
}	

void
freeAdjacents(AdjacentLink* adjacents) {
	AdjacentLink* adjacent = adjacents;
	while(NULL != adjacent) {
		AdjacentLink* next = adjacent->next;
		free(adjacent);
		adjacent = next;
	}		
}
void
freeUnvisited(NodeLink* unvisited) {
	NodeLink* link = unvisited;
	while (NULL != link) {
		NodeLink* next = link->next;
		free(link);
		link = next;
	}
}

void
freeGraph(Graph* graph) {
	int i;
	for(i = 0; i < graph->size; i++) {
		Node* n = graph->nodes[i];
		if (NULL != n) {
			freeAdjacents(n->adjacents);
			free(n);
		}			
	}

	free(graph->nodes);
	freeUnvisited(graph->unvisited);
	free(graph);	
}

int
findPath(const int startX, const int startY, 
		const int targetX, const int targetY,
		const byte* map, const int mapWidth, const int mapHeight,
		int* outBuffer, int outBufferSize) {

	Point start	= {startX, startY};
	Point target	= {targetX, targetY};
	Bounds mapBounds= {mapHeight, mapWidth};

	Graph *graph;
	buildGraph(&mapBounds, map, &graph);
	setStartPoint(graph, &start, &target, &mapBounds);

	Node* goal = planOptimalPath(graph, &target, &mapBounds);
	
	int hops = 0;
	if (NULL != goal)
		hops = getOptimalPath(goal, outBuffer, outBufferSize);

	/* clean up */
	freeGraph(graph);

	return hops;
}

 

[BinaryData]

Why must you hurt my brain!

[simplezz]

Why must you hurt my brain!

Hehe. It's not so difficult

I've improved the planOptimalPath function by storing the visited state in the node itself. That way I don't have to iterate the unvisited set for each descendant:

Node*
planOptimalPath(Graph* graph, const Point* target, const Bounds* b) {
	NodeLink* link;
	Node*	  goal = graph->nodes[pointToGridIndice(target, b->width)];

	while(NULL != graph->unvisited) {
		link = minUnvisited(graph->unvisited);
		if (NULL == link)
			return NULL;
		Node* unvisited    = link->node;
		unvisited->visited = True;

		if (goal == unvisited)
			return unvisited;
		graph->unvisited = removeNodeLink(link, graph->unvisited);

		AdjacentLink *al = unvisited->adjacents;
		while(NULL != al)  {
			if(!(*al->node)->visited) {
				Node* adjacent 	   = *al->node; 
				adjacent->distance = pointDiff(&adjacent->vector, target);
				adjacent->prev 	   = unvisited;
			}				
			al = al->next;
		}		
	}
	
	return NULL;		
}	

I just need to find a way to optimise minUnvisited(). Having to iterate the entire unvisited set each time seems grossly inefficient.

On a brighter note, I fixed getOptimalPath() so it's using a stack and returning the correct path order:

/* just a singly linked list in reality */
typedef struct _PathStack PathStack;
typedef struct _PathStack {
	int		indice;
	PathStack*	next;	
} PathStack;	

PathStack*
pushPath(PathStack* head, int indice) {
	PathStack* stack= malloc(sizeof(PathStack));
	stack->indice	= indice;
	stack->next	= head;
	return stack;
}
void
freeStack(PathStack* head) {
	PathStack* stack = head;
	while(NULL != stack) {
		PathStack* next = stack->next;
		free(stack);
		stack = next;
	}		
}

int
getOptimalPath(Node* target, int* outPath, int maxPath) {
	int		hops  = 0;
	Node	    	*iter = target;
	PathStack*  	path  = NULL;

	/* construct source..goal path stack */
	while(NULL != iter && maxPath > hops) {
		path = pushPath(path, iter->indice);
		iter = iter->prev;
		hops++;
	}
	
	/* populate outPath */
	PathStack* pathIter = path;
	while(NULL != pathIter) {
		*outPath++ = pathIter->indice;
		pathIter   = pathIter->next;	
	}		

	freeStack(path);

	return hops;
}	

 

[simplezz]

I gave it a slightly more complicated test:

void 
test3() {
	Byte map[] = {	0,1,0,0,1,0,0,0,1,1,1,1,1,
			1,1,1,0,0,1,1,1,1,0,1,0,1,
			1,0,1,1,1,1,0,0,0,1,1,1,1};
	int outBuffer[40];

	int hops = findPath(12, 0, 0, 2, map, 13, 3, outBuffer, 40);
	if (-1 != hops)
		printPath(outBuffer, hops);
}	

$  ./path
--------------
Length: 21
12
25
38
37
36
23
10
9
8
21
20
19
18
31
30
29
28
15
14
13
26

Seems to work fine so far. Though technically, that isn't the shortest path is it? Back to square one I guess lol.

[Andre S. Veteran]

http://www.redblobgames.com/pathfinding/a-star/introduction.html

[DevTech]

It is a common problem, specially in games.

As Andre points out, A-Star is the best (currently known) solution for most cases

But tons of people have played with various approaches to path finding and were nice enough to let everyone else see the results:

https://github.com/search?utf8=✓&q=path+find&type=Repositories&ref=searchresults

Actually GitHub search really sucks. Although there is more noise, a simpler search is probably better:

https://github.com/search?utf8=✓&q=path&type=Repositories&ref=searchresults

 

[simplezz]

Thanks for the input. I wanted to see how well a pure Dijkstra's solution did out of sheer curiosity.

#define NODE_LENGTH 1
Node*
planOptimalPath(Graph* graph, const Point* target, const Bounds* b) {
	NodeLink* link;
	Node*	  goal = graph->nodes[pointToGridIndice(target, b->width)];

	while(NULL != graph->unvisited) {
		link = minUnvisited(graph->unvisited);
		if (NULL == link)
			return NULL;
		Node* unvisited    = link->node;
		unvisited->visited = True;

		if (goal == unvisited)
			return unvisited;
		graph->unvisited = removeNodeLink(link, graph->unvisited);

		AdjacentLink *al = unvisited->adjacents;
		while(NULL != al)  {
			if(!(*al->node)->visited) {
				Node* adjacent 	   = *al->node; 
				adjacent->distance = unvisited->distance + NODE_LENGTH;
				adjacent->prev 	   = unvisited;
			}				
			al = al->next;
		}		
	}
	
	return NULL;		
}	

$  ./path
--------------
Length: 17
12
11
10
9
8
21
20
19
18
31
30
29
28
15
14
13
26

While it did find the shortest path, the performance was ghastly (as expected). My optimisation had good intentions but clearly failed to take into account the importance of distance travelled as part of the heuristic. That said, it's been fun unravelling the algorithm and learning graph theory.

A* looks interesting too. I'll take a stab at that next.