とりあえず

tower-defence.js

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`);

})();