package
{
import flash.display.Sprite;
import flash.events.Event;
/**
* 倉庫番を解くプログラム
*/
public class Main extends Sprite
{
/* マップの内容 */
public const ITEM_WALL:String = "*";
public const ITEM_PATH:String = ".";
public const ITEM_GOAL:String = "%";
public const ITEM_BOX:String = "o";
public const ITEM_PLAYER:String = "@";
public const ITEM_GOAL_BOX:String = "G";
/* マップの大きさ */
public const MAP_WIDTH:int = 9;
public const MAP_HEIGHT:int = 8;
/* 箱の数 */
public const MAP_BOXLIMIT:int = 3;
/* 盤面の元データ */
public var mapstr:Array = [
["*", "*", "*", "*", "*", "*", "*", "*", "*"],
["*", ".", ".", ".", ".", ".", ".", ".", "*"],
["*", ".", "*", "*", "o", "*", "*", ".", "*"],
["*", ".", "@", ".", ".", ".", "o", ".", "*"],
["*", "*", "o", "%", "%", "%", "*", ".", "*"],
["*", "*", ".", ".", ".", ".", "*", ".", "*"],
["*", "*", "*", "*", ".", ".", "*", "*", "*"],
["*", "*", "*", "*", "*", "*", "*", "*", "*"]
];
/* 盤面データ */
public var map:Array = new Array(MAP_HEIGHT);
// --------------------------------------------------------
// 調査済みのノード本体を格納するバッファ
public const NODEBUF_LIMIT:int = 0x10000;
public var nodebuf:Array = [NODEBUF_LIMIT];
public var nodebuf_head:int = 0;
public var goalpos:Array = new Array(MAP_BOXLIMIT); // ゴールの位置
/* 4方向を調べるための相対座標 */
/* 左", "上", "右", "下"の順 */
public var areadifpos:Array = [{x:-1, y:0}, {x:0, y:-1}, {x:1, y:0}, {x:0, y:1}];
public function Main():void
{
for (var i:int = 0; i < MAP_BOXLIMIT; i++ ) {
goalpos[i] = new t_point();
}
mapinit();
playstep_search();
}
// マップの初期化処理を行う
public function mapinit():void
{
var x:int, y:int;
for (y = 0; y < MAP_HEIGHT; y++) {
map[y] = new Array(MAP_WIDTH);
for (x = 0; x < MAP_WIDTH; x++) {
map[y][x] = mapstr[y][x];
}
}
}
// -------------------------------------------------------- //
// 正解の手を探索
public function playstep_search():void
{
var nownode:t_node, newnode:t_node;
var tmpnode:t_node = new t_node();
var i:int;
// 最初のノードを作る
nownode = playstep_makerootnode();
que_push(nownode);
// ノードを一つ取り出す
nownode = que_pop();
// 移動できるかどうかを確認
if (!playstep_playermovecheck(nownode, 3)) return;
// 新しいノードの人や荷物の位置を求める
playstep_playermove(tmpnode, nownode, areadifpos[3]);
printmap(nownode);
printmap(tmpnode);
}
// --------------------------------------------------------
// データ初期化関連
// 最初のノードを作る
public function playstep_makerootnode():t_node
{
var x:int, y:int, boxcount:int, goalcount:int;
var node:t_node;
node = get_newnode();
node.backnode = null;
node.cost = 1000000;
// マップを探索してゴール/箱/プレイヤーの位置を得る
boxcount = 0;
goalcount = 0;
for (y = 0; y < MAP_HEIGHT; y++) {
for (x = 0; x < MAP_WIDTH; x++) {
switch (map[y][x]) {
case ITEM_GOAL:
goalpos[goalcount].x = x;
goalpos[goalcount].y = y;
goalcount++;
break;
case ITEM_BOX:
node.boxpos[boxcount].x = x;
node.boxpos[boxcount].y = y;
boxcount++;
map[y][x] = ITEM_PATH;
break;
case ITEM_PLAYER:
node.playerpos.x = x;
node.playerpos.y = y;
map[y][x] = ITEM_PATH;
break;
}
}
}
return node;
}
// 新規ノード用のメモリーを割り当ててそのアドレスを返す
public function get_newnode():t_node
{
if (nodebuf_head >= NODEBUF_LIMIT) {
trace("nodebuf overflow\n");
return null;
// エラー処理
}
nodebuf[nodebuf_head] = new t_node();
nodebuf[nodebuf_head].createInstance();
nodebuf_head++;
return nodebuf[nodebuf_head - 1];
}
// --------------------------------------------------------
// 探索用キュー
public const SEARCHQUE_LIMIT:int = (256 * 10);
public var searchque:Array = [SEARCHQUE_LIMIT];
public var searchque_head:int = 0;
// 新しいノードを探索用キューにセットする
public function que_push(node:t_node):void
{
var tmpnode:t_node;
var i:int;
if (searchque_head >= SEARCHQUE_LIMIT) {
trace("searchque overflow\n");
// エラー処理
}
i = searchque_head - 1;
while(i >= 0 && node.cost > searchque[i].cost) {
searchque[i + 1] = searchque[i];
i--;
}
searchque[i + 1] = node;
searchque_head++;
}
// キューから探索候補を取り出す
public function que_pop():t_node
{
if (searchque_head == 0){
trace("searchque underflow\n");
// エラー処理
}
searchque_head--;
return searchque[searchque_head];
}
/* -------------------------------------------------------- */
/* その方向への移動を調べる/設定する */
/* 移動できるかどうか返す */
public function playstep_playermovecheck(node:t_node, dir:int):Boolean
{
var boxindex:int;
var checkpos:t_point = new t_point();
checkpos.x = node.playerpos.x + areadifpos[dir].x;
checkpos.y = node.playerpos.y + areadifpos[dir].y;
/* 範囲&壁チェック */
if (!playstep_movecheck(checkpos))
return false;
/* 移動先に箱があるとき，その方向へ動かせるかどうか */
boxindex = playstep_boxcheck(node, checkpos);
if (boxindex >= 0) {
if (playstep_boxmovecheck(node, checkpos, dir) < 0)
return false;
}
return true;
}
/* その方向へ移動する */
public function playstep_playermove(newnode:t_node, node:t_node, difpos:Object):void
{
var i:int, boxpos:int;
/* プレイヤーを移動させる */
newnode.playerpos.x = node.playerpos.x + difpos.x;
newnode.playerpos.y = node.playerpos.y + difpos.y;
/* 箱の位置を新しいノードにコピーする */
for (i = 0; i < MAP_BOXLIMIT; i++) {
newnode.boxpos[i].x = node.boxpos[i].x;
newnode.boxpos[i].y = node.boxpos[i].y;
/* その方向に箱があれば，箱を押していく */
/* 前段階でチェックしているので */
/* ここではチェックせずにそのまま押していく */
if ((newnode.boxpos[i].x == newnode.playerpos.x) &&
(newnode.boxpos[i].y == newnode.playerpos.y)) {
newnode.boxpos[i].x = node.boxpos[i].x + difpos.x;
newnode.boxpos[i].y = node.boxpos[i].y + difpos.y;
}
}
}
/* -------------------------------------------------------- */
/* 箱やゴールの重なり具合を調べる */
/* 範囲&壁チェック */
public function playstep_movecheck(checkpos:t_point):int
{
/* 範囲チェック */
if ((checkpos.x < 0) || (checkpos.x >= MAP_WIDTH) ||
(checkpos.y < 0) || (checkpos.y >= MAP_HEIGHT))
return 0;
/* 壁かどうか確認 */
if (map[checkpos.y][checkpos.x] == ITEM_WALL)
return 0;
return 1;
}
/* 指定されたポイントと荷物の位置が重なるかどうかを得る */
public function playstep_boxcheck(node:t_node, pos:t_point):int
{
var i:int;
for (i = 0; i < MAP_BOXLIMIT; i++) {
if ((node.boxpos[i].x == pos.x) &&
(node.boxpos[i].y == pos.y)) {
return i;
}
}
return 0;
}
/* 箱が移動できるか調べる */
public function playstep_boxmovecheck(node:t_node, newplayerpos:t_point, dir:int):int
{
var boxindex:int, overboxindex:int, overdir:int, i:int;
var newboxpos:t_point = new t_point();
var overboxpos:t_point = new t_point();
var nextoverboxpos:t_point = new t_point();
/* 該当する箱を探す */
boxindex = playstep_boxcheck(node, newplayerpos);
if (boxindex < 0)
return 0;
newboxpos.x = node.boxpos[boxindex].x + areadifpos[dir].x;
newboxpos.y = node.boxpos[boxindex].y + areadifpos[dir].y;
/* 新しい位置にある箱が動かせないのなら-1を返す */
if (!playstep_movecheck(newboxpos))
return 0;
/* その先に箱があるかどうか調べる */
overboxindex = playstep_boxcheck(node, newboxpos);
if (overboxindex >= 0)
return 0;
return boxindex;
}
public function print(_map:Array):void
{
var str:String;
for (var i:int = 0; i < _map.length; i++ ) {
for (var j:int = 0; j < _map[i].length; j++ ) {
if (j == _map[i].length - 1) {
str += _map[i][j];
str += "\n";
}else if (i == 0 && j == 0) {
str = _map[0][0];
}else {
str += _map[i][j];
}
}
}
trace(str);
}
/* -------------------------------------------------------- */
/* マップ表示 */
public function printmap(node:t_node):void
{
var tmpmap:Array = new Array(MAP_HEIGHT);
for (var i:int = 0; i < tmpmap.length; i++ ) {
tmpmap[i] = new Array(MAP_WIDTH);
}
var x:int, y:int;
for (y = 0; y < MAP_HEIGHT; y++) {
for (x = 0; x < MAP_WIDTH; x++) {
switch (map[y][x]) {
case ITEM_GOAL:
case ITEM_BOX:
case ITEM_PLAYER:
tmpmap[y][x] = ITEM_PATH;
break;
default:
tmpmap[y][x] = map[y][x];
break;
}
}
}
for (i = 0; i < MAP_BOXLIMIT; i++) {
x = node.boxpos[i].x;
y = node.boxpos[i].y;
tmpmap[y][x] = ITEM_BOX;
}
for (i = 0; i < MAP_BOXLIMIT; i++) {
x = goalpos[i].x;
y = goalpos[i].y;
if (tmpmap[y][x] == ITEM_BOX) {
tmpmap[y][x] = ITEM_GOAL_BOX;
} else {
tmpmap[y][x] = ITEM_GOAL;
}
}
x = node.playerpos.x;
y = node.playerpos.y;
tmpmap[y][x] = ITEM_PLAYER;
print(tmpmap);
}
}
}
