Created
December 8, 2014 05:49
-
-
Save GaZ3ll3/816bd753ce30e52f3d8e to your computer and use it in GitHub Desktop.
code game AI 1.0
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // debug | |
| // right :3 oclock , up: 12 oclock, left : 9oclock, down 6 oclock | |
| // Basic functions | |
| function isequal(u, v) { | |
| if (u[0] === v[0] && u[1] === v[1]) { | |
| return true; | |
| } else{ | |
| return false; | |
| } | |
| } | |
| function dist(u, v) { | |
| return Math.abs(u[0] - v[0]) + Math.abs(u[1] - v[1]); | |
| } | |
| function shotdist(u, v) { | |
| if (u[0] == v[0] || u[1] == v[1]) { | |
| return dist(u,v); | |
| } else { | |
| return 9999; | |
| } | |
| } | |
| function sameline(u , v) { | |
| if (shotdist(u, v) < 9999) { | |
| return true; | |
| } else { | |
| return false; | |
| } | |
| } | |
| function samevec(u, v, vec) { | |
| // u on v along vec | |
| var pro; | |
| if (vec[0] != 0 && u[1] == v[1]) { | |
| pro = (u[0] - v[0]) * vec[0]; | |
| if (pro > 0) { | |
| return pro; | |
| } | |
| } | |
| else if (vec[1] != 0 && u[0] == v[0]) { | |
| pro = (u[1] - v[1])*vec[1] ; | |
| if (pro> 0) { | |
| return pro; | |
| } | |
| } | |
| else { | |
| return 0; | |
| } | |
| } | |
| function str2num(string) { | |
| if (string === 'right') { return 3;} | |
| else if(string === 'up') {return 0;} | |
| else if(string === 'left') {return 9;} | |
| else {return 6;} | |
| } | |
| function str2vec(string){ | |
| if (string === 'right') { return [1, 0];} | |
| else if(string === 'up') {return [0, -1];} | |
| else if(string === 'left') {return [-1, 0];} | |
| else {return [0, 1];} | |
| } | |
| function num2vec(n) { | |
| if (n == 3) {return [ 1, 0];} | |
| else if (n == 0 || n == 12) {return [0, -1];} | |
| else if (n == 9) {return [-1, 0];} | |
| else {return [0, 1];} | |
| } | |
| function vec2num(v){ | |
| if (v[0] == 1) {return 3;} | |
| else if (v[1] == -1) {return 0;} | |
| else if (v[0] == -1) {return 9;} | |
| else {return 6;} | |
| } | |
| function numtoward(u, v, n, map){ | |
| if (sameline(u, v)) { | |
| if (u[0] > v[0] && n == 9) { | |
| for (var i = 0; i < u[0] - v[0]; i++){ | |
| if (map.info[v[0] + i][v[1]] == 0){ | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| else if (u[0] < v[0] && n == 3) { | |
| for (var i = 0; i < v[0] - u[0]; i++){ | |
| if (map.info[u[0] + i][v[1]] == 0){ | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| else if (u[1] > v[1] && (n == 12 || n == 0)) { | |
| for (var i = 0; i < u[1] - v[1]; i++){ | |
| if (map.info[v[0]][v[1] + i] == 0){ | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| else if (u[1] < v[1] && n == 6) { | |
| for (var i = 0; i < v[1] - u[1]; i++){ | |
| if (map.info[v[0]][u[1] + i] == 0){ | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| else { | |
| return false; | |
| } | |
| } | |
| else { | |
| return false; | |
| } | |
| } | |
| function vectoward(u, v, d) { | |
| if (sameline(u, v)) { | |
| if (u[0] > v[0] && d[0] == -1) { | |
| return true; | |
| } | |
| else if (u[0] < v[0] && d[0] == 1) { | |
| return true; | |
| } | |
| else if (u[1] > v[1] && d[1] == -1) { | |
| return true; | |
| } | |
| else if (u[1] < v[1] && d[1] == 1) { | |
| return true; | |
| } | |
| else { | |
| return false; | |
| } | |
| } | |
| else{ | |
| return false; | |
| } | |
| } | |
| function rot(_num, num, list) { | |
| residue = (_num - num + 12)% 12; | |
| if (residue == 0) { | |
| list.push(2); | |
| } else if (residue == 3){ | |
| list.push(0); | |
| } else if (residue == 6) { | |
| list.push(1); | |
| list.push(1); | |
| } else if (residue == 9){ | |
| list.push(1); | |
| } else { | |
| print('residue error.'); | |
| } | |
| } | |
| function available(u, map) { | |
| if (map.info[u[0]][u[1]] == 0){ | |
| return false; | |
| } else { | |
| return true; | |
| } | |
| } | |
| function left(u, dir){ | |
| var vec = num2vec((str2num(dir) + 9) % 12); | |
| return [u[0] + vec[0], u[1] + vec[1]]; | |
| } | |
| function right(u, dir){ | |
| var vec = num2vec((str2num(dir) + 3) % 12); | |
| return [u[0] + vec[0], u[1] + vec[1]]; | |
| } | |
| function front(u, dir){ | |
| var vec = num2vec((str2num(dir)) % 12); | |
| return [u[0] + vec[0], u[1] + vec[1]]; | |
| } | |
| function back(u, dir){ | |
| var vec = num2vec((str2num(dir) + 6) % 12); | |
| return [u[0] + vec[0], u[1] + vec[1]]; | |
| } | |
| function neighbor(num, list, u, v) { | |
| if (u.x > v[0]) { | |
| rot(num, 3, list); | |
| return 3; | |
| } | |
| else if (u.x < v[0]) { | |
| rot(num, 9, list); | |
| return 9; | |
| } | |
| else if (u.y > v[1]) { | |
| rot(num, 6, list); | |
| return 6; | |
| } | |
| else if (u.y < v[1]){ | |
| rot(num, 12, list); | |
| return 12; | |
| } | |
| else{ | |
| // nothing | |
| } | |
| } | |
| function goforstar(map, db, s){ | |
| if (map.star.pos) { | |
| db.path = astar.search(map.graph, | |
| map.graph.grid[s.tank.position[0]][s.tank.position[1]], | |
| map.graph.grid[map.star.pos[0]][map.star.pos[1]]); | |
| if (db.path && db.path.length > 0){ | |
| next = neighbor(str2num(s.tank.direction), db.task, db.path[0], s.tank.position); | |
| } | |
| } | |
| } | |
| function flee(map, db, enemy, s){ | |
| var target, i, j, _i, _j, opt = 0; | |
| if (enemy.pos) { target = enemy.pos; } | |
| else {target = enemy.last;} | |
| _i = target[0]; | |
| _j = target[1]; | |
| for (i = 0; i < map.size[0]; i++) { | |
| for (j = 0; j < map.size[1]; j++) { | |
| if (Math.abs(i - target[0]) + Math.abs(j - target[1]) + 1> opt && | |
| map.info[i][j] != 0){ | |
| opt = Math.abs(i - target[0]) + Math.abs(j - target[1]) + 1; | |
| _i = i; | |
| _j = j; | |
| } | |
| } | |
| } | |
| db.clean(); | |
| db.path = astar.search(map.graph, | |
| map.graph.grid[s.tank.position[0]][s.tank.position[1]], | |
| map.graph.grid[_i][_j]); | |
| if (db.path && db.path.length > 0){ | |
| next = neighbor(str2num(s.tank.direction), db.task, db.path[0], s.tank.position); | |
| } | |
| } | |
| function hunt(map, db, enemy, s){ | |
| var target, i, j, _i, _j, opt = 0; | |
| if (enemy.pos) { target = enemy.pos; } | |
| else {target = enemy.last;} | |
| _i = target[0]; | |
| _j = target[1]; | |
| db.clean(); | |
| var intel = map.info; | |
| if (map.star.pos){ | |
| intel[map.star.pos[0]][map.star.pos[1]] = 0; | |
| } | |
| map.graph = new Graph(intel); | |
| db.path = astar.search(map.graph, | |
| map.graph.grid[s.tank.position[0]][s.tank.position[1]], | |
| map.graph.grid[_i][_j]); | |
| if (db.path && db.path.length > 0){ | |
| next = neighbor(str2num(s.tank.direction), db.task, db.path[0], s.tank.position); | |
| } | |
| } | |
| // | |
| MapMarker = 0; | |
| StarMarker = 0; | |
| DeepBlueMarker = 0; | |
| EnemyMarker = 0; | |
| function Map(g){ | |
| var obj = { | |
| // EXPLICT TO ALL | |
| info: null, | |
| graph: null, | |
| star:{pos: null, | |
| iframe: null, | |
| oframe:null, | |
| last: null}, | |
| frame: null, | |
| sprize: 0, | |
| eprize: 0, | |
| // if rectangle, for performance consideration | |
| size: [g.map.length, g.map[0].length], | |
| preparse: function () { | |
| var i, j; | |
| this.info = new Array(this.size[0]); | |
| for (i = 0; i < this.size[0]; i++) { | |
| this.info[i] = new Array(this.size[1]); | |
| for (j = 0; j < this.size[1]; j++) { | |
| if (g.map[i][j] == 'x') { | |
| this.info[i][j] = 0; // cannot pass | |
| } | |
| else if (g.map[i][j] == '.') { | |
| this.info[i][j] = 1.0; | |
| } | |
| else if (g.map[i][j] == 'o'){ | |
| this.info[i][j] = 0.1; | |
| } | |
| } | |
| } | |
| }, | |
| parse: function () { | |
| this.preparse(); | |
| this.graph = new Graph(this.info); | |
| }, | |
| update: function(s, e, g, enemy){ | |
| this.frame = g.frames; | |
| if (g.star) { | |
| if (!this.star.pos) { | |
| this.iframe = this.frame; | |
| } | |
| this.star.pos = g.star; | |
| this.star.last = g.star; | |
| } | |
| else { | |
| if (this.star.pos && isequal(s.tank.position, this.star.pos)) { | |
| this.sprize = this.sprize + 1; | |
| } | |
| else if (this.star.pos && !isequal(s.tank.position, this.star.pos)) { | |
| this.eprize = this.eprize + 1; | |
| } | |
| else { | |
| } | |
| if (this.star.pos) { | |
| this.oframe = this.frame; | |
| } | |
| this.star.pos = g.star; | |
| } | |
| // do something here | |
| // rule out all blocks on the way to bullet. | |
| if (enemy.bullet) { | |
| // block all the ways | |
| var i; | |
| var eb = enemy.bullet; | |
| var vv = str2vec(enemy.bulletdir); | |
| for (i = 0; i < Math.max(this.size[0],this.size[1]); i++) { | |
| if (eb[0] + i * vv[0] < 0 || | |
| eb[0] + i * vv[0] >= this.size[0] || | |
| eb[1] + i * vv[1] < 0 || | |
| eb[1] + i * vv[1] >= this.size[1] || | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] == 0 || | |
| eb[0] + i * vv[0] == s.tank.position[0] || | |
| eb[1] + i * vv[1] == s.tank.position[1]){ | |
| break; | |
| } | |
| else{ | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] = 0; | |
| } | |
| } | |
| if(map.star.pos) { | |
| this.info[map.star.pos[0]][map.star.pos[1]] = 1.0; | |
| } | |
| this.graph = new Graph(this.info); | |
| } | |
| else if (enemy.pos && enemy.dir) { | |
| var i; | |
| var eb = enemy.pos; | |
| var vv = str2vec(enemy.dir); | |
| for (i = 0; i < Math.max(this.size[0],this.size[1]); i++) { | |
| if (eb[0] + i * vv[0] < 0 || | |
| eb[0] + i * vv[0] >= this.size[0] || | |
| eb[1] + i * vv[1] < 0 || | |
| eb[1] + i * vv[1] >= this.size[1] || | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] == 0 || | |
| eb[0] + i * vv[0] == s.tank.position[0] || | |
| eb[1] + i * vv[1] == s.tank.position[1]){ | |
| break; | |
| } | |
| else{ | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] = 0; | |
| } | |
| } | |
| vv = num2vec(str2num(enemy.dir) + 3); | |
| for (i = 0; i < Math.max(this.size[0],this.size[1]); i++) { | |
| if (eb[0] + i * vv[0] < 0 || | |
| eb[0] + i * vv[0] >= this.size[0] || | |
| eb[1] + i * vv[1] < 0 || | |
| eb[1] + i * vv[1] >= this.size[1] || | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] == 0 || | |
| eb[0] + i * vv[0] == s.tank.position[0] || | |
| eb[1] + i * vv[1] == s.tank.position[1]){ | |
| break; | |
| } | |
| else{ | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] = 0; | |
| } | |
| } | |
| vv = num2vec(str2num(enemy.dir) + 9); | |
| for (i = 0; i < Math.max(this.size[0],this.size[1]); i++) { | |
| if (eb[0] + i * vv[0] < 0 || | |
| eb[0] + i * vv[0] >= this.size[0] || | |
| eb[1] + i * vv[1] < 0 || | |
| eb[1] + i * vv[1] >= this.size[1] || | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] == 0 || | |
| eb[0] + i * vv[0] == s.tank.position[0] || | |
| eb[1] + i * vv[1] == s.tank.position[1] ){ | |
| break; | |
| } | |
| else{ | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] = 0; | |
| } | |
| } | |
| if (enemy.pb){ | |
| var eb = enemy.pb; | |
| var vv = enemy.vec; | |
| for (i = 0; i < Math.max(this.size[0],this.size[1]); i++) { | |
| if (eb[0] + i * vv[0] < 0 || | |
| eb[0] + i * vv[0] >= this.size[0] || | |
| eb[1] + i * vv[1] < 0 || | |
| eb[1] + i * vv[1] >= this.size[1] || | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] == 0 || | |
| eb[0] + i * vv[0] == s.tank.position[0] || | |
| eb[1] + i * vv[1] == s.tank.position[1]){ | |
| break; | |
| } | |
| else{ | |
| this.info[eb[0] + i * vv[0]][eb[1] + i * vv[1]] = 0; | |
| } | |
| } | |
| } | |
| if(map.star.pos) { | |
| this.info[map.star.pos[0]][map.star.pos[1]] = 1.0; | |
| } | |
| this.graph = new Graph(this.info); | |
| } | |
| else { | |
| this.graph = new Graph(this.info); | |
| } | |
| } | |
| }; | |
| return obj; | |
| } | |
| function Enemy() { | |
| var obj = { | |
| pos: null, | |
| last: null, | |
| exist: false, | |
| bullet: null, | |
| bulletdir: null, | |
| dir: null, | |
| lastdir: null, | |
| pb: null, | |
| vec: null, | |
| update: function(s, e, map){ | |
| if (e.tank) { | |
| this.exist = true; | |
| if (this.pos) { | |
| this.last = this.pos; | |
| this.pos = e.tank.position; | |
| } | |
| else { | |
| this.pos = e.tank.position; | |
| } | |
| if (this.dir) { | |
| this.lastdir = this.dir; | |
| this.dir = e.tank.direction; | |
| } | |
| else { | |
| this.dir = e.tank.direction; | |
| } | |
| if (e.bullet){ | |
| this.bullet = e.bullet.position; | |
| this.bulletdir = e.bullet.direction; | |
| } | |
| else if (this.bullet && this.bulletdir) { | |
| var vec = str2vec(this.bulletdir); | |
| this.bullet[0] = this.bullet[0] + 2*vec[0]; | |
| this.bullet[1] = this.bullet[1] + 2*vec[1]; | |
| if (this.bullet[0] < 0 || this.bullet[0] >= map.size[0] || | |
| this.bullet[1] < 0 || this.bullet[1] >= map.size[1] || | |
| map.info[this.bullet[0]][this.bullet[1]] == 'x') { | |
| // hit stone | |
| this.bullet = null; | |
| this.bulletdir = null; | |
| } | |
| } | |
| // need to update bullet's location | |
| } | |
| else { | |
| this.exit = false; | |
| if (this.pos && this.dir){ | |
| this.last = this.pos; | |
| this.lastdir = this.dir; | |
| var ld; | |
| if (this.lastdir){ | |
| ld = str2vec(this.lastdir); | |
| } | |
| else { | |
| ld = [0, 0]; | |
| } | |
| this.pos[0] = this.pos[0] + ld[0]; | |
| this.pos[1] = this.pos[1] + ld[1]; | |
| this.dir = null; | |
| } | |
| else { | |
| this.pos = null; | |
| this.dir = null; | |
| } | |
| if (map.star.iframe == map.frame){ | |
| this.pos[0] = 2*map.star.last[0] - s.tank.position[0]; | |
| this.pos[1] = 2*map.star.last[1] - s.tank.position[1]; | |
| this.dir = null; | |
| } | |
| if (map.star.oframe == map.frame){ | |
| if (map.star.last && !isequal(s.tank.position, map.star.last)){ | |
| this.last = map.star.last; | |
| this.lastdir = null; | |
| // can guess | |
| this.dir = null; | |
| this.pos = null; | |
| } | |
| } | |
| } | |
| } | |
| }; | |
| return obj; | |
| } | |
| function DeepBlue() { | |
| var obj = { | |
| task : [], | |
| path: null, | |
| mind: 0, | |
| oracle: 0, | |
| consume: function(w) { | |
| if (this.task.length > 0) { | |
| switch (this.task[0]) { | |
| case 0: | |
| w.turn('left'); | |
| break; | |
| case 1: | |
| w.turn('right'); | |
| break; | |
| case 2: | |
| w.go(1); | |
| break; | |
| case 3: | |
| w.fire(); | |
| break; | |
| default: | |
| // do nothing | |
| break; | |
| } | |
| this.task.shift(); | |
| } | |
| else { | |
| // nothing | |
| } | |
| }, | |
| push: function(n) { | |
| this.task.push(n); | |
| }, | |
| head: function(n) { | |
| this.task.unshift(n); | |
| } , | |
| clean: function() { | |
| this.task = []; | |
| }, | |
| predict: function(s, Enemy, Map) { | |
| // algorithm for MIND | |
| } | |
| }; | |
| return obj; | |
| } | |
| function onIdle(s, e, g) { | |
| // analyse the map before everything else | |
| if (MapMarker === 0){ | |
| map = Map(g); | |
| map.parse(); | |
| MapMarker = 1; | |
| } | |
| if (EnemyMarker === 0){ | |
| enemy = Enemy(); | |
| EnemyMarker = 1; | |
| } | |
| if (DeepBlueMarker === 0){ | |
| db = DeepBlue(); | |
| DeepBlueMarker = 1; | |
| } | |
| // each frame, do such thing to initialize all | |
| map.preparse(); | |
| map.update(s, e, g, enemy); | |
| enemy.update(s, e, map); | |
| // first thing is getting stars. | |
| // DeepBlue's idea is | |
| /* status of the tank , each time/step check status of tank. | |
| * if mind = 0, flee away. (too dangerous) | |
| * if mind = 1, go for star. (safe enough) | |
| * if mind = 2, enemy stopped, maybe fired. | |
| * if mind = 3, bullet coming. | |
| * IF mind = 4, attack, chase enemy | |
| * if mind = 5, higher AI levels.*/ | |
| /* | |
| print("current: " + ENEMY.CURR) | |
| print("curr dir: " + ENEMY.CURRDIR) | |
| print("last : " + ENEMY.LAST) | |
| print("last dir: " + ENEMY.LASTDIR) | |
| print("bullet: " + ENEMY.BULLET) | |
| print("bullet direction " + ENEMY.BULLETDIR) | |
| */ | |
| // prediction level, predict 4 steps right now | |
| /* predict position : | |
| * 1. if visible, locate enemy | |
| * 2. if not visible, guess | |
| * 3. if star is taken, location is known | |
| * 4. if star comes out, location is known | |
| */ | |
| // Oracle tells what will happen next time, a learning machine from others' behavior. | |
| // danger has two levels, maybe more | |
| // safe or not? | |
| // first push all steps into queue looking for star. | |
| // if detour happens, re-calculate all steps. | |
| //----------------------------------------------------------- | |
| // if there is danger potential, avoid it. | |
| // if not dangerous, go to star, until it is dangerous. | |
| if (db.task.length == 0){ | |
| // when it is not dangerous but have a chance to shot, make it. | |
| // when it is uncertain about enemy's location, but have to pass through, shot to uncertain. | |
| if (enemy.bullet){ | |
| // try to avoid it instead of telling where it comes from. | |
| /* distance is very subtle. */ | |
| enemy.pb = null; | |
| var range = shotdist(enemy.bullet, s.tank.position); | |
| var t = Math.floor(range/2); | |
| // it is travellig at 2 units/frame | |
| if (t < 2) { | |
| if(!s.bullet) { | |
| db.head(3); | |
| } | |
| } | |
| else if (t == 2 || t == 3) { | |
| // flee | |
| if (available(left(s.tank.position, s.tank.direction),map)){ | |
| db.head(2); | |
| db.head(0); | |
| } | |
| else if (available(right(s.tank.position, s.tank.direction),map)){ | |
| db.head(2); | |
| db.head(1); | |
| } | |
| else{ | |
| if(!s.bullet) { | |
| db.head(3); | |
| } | |
| } | |
| } | |
| else if (t == 4 ) { | |
| if (!available(left(s.tank.position, s.tank.direction),map) || | |
| !available(right(s.tank.position, s.tank.direction),map)) { | |
| if (available(front(s.tank.position, s.tank.direction),map)) { | |
| db.head(2); | |
| } | |
| } | |
| else{ | |
| if (available(left(s.tank.position, s.tank.direction),map)){ | |
| db.head(2); | |
| db.head(0); | |
| } | |
| else if (available(right(s.tank.position, s.tank.direction),map)){ | |
| db.head(2); | |
| db.head(1); | |
| } | |
| else{ | |
| if(!s.bullet) { | |
| db.head(3); | |
| } | |
| } | |
| } | |
| } | |
| else if (t > 4) { | |
| if (!available(left(s.tank.position, s.tank.direction),map) || | |
| !available(right(s.tank.position, s.tank.direction),map)) { | |
| if (available(back(s.tank.position, s.tank.direction),map)) { | |
| db.head(0); | |
| db.head(0); | |
| db.head(2); | |
| } | |
| } | |
| } | |
| } | |
| // possible bullet | |
| if (!enemy.bullet && enemy.pb) { | |
| enemy.pb[0] = enemy.pb[0] + 2* enemy.vec[0]; | |
| enemy.pb[1] = enemy.pb[1] + 2* enemy.vec[1]; | |
| if ( enemy.pb[0] < 0 || enemy.pb[0] >= map.size[0] || | |
| enemy.pb[1] < 0 || enemy.pb[1] >= map.size[1] || | |
| map.info[enemy.pb[0]][enemy.pb[1]] == 'x' ) { | |
| // hit stone | |
| enemy.pb = null; | |
| } | |
| // consider next move if I will be hit. | |
| var mv = str2vec(s.tank.direction); | |
| var mn = [s.tank.position[0] + mv[0], s.tank.position[1] + mv[1]]; | |
| var proj ; | |
| if (enemy.pb){ | |
| proj = samevec( enemy.pb, mn, enemy.vec); | |
| } | |
| else { | |
| proj = 0; | |
| } | |
| // 1. parallel move | |
| if (enemy.pb && enemy.vec && numtoward(enemy.pb, s.tank.position, vec2num(enemy.vec), map)){ | |
| // danger , detour needed. | |
| if (mv[0]*enemy.vec[0] + mv[1]*enemy.vec[1] != 0){ | |
| var ss = shotdist(enemy.pb, s.tank.position); | |
| var t = Math.floor(ss/2); | |
| if (t == 2 || t==3){ | |
| if (available(left(s.tank.position, s.tank.direction),map)){ | |
| db.head(2); | |
| db.head(0); | |
| } | |
| else{ | |
| db.head(2); | |
| db.head(1); | |
| } | |
| } | |
| } | |
| else { | |
| var ss = shotdist(enemy.pb, s.tank.position); | |
| var t = Math.floor(ss/2); | |
| if (t == 1 || t == 2){ | |
| db.head(2); | |
| } | |
| else{ | |
| db.head(2); | |
| db.head(1); | |
| db.head(1); | |
| } | |
| } | |
| } | |
| else if (proj == 1) { | |
| // only one step apart from | |
| if (available(left(s.tank.position, s.tank.direction),map)){ | |
| db.head(0); | |
| } | |
| else{ | |
| db.head(1); | |
| } | |
| } | |
| } | |
| if (!enemy.pb && e.tank && enemy.last && enemy.lastdir && | |
| isequal(enemy.pos, enemy.last) && | |
| isequal(enemy.dir, enemy.lastdir)) { | |
| // if danger ahead, then detour | |
| var bv = str2vec(enemy.dir); | |
| // no bullet exists on board, then enemy fires one bullet | |
| if (!enemy.bullet){ | |
| enemy.pb = new Array(2); | |
| enemy.pb[0] = enemy.pos[0] + 2*bv[0]; | |
| enemy.pb[1] = enemy.pos[1] + 2*bv[1]; | |
| enemy.vec = new Array(2); | |
| enemy.vec[0] = bv[0]; | |
| enemy.vec[1] = bv[1]; | |
| } | |
| } | |
| if (map.star.pos) { | |
| if (numtoward(s.tank.position, map.star.pos, str2num(s.tank.direction),map) && | |
| ( (enemy.last && numtoward(enemy.last, map.star.pos, str2num(enemy.lastdir),map) ) || | |
| (enemy.last && dist(enemy.last, map.star.pos) < 6 && g.map[enemy.last[0]][enemy.last[1]] == 'o') ) ){ | |
| while(db.task[0] == 2){ | |
| db.task.shift(); | |
| } | |
| if(!s.bullet) { | |
| db.head(3); | |
| } | |
| } | |
| else{ | |
| if (map.sprize > map.eprize + 1){ | |
| flee(map, db, enemy,s); | |
| } | |
| else { | |
| goforstar(map, db, s); | |
| } | |
| } | |
| } | |
| else { | |
| flee(map, db, enemy, s); | |
| } | |
| if (enemy.last && numtoward(s.tank.position, enemy.last, str2num(s.tank.direction),map)){ | |
| if (db.task[0] == 2) { | |
| // do not go ! | |
| db.task.shift(); | |
| } | |
| if (db.task[0] != 3){ | |
| db.head(3); | |
| } | |
| } | |
| } | |
| db.consume(s); | |
| } | |
| // do not edit ------------------------------------------------ | |
| // A star search code ----------------------------------------- | |
| function pathTo(node){ | |
| var curr = node, | |
| path = []; | |
| while(curr.parent) { | |
| path.push(curr); | |
| curr = curr.parent; | |
| } | |
| return path.reverse(); | |
| } | |
| function getHeap() { | |
| return new BinaryHeap(function(node) { | |
| return node.f; | |
| }); | |
| } | |
| var astar = { | |
| init: function(graph) { | |
| for (var i = 0, len = graph.nodes.length; i < len; ++i) { | |
| var node = graph.nodes[i]; | |
| node.f = 0; | |
| node.g = 0; | |
| node.h = 0; | |
| node.visited = false; | |
| node.closed = false; | |
| node.parent = null; | |
| } | |
| }, | |
| /** | |
| * Perform an A* Search on a graph given a start and end node. | |
| * @param {Graph} graph | |
| * @param {GridNode} start | |
| * @param {GridNode} end | |
| * @param {Object} [options] | |
| * @param {bool} [options.closest] Specifies whether to return the | |
| path to the closest node if the target is unreachable. | |
| * @param {Function} [options.heuristic] Heuristic function (see | |
| * astar.heuristics). | |
| */ | |
| search: function(graph, start, end, options) { | |
| astar.init(graph); | |
| options = options || {}; | |
| var heuristic = options.heuristic || astar.heuristics.manhattan, | |
| closest = options.closest || false; | |
| var openHeap = getHeap(), | |
| closestNode = start; // set the start node to be the closest if required | |
| start.h = heuristic(start, end); | |
| openHeap.push(start); | |
| while(openHeap.size() > 0) { | |
| // Grab the lowest f(x) to process next. Heap keeps this sorted for us. | |
| var currentNode = openHeap.pop(); | |
| // End case -- result has been found, return the traced path. | |
| if(currentNode === end) { | |
| return pathTo(currentNode); | |
| } | |
| // Normal case -- move currentNode from open to closed, process each of its neighbors. | |
| currentNode.closed = true; | |
| // Find all neighbors for the current node. | |
| var neighbors = graph.neighbors(currentNode); | |
| for (var i = 0, il = neighbors.length; i < il; ++i) { | |
| var neighbor = neighbors[i]; | |
| if (neighbor.closed || neighbor.isWall()) { | |
| // Not a valid node to process, skip to next neighbor. | |
| continue; | |
| } | |
| // The g score is the shortest distance from start to current node. | |
| // We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet. | |
| var gScore = currentNode.g + neighbor.getCost(currentNode), | |
| beenVisited = neighbor.visited; | |
| if (!beenVisited || gScore < neighbor.g) { | |
| // Found an optimal (so far) path to this node. Take score for node to see how good it is. | |
| neighbor.visited = true; | |
| neighbor.parent = currentNode; | |
| neighbor.h = neighbor.h || heuristic(neighbor, end); | |
| neighbor.g = gScore; | |
| neighbor.f = neighbor.g + neighbor.h; | |
| if (closest) { | |
| // If the neighbour is closer than the current closestNode or if it's equally close but has | |
| // a cheaper path than the current closest node then it becomes the closest node | |
| if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) { | |
| closestNode = neighbor; | |
| } | |
| } | |
| if (!beenVisited) { | |
| // Pushing to heap will put it in proper place based on the 'f' value. | |
| openHeap.push(neighbor); | |
| } | |
| else { | |
| // Already seen the node, but since it has been rescored we need to reorder it in the heap | |
| openHeap.rescoreElement(neighbor); | |
| } | |
| } | |
| } | |
| } | |
| if (closest) { | |
| return pathTo(closestNode); | |
| } | |
| // No result was found - empty array signifies failure to find path. | |
| return []; | |
| }, | |
| // See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html | |
| heuristics: { | |
| manhattan: function(pos0, pos1) { | |
| var d1 = Math.abs(pos1.x - pos0.x); | |
| var d2 = Math.abs(pos1.y - pos0.y); | |
| if (d1 == 0 || d2 == 0){ | |
| return d1 + d2; | |
| } | |
| else{ | |
| return d1 + d2 + 1; | |
| } | |
| }, | |
| diagonal: function(pos0, pos1) { | |
| var D = 1; | |
| var D2 = Math.sqrt(2); | |
| var d1 = Math.abs(pos1.x - pos0.x); | |
| var d2 = Math.abs(pos1.y - pos0.y); | |
| return (D * (d1 + d2)) + ((D2 - (2 * D)) * Math.min(d1, d2)); | |
| } | |
| } | |
| }; | |
| /** | |
| * A graph memory structure | |
| * @param {Array} gridIn 2D array of input weights | |
| * @param {Object} [options] | |
| * @param {bool} [options.diagonal] Specifies whether diagonal moves are allowed | |
| */ | |
| function Graph(gridIn, options) { | |
| options = options || {}; | |
| this.nodes = []; | |
| this.diagonal = !!options.diagonal; | |
| this.grid = []; | |
| for (var x = 0; x < gridIn.length; x++) { | |
| this.grid[x] = []; | |
| for (var y = 0, row = gridIn[x]; y < row.length; y++) { | |
| var node = new GridNode(x, y, row[y]); | |
| this.grid[x][y] = node; | |
| this.nodes.push(node); | |
| } | |
| } | |
| } | |
| Graph.prototype.neighbors = function(node) { | |
| var ret = [], | |
| x = node.x, | |
| y = node.y, | |
| grid = this.grid; | |
| // West | |
| if(grid[x-1] && grid[x-1][y] ) { | |
| ret.push(grid[x-1][y]); | |
| } | |
| // East | |
| if(grid[x+1] && grid[x+1][y]) { | |
| ret.push(grid[x+1][y]); | |
| } | |
| // South | |
| if(grid[x] && grid[x][y-1]) { | |
| ret.push(grid[x][y-1]); | |
| } | |
| // North | |
| if(grid[x] && grid[x][y+1]) { | |
| ret.push(grid[x][y+1]); | |
| } | |
| if (this.diagonal) { | |
| // Southwest | |
| if(grid[x-1] && grid[x-1][y-1]) { | |
| ret.push(grid[x-1][y-1]); | |
| } | |
| // Southeast | |
| if(grid[x+1] && grid[x+1][y-1]) { | |
| ret.push(grid[x+1][y-1]); | |
| } | |
| // Northwest | |
| if(grid[x-1] && grid[x-1][y+1]) { | |
| ret.push(grid[x-1][y+1]); | |
| } | |
| // Northeast | |
| if(grid[x+1] && grid[x+1][y+1]) { | |
| ret.push(grid[x+1][y+1]); | |
| } | |
| } | |
| return ret; | |
| }; | |
| Graph.prototype.toString = function() { | |
| var graphString = [], | |
| nodes = this.grid, // when using grid | |
| rowDebug, row, y, l; | |
| for (var x = 0, len = nodes.length; x < len; x++) { | |
| rowDebug = []; | |
| row = nodes[x]; | |
| for (y = 0, l = row.length; y < l; y++) { | |
| rowDebug.push(row[y].weight); | |
| } | |
| graphString.push(rowDebug.join(" ")); | |
| } | |
| return graphString.join("\n"); | |
| }; | |
| function GridNode(x, y, weight) { | |
| this.x = x; | |
| this.y = y; | |
| this.weight = weight; | |
| } | |
| GridNode.prototype.toString = function() { | |
| return "[" + this.x + " " + this.y + "]"; | |
| }; | |
| GridNode.prototype.getCost = function() { | |
| return this.weight; | |
| }; | |
| GridNode.prototype.isWall = function() { | |
| return this.weight === 0; | |
| }; | |
| function BinaryHeap(scoreFunction){ | |
| this.content = []; | |
| this.scoreFunction = scoreFunction; | |
| } | |
| BinaryHeap.prototype = { | |
| push: function(element) { | |
| // Add the new element to the end of the array. | |
| this.content.push(element); | |
| // Allow it to sink down. | |
| this.sinkDown(this.content.length - 1); | |
| }, | |
| pop: function() { | |
| // Store the first element so we can return it later. | |
| var result = this.content[0]; | |
| // Get the element at the end of the array. | |
| var end = this.content.pop(); | |
| // If there are any elements left, put the end element at the | |
| // start, and let it bubble up. | |
| if (this.content.length > 0) { | |
| this.content[0] = end; | |
| this.bubbleUp(0); | |
| } | |
| return result; | |
| }, | |
| remove: function(node) { | |
| var i = this.content.indexOf(node); | |
| // When it is found, the process seen in 'pop' is repeated | |
| // to fill up the hole. | |
| var end = this.content.pop(); | |
| if (i !== this.content.length - 1) { | |
| this.content[i] = end; | |
| if (this.scoreFunction(end) < this.scoreFunction(node)) { | |
| this.sinkDown(i); | |
| } | |
| else { | |
| this.bubbleUp(i); | |
| } | |
| } | |
| }, | |
| size: function() { | |
| return this.content.length; | |
| }, | |
| rescoreElement: function(node) { | |
| this.sinkDown(this.content.indexOf(node)); | |
| }, | |
| sinkDown: function(n) { | |
| // Fetch the element that has to be sunk. | |
| var element = this.content[n]; | |
| // When at 0, an element can not sink any further. | |
| while (n > 0) { | |
| // Compute the parent element's index, and fetch it. | |
| var parentN = ((n + 1) >> 1) - 1, | |
| parent = this.content[parentN]; | |
| // Swap the elements if the parent is greater. | |
| if (this.scoreFunction(element) < this.scoreFunction(parent)) { | |
| this.content[parentN] = element; | |
| this.content[n] = parent; | |
| // Update 'n' to continue at the new position. | |
| n = parentN; | |
| } | |
| // Found a parent that is less, no need to sink any further. | |
| else { | |
| break; | |
| } | |
| } | |
| }, | |
| bubbleUp: function(n) { | |
| // Look up the target element and its score. | |
| var length = this.content.length, | |
| element = this.content[n], | |
| elemScore = this.scoreFunction(element); | |
| while(true) { | |
| // Compute the indices of the child elements. | |
| var child2N = (n + 1) << 1, | |
| child1N = child2N - 1; | |
| // This is used to store the new position of the element, if any. | |
| var swap = null, | |
| child1Score; | |
| // If the first child exists (is inside the array)... | |
| if (child1N < length) { | |
| // Look it up and compute its score. | |
| var child1 = this.content[child1N]; | |
| child1Score = this.scoreFunction(child1); | |
| // If the score is less than our element's, we need to swap. | |
| if (child1Score < elemScore){ | |
| swap = child1N; | |
| } | |
| } | |
| // Do the same checks for the other child. | |
| if (child2N < length) { | |
| var child2 = this.content[child2N], | |
| child2Score = this.scoreFunction(child2); | |
| if (child2Score < (swap === null ? elemScore : child1Score)) { | |
| swap = child2N; | |
| } | |
| } | |
| // If the element needs to be moved, swap it, and continue. | |
| if (swap !== null) { | |
| this.content[n] = this.content[swap]; | |
| this.content[swap] = element; | |
| n = swap; | |
| } | |
| // Otherwise, we are done. | |
| else { | |
| break; | |
| } | |
| } | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment