3Dプログラミング講座・その13:経路探索(A*:A-STAR)&巡回セールスマン問題:くろにゃんこ



経路探索(A*:A-STAR)&巡回セールスマン問題
経路探索(A*:A-STAR)&巡回セールスマン問題:巨大サイズ
ファイルはこちら



現在座標
目標座標


prg3d009kuro.htm

...省略...

<script>

var TMan = new N6LTimerMan();  //タイマーマネージャー
var rate = 2;
var img = new Array();
var readed = [false, false, false];
var answer = new Array();
var answercost = 1e12;
var answerhcost = 1e12;
var wanswer = new Array();
var wanswercost = 1e12;
var wanswerhcost = 1e12;
var data;
var elm;
var ctx;
var movefrm = 4;
var anifrm0 = 4;
var anifrm1 = 32;
var anispan = 4;
var tipsize = 8;
var maxdep = 120;
var coleps = 5;
var eps = 5e-14;
var tipmapsize = [480 / 8, 320 / 8];
var overthink = 10000;
var think = 0;
var rethink = 1.5;
var rtd = 0;
var rep = 0;
var sdep = 0;
var rew = 6;
var nrep = 0;
var bto = false;
var wthink = 0;
var wrethink = 1.5;
var wrtd = 0;
var wrep = 0;
var wsdep = 0;
var wrew = 6;
var wnrep = 0;
var wbto = false;
var rearway;

var tipcost = [
[64,  [0,   255,   0]],
[256, [0,   128,   0]],
[1024, [192, 192,   0]],
[8,  [160, 128,  32]],
[8,  [128, 128, 128]] ];

var movedir = [
[[1,   0], 1,        [0,7,1,6,2,5,3,4]],
[[1,   1], 1.414214, [1,0,2,7,3,6,4,5]],
[[0,   1], 1,        [2,1,3,0,4,7,5,6]],
[[-1,  1], 1.414214, [3,2,4,1,5,0,6,7]],
[[-1,  0], 1,        [4,3,5,2,6,1,7,0]],
[[-1, -1], 1.414214, [5,4,6,3,7,2,0,1]],
[[0,  -1], 1,        [6,5,7,4,0,3,1,2]],
[[1,  -1], 1.414214, [7,6,0,5,1,4,2,3]] ];

class Kuro {
  constructor() {
    this.frm = 0;
    this.pos = [160, 265];
    this.tgt = [160, 265];
    this.route = new Array();
    this.nowroute = 0;
    this.state = 0;
    this.size = 32;
  }
}

class Col {
  constructor(r, g, b, a) {
    this.r = 0;
    this.g = 0;
    this.b = 0;
    this.a = 0;
    if(isNaN(a) == false){
      this.r = r;
      this.g = g;
      this.b = b;
      this.a = a;
    }
  }
}

var tipmap = new Array();
var kuro = new Kuro();

function enter() {
  if(readed[0] == false){
    img[0] = new Image();
    img[0].src = "./img/astarmap.jpg";
    img[0].onload = () => {
      readed[0] = true;
      analyzemap();
      return;
    };
  }
  if(readed[1] == false){
    img[1] = new Image();
    img[1].src = "./img/kuro000.png";
    img[1].onload = () => {
      readed[1] = true;
      return;
    };
  }
  if(readed[2] == false){
    img[2] = new Image();
    img[2].src = "./img/kuro001.png";
    img[2].onload = () => {
      readed[2] = true;
      return;
    };
  }

  elm = document.getElementById('cnv0');
  ctx = elm.getContext("2d");

  elm.addEventListener("click",e=>{
    const rect = e.target.getBoundingClientRect();
    const viewX = e.clientX - rect.left,
          viewY = e.clientY - rect.top;
    const scaleWidth = elm.clientWidth / elm.width,
          scaleHeight = elm.clientHeight / elm.height;
    const canvasX = Math.floor(viewX / scaleWidth),
          canvasY = Math.floor(viewY / scaleHeight);

    kuro.tgt = [canvasX, canvasY];
    calcroute();
  });

  TMan.add();
  Loop(0);
}

function Loop(id){
  if(isreaded() == true){
    ctx.fillStyle = "rgb(0, 0, 0)" ;
    ctx.strokeStyle = 'rgb(0, 0, 0)';
    ctx.clearRect(0, 0, 480, 320);
    ctx.drawImage(img[0], 0, 0);

    movekuro();
    drawkuro();
    dispinfo();

  }
  TMan.timer[id].setalerm(function() { Loop(id); }, 50);
}

function drawkuro(){
  var dimg = img[1];
  if((kuro.frm % anifrm0) == 0) dimg = img[2];
  var dy = anispan * Math.sin((kuro.frm % anifrm1) / anifrm1 * Math.PI * 2);

  ctx.drawImage(dimg, kuro.pos[0] - (kuro.size / 2), kuro.pos[1] + dy - (kuro.size / 2));
}

function analyzemap(){
  ctx.fillStyle = "rgb(0, 0, 0)" ;
  ctx.strokeStyle = 'rgb(0, 0, 0)';
  ctx.clearRect(0, 0, 480, 320);
  ctx.drawImage(img[0], 0, 0);

  var w = 480;
  var h = 320;
  var imgdata = ctx.getImageData(0, 0, w, h);
  var data = imgdata.data;
  var x;
  var y;
  var i;
  var tip;
  tipmap = new Array();
  for(y = 0; y < h; y = y + tipsize){
    for(x = 0; x < w; x = x + tipsize){
      var c = getcolor(data, x, y, w, h);
      tip = 0;
      for(i = 0; i < tipcost.length; i++){
        if((tipcost[i][1][0] - coleps <= c.r)&&(c.r <= tipcost[i][1][0] + coleps)&&
           (tipcost[i][1][1] - coleps <= c.g)&&(c.g <= tipcost[i][1][1] + coleps)&&
           (tipcost[i][1][2] - coleps <= c.b)&&(c.b <= tipcost[i][1][2] + coleps)){
          tip = i;
          break;
        }
      }
      if((tip < 0)||(tipcost.length <= tip)) tip = 0;
      tipmap.push(tip);
    }
  }
}

function getcolor(data, x, y, w, h){
  var pos = (y * w + x) * 4;
  var ret = new Col();
  if(w * h * 4 < pos) return ret;
  ret.r = data[pos + 0];
  ret.g = data[pos + 1];
  ret.b = data[pos + 2];
  ret.a = data[pos + 3];
  return ret;
}

function movekuro(){
  kuro.frm++;
  if(kuro.state == 0) return;

  if((kuro.frm % movefrm) == (movefrm - 1)) kuro.nowroute++;
  if(kuro.route.length - 2 < kuro.nowroute){
    kuro.pos = kuro.tgt;
    kuro.state = 0;
  }
  else {
    var now = [kuro.route[kuro.nowroute][0] * tipsize, kuro.route[kuro.nowroute][1] * tipsize];
    var next = [kuro.route[kuro.nowroute + 1][0] * tipsize, kuro.route[kuro.nowroute + 1][1] * tipsize];
    var delta = [(next[0] - now[0]) / movefrm * (kuro.frm % movefrm), (next[1] - now[1]) / movefrm * (kuro.frm % movefrm)];
    kuro.pos = [now[0] + delta[0], now[1] + delta[1]];
  }
}

function calcroute(){
  kuro.route = new Array();
  kuro.nowroute = 0;

  var st = [Math.floor(kuro.pos[0] / tipsize), Math.floor(kuro.pos[1] / tipsize)];
  var ed =  [Math.floor(kuro.tgt[0] / tipsize), Math.floor(kuro.tgt[1] / tipsize)];
  var wans = new Array();
  wanswer = new Array();
  wanswercost = 1e12;
  wanswerhcost = 1e12;
  wthink = 0;
  wbto = false;
  wrtd = -1;
  wnrep = -1;
  getnearway(st, ed);
  var ret;
  if((st[0] != nearway[0])||(st[1] != nearway[1])){
    ret = serchway(wans.slice(), st, ed, 0, 0, maxdep, 0);
    if(ret == true){
      wanswer = answer.slice();
      wanswercost = answercost;
      wanswerhcost = answerhcost;
    }
  }
  var ans = new Array();
  answer = new Array();
  answercost = 1e12;
  answerhcost = 1e12;
  think = 0;
  bto = false;
  rtd = -1;
  nrep = -1;
  r = astar(ans.slice(), st, ed, 0, 0, maxdep, 0);
  ret = (ret || r);

  if(ret == true){
    if(wanswercost < answercost){
      kuro.route = wanswer.slice();
    }
    else {
      kuro.route = answer.slice();
    }
    kuro.nowroute = 0;
    kuro.state = 1;
  }

  return ret;
}

//ans:経路配列
//now:現在位置
//end:終了位置
//cost:経路コスト
//hcost:推計経路コスト
//maxdepth:最大ネスト深度
//depth:現在のネスト数
//answer:解答経路文字列
//answercost:解答経路コスト
//ret:解決できたか?
function serchway(ans, now, end, cost, hcost, maxdepth, depth){
  wthink++;
  if((maxdepth < depth)||(overthink < wthink)){
      wbto = true;
      return false;
  }
  var ret = false;
  var rrr;
  ans.push(now);
  if((now[0] == nearway[0])&&(now[1] == nearway[1])) {
    if((cost < wanswercost)||((wanswercost - eps < cost)&&(cost < wanswercost + eps)&&(hcost < wanswerhcost))){
      wanswercost = cost;
      wanswerhcost = hcost;
      wanswer = ans.slice();
      if(wrtd < 0){
        wrtd = depth / rethink;
        if(depth - wrtd < wrew) wrtd = depth - wrew;
//        wbto = true;
      }
      else {
        rrr = depth / rethink;
        if(depth - rrr < wrew) rrr = depth - wrew;
        if(rrr < wrtd) wrtd = rrr;
//        wbto = true;
      }
      answer = ans.slice();
      answercost = 1e12;
      answerhcost = 1e12;
      think = 0;
      bto = false;
      rtd = -1;
      nrep = -1;
      var r = astar(ans.slice(), nearway, end, cost, h, maxdepth, 0);
      return r;
    }
  }
  var i;
  var dir = setdir(now, nearway);
  for(i = 0; i < dir.length; i++){
    if(wbto == true){
      if(wrtd < depth){
        if(overthink < wthink) return ret;
      }
      else {
        if((i < dir.length - 1)){
          wbto = false;
          wthink = 0;
        }
      }
    }
    var next = [Math.floor(now[0] + movedir[dir[i]][0][0]), Math.floor(now[1] + movedir[dir[i]][0][1])];
    if(isoutmap(next) == true) continue;
    if(isGone(ans, next) == false){
      var h = heuristic(next, nearway);
      if(cost + h < wanswercost){
        if(h < hcost) h = hcost;
        var crnt = tipmapsize[0] * next[1] + next[0];
        var mcost = tipcost[tipmap[crnt]][0] * movedir[dir[i]][1];
        var r = serchway(ans.slice(), next, end, cost + mcost, h, maxdepth, depth + 1);
        ret = (ret || r);
      }
    }
    if((depth <= wrtd)&&(i == dir.length - 1)){
      rrr = depth / wrethink;
      if(depth - rrr < wrew) rrr = depth - wrew;
      if(rrr < wrtd) wrtd = rrr;
      wbto = true;
    }
  }
  return ret;
}

