Mazen Maze Creator Git

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * mazen-ng
 * Copyright (C) Jacob Zimmermann 2009 <jacob@jzimm.net>
 * 
 * mazen-ng is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * mazen-ng is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#pragma implementation

#include "polygon-walker.h"
#include <stdexcept>

PolygonWalker::PolygonWalker (const GridMaze& m): Walker (m) {
}

void PolygonWalker::map (xy p, int c) {
	s_mat (p, c);
	int nc = c + 1;

	if (p.x < maze.width () - 1) {
		xy pr = p.right ();
		if (!maze.vert (pr) && g_mat (pr) > nc)
			map (pr, nc);
	}
	
	if (p.x > 0 && !maze.vert (p)) {
		xy pl = p.left ();
		if (g_mat (pl) > nc)
			map (pl, nc);
	}

	xy pu = p.up ();
	pu.y %= maze.height ();
	if (!maze.horiz (pu) && g_mat (pu) > nc)
		map (pu, nc);

	if (!maze.horiz (p)) {
		xy pd = p.down ();
		if (pd.y < 0)
			pd.y = maze.height () - 1;
		if (g_mat (pd) > nc)
			map (pd, nc);
	}
}

void PolygonWalker::gen_solution (std::list<xy>& s) const {
	xy p = maze.get_entrance ();
	int c = g_mat (p);
	int best_c, nc;
	xy best_p;

	int mwidth = maze.width ();
	int mheight = maze.height ();
	
	while (c > 0) {
		s.push_back (p);
		best_c = c;

		if (p.x > 0 && !maze.vert (p)) {
			xy pl = p.left ();
			nc = g_mat (pl);
			if (nc < best_c) {
				best_p = pl;
				best_c = nc;
			}
		}

		if (p.x < mwidth) {
			xy pr = p.right ();
			if (!maze.vert (pr)) {
				nc = g_mat (pr);
				if (nc < best_c) {
					best_p = pr;
					best_c = nc;
				}
			}
		}

		if (!maze.horiz (p)) {
			xy pd = p.down ();
			if (pd.y < 0)
				pd.y = mheight - 1;
			nc = g_mat (pd);
			if (nc < best_c) {
				best_p = pd;
				best_c = nc;
			}
		}

		if (p.y < mheight) {
			xy pu = p.up ();
			pu.y %= mheight;
			if (!maze.horiz (pu)) {
				nc = g_mat (pu);
				if (nc < best_c) {
					best_p = pu;
					best_c = nc;
				}
			}
		}

		if (c == best_c && best_c > 0)
			throw std::runtime_error ("The impossible happened in PolygonWalker::gen_solution ()");

		c = best_c;
		p = best_p;
	};
}