Last active
July 7, 2017 12:48
-
-
Save gooocho/13b209837ec653d76c6c7643cbc8a797 to your computer and use it in GitHub Desktop.
とりあえず
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
var gameMap; | |
(function() { | |
'use strict'; | |
const startTime = Date.now(); | |
const MOVE = { | |
walk: 'WALK', | |
fly: 'FLY', | |
}; | |
// ChipCharacter => ChipInfo | |
const CHIPSET = { | |
' ': { | |
name: 'BLANK', | |
moveCost: { | |
[MOVE.walk]: 1, | |
[MOVE.fly]: 1 | |
}, | |
goalMoveList: [] | |
}, | |
'#': { | |
name: 'WALL', | |
moveCost: { | |
[MOVE.walk]: Infinity, | |
[MOVE.fly]: 1 | |
}, | |
goalMoveList: [] | |
}, | |
'G': { | |
name: 'WALK_GOAL', | |
moveCost: { | |
[MOVE.walk]: 1, | |
[MOVE.fly]: 1 | |
}, | |
goalMoveList: [MOVE.walk] | |
}, | |
'g': { | |
name: 'FLY_GOAL', | |
moveCost: { | |
[MOVE.walk]: Infinity, | |
[MOVE.fly]: 1 | |
}, | |
goalMoveList: [MOVE.fly] | |
}, | |
}; | |
const SETTINGS = { | |
mapStr1: ` | |
######### | |
# # #g | |
## ####g | |
# # g | |
# # g | |
# #Gg | |
######### | |
` | |
}; | |
class Iterable { | |
forEach(func) { | |
for (let [el, index] of this) { | |
func.call(this, el, index, this); | |
} | |
} | |
find(func) { | |
for (let [el, index] of this) { | |
if (func.call(this, el, index, this)) { | |
return el; | |
} | |
} | |
} | |
map(func) { | |
const ret = []; | |
for (let [el, index] of this) { | |
ret.push(func.call(this,el, index, this)); | |
} | |
return ret; | |
} | |
filter(func) { | |
const ret = []; | |
for (let [el, index] of this) { | |
if (func.call(this, el, index, this)) { | |
ret.push(el); | |
} | |
} | |
return ret; | |
} | |
reduce(func, initial) { | |
let first = true; | |
let accum = initial; | |
for (let [current, index] of this) { | |
if (first) { | |
first = false; | |
if (arguments.length === 1) { | |
accum = current; | |
continue; | |
} | |
} | |
accum = func.call(func, accum, current, index); | |
} | |
return accum; | |
} | |
} | |
class LinkedListNode { | |
constructor(data, prev, next) { | |
this.data = data; | |
this.prev = prev; | |
this.next = next; | |
} | |
} | |
// FIXME: use log(n) order algorithm | |
class LinkedList extends Iterable { | |
constructor() { | |
super(); | |
this.length = 0; | |
this.lead = new LinkedListNode(null); | |
this.anchor = new LinkedListNode(null); | |
this.lead.next = this.anchor; | |
this.anchor.prev = this.lead; | |
} | |
static fromArray(array) { | |
const linkedList = new LinkedList(); | |
array.forEach(el => linkedList.addLast(el)); | |
return linkedList; | |
} | |
get first() { | |
if (this.length) { | |
return this.lead.next; | |
} | |
return null; | |
} | |
get last() { | |
if (this.length) { | |
return this.anchor.prev; | |
} | |
return null; | |
} | |
add(data, prev, next) { | |
this.length += 1; | |
prev.next = next.prev = new LinkedListNode(data, prev, next); | |
return this; | |
} | |
addFirst(addData) { | |
return this.add(addData, this.lead, this.lead.next); | |
} | |
addLast(addData) { | |
return this.add(addData, this.anchor.prev, this.anchor); | |
} | |
addBeforeWhere(addData, func) { | |
for (let [data, node] of this) { | |
if (func(data)) { | |
return this.add(addData, node.prev, node); | |
} | |
} | |
return this.addLast(addData); | |
} | |
addAfterWhere(addData, func) { | |
for (let [data, node] of this) { | |
if (func(data)) { | |
return this.add(addData, node, node.next); | |
} | |
} | |
return this.addLast(addData); | |
} | |
removeFirst() { | |
if (this.length) { | |
const firstNode = this.lead.next; | |
this.length -= 1; | |
this.lead.next = firstNode.next; | |
firstNode.next.prev = this.lead; | |
return firstNode.data; | |
} | |
return null; | |
} | |
removeLast() { | |
if (this.length) { | |
const lastNode = this.anchor.prev; | |
this.length -= 1; | |
this.last.prev = lastNode.prev; | |
lastNode.prev.next = this.anchor; | |
return lastNode.data; | |
} | |
return null; | |
} | |
removeWhere(func) { | |
for (let [data, node] of this) { | |
if (func(data)) { | |
this.length -= 1 | |
node.prev.next = node.next; | |
node.next.prev = node.prev; | |
return data; | |
} | |
} | |
return null; | |
} | |
*[Symbol.iterator]() { | |
let node = this.lead; | |
while ((node = node.next) !== this.anchor) { | |
yield [node.data, node, this]; | |
}; | |
} | |
} | |
class Vec2 { | |
constructor(x, y) { | |
this.x = x; | |
this.y = y; | |
} | |
add(vec2) { | |
return new Vec2(this.x + vec2.x, this.y + vec2.y); | |
} | |
sub(vec2) { | |
return new Vec2(this.x - vec2.x, this.y - vec2.y); | |
} | |
equal(vec2) { | |
return this.x === vec2.x && this.y === vec2.y; | |
} | |
distanceSquare(vec2) { | |
const diffX = this.x - vec2.x; | |
const diffY = this.y - vec2.y; | |
return diffX * diffX + diffY * diffY; | |
} | |
toString() { | |
return `(${this.x}, ${this.y})`; | |
} | |
} | |
Vec2.ORIGIN = new Vec2(0, 0); | |
class Plane extends Iterable { | |
constructor(width, height) { | |
super(); | |
this.width = width; | |
this.height = height; | |
this.data = new Array(height); | |
for (let y = 0; y < height; ++y) { | |
this.data[y] = new Array(width); | |
} | |
} | |
getVec2(vec2) { | |
return (this.data[vec2.y] || {})[vec2.x]; | |
} | |
setVec2(vec2, value) { | |
return (this.data[vec2.y] || {})[vec2.x] = value; | |
} | |
*[Symbol.iterator]() { | |
for (let y = 0; y < this.height; ++y) { | |
const row = this.data[y]; | |
for (let x = 0; x < this.width; ++x) { | |
yield [row[x], new Vec2(x, y), this]; | |
} | |
} | |
} | |
} | |
class MapParseError extends Error { | |
constructor(message) { | |
super(message); | |
} | |
} | |
class Chip { | |
constructor(vec2, chipInfo) { | |
this.vec2 = vec2; | |
this.chipInfo = chipInfo; | |
} | |
} | |
class MoveCost { | |
constructor(vec2, cost) { | |
this.vec2 = vec2; | |
this.cost = cost; | |
} | |
} | |
class MoveGuide { | |
constructor(accumCost, next) { | |
this.accumCost = accumCost; | |
this.next = next; | |
this.prevList = []; | |
} | |
} | |
class MoveGuidePlane extends Plane { | |
constructor(width, height, moveCostLinkedList, surroundingMovableMoveCostPlane) { | |
super(width, height); | |
for (let [_, vec2] of this) { | |
this.setVec2(vec2, new MoveGuide(Infinity, null)); | |
} | |
moveCostLinkedList.forEach(moveCost => this.getVec2(moveCost.vec2).accumCost = 0); | |
this.updateMoveGuidePlane(moveCostLinkedList, surroundingMovableMoveCostPlane); | |
} | |
// destructive | |
updateMoveGuidePlane(moveCostLinkedList, surroundingMovableMoveCostPlane) { | |
for (let i = 0; i < 400; ++i) { | |
if (moveCostLinkedList.length === 0) { | |
console.info('ok', i); | |
break; | |
} | |
const currentMoveCost = moveCostLinkedList.removeFirst(); | |
const {vec2: currentVec2, cost: currentCost} = currentMoveCost; | |
const currentMoveGuide = this.getVec2(currentVec2); | |
currentMoveGuide.prevList = []; | |
surroundingMovableMoveCostPlane.getVec2(currentVec2).forEach(nextMoveCost => { | |
const {vec2: nextVec2, cost: nextCost} = nextMoveCost; | |
const nextMoveGuide = this.getVec2(nextVec2); | |
const distance = Math.sqrt(nextVec2.distanceSquare(currentVec2)); | |
const nextAccumCost = ( | |
currentMoveGuide.accumCost + | |
nextCost * distance | |
); | |
if (nextMoveGuide.accumCost > nextAccumCost) { | |
nextMoveGuide.accumCost = nextAccumCost; | |
nextMoveGuide.next = currentMoveCost; | |
currentMoveGuide.prevList.push(nextMoveCost); | |
moveCostLinkedList.addBeforeWhere( | |
nextMoveCost, | |
moveCost => this.getVec2(moveCost.vec2).accumCost > nextAccumCost | |
) | |
} | |
}); | |
} | |
} | |
toString() { | |
const vec2StrToArrow = { | |
'(-1, -1)': '↖', | |
'(-1, 0)': '←', | |
'(-1, 1)': '↙', | |
'(0, -1)': '↑', | |
'(0, 0)': '・', | |
'(0, 1)': '↓', | |
'(1, -1)': '↗', | |
'(1, 0)': '→', | |
'(1, 1)': '↘', | |
}; | |
let str = '\n'; | |
for (let y = 0; y < this.data.length; ++y) { | |
for (let x = 0; x < this.data[y].length; ++x) { | |
if (this.data[y][x].accumCost === 0) { | |
str += '☆'; | |
} else { | |
const next = this.data[y][x].next; | |
if (next) { | |
str += vec2StrToArrow[next.vec2.sub(new Vec2(x, y))]; | |
} else { | |
str += '・'; | |
} | |
} | |
} | |
str += '\n'; | |
} | |
return str; | |
} | |
} | |
class GameMap { | |
constructor(mapStr) { | |
this.body = GameMap.parser(mapStr); | |
this.moveNameObj = Object.values(MOVE).map(moveName => { | |
const moveCostPlane = new Plane(this.body.width, this.body.height); | |
for (let [chip, vec2] of this.body) { | |
moveCostPlane.setVec2( | |
vec2, | |
new MoveCost(vec2, chip.chipInfo.moveCost[moveName]) | |
); | |
} | |
const goalMoveCostList = this.body | |
.filter(chip => chip.chipInfo.goalMoveList.includes(moveName)) | |
.map(chip => moveCostPlane.getVec2(chip.vec2)); | |
const surroundingMovableMoveCostPlane = new Plane(this.body.width, this.body.height); | |
for (let [chip, vec2] of this.body) { | |
surroundingMovableMoveCostPlane.setVec2( | |
vec2, | |
GameMap.movableChipList( | |
vec2, | |
GameMap.surroundingChipList(vec2, this.body), | |
moveName | |
).map(chip => moveCostPlane.getVec2(chip.vec2)) | |
); | |
} | |
const moveCostLinkedList = LinkedList.fromArray(goalMoveCostList); | |
const moveGuidePlane = new MoveGuidePlane( | |
this.body.width, | |
this.body.height, | |
moveCostLinkedList, | |
surroundingMovableMoveCostPlane | |
); | |
return [ | |
moveName, | |
{ | |
moveCostPlane, | |
goalMoveCostList, | |
surroundingMovableMoveCostPlane, | |
moveGuidePlane | |
} | |
]; | |
}).reduce((a, c) => (a[c[0]] = c[1], a), {}); | |
} | |
update(chip) { | |
// update mapBody | |
this.body.setVec2(chip.vec2, chip); | |
Object.values(MOVE).map(moveName => { | |
const { | |
moveCostPlane, | |
goalMoveCostList, | |
surroundingMovableMoveCostPlane, | |
moveGuidePlane | |
} = this.moveNameObj[moveName]; | |
// update moveCostPlane | |
moveCostPlane.setVec2( | |
chip.vec2, | |
new MoveCost(chip.vec2, chip.chipInfo.moveCost[moveName]) | |
); | |
// TODO: update goalMoveCostList | |
// update surroundingChip information of surroundingChip | |
// | |
// surrounding walls is not contained in surroundingMovableMoveCostPlane | |
// so, we cannot use surroundingMovableMoveCostPlane | |
GameMap.surroundingChipList(chip.vec2, this.body).forEach(surroundingChip => { | |
const movableChipListOfSurrounding = GameMap.movableChipList( | |
surroundingChip.vec2, | |
GameMap.surroundingChipList(surroundingChip.vec2, this.body), | |
moveName | |
); | |
surroundingMovableMoveCostPlane.setVec2( | |
surroundingChip.vec2, | |
movableChipListOfSurrounding | |
.map(movableChip => moveCostPlane.getVec2(movableChip.vec2)) | |
); | |
}); | |
// update moveGuide of updating chip | |
const currentCost = chip.chipInfo.moveCost[moveName]; | |
const moveCostList = [ | |
new MoveCost(chip.vec2, Infinity), | |
...surroundingMovableMoveCostPlane.getVec2(chip.vec2) | |
.map(surroundingMoveCost => { | |
const moveGuide = moveGuidePlane.getVec2(surroundingMoveCost.vec2); | |
const distance = Math.sqrt(chip.vec2.distanceSquare(surroundingMoveCost.vec2)); | |
return new MoveCost( | |
surroundingMoveCost.vec2, | |
moveGuide.accumCost + | |
currentCost * distance | |
); | |
}) | |
]; | |
const minMoveCost = moveCostList.reduce((a, c) => a.cost > c.cost ? c : a); | |
const isMovable = Number.isFinite(minMoveCost.cost); | |
moveGuidePlane.getVec2(chip.vec2).accumCost = minMoveCost.cost; | |
if (isMovable) { | |
moveGuidePlane.getVec2(chip.vec2).next = moveCostPlane.getVec2(minMoveCost.vec2); | |
} else { | |
moveGuidePlane.getVec2(chip.vec2).next = null; | |
} | |
// update moveGuidePlane | |
// incremental update gives wrong result... | |
const moveCostLinkedList = LinkedList.fromArray(goalMoveCostList); | |
this.moveNameObj[moveName].moveGuidePlane = new MoveGuidePlane( | |
this.body.width, | |
this.body.height, | |
moveCostLinkedList, | |
surroundingMovableMoveCostPlane | |
); | |
}); | |
} | |
static surroundingChipList(vec2, mapBody) { | |
return GameMap.diffVec2List | |
.map(diffVec2 => mapBody.getVec2(vec2.add(diffVec2))) | |
.filter(Boolean); | |
} | |
static parser(str) { | |
const lines = str.split('\n').slice(1, -1); | |
if (lines.length === 0 || lines.some(line => line.length === 0)) { | |
throw new MapParseError(`gameMap data have zero length.`); | |
} | |
if (lines.some(line => line.length !== lines[0].length)) { | |
throw new MapParseError(`gameMap data do not have rectangular shape.`); | |
} | |
const width = lines[0].length; | |
const height = lines.length; | |
const plane = new Plane(width, height); | |
lines.forEach((line, y) => { | |
Array.prototype.forEach.call(line, (ch, x) => { | |
const chipInfo = CHIPSET[ch]; | |
if (!chipInfo) { | |
throw new MapParseError(`${ch} is not defined in CHIPSETs`); | |
} | |
const vec2 = new Vec2(x, y); | |
plane.setVec2(vec2, new Chip(vec2, chipInfo)); | |
}); | |
}); | |
return plane; | |
} | |
static movableChipList(vec2, surroundingChipList, moveName) { | |
return surroundingChipList | |
.filter(chip => Number.isFinite(chip.chipInfo.moveCost[moveName])) | |
.filter((chip, ind, whole) => { | |
switch (moveName) { | |
case MOVE.fly: | |
return true; | |
case MOVE.walk: | |
// forbid diagonal move | |
// | |
// #### | |
// # # can move to up | |
// # S# can move to up left | |
// # ## can move to left | |
// #### can not move to down left | |
// | |
const subVec2 = chip.vec2.sub(vec2); | |
if (subVec2.distanceSquare(Vec2.ORIGIN) === 1) { | |
return true; | |
} | |
const adjacentVec2x = vec2.add(new Vec2(subVec2.x, 0)); | |
const adjacentVec2y = vec2.add(new Vec2(0, subVec2.y)); | |
return ( | |
whole.find(chip => chip.vec2.equal(adjacentVec2x)) && | |
whole.find(chip => chip.vec2.equal(adjacentVec2y)) | |
); | |
default: | |
throw new Error(`${moveName} is not defined in MOVEs`); | |
} | |
}) | |
} | |
} | |
GameMap.diffVec2List = [ | |
new Vec2(-1, -1), | |
new Vec2(-1, 0), | |
new Vec2(-1, +1), | |
new Vec2( 0, -1), | |
new Vec2( 0, +1), | |
new Vec2(+1, -1), | |
new Vec2(+1, 0), | |
new Vec2(+1, +1) | |
]; | |
class Game { | |
constructor() { | |
this.gameMap = new GameMap(SETTINGS.mapStr1); | |
} | |
} | |
class GameRunner { | |
constructor() { | |
const game = new Game(); | |
} | |
} | |
// const gamaRunner = new GameRunner(); | |
const _4_2 = new Vec2(4, 2); | |
const _5_2 = new Vec2(5, 2); | |
const _3_5 = new Vec2(3, 5); | |
gameMap = new GameMap(SETTINGS.mapStr1); | |
console.info(gameMap.moveNameObj.WALK.moveGuidePlane.toString()); | |
gameMap.update(new Chip(_4_2, CHIPSET[' '])); | |
console.info(gameMap.moveNameObj.WALK.moveGuidePlane.toString()); | |
gameMap.update(new Chip(_5_2, CHIPSET[' '])); | |
console.info(gameMap.moveNameObj.WALK.moveGuidePlane.toString()); | |
gameMap.update(new Chip(_3_5, CHIPSET['#'])); | |
console.info(gameMap.moveNameObj.WALK.moveGuidePlane.toString()); | |
const endTime = Date.now(); | |
console.info(`time elapsed: ${endTime - startTime}ms`); | |
})(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment