用Javascript實做簡單的路徑搜尋
Mon, 04 Sep 2006 14:02:02 +0800其實這個方法是在書上看到的,只是把它改成用Javascript來實現。
原來的方法適用在迷宮內可行走路徑寬度都是1時最適當,當迷宮有比較大的行走空間,就會有多餘的路徑(會在多餘空間裡來回走動)。好處是只要有可以到達的目標,就一定會找出路徑,速度也很快。
我把這個方法稍做修改,讓他至少能在起點與目標可直線到達,或是障礙不複雜的狀況下,可以用比較有效率的路徑到達目標。
程式如下:
var start = new Point (1,5);//開始的點座標 var end = new Point (2,3);//結束的點座標 var arr = new Array();//地圖陣列 var dim = 8;//迷宮大小,8*8 arr.push(new Array(1,1,0,0,0,0,0,1)); arr.push(new Array(0,0,0,0,0,0,0,1)); arr.push(new Array(1,0,1,1,1,0,0,1)); arr.push(new Array(1,0,0,1,1,1,0,1)); arr.push(new Array(1,1,1,1,0,0,0,1)); arr.push(new Array(1,0,0,0,0,0,0,1)); arr.push(new Array(0,0,0,0,0,0,0,1)); arr.push(new Array(1,1,0,0,0,0,0,0)); var _closed = new Array();//紀錄走過的路徑 var record = new Array(dim*dim);//紀錄可行走的路徑 //陣列內容會改變以紀錄走過的路徑,為了不破壞原來的資料,所以複製一份來用 for (var y=0; y<8; y++) { for (var x=0; x<8; x++) { var obj = document.getElementById(y+"_"+x); obj.innerHTML = " "; if (arr[y][x] == 0) { obj.style.background = "white"; record[y*dim+x] = 1;//可行走 } else { obj.style.background = "black"; record[y*dim+x] = 0;//不可行走 } } } //為了在表格中顯示找到的路徑用 var obj = document.getElementById(start.y+"_"+start.x); obj.innerHTML = "S"; obj.style.background= "red"; obj = document.getElementById(end.y+"_"+end.x); obj.innerHTML = "E"; //以上 direction = new Array();//定義方向的變數 //存放的是方向對於座標的偏移量 //依照在陣列中的索引,總共有0~7種方向 direction.push(new Point(-1,-1)); direction.push(new Point(-1,0)); direction.push(new Point(-1,1)); direction.push(new Point(0,1)); direction.push(new Point(1,1)); direction.push(new Point(1,0)); direction.push(new Point(1,-1)); direction.push(new Point(0,-1)); try { //初始起點的狀況 var triger = true; _closed.push(new Point(start.x, start.y)); record[start.y*dim+start.x] = 0; while (!start.compare(end) && triger) { alert("pause");//每次迭代都會暫停,顯示路徑搜尋的過程 getRouteNext();//決定下一個路徑的點,直到到達終點為止 } alert(_closed.length); } catch (e) {alert(e);} //函數:依照兩個點的相對關係來算出方向 function getDirection (_start, _end) { try { var tmp = Math.atan2(_end.x-_start.x, _end.y-_start.y); tmp = Math.floor(tmp / 2 / Math.PI * 360); if (tmp > -157.5 && tmp < -112.5) return 0; if (tmp > -112.5 && tmp < -67.5) return 1; if (tmp > -67.5 && tmp < -22.5) return 2; if (tmp > -22.5 && tmp < 22.5) return 3; if (tmp > 22.5 && tmp < 67.5) return 4; if (tmp > 67.5 && tmp < 112.5) return 5; if (tmp > 112.5 && tmp < 157.5) return 6; if (tmp > 157.5 || tmp < -157.5) return 7; } catch (e) {alert(e);} } //定義點的物件,可利用move方法來移動 function Point(_x, _y) { this.x = _x; this.y = _y; this.count = 0; this.compare = function (_point) { if (this.x==_point.x && this.y==_point.y) { return true; } else { return false; } } this.move = function (_direction) { this.x += direction[_direction].x; this.y += direction[_direction].y; var obj = document.getElementById(this.y+"_"+this.x); obj.innerHTML = 0; obj.style.background = "red"; } } //函數:決定下一個路徑的點,直到到達終點為止 function getRouteNext () { var dir = getDirection(start,end);//目前所在的點與目標的點的方向 var dirarr = makeDirection(dir);//依照方向產生依序要測試的點陣列 var test = 0; for (var i=0; i -1 && start.x + direction[dirarr[i]].x < dim && start.y + direction[dirarr[i]].y > -1 && start.y + direction[dirarr[i]].y < dim && record[(start.y+direction[dirarr[i]].y)*dim+start.x+direction[dirarr[i]].x] == 1 ) { start.move(dirarr[i]);//如果測試的點可行走,則移動到這個點 _closed.push(new Point(start.x,start.y));//將點存入路徑中 record[start.y*dim+start.x] = 0;//將點標示為不可行走(已走過) return dirarr[i]; } } //test==8時,表示目前走到的這一格無法再走下去 //必須退回前一格測試其他可行的路徑 if (test == 8) { tmp = _closed.pop(); if (_closed.length == 0) {//退回原點表示無路可走,終點無法到達 alert("no road to target!!!");//顯示錯誤訊息 triger = false;//跳出while迴圈 } else { //否則就後退一步 start = _closed[_closed.length-1]; var obj = document.getElementById(tmp.y+"_"+tmp.x); obj.innerHTML = 1; obj.style.background = "white"; } } } //傳入起始方向,傳回以起始方向為中心的方向陣列 //方向的改變方式仍會影響路徑的搜尋 function makeDirection (_init) { try { if (_init > 7 || _init < 0) throw "Initial direction must between 0 and 7."; var arr1 = new Array(); arr1.push(_init); arr1.push(shiftDirection(_init,-1)); arr1.push(shiftDirection(_init,1)); arr1.push(shiftDirection(_init,-2)); arr1.push(shiftDirection(_init,2)); arr1.push(shiftDirection(_init,-3)); arr1.push(shiftDirection(_init,3)); arr1.push(shiftDirection(_init,4)); return arr1; } catch (e) { alert(e); } } //傳入方向與要計算的偏移量,傳回正確的方向 function shiftDirection(_dir, _shift) { var ret = _dir + _shift; if (ret > 7) { ret -= 8; } else if (ret < 0) { ret += 8; } return ret; }
我用一個表格來顯示迷宮以及路徑搜尋的狀況。請參考以下的例子:
原始的方法:
改良過的方法:
改變一下起點與終點,可以發現其實改良過的方法在特定狀況下效果還是不好。在某些起點與終點的組合中,甚至會走遍迷宮才走到終點,而不是較有效率的路徑。這還是要使用A*法才能辦得到吧。