ブラウザ三国志でダイクストラを行ってみる。

「ブラウザ三国志」というゲームがあります。
そのゲームでは領地の奪い合い、砦攻略を目指して軍を進めていきます。
基本ゲームはしませんが、「ソーシャルゲーム」という分野においての勉強としてずっと続けています。いやバランス良くて本当に面白い。。。ってそんな事やってる場合じゃない＞＜


ChromeExtentionの仕組みみたいな部分での調査が大きいので「処理速度」や汚さは勘弁してください。あくまでそんな事できるんだ。程度でお読みください。

思い立ち

さてブラウザ三国志で砦攻略で重要になってくるのが、座標計算です。
次の砦に向かうという時に領地レベル☆１をめがけて経路を作ってつなげていきます。
自分１人でやっていくのはいいのですが、「同盟」を組んで同盟員とつなげていくと

「今度ここー」
「次私ここー」

みたいな事が起こってきます。
それを掲示板等で共有して進んでいくわけです。ソーシャルですねぇー。

で「ここ」って決めてく経路があるのです。
で、既にツール等もあるのですが、せっかくだから自分で作ってみよー！って思ったわけです。
ひとまずChromeExtensionで行きます。

今回は簡単に「51x51マップ」内で指定した座標間を結ぶ。をやってみましょう。

動きとしては
・51x51マップ時のみに動作する
　・座標を取得してくる
　・ダイクストラで経路を算出する
　・算出した経路をHTML表示する

って流れですかね。

Chrome Extentionを作成してみよう！

さて、まずはボタンを表示してみましょう。
ここを元に構成を勉強して、、、とひとまずHTMLを書けました。

こんな感じ。





ブラ三おなじみのアイコンで、
アイコンをクリックするとHTMLを出力してくれるようになりました。

座標データを収集

さて、このツールは何につけても座標データが存在しないといけません。

って事で
・HTMLのデータを取得
・そこから座標データを抜き出す！
という流れを説明します。

まず51x51マップか、、、という判定。
既存のページ(対象のHTML)の要素を取得するには先ほどのページで使った
「browser_action」とは別に「content_scripts」という仕組みを使用する方法があります。

以下をmanifest.jsonに追記します。

view plainprint?

1. "content_scripts": [  
2.   {  
3.     "matches": [  
4.       "http://m21.3gokushi.jp/big_map.php*"  
5.     ],  
6.   
7.     "js" : [  
8.       "script.js"  
9.     ],  
10.   
11.     "run_at": "document_end",  
12.     "all_frames": true  
13. ]  

  "content_scripts": [
    {
      "matches": [
        "http://m21.3gokushi.jp/big_map.php*"
      ],

      "js" : [
        "script.js"
      ],

      "run_at": "document_end",
      "all_frames": true
  ]

※要素のつなぎは「,」を忘れずに。

という風に記述します。
matchesはそのページに来たら。jsは使用するJavaScript、run_atはどのタイミングで動作するか？です。
all_frameはすべてのフレームに対して処理を行うか？を記述します。

manifest.jsonは更新したら再読込の必要あります。
これらを思い通りに動かせる(読み込み失敗とかがない)ようになるまでは
Googleのトップページで練習した方が良いかもです。

ブラウザ三国志(mixi)ですが難しいのはページの構成ですね。
URLはもちろんmixiを指しますが、アプリ自体は
「"http://m21.3gokushi.jp/big_map.php*"」にアクセスしています。
なので、それをマッチに入れて、Frameをtrueにしているわけです。

ここまでで、ひとまず「全体地図」のクリックで動作するか確認しておくべきでしょう。

そこまでできたらアプリケーションが使用しているHTMLをハックします。
そうすれば



というコードが存在するので、このデータを

view plainprint?

1. var map51 = document.getElementById( "map51-wrapper" );  
2. if ( map51 == null ) {  
3.   return;  
4. }  

var map51 = document.getElementById( "map51-wrapper" );
if ( map51 == null ) {
  return;
}

という感じでデータを取得してきます。
その中に

view plainprint?

1. <a   
2. href=​"/​land.php?x=-22&y=-52#ptop"   
3. onmouseover=​"return gloss('  
4.   
5. <​dl class="​bigmap"​>  
6. ​<​dt class="​bigmap-caption"​>​空き地<​/​dt>  
7. ​<​dd class="​bigmap-subcap"​>​&​nbsp;​<​/​dd>  
8. ​<​dt>​座標&​nbsp;​/​&​nbsp;​距離<​/​dt>​  
9. <​dd>​(-22,-52)​&​nbsp;​/​&​nbsp;​[35.36]​<​/​dd>​  
10. <​dt>​戦力<​/​dt>  
11. ​<​dd>​★<​/​dd>​  
12. <​dt class="​bottom-popup-l"​>​資源<​/​dt>  
13. ​<​dd class="​bottom-popup-r"​>​木1&​nbsp;​岩0&​nbsp;​鉄0&​nbsp;​糧0<​/​dd>​<​/​dl>​'  
14.   
15. )​;​" onmouseout=​"nd()​;​">​  
16. 1​  
17. </a>  

<a 
href=​"/​land.php?x=-22&y=-52#ptop" 
onmouseover=​"return gloss('

<​dl class="​bigmap"​>
​<​dt class="​bigmap-caption"​>​空き地<​/​dt>
​<​dd class="​bigmap-subcap"​>​&​nbsp;​<​/​dd>
​<​dt>​座標&​nbsp;​/​&​nbsp;​距離<​/​dt>​
<​dd>​(-22,-52)​&​nbsp;​/​&​nbsp;​[35.36]​<​/​dd>​
<​dt>​戦力<​/​dt>
​<​dd>​★<​/​dd>​
<​dt class="​bottom-popup-l"​>​資源<​/​dt>
​<​dd class="​bottom-popup-r"​>​木1&​nbsp;​岩0&​nbsp;​鉄0&​nbsp;​糧0<​/​dd>​<​/​dl>​'

)​;​" onmouseout=​"nd()​;​">​
1​
</a>

というデータがありますので取得します。

view plainprint?

1. // ULタグを取得  
2. var mapUlList = map51.getElementsByTagName("ul");  
3. for ( var ulIdx = 0; ulIdx < mapUlList.length; ++ulIdx ) {  
4.   // 内部のLiタグを取得  
5.   var mapLiList = mapUlList[ulIdx].getElementsByTagName("li");  
6.   for ( var liIdx = 0; liIdx < mapUlList.length; ++liIdx ) {  
7.     // Aタグを取得  
8.     var linkTag = mapLiList[liIdx].getElementsByTagName("a")[0];  
9.     dijkstra.pointArray[ulIdx][liIdx] = createPoint(linkTag);  
10.   }  
11. }  

// ULタグを取得
var mapUlList = map51.getElementsByTagName("ul");
for ( var ulIdx = 0; ulIdx < mapUlList.length; ++ulIdx ) {
  // 内部のLiタグを取得
  var mapLiList = mapUlList[ulIdx].getElementsByTagName("li");
  for ( var liIdx = 0; liIdx < mapUlList.length; ++liIdx ) {
    // Aタグを取得
    var linkTag = mapLiList[liIdx].getElementsByTagName("a")[0];
    dijkstra.pointArray[ulIdx][liIdx] = createPoint(linkTag);
  }
}

createPoint(linkTag)で座標データを解析しています。

+ expand sourceview plainprint?

1. var createPoint = function ( linkTag ) {  
2.   
3.   var point = {};  
4.   point.x    = 0;  
5.   point.y    = 0;  
6.   point.team = "";  
7.   point.lv   = 0;  
8.   
9.   var lv  = replaceAll(linkTag.innerHTML,"\n","");  
10.   if ( lv != "1" && lv != "2" && lv != "3" && lv != "4" && lv != "5" ) {  
11.     return point;  
12.   }  
13.   point.lv = parseFloat(lv);  
14.   if ( point.lv != 1 ) {  
15.    point.lv = parseFloat(lv) *  parseFloat(lv);  
16.   }  
17.   // 文字列に変換  
18.   var text = linkTag.outerHTML;  
19.   
20.   // リンクタグの解析  
21.   var firstIdx = text.indexOf("'");  
22.   var lastIdx  = text.lastIndexOf("'");   
23.   var data = text.slice(firstIdx+1,lastIdx);  
24.   
25.   data = replaceAll(data,"<","<");  
26.   data = replaceAll(data,">",">");  
27.   data = replaceAll(data,""","'");  
28.   data = replaceAll(data,"&","&");  
29.   data = replaceAll(data,"&n"," ");  
30.   data = replaceAll(data," bsp;"," ");  
31.   
32.   var dp = new DOMParser();  
33.   var doc = dp.parseFromString(data, "text/xml");  
34.   
35.   var dtTags = doc.getElementsByTagName("dt");  
36.   var ddTags = doc.getElementsByTagName("dd");  
37.   
38.   // タグ数回繰り返す  
39.   for ( var idx = 0; idx < dtTags.length; ++idx ) {  
40.   
41.     var dtTag = dtTags[idx];  
42.     var tagVal = dtTag.firstChild.data;  
43.   
44.     if ( tagVal == "君主名" ) {  
45.       point.team = ddTags[idx].firstChild.data;  
46.     } else if ( tagVal == "座標 / 距離") {  
47.       var tagData = ddTags[idx].firstChild.data;  
48.       var startP = tagData.indexOf("(");  
49.       var endP   = tagData.lastIndexOf(")");   
50.       var pointData = tagData.slice(startP+1,endP);  
51.       var pointArray = pointData.split(",");  
52.       point.x = pointArray[0];  
53.       point.y = pointArray[1];  
54.     }  
55.   }  
56.   
57.   return point;  
58. };  

var createPoint = function ( linkTag ) {

  var point = {};
  point.x    = 0;
  point.y    = 0;
  point.team = "";
  point.lv   = 0;

  var lv  = replaceAll(linkTag.innerHTML,"\n","");
  if ( lv != "1" && lv != "2" && lv != "3" && lv != "4" && lv != "5" ) {
    return point;
  }
  point.lv = parseFloat(lv);
  if ( point.lv != 1 ) {
   point.lv = parseFloat(lv) *  parseFloat(lv);
  }
  // 文字列に変換
  var text = linkTag.outerHTML;

  // リンクタグの解析
  var firstIdx = text.indexOf("'");
  var lastIdx  = text.lastIndexOf("'"); 
  var data = text.slice(firstIdx+1,lastIdx);

  data = replaceAll(data,"<","<");
  data = replaceAll(data,">",">");
  data = replaceAll(data,""","'");
  data = replaceAll(data,"&","&");
  data = replaceAll(data,"&n"," ");
  data = replaceAll(data," bsp;"," ");

  var dp = new DOMParser();
  var doc = dp.parseFromString(data, "text/xml");

  var dtTags = doc.getElementsByTagName("dt");
  var ddTags = doc.getElementsByTagName("dd");

  // タグ数回繰り返す
  for ( var idx = 0; idx < dtTags.length; ++idx ) {

    var dtTag = dtTags[idx];
    var tagVal = dtTag.firstChild.data;

    if ( tagVal == "君主名" ) {
      point.team = ddTags[idx].firstChild.data;
    } else if ( tagVal == "座標 / 距離") {
      var tagData = ddTags[idx].firstChild.data;
      var startP = tagData.indexOf("(");
      var endP   = tagData.lastIndexOf(")"); 
      var pointData = tagData.slice(startP+1,endP);
      var pointArray = pointData.split(",");
      point.x = pointArray[0];
      point.y = pointArray[1];
    }
  }

  return point;
};

相手が存在する場合等もありますから、
x,y,同盟名,lv(領地の強さ)を設定したpointオブジェクトを貯めこんでおきます。
パーサを使用していますが、大きなマップ等になったら変更する予定ではあります。
※51x51ではそんなに重くなかった。

。。。さぁこれで座標データの抜き出しはOKです。
ダイクストラを行ってみましょう！

ダイクストラで最短経路を算出

さて座標データはすべて取得できたので、そのデータから最短経路を算出してみましょう。
実際のソースを貼っておきます。

+ expand sourceview plainprint?

1. //Map51x51かを確認  
2. var map51 = document.getElementById( "map51-content" );  
3. if ( map51 == null ) {  
4.   return;  
5. }  
6.   
7. var MAX_X = 51;  
8. var MAX_Y = 51;  
9.   
10. // ダイクストラのロジック  
11. var dijkstra = {};  
12.   
13. // 座標データ  
14. dijkstra.pointArray = new Array(MAX_X);  
15. for ( var idx = 0; idx < dijkstra.pointArray.length; ++idx ) {  
16.   dijkstra.pointArray[idx] = new Array(MAX_Y);  
17. }  
18.   
19. // 経路算出  
20. dijkstra.getRoute = function(startX,startY,endX,endY){  
21.   
22.   // その座標まで行くルート  
23.   var workRouteArray = new Array(MAX_X);  
24.   // 決定している距離  
25.   var pointArray = new Array(MAX_X);  
26.   // すべての配列を初期化  
27.   for ( var xidx = 0; xidx < workRouteArray.length; ++xidx ) {  
28.     workRouteArray[xidx] = new Array(MAX_Y);  
29.     pointArray[xidx] = new Array(MAX_Y);  
30.     for ( var yidx = 0; yidx < pointArray[xidx].length; ++yidx ) {  
31.       workRouteArray[xidx][yidx] = null;  
32.       pointArray[xidx][yidx] = Number.POSITIVE_INFINITY;  
33.     }  
34.   }  
35.   
36.   // 作業する座標  
37.   var workPointArray = new Array();  
38.   
39.   // 始点オブジェクト  
40.   var nowPoint = dijkstra.pointArray[startX][startY];  
41.   var nowX = startX;  
42.   var nowY = startY;  
43.   var nowLen = 0;  
44.   
45.   // 作業用のリストを取得する  
46.   workRouteArray[nowX][nowY] = new Array();  
47.   var nowRoute;  
48.   
49.   while ( true ) {  
50.   
51.  pointArray[nowX][nowY] = nowLen;  
52.  nowRoute = workRouteArray[nowX][nowY];  
53.   
54.     // 近隣の座標を算出  
55.     for ( var addX = -1; addX <= 1; ++addX ) {  
56.   
57.       var wkX = nowX + addX;  
58.       if ( wkX < 0 ) continue;  
59.       if ( wkX >= MAX_X ) continue;  
60.        
61.       // 周りを見渡す  
62.       for ( var addY = -1; addY <= 1; ++addY ) {  
63.          
64.         var wkY = nowY + addY;  
65.         if ( wkY < 0 ) continue;  
66.         if ( wkY >= MAX_Y ) continue;  
67.   
68.         // 既に決定済の場合  
69.         if ( pointArray[wkX][wkY] != Number.POSITIVE_INFINITY ) {  
70.           continue;  
71.         }  
72.   
73.         // その座標のルートを取得  
74.         var workRoute = workRouteArray[wkX][wkY];  
75.         // そこに行っていいのか？  
76.         if ( workRoute === undefined ) {  
77.           continue;  
78.         }  
79.   
80.         // 作業中の場所を取得  
81.         var point = dijkstra.pointArray[wkX][wkY];  
82.   
83.         //既に存在した場合  
84.         if ( workRoute != null ) {  
85.          var workLen = workRoute.length;  
86.          var nowRouteLen  = nowRoute.length;  
87.          //作業用のリストが短い場合  
88.          if ( (workLen - 1) <= nowRouteLen ) {  
89.           continue;  
90.          }  
91.   
92.          var workLv = 0;  
93.          //TODO レベル加算を見る必要あり  
94.          for ( var idx = 0; idx < workLen; ++idx ) {  
95.           var point = workRoute[idx];  
96.           var lv = parseFloat(point.lv);  
97.           workLv = workLv + lv;  
98.          }  
99.   
100.          if ( (nowLen + parseFloat(point.lv)) > workLv  ) {  
101.           continue;  
102.          }  
103.         }  
104.   
105.         // 行けない場所だった場合  
106.         if ( point.lv == "0" ) {  
107.           // 行っちゃダメにする  
108.           workRouteArray[wkX][wkY] = undefined;  
109.           continue;  
110.         }  
111.   
112.         var newRoute = new Array();  
113.         for (var i=0, l= nowRoute.length; i<l; i++) {  
114.             newRoute[i] = nowRoute[i];  
115.         }  
116.   
117.         //その地点を設定  
118.         newRoute.push(point);  
119.         // 作業用のルートを作成  
120.         workRouteArray[wkX][wkY] = newRoute;  
121.   
122.         // 作業の配列に座標を指定  
123.         var workPoint = {};  
124.         workPoint.x = wkX;  
125.         workPoint.y = wkY;  
126.   
127.         workPointArray.push(workPoint);  
128.       }  
129.     }  
130.   
131.     //console.log(workPointArray.length);  
132.     //for ( var cnt = 0; cnt < workPointArray.length; ++cnt ) {  
133.      //console.log("作業リスト" + workPointArray[cnt].x + ":" + workPointArray[cnt].y);  
134.     //}  
135.   
136.     var minLen = Number.POSITIVE_INFINITY;  
137.     var deleteIdx = 0;  
138.   
139.     // 作業リスト数回繰り返す  
140.     for ( var cnt = 0; cnt < workPointArray.length; ++cnt ) {  
141.        
142.      var workPoint = workPointArray[cnt];  
143.         var wkX = workPoint.x;  
144.         var wkY = workPoint.y;  
145.     
146.      var workRoute = workRouteArray[wkX][wkY];  
147.      var wkLen = 0;  
148.   
149.      for ( var idx = 0; idx < workRoute.length; ++idx ) {  
150.       var point = workRoute[idx];  
151.       var lv = parseFloat(point.lv);  
152.       wkLen = wkLen + lv;  
153.      }  
154.   
155.      // 設定できた場合  
156.      if ( minLen == Number.POSITIVE_INFINITY || wkLen < minLen ) {  
157.       minLen = wkLen;  
158.   
159.       nowX = wkX;  
160.       nowY = wkY;  
161.       nowLen = wkLen;  
162.       deleteIdx = cnt;  
163.      }  
164.     }  
165.   
166.   
167.     // 行く所がない場合  
168.     if ( minLen == Number.POSITIVE_INFINITY ) {  
169.       break;  
170.     }  
171.     workPointArray.splice(deleteIdx, 1);  
172.       
173.     // 現在の点を編集  
174.     nowPoint = this.pointArray[nowX][nowY];  
175.  //console.log("[" + nowPoint.x + "," + nowPoint.y + "]" + nowPoint.lv );  
176.     // 終点と同一点だった場合  
177.     if ( nowX == endX && nowY == endY ) {  
178.       // 作業ルートから取得  
179.       return workRouteArray[endX][endY];  
180.     }  
181.   }  
182.   
183.   // 決まらなかった場合  
184.   return null;  
185. };  
186.   
187. var nbsp = String.fromCharCode( 160 );  
188. // 全ての文字列 s1 を s2 に置き換える  
189. function replaceAll(expression, org, dest){    
190.     return expression.split(org).join(dest);    
191. }    
192.   
193. var createPoint = function ( linkTag ) {  
194.   
195.   var point = {};  
196.   point.x    = 0;  
197.   point.y    = 0;  
198.   point.team = "";  
199.   point.lv   = 0;  
200.   
201.   var lv  = replaceAll(linkTag.innerHTML,"\n","");  
202.   if ( lv != "1" && lv != "2" && lv != "3" && lv != "4" && lv != "5" ) {  
203.     return point;  
204.   }  
205.   point.lv = parseFloat(lv);  
206.   if ( point.lv != 1 ) {  
207.    point.lv = parseFloat(lv) *  parseFloat(lv);  
208.   }  
209.   // 文字列に変換  
210.   var text = linkTag.outerHTML;  
211.   
212.   // リンクタグの解析  
213.   var firstIdx = text.indexOf("'");  
214.   var lastIdx  = text.lastIndexOf("'");   
215.   var data = text.slice(firstIdx+1,lastIdx);  
216.   
217.   data = replaceAll(data,"<","<");  
218.   data = replaceAll(data,">",">");  
219.   data = replaceAll(data,""","'");  
220.   data = replaceAll(data,"&","&");  
221.   data = replaceAll(data,"&n"," ");  
222.   data = replaceAll(data," bsp;"," ");  
223.   
224.   var dp = new DOMParser();  
225.   var doc = dp.parseFromString(data, "text/xml");  
226.   
227.   var dtTags = doc.getElementsByTagName("dt");  
228.   var ddTags = doc.getElementsByTagName("dd");  
229.   
230.   // タグ数回繰り返す  
231.   for ( var idx = 0; idx < dtTags.length; ++idx ) {  
232.   
233.     var dtTag = dtTags[idx];  
234.     var tagVal = dtTag.firstChild.data;  
235.   
236.     if ( tagVal == "君主名" ) {  
237.       point.team = ddTags[idx].firstChild.data;  
238.     } else if ( tagVal == "座標 / 距離") {  
239.       var tagData = ddTags[idx].firstChild.data;  
240.       var startP = tagData.indexOf("(");  
241.       var endP   = tagData.lastIndexOf(")");   
242.       var pointData = tagData.slice(startP+1,endP);  
243.       var pointArray = pointData.split(",");  
244.       point.x = pointArray[0];  
245.       point.y = pointArray[1];  
246.     }  
247.   }  
248.   
249.   return point;  
250. };  
251.   
252.   
253. console.log("start");  
254. // ULタグを取得  
255. var mapUlList = map51.getElementsByTagName("ul");  
256. for ( var ulIdx = 0; ulIdx < mapUlList.length; ++ulIdx ) {  
257.   // 内部のLiタグを取得  
258.   var mapLiList = mapUlList[ulIdx].getElementsByTagName("li");  
259.   for ( var liIdx = 0; liIdx < mapUlList.length; ++liIdx ) {  
260.     // Aタグを取得  
261.     var linkTag = mapLiList[liIdx].getElementsByTagName("a")[0];  
262.     dijkstra.pointArray[ulIdx][liIdx] = createPoint(linkTag);  
263.   }  
264. }  
265.   
266. console.log("getRoute()");  
267. var route;  
268. route = dijkstra.getRoute(0,0,50,50);  
269. if ( route != null ) {  
270.  console.log("route log:" + route.length);  
271.  for ( var idx = 0; idx < route.length; ++idx ) {  
272.   var point = route[idx];  
273.   console.log("[" + point.x + "," + point.y + "]" + point.lv );  
274.  }  
275. }  
276. console.log("end");  

//Map51x51かを確認
var map51 = document.getElementById( "map51-content" );
if ( map51 == null ) {
  return;
}

var MAX_X = 51;
var MAX_Y = 51;

// ダイクストラのロジック
var dijkstra = {};

// 座標データ
dijkstra.pointArray = new Array(MAX_X);
for ( var idx = 0; idx < dijkstra.pointArray.length; ++idx ) {
  dijkstra.pointArray[idx] = new Array(MAX_Y);
}

// 経路算出
dijkstra.getRoute = function(startX,startY,endX,endY){

  // その座標まで行くルート
  var workRouteArray = new Array(MAX_X);
  // 決定している距離
  var pointArray = new Array(MAX_X);
  // すべての配列を初期化
  for ( var xidx = 0; xidx < workRouteArray.length; ++xidx ) {
    workRouteArray[xidx] = new Array(MAX_Y);
    pointArray[xidx] = new Array(MAX_Y);
    for ( var yidx = 0; yidx < pointArray[xidx].length; ++yidx ) {
      workRouteArray[xidx][yidx] = null;
      pointArray[xidx][yidx] = Number.POSITIVE_INFINITY;
    }
  }

  // 作業する座標
  var workPointArray = new Array();

  // 始点オブジェクト
  var nowPoint = dijkstra.pointArray[startX][startY];
  var nowX = startX;
  var nowY = startY;
  var nowLen = 0;

  // 作業用のリストを取得する
  workRouteArray[nowX][nowY] = new Array();
  var nowRoute;

  while ( true ) {

 pointArray[nowX][nowY] = nowLen;
 nowRoute = workRouteArray[nowX][nowY];

    // 近隣の座標を算出
    for ( var addX = -1; addX <= 1; ++addX ) {

      var wkX = nowX + addX;
      if ( wkX < 0 ) continue;
      if ( wkX >= MAX_X ) continue;
     
      // 周りを見渡す
      for ( var addY = -1; addY <= 1; ++addY ) {
       
        var wkY = nowY + addY;
        if ( wkY < 0 ) continue;
        if ( wkY >= MAX_Y ) continue;

        // 既に決定済の場合
        if ( pointArray[wkX][wkY] != Number.POSITIVE_INFINITY ) {
          continue;
        }

        // その座標のルートを取得
        var workRoute = workRouteArray[wkX][wkY];
        // そこに行っていいのか？
        if ( workRoute === undefined ) {
          continue;
        }

        // 作業中の場所を取得
        var point = dijkstra.pointArray[wkX][wkY];

        //既に存在した場合
        if ( workRoute != null ) {
         var workLen = workRoute.length;
         var nowRouteLen  = nowRoute.length;
         //作業用のリストが短い場合
         if ( (workLen - 1) <= nowRouteLen ) {
          continue;
         }

         var workLv = 0;
         //TODO レベル加算を見る必要あり
         for ( var idx = 0; idx < workLen; ++idx ) {
          var point = workRoute[idx];
          var lv = parseFloat(point.lv);
          workLv = workLv + lv;
         }

         if ( (nowLen + parseFloat(point.lv)) > workLv  ) {
          continue;
         }
        }

        // 行けない場所だった場合
        if ( point.lv == "0" ) {
          // 行っちゃダメにする
          workRouteArray[wkX][wkY] = undefined;
          continue;
        }

        var newRoute = new Array();
        for (var i=0, l= nowRoute.length; i<l; i++) {
            newRoute[i] = nowRoute[i];
        }

        //その地点を設定
        newRoute.push(point);
        // 作業用のルートを作成
        workRouteArray[wkX][wkY] = newRoute;

        // 作業の配列に座標を指定
        var workPoint = {};
        workPoint.x = wkX;
        workPoint.y = wkY;

        workPointArray.push(workPoint);
      }
    }

    //console.log(workPointArray.length);
    //for ( var cnt = 0; cnt < workPointArray.length; ++cnt ) {
     //console.log("作業リスト" + workPointArray[cnt].x + ":" + workPointArray[cnt].y);
    //}

    var minLen = Number.POSITIVE_INFINITY;
    var deleteIdx = 0;

    // 作業リスト数回繰り返す
    for ( var cnt = 0; cnt < workPointArray.length; ++cnt ) {
     
     var workPoint = workPointArray[cnt];
        var wkX = workPoint.x;
        var wkY = workPoint.y;
  
     var workRoute = workRouteArray[wkX][wkY];
     var wkLen = 0;

     for ( var idx = 0; idx < workRoute.length; ++idx ) {
      var point = workRoute[idx];
      var lv = parseFloat(point.lv);
      wkLen = wkLen + lv;
     }

     // 設定できた場合
     if ( minLen == Number.POSITIVE_INFINITY || wkLen < minLen ) {
      minLen = wkLen;

      nowX = wkX;
      nowY = wkY;
      nowLen = wkLen;
      deleteIdx = cnt;
     }
    }


    // 行く所がない場合
    if ( minLen == Number.POSITIVE_INFINITY ) {
      break;
    }
    workPointArray.splice(deleteIdx, 1);
    
    // 現在の点を編集
    nowPoint = this.pointArray[nowX][nowY];
 //console.log("[" + nowPoint.x + "," + nowPoint.y + "]" + nowPoint.lv );
    // 終点と同一点だった場合
    if ( nowX == endX && nowY == endY ) {
      // 作業ルートから取得
      return workRouteArray[endX][endY];
    }
  }

  // 決まらなかった場合
  return null;
};

var nbsp = String.fromCharCode( 160 );
// 全ての文字列 s1 を s2 に置き換える
function replaceAll(expression, org, dest){  
    return expression.split(org).join(dest);  
}  

var createPoint = function ( linkTag ) {

  var point = {};
  point.x    = 0;
  point.y    = 0;
  point.team = "";
  point.lv   = 0;

  var lv  = replaceAll(linkTag.innerHTML,"\n","");
  if ( lv != "1" && lv != "2" && lv != "3" && lv != "4" && lv != "5" ) {
    return point;
  }
  point.lv = parseFloat(lv);
  if ( point.lv != 1 ) {
   point.lv = parseFloat(lv) *  parseFloat(lv);
  }
  // 文字列に変換
  var text = linkTag.outerHTML;

  // リンクタグの解析
  var firstIdx = text.indexOf("'");
  var lastIdx  = text.lastIndexOf("'"); 
  var data = text.slice(firstIdx+1,lastIdx);

  data = replaceAll(data,"<","<");
  data = replaceAll(data,">",">");
  data = replaceAll(data,""","'");
  data = replaceAll(data,"&","&");
  data = replaceAll(data,"&n"," ");
  data = replaceAll(data," bsp;"," ");

  var dp = new DOMParser();
  var doc = dp.parseFromString(data, "text/xml");

  var dtTags = doc.getElementsByTagName("dt");
  var ddTags = doc.getElementsByTagName("dd");

  // タグ数回繰り返す
  for ( var idx = 0; idx < dtTags.length; ++idx ) {

    var dtTag = dtTags[idx];
    var tagVal = dtTag.firstChild.data;

    if ( tagVal == "君主名" ) {
      point.team = ddTags[idx].firstChild.data;
    } else if ( tagVal == "座標 / 距離") {
      var tagData = ddTags[idx].firstChild.data;
      var startP = tagData.indexOf("(");
      var endP   = tagData.lastIndexOf(")"); 
      var pointData = tagData.slice(startP+1,endP);
      var pointArray = pointData.split(",");
      point.x = pointArray[0];
      point.y = pointArray[1];
    }
  }

  return point;
};


console.log("start");
// ULタグを取得
var mapUlList = map51.getElementsByTagName("ul");
for ( var ulIdx = 0; ulIdx < mapUlList.length; ++ulIdx ) {
  // 内部のLiタグを取得
  var mapLiList = mapUlList[ulIdx].getElementsByTagName("li");
  for ( var liIdx = 0; liIdx < mapUlList.length; ++liIdx ) {
    // Aタグを取得
    var linkTag = mapLiList[liIdx].getElementsByTagName("a")[0];
    dijkstra.pointArray[ulIdx][liIdx] = createPoint(linkTag);
  }
}

console.log("getRoute()");
var route;
route = dijkstra.getRoute(0,0,50,50);
if ( route != null ) {
 console.log("route log:" + route.length);
 for ( var idx = 0; idx < route.length; ++idx ) {
  var point = route[idx];
  console.log("[" + point.x + "," + point.y + "]" + point.lv );
 }
}
console.log("end");

このコードでは0,0 - 51,51を算出するわけですが、あくまで動作確認ように行なっているだけです。
実際には、始点座標から終点座標を入力するのが良いですね。

実際のコードのcreatePoint()はLvに対してべき乗の重みを付けています。


画面に表示してみよう

さて、座標は判定できたのでそのままHTMLに表示していきます。

view plainprint?

1. route = dijkstra.getRoute(0,0,50,50);  
2. var pointArray = new Array();  
3.   
4. //経路のリストを連想配列に入れる  
5. for ( var idx = 0; idx < route.length; ++idx ) {  
6.  var point = route[idx];  
7.  pointArray[point.arrayX + "," + point.arrayY] = point;  
8. }  
9.   
10. for ( var ulIdx = 0; ulIdx < mapUlList.length; ++ulIdx ) {  
11.   // 内部のLiタグを取得  
12.   var mapLiList = mapUlList[ulIdx].getElementsByTagName("li");  
13.   for ( var liIdx = 0; liIdx < mapUlList.length; ++liIdx ) {  
14.     
15.    var idx = pointArray[ulIdx + "," + liIdx];  
16.    if ( idx === undefined ) {  
17.     continue;  
18.    }  
19.    // Aタグを取得  
20.    var liTag = mapLiList[liIdx];  
21.    liTag.style.backgroundColor = "#555555";  
22.   
23.   }  
24. }  
25.    

route = dijkstra.getRoute(0,0,50,50);
var pointArray = new Array();

//経路のリストを連想配列に入れる
for ( var idx = 0; idx < route.length; ++idx ) {
 var point = route[idx];
 pointArray[point.arrayX + "," + point.arrayY] = point;
}

for ( var ulIdx = 0; ulIdx < mapUlList.length; ++ulIdx ) {
  // 内部のLiタグを取得
  var mapLiList = mapUlList[ulIdx].getElementsByTagName("li");
  for ( var liIdx = 0; liIdx < mapUlList.length; ++liIdx ) {
  
   var idx = pointArray[ulIdx + "," + liIdx];
   if ( idx === undefined ) {
    continue;
   }
   // Aタグを取得
   var liTag = mapLiList[liIdx];
   liTag.style.backgroundColor = "#555555";

  }
}
 

配列のポイントがあった方が処理しやすかったので
routeのオブジェクトにarrayX,arrayYを設定しています。

あとはULとLI回回して背景を変更するって感じです。
で出来上がったマップが以下の通り。


コードにより☆５までしか判定してないので最終地点に拠点等が存在すると
経路算出でエラーになります。

ここに載っているように世界にすぐ配信できます。
権利関係微妙ですが他のツール等に比べるとおとなしいので公開しておきました
誰かアイコン作って！（128x128pngしか受け付けない＞＜）

仕事中に呆けて遊んでいたのでやっとアウトプットできた感じ＞＜

今回のマップのダイクストラでの醍醐味は
重さが領地のレベルである事。☆２を進んだ時に遠征だときついだとか
その辺を考慮して重さを設定するところですね。

このソースを利用してマップをDBに貯めこんで計算してとかやれば大規模な遠征の道順等も教えてくれるはずです。
これをつくりはじめた時に、AppEngineを利用して
座標を全ユーザから送信してもらって、それで地図を更新して行くという仕様を考えましたけど
本気で行くと有料レベルになると思って止めました。
※お金発生してもOKですけど、お金取る(CM)とか入れると厄介かなぁと。。。

今回はゲーム周りでしたが、Tweetボタンやいいねボタンがないようなページを
簡単に共有したり、その他他人のWebページに１つエッセンスを加えて処理をやりやすくしたり、
Webのマクロみたいなイメージで処理する事が可能になります。

ChromeExtentionはChromeOSの登場によって
ChromeOS上で動作するアプリケーションを作れる事になります。
ChromeOSがどの程度市場を席巻するかは不明ですが、１つのアプリの公開形態としては
注視しておいても良いでしょう。

さぁ同盟員に書簡して使ってもらおう！