//ans:経路配列
//now:現在位置
//end:終了位置
//cost:経路コスト
//hcost:推計経路コスト
//maxdepth:最大ネスト深度
//depth:現在のネスト数
//answer:解答経路文字列
//answercost:解答経路コスト
//ret:解決できたか?
function astar(ans, now, end, cost, hcost, maxdepth, depth){
  think++;
  if((maxdepth < depth)||(overthink < think)){
      bto = true;
      return false;
  }
  var ret = false;
  var rrr;
  ans.push(now);
  if((now[0] == end[0])&&(now[1] == end[1])) {
    if((cost < answercost)||((answercost - eps < cost)&&(cost < answercost + eps)&&(hcost < answerhcost))){
      answercost = cost;
      answerhcost = hcost;
      answer = ans.slice();
      if(rtd < 0){
        rtd = depth / rethink;
        if(depth - rtd < rew) rtd = depth - rew;
//        bto = true;
      }
      else {
        rrr = depth / rethink;
        if(depth - rrr < rew) rrr = depth - rew;
        if(rrr < rtd) rtd = rrr;
//        bto = true;
      }
      return true;
    }
  }
  var i;
  var dir = setdir(now, end);
  for(i = 0; i < dir.length; i++){
    if(bto == true){
      if(rtd < depth){
        if(overthink < think) return ret;
      }
      else {
        if((i < dir.length - 1)){
          bto = false;
          think = 0;
        }
      }
    }
    var next = [Math.floor(now[0] + movedir[dir[i]][0][0]), Math.floor(now[1] + movedir[dir[i]][0][1])];
    if(isoutmap(next) == true) continue;
    if(isGone(ans, next) == false){
      var h = heuristic(next, end);
      if(cost + h < answercost){
        if(h < hcost) h = hcost;
        var crnt = tipmapsize[0] * next[1] + next[0];
        var mcost = tipcost[tipmap[crnt]][0] * movedir[dir[i]][1];
        var r = astar(ans.slice(), next, end, cost + mcost, h, maxdepth, depth + 1);
        ret = (ret || r);
      }
    }
    if((depth <= rtd)&&(i == dir.length - 1)){
      rrr = depth / rethink;
      if(depth - rrr < rew) rrr = depth - rew;
      if(rrr < rtd) rtd = rrr;
      bto = true;
    }
  }
  return ret;
}

function getnearway(now, end){
  var sub;
  var near = [-1, -1];
  var nd = 1e12;
  var nh = 1e12;
  var d;
  var h;
  var x;
  var y;
  var crnt;
  var tip;
  for(y = 0; y < tipmapsize[1]; y++){
    for(x = 0; x < tipmapsize[0]; x++){
      crnt = tipmapsize[0] * y + x;
      tip = tipmap[crnt];
      if((tip == 3)||(tip == 4)){
        sub = [x - now[0], y - now[1]];
        d = Math.sqrt(sub[0] * sub[0] + sub[1] * sub[1]);
        h = heuristic([x, y], end);
        if((d < nd)||(h < nh)&&(nd - eps < d)&&(d < nd + eps)){
          nd = d;
          nh = h;
          near = [x, y];
        }
      }
    }
  }
  nearway = near;
}

function setdir(now, end){
  var sub = [Math.floor(end[0] - now[0]), Math.floor(end[1] - now[1])];
  if(sub[0] == 0) sub[0] = 0;
  else if(sub[0] < 0) sub[0] = -1;
  else sub[0] = 1;
  if(sub[1] == 0) sub[1] = 0;
  else if(sub[1] < 0) sub[1] = -1;
  else sub[1] = 1;
  var i;
  for(i = 0; i < movedir.length; i++){
    if((sub[0] == movedir[i][0][0])&&(sub[1] == movedir[i][0][1])) return movedir[i][2];
  }
  return movedir[0][2];
}

function heuristic(now, end){
  var sub = [end[0] - now[0], end[1] - now[1]];
  var crnt = tipmapsize[0] * now[1] + now[0];
  var ret = Math.sqrt(sub[0] * sub[0] + sub[1] * sub[1]) / rate * tipcost[tipmap[crnt]][0];
  return ret;
}

function isoutmap(pos){
  if((pos[0] < 0)||(tipmapsize[0] - 1 < pos[0])||(pos[1] < 0)||(tipmapsize[1] - 1 < pos[1])) return true;
  return false;
}

function isGone(ans, now){
  var i;
  for(i = 0; i < ans.length; i++){
    if((ans[i][0] == now[0])&&(ans[i][1] == now[1])){
      return true;
    }
  }
  return false;
}

function isreaded(){
  for(var i = 0; i < 3; i++){
    if(readed[i] == false) return false;
  }
  return true;
}

function dispinfo(){
  var nowelm = document.getElementById('OUTTXTNOW');
  var tgtelm = document.getElementById('OUTTXTTGT');

  nowelm.value = Math.floor(kuro.pos[0]) + ', ' + Math.floor(kuro.pos[1]) + ' :state: ' + kuro.state;
  tgtelm.value = Math.floor(kuro.tgt[0]) + ', ' + Math.floor(kuro.tgt[1]);
}

</script>

...省略...


var tipcost = [
[移動コスト, チップの色[r, g, b]],
...
];

var movedir = [
[xy変位[dx, dy], コストの倍率, 探索順番[...]],
...
];

function analyzemap()
8ピクセル毎にマップイメージから色を取得して
tipcostの色と照合してチップ番号をマップデータに格納しています

function heuristic(now, end)
終点までの距離をrateで割った値に現在位置の移動コストを掛けた値を推計値とする

function calcroute()
astar呼び出し準備の関数

function serchway(ans, now, end, cost, hcost, maxdepth, depth)
近くへの道へのastar

function astar(ans, now, end, cost, hcost, maxdepth, depth)

think++;
if((maxdepth < depth)||(overthink < think)){
 bto = true;
 return false;
}
思考のし過ぎとネストの深すぎを解答不可能としてリターン
btoがtrueだとrtdまで思考放棄してネストを戻る

ans.push(now);
仮解答の格納

if((now[0] == end[0])&&(now[1] == end[1])) {
 if((cost < answercost)||((answercost - eps < cost)&&(cost < answercost + eps)&&(hcost < answerhcost))){
終了条件と良解答条件で良解答を格納して解答できたとしてリターン

var dir = setdir(now, end);
周囲8方向の探索順番を格納

if(bto == true){
 if(rtd < depth){
  if(overthink < think) return ret;
 }
 else {
  if((i < dir.length - 1)){
   bto = false;
   think = 0;
  }
 }
}

btoがtrueならばrtdまでネストを戻る
戻ったら思考再開

var next = [Math.floor(now[0] + movedir[dir[i]][0][0]), Math.floor(now[1] + movedir[dir[i]][0][1])];
探索順番から周囲1マス進む

if(isoutmap(next) == true) continue;
マップ範囲外はコンティニュー

if(isGone(ans, next) == false){
 var h = heuristic(next, end);
 if(cost + h < answercost){
一度も行っていないマスで終点までの移動コストが解答コストよりも小さかったら

if(h < hcost) h = hcost;
大きい方の推計を保存

var crnt = tipmapsize[0] * next[1] + next[0];
var mcost = tipcost[tipmap[crnt]][0] * movedir[dir[i]][1];
チップの移動コストの計算

var r = astar(ans.slice(), next, end, cost + mcost, h, maxdepth, depth + 1);
ret = (ret || r);
+1ネストして再帰呼び出し
戻り値をorして解答できたかを保存

このアルゴリズムの解説

経路探索は
再帰的全検索で解こうとすると
日が暮れてしまいます

なのでおらはどうしたかというと
設定した最大ネスト深度まで潜ったら
一旦リターンして最大ネスト深度までの解答を検索します
運よく解答が見つかったら
ネストをしかるべく設定されたネスト深度分
強制的に戻してしまって
次のノードに進むというものです

(そのノードで仮解答が出ていたとしたら
その周辺の計算はその仮解答の微調整というだけなので
ネストを深く潜りすぎるのならば深追いは禁物ということで
それ以上の計算を諦めて処理を高速化します)

で、詳細な正解は多分出ないかと思いますが
大体の良解答は出るのではと思います

で巡回セールスマン問題は
巡回地点の全組み合わせを列挙して
その経路探索を行っているだけです

ですからこの処理で例えば
「上」「左」「右」「下」
という優先順位の計算だったとするならば
上回りの解答を特に優先してピックアップするので
それが嫌ならば処理時間が2倍になってしまうことを覚悟で
「下」「右」「左」「上」
の逆優先順位で再計算すればいいです
優先順位の再計算は指数関係ではなく高々N倍なので
ネストをしつこく計算するよりは
優先順位を再計算したほうが高速だと思います

「上」「左」「右」「下」
という優先順位で最大ネスト深度5ネスト回復3で再帰検索をかけて
解答が見つからない最悪の場合は
・「上」「上」「上」「上」「上」
・「上」「左」「上」「上」「上」
・「上」「右」「上」「上」「上」
・「上」「下」「上」「上」「上」
・「左」「上」「上」「上」「上」
・「左」「左」「上」「上」「上」
・「左」「右」「上」「上」「上」
・「左」「下」「上」「上」「上」
・「右」「上」「上」「上」「上」
・「右」「左」「上」「上」「上」
・「右」「右」「上」「上」「上」
・「右」「下」「上」「上」「上」
・「下」「上」「上」「上」「上」
・「下」「左」「上」「上」「上」
・「下」「右」「上」「上」「上」
・「下」「下」「上」「上」「上」
という検索ですが
「・」1つごとに最大4^3だけ仮解答を検索して
方向のネスト回復乗 つまり 4^3 - 仮解答が見つかるまでの検索数 だけ
検索を省略しています
枝葉末節にそこまで拘らない為に
ネスト回復をして大体の解答を得ます
要するに方向のネスト回復乗分の検索を最初に仮解答が見つかった以降の検索を省略しているだけです

この方法で重要なのは通常に解答が見つかるくらいのネスト深度よりも
深く最大ネスト深度を設定することで
ネスト回復は 解答が見つかったネスト深度 / 1.5 としています
そうすることによって
枝葉末節の計算のし過ぎを防ぎます








3Dプログラミング入門講座
NAS6LIB
ポリゴンテスト解説・x3dom使い方
その1:ベクトル
その2:行列
その3:クォータニオン
その4:基本総復習・実践
その5:応用その1・メッシュアニメーション、動的テクスチャ
その6:応用その2・GLSL、カスタムシェーダー、キーボード、ファイル
その7:応用その3・ゲームプログラミング、タグの動的追加
その8:応用その4・GLSL、シェーダー、その2
その9:物理演算その1・電卓で相対性理論を解く方法
その10:物理演算その2・相対性理論的ニュートン力学
その11:物理演算その3・ケプラー方程式で惑星軌道シミュレーターを作る
その12:物理演算その4・ルンゲクッタ法で作った 相対性理論的ニュートン力学物理エンジンで惑星軌道シミュレーターを作る
その13:経路探索(A*:A-STAR)&巡回セールスマン問題 : 巨大サイズ : くろにゃんこ
その14:プログラミングにおける配列テーブルテクニック


 ■■■ THREE.JSプログラミング講座 ■■■ 
THREE.JSテスト解説・THREE.JS使い方
THREE.JS examplesをいじってみた(フレネル反射透過シェーダー)
THREE.JS (半透明シェーダー)
THREE.JS 3D演算で必要な計算(具体例)★とても重要★
THREE.JS THREE-VRM をいじってみた


<<prev ルンゲクッタ法で作った 相対性理論的ニュートン力学物理エンジンで惑星軌道シミュレーターを作る  : プログラミングにおける配列テーブルテクニック next>>





戻る