A*

library astar;

import 'dart:html';
//import 'dart:async';
import 'dart:collection';

CanvasElement canvas;
CanvasRenderingContext2D context;
List<List<int>> world;
//Timer running;
Vector mouse, currentTilePosition, previousTilePosition, start, end;

int width = 480, height = 480, FPS = 60;

void main() {
  
  mouse = new Vector.zero();
  previousTilePosition = new Vector.zero();
  
  canvas = new CanvasElement(width: width, height: height);
  query('body').children.add(canvas);
  
  context = canvas.getContext("2d");
  canvas  
    ..onMouseMove.listen((event) => onMouseMove(event))
    ..onMouseDown.listen((event) => onMouseDown(event))
    ..onMouseUp.listen((event) => onMouseUp(event))
    ..onContextMenu.listen((event) => event.preventDefault());
  
  world = new List<List<int>>(30);
  for (var y = 0; y < 30; y++) {
    world[y] = new List<int>(30);
    for (var x = 0; x < 30; x++) {
      world[y][x] = 0;
    }
  }
  
  //running = new Timer.periodic(new Duration(milliseconds: 1000 ~/ FPS), (Timer timer) => update());
  window.requestAnimationFrame(draw);
}

void update() {

}

void draw(num _) {
  
  for (var y = 0; y < 30; y++) {
    for (var x = 0; x < 30; x++) {
      
      if (world[x][y] == 0)
        context.fillStyle = '#999';
      else if (world[x][y] == 1)
        context.fillStyle = '#faa';
      else if (world[x][y] == 2)
        context.fillStyle = '#afa';
      else if (world[x][y] == 3)
        context.fillStyle = '#ccc';
      else if (world[x][y] == 4)
        context.fillStyle = '#aaf';
      
      context
        ..beginPath()
        ..rect(x * 16, y * 16, 16, 16)
        ..fill()
        ..lineWidth = 1
        ..strokeStyle = '#333'
        ..stroke();
    }
  }
  
  window.requestAnimationFrame(draw);
}

void updateMouse(MouseEvent evt) {
  mouse.x = evt.client.x - canvas.getBoundingClientRect().left;
  mouse.y = evt.client.y - canvas.getBoundingClientRect().top;
  
  currentTilePosition = getHoveredTilePosition();
}

void onMouseMove(MouseEvent evt) {
  updateMouse(evt);
  setTile(evt);
    
  // only run A* when a mouse button is pressed and the tile has changed
  if (evt.which != 0)
    if (currentTilePosition.x != previousTilePosition.x || currentTilePosition.y != previousTilePosition.y) {  
      previousTilePosition = currentTilePosition;
      aStar();
    }
}

void onMouseDown(MouseEvent evt) {
  // prevent the mouse cursor from changing
  evt.preventDefault();
}

void onMouseUp(MouseEvent evt) {  
  setTile(evt);
  aStar();
}

void setTile(MouseEvent evt) {     
  if (evt.which == 1) {
    if (start != null)
      world[start.x][start.y] = 0;
    start = new Vector(currentTilePosition.x, currentTilePosition.y);
    world[currentTilePosition.x][currentTilePosition.y] = 1;  
  }
  else if (evt.which == 2) {
    if (end != null)
      world[end.x][end.y] = 0;
    end = new Vector(currentTilePosition.x, currentTilePosition.y);
    world[currentTilePosition.x][currentTilePosition.y] = 2; 
  }
  else if (evt.which == 3) {
    if (currentTilePosition.x != previousTilePosition.x || currentTilePosition.y != previousTilePosition.y) {
    if (world[currentTilePosition.x][currentTilePosition.y] != 3)
      world[currentTilePosition.x][currentTilePosition.y] = 3;
    else
      world[currentTilePosition.x][currentTilePosition.y] = 0;
    }
  } 
}

/*
 * Adds or updates a node with the position [x] and [y] and sets the [parent].
 */
void addOrUpdateNode(int x, int y, Node parent, List<Node> open, List<Node> closed) {
  
  // return if its not a valid tile
  if (!(world[x][y] == 0 || world[x][y] == 2))
    return;
  
  // return if its already in the closed list
  for (var i = 0; i < closed.length; i++) {
    if (closed[i].position.x == x && closed[i].position.y == y) {
      return;
    }
  }
  
  // update and return if its already in the open list
  for (var i = 0; i < open.length; i++) {
    if (open[i].position.x == x && open[i].position.y == y) {
      if (parent.g + 10 < open[i].g) {
        open[i].parent = parent;
        open[i].g = parent.g + 10;
        open[i].f = open[i].g + open[i].h;
      }
      return;
    }
  }
  
  // else add it to open list
  open.add(new Node(x, y, parent));
}

/*
 * Sets the individual nodes after a path has been found
 */
void setNode(Node node) {
  // don't set node over start and end positions
  if (!((node.position.x == start.x && node.position.y == start.y) ||
      (node.position.x == end.x && node.position.y == end.y)))
    world[node.position.x][node.position.y] = 4;
  
  // continue with parent node
  if (node.parent != null) {
    setNode(node.parent);
  }
}

/**
 * Main function of A*, finds a path from the start to the end.
 */
void aStar() {
  if (start != null && end != null) {
    
    // clear world of current route
    for (var y = 0; y < 30; y++) {
      for (var x = 0; x < 30; x++) {
        if (world[x][y] == 4)
          world[x][y] = 0;
      }
    }
      
    Node startNode = new Node(start.x, start.y);
    Node endNode;
    
    List<Node> open = new List();
    List<Node> closed = new List();
       
    open.add(startNode);
        
    while (open.length > 0) {
     
      // take first node from open list
      Node currentNode = open.removeAt(0);
      
      // first check if its the end point
      if (currentNode.position.x == end.x && currentNode.position.y == end.y) {
        endNode = currentNode;
        break;
      }
    
      // add neighbours
      if (currentNode.position.x - 1 > -1)
        addOrUpdateNode(currentNode.position.x - 1, currentNode.position.y, currentNode, open, closed);
      if (currentNode.position.x + 1 < 30)
        addOrUpdateNode(currentNode.position.x + 1, currentNode.position.y, currentNode, open, closed);
      if (currentNode.position.y - 1 > -1)
        addOrUpdateNode(currentNode.position.x, currentNode.position.y - 1, currentNode, open, closed);
      if (currentNode.position.y + 1 < 30)
        addOrUpdateNode(currentNode.position.x, currentNode.position.y + 1, currentNode, open, closed);
      
      // add node to closed list
      closed.add(currentNode);     
      
      // sort open list
      open.sort((Node a, Node b) {
        return (a.f - b.f);
      });   
    }
    
    // if a path has been found set the nodes
    if (endNode != null) {
      setNode(endNode);
    }
    
  }
}

Vector getHoveredTilePosition() {
  return new Vector(
      mouse.x ~/ 16,
      mouse.y ~/ 16);
}

class Vector {
  num x, y;
  
  Vector(this.x, this.y);
  Vector.zero() : x = 0, y = 0;
  
  Vector operator +(Vector other) => new Vector(x + other.x, y + other.y);
  
  String toString() {
    return "$x/$y";
  }
}

class Node {
  Vector position;
  Node parent;
  int g = 0, h = 0, f = 0;
  
  Node(int x, int y, [Node parent]) {
    this.position = new Vector(x, y);
    if (parent != null) {
      this.parent = parent;
      g = parent.g + 10; // current movement cost
    }
    h = (x - end.x).abs() + (y - end.y).abs(); // heuristic movement cost to target (manhattan distance)
    f = g + h; // total movement cost
  }
}