code: plan9front

ref: e72da62915b09d5673b0c0179ba8dfe045aeb8c3
dir: /sys/src/games/sokoban/route.c/

#include <u.h>
#include <libc.h>
#include <draw.h>

#include "sokoban.h"

static int dirlist[] = { Up, Down, Left, Right, Up, Down, Left, Right, };
static int ndir = 4;

static Point
dir2point(int dir)
{
	switch(dir) {
	case Up:
		return Pt(0, -1);
	case Down:
		return Pt(0, 1);
	case Left:
		return Pt(-1, 0);
	case Right:
		return Pt(1, 0);
	}
	return Pt(0,0);
}

int
validpush(Point g, Step *s, Point *t)
{
	int i;
	Point m;

	if (s == nil)
		return 0;

	m = dir2point(s->dir);

	// first test for  Cargo next to us (in direction dir)
	if (s->count > 0) {
		g = addpt(g, m);
		if (!ptinrect(g, Rpt(Pt(0,0), level.max)))
			return 0;
		switch (level.board[g.x][g.y]) {
		case Wall:
		case Empty:
		case Goal:
			return 0;
		}
	}
	// then test for  enough free space for us _and_ Cargo
	for (i=0; i < s->count; i++) {
		g = addpt(g, m);
		if (!ptinrect(g, Rpt(Pt(0,0), level.max)))
			return 0;
		switch (level.board[g.x][g.y]) {
		case Wall:
		case Cargo:
		case GoalCargo:
			return 0;
		}
	}
	if (t != nil)
		*t = g;
	return 1;
}

int
isvalid(Point s, Route* r, int (*isallowed)(Point, Step*, Point*))
{
	Point m;
	Step *p;

	if (r == nil)
		return 0;

	m = s;
	for (p = r->step; p < r->step + r->nstep; p++)
		if (!isallowed(m, p, &m))
			return 0;
	return 1;
}

static Walk*
newwalk(void)
{
	Walk *w;

	w = mallocz(sizeof *w, 1);
	if (w == nil)
		sysfatal("cannot allocate walk");
	return w;
}

static void
resetwalk(Walk *w)
{
	Route **p;

	if (w == nil || w->route == nil)
		return;

	for (p=w->route; p < w->route + w->nroute; p++)
		freeroute(*p);
	w->nroute = 0;
}

static void
freewalk(Walk *w)
{
	if (w == nil)
		return;

	resetwalk(w);
	if(w->route)
		free(w->route);
	free(w);
}

static void
addroute(Walk *w, Route *r)
{
	if (w == nil || r == nil)
		return;

	if (w->beyond < w->nroute+1) {
		w->beyond = w->nroute+1;
		w->route = realloc(w->route, sizeof(Route*)*w->beyond);
	}
	if (w->route == nil)
		sysfatal("cannot allocate route in addroute");
	w->route[w->nroute] = r;
	w->nroute++;
}

void
freeroute(Route *r)
{
	if (r == nil)
		return;
	free(r->step);
	free(r);
}

Route*
extend(Route *rr, int dir, int count, Point dest)
{
	Route *r;

	r = mallocz(sizeof *r, 1);
	if (r == nil)
		sysfatal("cannot allocate route in extend");
	r->dest = dest;

	if (count > 0) {
		r->nstep = 1;
		if (rr != nil)
			r->nstep += rr->nstep;

		r->step = malloc(sizeof(Step)*r->nstep);
		if (r->step == nil)
			sysfatal("cannot allocate step in extend");

		if (rr != nil)
			memmove(r->step, rr->step, sizeof(Step)*rr->nstep);

		r->step[r->nstep-1].dir = dir;
		r->step[r->nstep-1].count = count;
	}
	return r;
}

static Step*
laststep(Route*r)
{
	if (r != nil && r->nstep > 0)
		return &r->step[r->nstep-1];
	return nil;
}

static int*
startwithdirfromroute(Route *r, int* dl, int n)
{
	Step *s;
	int *p;
	
	if (r == nil || dl == nil)
		return dl;

	s =  laststep(r);
	if (s == nil || s->count == 0)
		return dl;

	for (p=dl; p < dl + n; p++)
		if (*p == s->dir)
			break;
	return p;
}

static Route*
bfstrydir(Route *r, int dir, Visited *v)
{
	Point m, p, n;

	if (r == nil)
		return nil;

	m = r->dest;
	p = dir2point(dir);
	n = addpt(m, p);

	if (ptinrect(n, Rpt(Pt(0,0), level.max)) && v->board[n.x][n.y] == 0) {
		v->board[n.x][n.y] = 1;
		switch (level.board[n.x][n.y]) {
		case Empty:
		case Goal:
			return extend(r, dir, 1, n);
		}
	}
	return nil;
}

static Route*
bfs(Point src, Point dst, Visited *v)
{
	Walk *cur, *new, *tmp;
	Route *r, **p;
	int progress, *dirs, *dirp;
	Point n;

	if (v == nil)
		return nil;

	cur = newwalk();
	new = newwalk();
	v->board[src.x][src.y] = 1;
	r = extend(nil, 0, 0, src);
	if (eqpt(src, dst)) {
		freewalk(cur);
		freewalk(new);
		return r;
	}
	addroute(cur, r);
	progress = 1;
	while (progress) {
		progress = 0;
		for (p=cur->route; p < cur->route + cur->nroute; p++) {
			dirs = startwithdirfromroute(*p, dirlist, ndir);
			for (dirp=dirs; dirp < dirs + ndir; dirp++) {
				r = bfstrydir(*p, *dirp, v);
				if (r != nil) {
					progress = 1;
					n = r->dest;
					if (eqpt(n, dst)) {
						freewalk(cur);
						freewalk(new);
						return(r);
					}
					addroute(new, r);
				}
			}
		}
		resetwalk(cur);
		tmp = cur;
		cur = new;
		new = tmp;
	}
	freewalk(cur);
	freewalk(new);
	return nil;
}

Route*
findroute(Point src, Point dst)
{
	Visited v;
	Route* r;

	memset(&v, 0, sizeof(Visited));
	r = bfs(src, dst, &v);
	return r;
}