diff options
Diffstat (limited to 'SameGameJS/samegame.js')
-rwxr-xr-x | SameGameJS/samegame.js | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/SameGameJS/samegame.js b/SameGameJS/samegame.js new file mode 100755 index 0000000..6bac624 --- /dev/null +++ b/SameGameJS/samegame.js @@ -0,0 +1,326 @@ +var dimpx,dim,cc; +var seed,cscore; +var board=null; +var boarde=null; +var dx=[0,1,0,-1]; +var dy=[-1,0,1,0]; +var pendingrem=[]; +var sol=[]; +var optscore; +var ismobile; +String.prototype.getHash=function() +{ + var ret=0,ch; + if(this.length===0)return ret; + for(var i=0;i<this.length;++i) + { + ch=this.charCodeAt(i); + ret=((ret<<5)-ret)+ch;ret>>>=0; + } + return ret; +} +function randomInt(min,max) +{ + seed*=214013;seed+=2531011;seed&=0xffffffff; + return min+(seed^seed>>15)%(max-min+1); +} + +function init() +{ + if( navigator.userAgent.match(/Android/i) + || navigator.userAgent.match(/webOS/i) + || navigator.userAgent.match(/iPhone/i) + || navigator.userAgent.match(/iPad/i) + || navigator.userAgent.match(/iPod/i) + || navigator.userAgent.match(/BlackBerry/i) + || navigator.userAgent.match(/Windows Phone/i) + ) + ismobile=true; + dimpx=(window.innerWidth>window.innerHeight?window.innerHeight:window.innerWidth)*(ismobile?0.9:0.75); + document.getElementById("containerDiv").style.width=dimpx+"px"; + document.getElementById("containerDiv").style.height=dimpx+"px"; +} +function gameInit() +{ + for(var e=document.getElementById("containerDiv").children,i=0;i<e.length;++i) + if(e[i].id!=="endgameDiv"&&e[i].id!=="scDiv"){e[i].remove();e=document.getElementById("containerDiv").children;--i;} + if(document.getElementById("bsize").value=="1")dim=6; + if(document.getElementById("bsize").value=="2")dim=12; + if(document.getElementById("bsize").value=="3")dim=20; + cc=parseInt(document.getElementById("ccnt").value); + if(document.getElementById("seed").value.length!==0) + if(!isNaN(parseInt(document.getElementById("seed").value))) + seed=parseInt(document.getElementById("seed").value); + else + seed=document.getElementById("seed").value.getHash(); + else + seed=Math.floor(Math.random()*2000000000); + document.getElementById("cseed").innerHTML=seed.toString(); + document.getElementById("seed").value=""; + document.getElementById("score").innerHTML="0"; + cscore=0; + board=new Array(dim+4);for(var i=0;i<dim+4;++i)board[i]=new Array(dim+4); + boarde=new Array(dim+4);for(var i=0;i<dim+4;++i)boarde[i]=new Array(dim+4); + for(var i=0;i<dim;++i) + for(var j=0;j<dim;++j) + { + board[i][j]=randomInt(1,cc); + boarde[i][j]=document.createElement("div"); + boarde[i][j].classList.add("clickable"); + boarde[i][j].classList.add(board[i][j]==1?"red":board[i][j]==2?"green":board[i][j]==3?"blue":"orange"); + boarde[i][j].style.bottom=i*dimpx/dim+"px"; + boarde[i][j].style.left=j*dimpx/dim+"px"; + boarde[i][j].style.width=boarde[i][j].style.height=dimpx/dim*.95+"px"; + boarde[i][j].i=i;boarde[i][j].j=j;boarde[i][j].h=0; + boarde[i][j].addEventListener("mouseenter",menter); + boarde[i][j].addEventListener("mouseleave",mleave); + boarde[i][j].addEventListener("click",mclick); + document.getElementById("containerDiv").appendChild(boarde[i][j]); + } + document.getElementById("endgameDiv").style.fontSize="0px"; + document.getElementById("endgameDiv").style.border="0px 0px"; + document.getElementById("endgameDiv").style.transform="translate(-50%,-50%) rotate(180deg)"; + document.getElementById("endgameDiv").style.WebkitTransform="translate(-50%,-50%) rotate(180deg)"; + document.getElementById("scoreopt").innerHTML=solve().toString(); +} +function getBGColor(c,a) +{ + return "rgba("+(c==1?"255,0,0,":c==2?"0,255,0,":c==3?"0,0,255,":"255,192,0,")+a+")"; +} +function menter(e) +{ + if(e===null)return; + var i=e.target?e.target.i:e.i,j=e.target?e.target.j:e.j; + if(boarde[i][j].h===1)return; + if(e.target!==undefined) + { + var s=0; + for(var k=0;k<4;++k) + if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])++s; + if(s===0)return; + } + boarde[i][j].style.backgroundColor=getBGColor(board[i][j],0.8); + boarde[i][j].h=1; + for(var k=0;k<4;++k) + if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j]) + menter(boarde[i+dx[k]][j+dy[k]]); +} +function mleave(e) +{ + if(e===null)return; + var i=e.target?e.target.i:e.i,j=e.target?e.target.j:e.j; + if(boarde[i][j].h===0)return; + if(e.target!==undefined) + { + var s=0; + for(var k=0;k<4;++k) + if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])++s; + if(s===0)return; + } + boarde[i][j].style.backgroundColor=getBGColor(board[i][j],0.6); + boarde[i][j].h=0; + for(var k=0;k<4;++k) + if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j]) + mleave(boarde[i+dx[k]][j+dy[k]]); +} +function mclick(e) +{ + var i,j,c; + if(e.target!==undefined) + { + if(pendingrem.length!==0)return; + var s=0; + i=e.target.i;j=e.target.j; + for(var k=0;k<4;++k) + if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j])++s; + if(s===0)return; + }else{i=e.i;j=e.j;} + c=board[i][j];board[i][j]=0; + for(var k=0;k<4;++k) + if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==c) + mclick(boarde[i+dx[k]][j+dy[k]]); + pendingrem.push(boarde[i][j]); + boarde[i][j].style.width=boarde[i][j].style.height=1.5*dimpx/dim*.95+"px"; + boarde[i][j].style.transform="translate(-16.66%,16.66%)"; + boarde[i][j].style.WebkitTransform="translate(-16.66%,16.66%)"; + boarde[i][j].style.backgroundColor=getBGColor(board[i][j],0); + boarde[i][j].removeEventListener("mouseenter",menter); + boarde[i][j].removeEventListener("mouseleave",mleave); + boarde[i][j].removeEventListener("click",mclick); + if(e.target!==undefined) + { + var tilesremoved=pendingrem.length; + cscore+=(tilesremoved-2)*(tilesremoved-2); + document.getElementById("scDiv").innerHTML="+"+((tilesremoved-2)*(tilesremoved-2)).toString(); + document.getElementById("scDiv").style.transition="none"; + document.getElementById("scDiv").style.color=(thm==0?"rgba(0,0,0,1)":"rgba(255,255,255,1)"); + document.getElementById("scDiv").style.transition="0.4s"; + document.getElementById("scDiv").style.top="10%"; + setTimeout(function(){document.getElementById("scDiv").style.color=(thm==0?"rgba(0,0,0,0)":"rgba(255,255,255,0)");},200); + document.getElementById("score").innerHTML=cscore.toString(); + setTimeout(doTilesRemove,512); + } +} +function doTilesRemove() +{ + for(var i=0;i<pendingrem.length;++i) + { + boarde[pendingrem[i].i][pendingrem[i].j]=null; + pendingrem[i].remove(); + } + pendingrem.length=0; + document.getElementById("scDiv").style.transition="none"; + document.getElementById("scDiv").style.top="50%"; + document.getElementById("scDiv").style.color=(thm==0?"rgba(0,0,0,0)":"rgba(255,255,255,0)"); + updateBoard(); +} +function updateBoard() +{ + //drop down + for(var j=0;j<dim;++j) + { + var rc=[],re=[]; + for(var i=0;i<dim;++i) + if(board[i][j]!==0){rc.push(board[i][j]);re.push(boarde[i][j]);} + for(var i=0;i<rc.length;++i) + { + board[i][j]=rc[i]; + boarde[i][j]=re[i]; + boarde[i][j].i=i; + boarde[i][j].style.bottom=i*dimpx/dim+"px"; + } + for(var i=rc.length;i<dim;++i){board[i][j]=0;boarde[i][j]=null;} + } + //shift left + for(var j=0;j<dim;++j) + { + var empty=true; + for(var i=0;i<dim;++i)if(board[i][j]!==0){empty=false;break;} + if(empty) + { + var nec=-1; + for(var k=j+1;k<dim;++k) + { + var e2=true; + for(var i=0;i<dim;++i)if(board[i][k]!==0){e2=false;break;} + if(!e2){nec=k;break;} + } + if(nec>-1) + for(var i=0;i<dim;++i) + { + board[i][j]=board[i][nec];board[i][nec]=0; + boarde[i][j]=boarde[i][nec];boarde[i][nec]=null; + if(boarde[i][j]!==null) + { + boarde[i][j].j=j; + boarde[i][j].style.left=j*dimpx/dim+"px"; + } + } + } + } + if(checkEndGame()) + { + document.getElementById("egscore").innerHTML=cscore.toString(); + document.getElementById("endgameDiv").style.fontSize="2em"; + document.getElementById("endgameDiv").style.border="0.5em 2em"; + document.getElementById("endgameDiv").style.transform="translate(-50%,-50%)"; + document.getElementById("endgameDiv").style.WebkitTransform="translate(-50%,-50%)"; + } +} +function checkEndGame() +{ + var e=true,nsn=true; + for(var i=0;i<dim;++i) + for(var j=0;j<dim;++j) + { + if(board[i][j]!==0)e=false; + var s=0; + for(var k=0;k<4;++k) + if(i+dx[k]>=0&&i+dx[k]<dim&&j+dy[k]>=0&&j+dy[k]<dim&&board[i+dx[k]][j+dy[k]]==board[i][j]&&board[i][j]!==0)++s; + if(s!==0)nsn=false; + } + return e||nsn; +} +//====================================================================================== +//= The Same Game AI - Greedy AI = +//= poj 1027 = +//====================================================================================== +var b,v; +var q=[]; +function Int(v){this.v=v;} +function Pnt(x,y){this.x=x;this.y=y;} +function inBound(p){return (p.x>=0&&p.x<dim&&p.y>=0&&p.y<dim);} +function bfs(x,y,s,rmv) +{ + q[0]=new Pnt(x,y);var col=b[y][x]; + var ret=0,L=0,R=0; + while(L<=R) + { + var cur=q[L++]; + if(v[cur.y][cur.x]===0)++ret;else continue; + v[cur.y][cur.x]=s; + for(var i=0;i<4;++i) + { + var np=new Pnt(cur.x+dx[i],cur.y+dy[i]); + if(inBound(np)&&v[np.y][np.x]===0&&col==b[np.y][np.x]) + q[++R]=new Pnt(np.x,np.y); + } + } + if(rmv) + for(var i=0;i<dim;++i)for(var j=0;j<dim;++j)if(v[i][j]===s)b[i][j]=0; + return ret; +} +function solverUpdateBoard(x,y,s) +{ + for(var i=0;i<dim+4;++i)for(var j=0;j<dim+4;++j)v[i][j]=0; + var col=b[y][x]; + bfs(x,y,s,true); + for(var j=0;j<dim;++j) + for(var i=dim;i>0;--i) + for(var k=dim-1;k>=0;--k) + if(b[k][j]===0){var t=b[k][j];b[k][j]=b[k+1][j];b[k+1][j]=t;} + for(var k=0;k<dim;++k) + for(var j=0;j<dim-1;++j) + { + var s=0; + for(var i=0;i<dim;++i)if(b[i][j]===0)++s; + if(s===dim)for(var i=0;i<dim;++i){var t=b[i][j];b[i][j]=b[i][j+1];b[i][j+1]=t;} + } +} +function solve() +{ + b=new Array(dim+4);for(var i=0;i<dim+4;++i)b[i]=new Array(dim+4); + for(var i=0;i<dim;++i)for(var j=0;j<dim;++j)b[i][j]=board[i][j]; + v=new Array(dim+4);for(var i=0;i<dim+4;++i)v[i]=new Array(dim+4); + for(var j=0;j<dim+2;++j)b[dim][j]=0; + for(var i=0;i<dim+2;++i)b[i][dim]=0; + var s=0;optscore=0;sol.length=0; + var col,finalcol; + for(;;) + { + ++s; + for(var i=0;i<dim+4;++i)for(var j=0;j<dim+4;++j)v[i][j]=0; + var stPnt=new Pnt(1<<25,1<<25),maxn=-1; + for(j=0;j<dim;++j) + for(i=0;i<dim;++i) + if(v[i][j]===0&&b[i][j]!==0) + { + col=b[i][j]; + var num=bfs(j,i,s,false); + if(num>maxn){stPnt=new Pnt(j,i);maxn=num;finalcol=col;} + else if(num==maxn) + { + if(j<stPnt.x){stPnt=new Pnt(j,i);finalcol=col;} + else if(j==stPnt.x&&i<stPnt.y) + {stPnt=new Pnt(j,i);finalcol=col;} + } + } + if(maxn<=1)break; + optscore+=(maxn-2)*(maxn-2); + console.log("Move "+s+" at ("+stPnt.y+","+stPnt.x+"): removed "+maxn+" balls of color "+finalcol+", got "+(maxn-2)*(maxn-2)+" points."); + sol.push(new Pnt(stPnt.y,stPnt.x)); + solverUpdateBoard(stPnt.x,stPnt.y,s); + } + console.log("Optimal score: "+optscore); + return optscore; +}
\ No newline at end of file |