Artifact 0bb4050087a6fb3f53ef5a516cd7759f02325de4

• File src/solver.d
  • 2012-07-14 12:29:17 - part of checkin [9d4aca73fa] on branch trunk - GUI+Solver revived. (user: kinaba) [annotate]

import util;
import game;
import driver;

/*
interface Solver
{
	this(const(Game) g);
	char single_step();
}
*/

class Solver_0
{
	this(const(Game) g) {}
	char single_step() { return 'W'; }
}

class Solver_1
{
	int g_wc = 0;

	Game g;
	this(const(Game) g)
	{
		this.g = g.clone();
	}

	char single_step()
	{
		char c = act(g);
		g.command(c);
		return c;
	}

	char act(const(Game) g)
	{
		const Pos   ro = g.map.robot;
		const Pos[] la = g.map.lambdas();
		const Pos   li = g.map.lift;

		char c = 'W';
		if( la.empty ) {
			auto r = search(g, ro, li);
			c = r[0];
		} else {
			Tuple!(char,int)[] cand;
			foreach(lam; la)
				cand ~= search(g, ro, lam);
			sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
				if(c1[1] != c2[1])
					return c1[1] < c2[1];
				return c1[0] < c2[0];
			})(cand);
			c = cand[0][0];
		}
		if(c=='W') {
			g_wc++;
			if(g_wc > 10)
				c = 'A';
		}
		else
			g_wc = 0;
		return c;
	}

	Tuple!(char,int) search(in Game g, in Pos s, in Pos o)
	{
		const(Pos)[] q = [o];
		bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
		for(int step=1; q.length; ++step) {
			Pos[] q2;
			foreach(p; q) {
				int[] dy=[-1,+1,0,0];
				int[] dx=[0,0,-1,+1];
				for(int i=0; i<4; ++i) {
					int y = p.y+dy[i];
					int x = p.x+dx[i];
					if(v[y][x]) continue;
					if(y==s.y && x==s.x) {
						if(i==0) return tuple('U',step);
						if(i==1) return tuple('D',step);
						if(i==2) return tuple('R',step);
						if(i==3) return tuple('L',step);
					} else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
						q2 ~= new Pos(y,x);
						v[y][x]=true;
					} else if(g.map[y,x]=='.' && g.map[y-1,x]!='*') {
						q2 ~= new Pos(y,x);
						v[y][x]=true;
					}
				}
			}
			q = q2;
		}
		q = [o];
		v = new bool[][](g.map.H+2, g.map.W+2);
		for(int step=1000; q.length; ++step) {
			Pos[] q2;
			foreach(p; q) {
				int[] dy=[-1,+1,0,0];
				int[] dx=[0,0,-1,+1];
				for(int i=0; i<4; ++i) {
					int y = p.y+dy[i];
					int x = p.x+dx[i];
					if(v[y][x]) continue;
					if(y==s.y && x==s.x) {
						if(i==0) return tuple('U',step);
						if(i==1) return tuple('D',step);
						if(i==2) return tuple('R',step);
						if(i==3) return tuple('L',step);
					} else if(g.map[y,x]==' '||g.map[y,x]=='\\') {
						q2 ~= new Pos(y,x);
						v[y][x]=true;
					} else if(g.map[y,x]=='.'/* && g[y-1,x]!='*'*/) {
						q2 ~= new Pos(y,x);
						v[y][x]=true;
					}
				}
			}
			q = q2;
		}
		return tuple('W', int.max);
	}
}