int frame_count = 0;
int [][] scent_map;
int [][] walk_map;
int map_width = 20;
int map_height = 20;
int map_scale = 20;
Player player;
ArrayList monsters;

void setup(){
  size(400, 400);
  generate();
}
void draw(){
  background(0);
  noStroke();
  for(int r = 0; r < map_height; r++){
    for(int c = 0; c < map_width; c++){
      fill(0, max(0, scent_map[r][c] - (frame_count)), 0);
      myRect(c, r);
    }
  }
  Agent temp;
  for(int i = 0; i < monsters.size(); i++){
    temp = (Agent)monsters.get(i);
    fill(255,0,0);
    myRect(temp.x, temp.y);
  }
  fill(0,255,0);
  myRect(player.x, player.y);
}

void keyPressed(){
  // generate a scent after the player
  scent_map[player.y][player.x] = (frame_count++) + 100;
  if(keyCode == UP && player.y > 0){
    player.y--;
  } 
  else if(keyCode == RIGHT && player.x < map_width-1){
    player.x++;
  } 
  else if(keyCode == DOWN && player.y < map_height-1){
    player.y++;
  } 
  else if(keyCode == LEFT && player.x > 0){
    player.x--;
  }
  Agent temp;
  for(int i = 0; i < monsters.size(); i++){
    temp = (Agent)monsters.get(i);
    temp.seek();
  }
  // on collision - redraw the map
  if(player.collides()){
    generate();
  }
}

void myRect(int x, int y){
  rect(x * map_scale, y * map_scale, map_scale, map_scale);
}

void generate(){
  frame_count = 0;
  scent_map = new int[map_height][map_width];
  walk_map = new int[map_height][map_width];
  for(int r = 0; r < map_height; r++){
    for(int c = 0; c < map_width; c++){
      scent_map[r][c] = -1;
      walk_map[r][c] = 0;
    }
  }
  monsters = new ArrayList();
  for(int i = 0; i < 10; i++){
    monsters.add(new Agent((int)random(map_width), (int)random(map_height)));
  }
  do player = new Player((int)random(map_width), (int)random(map_height));
  while(player.collides());
}

class Dot{
  int x, y;
  Dot(int x, int y){
    this.x = x;
    this.y = y;
  }
}

class Player extends Dot{
  Player(int x, int y){
    super(x, y);
  }
  boolean collides(){
    Agent temp;
    for(int i = 0; i < monsters.size(); i++){
      temp = (Agent)monsters.get(i);
      if(temp.x == x && temp.y == y){
        return true;
      }
    }
    return false;
  }
}

class Node extends Dot{
  int scent;
  int dist;
  boolean walkable;
  Node(int x, int y){
    super(x, y);
    scent = dist = 0;
    walkable = false;
  }
  void set(int x, int y){
    this.x = x;
    this.y = y;
    // use Manhattan distance heuristic
    dist = abs(player.x - x) + abs(player.y - y);
    walkable = x > -1 && y > -1 && x < map_width && y < map_height && walk_map[y][x] == 0;
    if(walkable) scent = scent_map[y][x];
  }
}

class Agent extends Dot{
  // if I wanted to be a bit tighter I could make these
  // utility Nodes static - saving on a lot of memory
  Node [] nodes;
  Node best_node;
  Agent(int x, int y){
    super(x, y);
    nodes = new Node[4];
    for(int i = 0; i < nodes.length; i++){
      nodes[i] = new Node(x, y);
    }
    walk_map[y][x] = 1;
  }
  // essentially what we do here is do head to the next closest node towards the player
  // but if we pick up a scent trail, then we follow it.
  // the effect of this is that although the tracking turns into a conga line
  // we get an effective pursuit of the player with almost no overhead for our troubles
  void seek(){
    nodes[0].set(x, y-1);
    nodes[1].set(x+1, y);
    nodes[2].set(x, y+1);
    nodes[3].set(x-1, y);
    int best_dist = Integer.MAX_VALUE;
    int best_scent = 0;
    best_node = null;
    for(int i = 0; i < nodes.length; i++){
      if(nodes[i].walkable){
        if(nodes[i].scent > best_scent){
          best_scent = nodes[i].scent;
          best_node = nodes[i];
        } 
        else if(best_scent == 0 && nodes[i].dist < best_dist){
          best_dist = nodes[i].dist;
          best_node = nodes[i];
        }
      }
    }
    if(best_node != null){
    walk_map[y][x] = 0;
    x = best_node.x;
    y = best_node.y;
    walk_map[y][x] = 1;
    }
  }
}