nextTankId = 0

-------------------------
-- Creates a new bot-tank
-------------------------
function newBotTank(name, posX, posY, dir, color)
   local o = {}
   
   
   ------------------------------
   -- Constructor of the bot-tank
   ------------------------------
   function o:construct(name, posX, posY, dir, color)
      self.super = newTank(name, posX, posY, dir, color)
      setmetatable(self, { __index = self.super, __newindex = self.super } )
      
      -- Load the AI-label sprite
      self.aiLabelSprite = newSprite("images/sprites.png", 76, 114, 29, 15)
      self.aiLabelSprite:setCenter(0.5, 0.5)
      self.aiLabelTime = 0.0
      self.aiLabelAlpha = 0
      
      -- Create the map of the accessible tiles
      -- (each value corresponds to the "cost" to go the tile)
      self.accessibleTiles = {}
      for i = 0, boombastic.numTilesX - 1 do
         self.accessibleTiles[i] = {}
         for j = 0, boombastic.numTilesY - 1 do
            self.accessibleTiles[i][j] = nil
         end
      end
      
      -- Create the map of the dangerous tiles (greater the value is, greater the danger is)
      self.dangerousTiles = {}
      for i = 0, boombastic.numTilesX - 1 do
         self.dangerousTiles[i] = {}
         for j = 0, boombastic.numTilesY - 1 do
            self.dangerousTiles[i][j] = 0
         end
      end
      
      self.targetTileX = nil
      self.targetTileY = nil
      self.id = nextTankId
      nextTankId = nextTankId + 1
      
      return self
   end
   
   
   -----------------------------------------------------------
   -- Updates the map of the accessible tiles, by calculating,
   -- for each tile, the cost to go to this tile
   -----------------------------------------------------------
   function o:updateAccessibleTiles()
      local dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }
      local posX, posY = convertPixelsToTile(self.x, self.y)
      
      -- Clear the map of accessible-tiles
      for i = 0, boombastic.numTilesX - 1 do
         for j = 0, boombastic.numTilesY - 1 do
            if (not boombastic.map:tileIsBlock(i, j)) then
               self.accessibleTiles[i][j] = (math.abs(i - posX) + math.abs(j - posY)) * 100000
            else
               self.accessibleTiles[i][j] = nil
            end
         end
      end
      
      -- Apply the dijkstra algorithm to calculate the cost of each tile
      -- We don't do all the iterations because PSP is not powerful enough...
      self.accessibleTiles[posX][posY] = 0
      local queue = { posX, posY, next = nil }
      
      local numIterations = 0
      while (queue and numIterations < 10) do
         local curTile = queue
         queue = queue.next
         local curCost = self.accessibleTiles[curTile[1]][curTile[2]]
         
         for i = 1, 4 do
            local tileX = curTile[1] + dirs[i][1]
            local tileY = curTile[2] + dirs[i][2]
            
            if (tileIsInMap(tileX, tileY)
                  and not boombastic.map:tileIsBlock(tileX, tileY)
                  and self.accessibleTiles[tileX][tileY] >= 100000) then
               
               -- Evaluate the cost of the current tile
               if (boombastic.rocks:tileIsRock(tileX, tileY)) then
                  cost = curCost + 1000
               elseif (self.dangerousTiles[tileX][tileY] ~= 0) then
                  cost = curCost + self.dangerousTiles[tileX][tileY] * 100
               elseif (boombastic.bonuses:tileIsBonus(tileX, tileY)) then
                  cost = curCost + 1
               else
                  cost = curCost + 10
               end
               self.accessibleTiles[tileX][tileY] = cost
               
               -- Insert the new element sorted into the queue
               local prev = nil
               local cur = queue
               while (cur and self.accessibleTiles[cur[1]][cur[2]] < cost) do
                  prev = cur
                  cur = cur.next
               end
               if (prev) then
                  prev.next = { tileX, tileY, next = prev.next }
               else
                  queue = { tileX, tileY, next = queue }
               end
            end
         end
         
         numIterations = numIterations + 1
      end
   end
   
   
   ----------------------------------------------------------------------------
   -- Updates the map of the dangerous tiles: greater the value of the grid is,
   -- greater the danger is for the tank
   ----------------------------------------------------------------------------
   function o:updateDangerousTiles()
      local dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }
      
      -- Clear the map of dangerous-tiles
      for i = 0, boombastic.numTilesX - 1 do
         for j = 0, boombastic.numTilesY - 1 do
            self.dangerousTiles[i][j] = 0
         end
      end
      
      -- Mark the position of the other tanks as dangerous
      for k, tank in ipairs(boombastic.tanks) do
         if (tank ~= self and tank:isAlive()) then
            local tankTileX, tankTileY = convertPixelsToTile(tank.x, tank.y)
            self.dangerousTiles[tankTileX][tankTileY] = 1
         end
      end
      
      -- Mark the tiles where there is a bomb or an explosion as dangerous
      for i = 0, boombastic.numTilesX - 1 do
         for j = 0, boombastic.numTilesY - 1 do
            if (boombastic.bombs:tileIsBomb(i, j)) then
               local power = boombastic.bombs:getBombPower(i, j)
               self.dangerousTiles[i][j] = 2
               
               for k = 1, 4 do
                  for l = 1, power do
                     local posX = i + l * dirs[k][1]
                     local posY = j + l * dirs[k][2]
                     
                     if (tileIsBlocking(posX, posY)) then
                        break
                     end
                     
                     if (self.dangerousTiles[posX][posY] < 2) then
                        self.dangerousTiles[posX][posY] = 2
                     end
                  end
               end
            end
            
            if (boombastic.explosions:tileIsExplosion(i, j)) then
               self.dangerousTiles[i][j] = 3
            end
         end
      end
   end
   
   
   -------------------------------------------------
   -- Returns the nearest safe-tile for the tank
   -------------------------------------------------
   function o:getNearestSafeTile()
      local tileX = nil
      local tileY = nil
      local cost = nil
      
      for i = 0, boombastic.numTilesX - 1 do
         for j = 0, boombastic.numTilesY - 1 do
            if (self.dangerousTiles[i][j] == 0 and self.accessibleTiles[i][j]
                  and (not cost or cost > self.accessibleTiles[i][j])) then
               tileX = i
               tileY = j
               cost = self.accessibleTiles[i][j]
            end
         end
      end
      
      return tileX, tileY
   end
   
   
   -------------------------------------------------------------------
   -- Gets the direction to take for the tank to go to its target-tile
   -------------------------------------------------------------------
   function o:getDirectionToTarget()
      local tankTileX, tankTileY = convertPixelsToTile(self.x, self.y)
      
      
      -- If the tank is already on the target-tile or if it is idle, we make
      -- sure it is not at more than 5 pixels from the center of the current tile
      if (not self.targetTileX or not self.targetTileY
            or (tankTileX == self.targetTileX and tankTileY == self.targetTileY)) then
         local targetX, targetY = convertTileToPixels(tankTileX, tankTileY)
         local deltaX = self.x - targetX
         local deltaY = self.y - targetY
         
         if (deltaX <= -5) then
            return TankDirection.RIGHT
         elseif (deltaX >= 5) then
            return TankDirection.LEFT
         elseif (deltaY <= -5) then
            return TankDirection.DOWN
         elseif (deltaY >= 5) then
            return TankDirection.UP
         end
      
      
      -- If the tank is not already on the target-tile, we calculate the
      -- shortest (cost-wise) path to the target-tile, and we return the first
      -- direction to take
      else
         local curTileX = self.targetTileX
         local curTileY = self.targetTileY
         local dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }
         local dir = nil
         
         if (not self.accessibleTiles[curTileX][curTileY]) then
            return nil
         end
         
         local cost = self.accessibleTiles[curTileX][curTileY]
         while (curTileX and curTileY) do
            local nextTileX = nil
            local nextTileY = nil
            
            for i = 1, 4 do
               local tileX = curTileX + dirs[i][1]
               local tileY = curTileY + dirs[i][2]
               
               if (tileIsInMap(tileX, tileY) and self.accessibleTiles[tileX][tileY]) then
                  if (self.accessibleTiles[tileX][tileY] < cost) then
                     nextTileX = tileX
                     nextTileY = tileY
                     cost = self.accessibleTiles[tileX][tileY]
                     dir = i - 1
                  end
               end
            end
            
            curTileX = nextTileX
            curTileY = nextTileY
         end
         
         return dir
      end
   end
   
   
   ---------------------------------------------
   -- Makes the tank try to reach the given tile
   ---------------------------------------------
   function o:goToTile(tileX, tileY)
      self.targetTileX = tileX
      self.targetTileY = tileY
   end
   
   
   -----------------------
   -- Updates the bot-tank
   -----------------------
   function o:update(dt)
      if (not self:isAlive()) then
         return
      end
      
      local shouldHaveMoved = false
      local x, y = self.x, self.y
      local dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }
      local tileX, tileY = convertPixelsToTile(x, y)
      
      if (system.getFrame() % nextTankId == self.id) then
         
         -- Update the map of dangerous-tiles and the map of accessible-tiles
         self:updateDangerousTiles()
         self:updateAccessibleTiles()
         local safe = (self.dangerousTiles[tileX][tileY] == 0)
         
         -- Calculate which tank will be our target (the nearest one)
         local targetTankTileX = 0
         local targetTankTileY = 0
         local targetTankDistance = 99999
         for k, tank in ipairs(boombastic.tanks) do
            if (tank ~= self and tank:isAlive()) then
               local distance = math.abs(self.x - tank.x) + math.abs(self.y - tank.y)
               if (distance < targetTankDistance) then
                  targetTankTileX, targetTankTileY = convertPixelsToTile(tank.x, tank.y)
                  targetTankDistance = distance
               end
            end
         end
         
         -- Update the target-tile of the tank
         if (not safe) then
            local safeTileX, safeTileY = self:getNearestSafeTile()
            self:goToTile(safeTileX, safeTileY)
         elseif (self.numBombs > 0) then
            self:goToTile(targetTankTileX, targetTankTileY)
         else
            self:goToTile(nil, nil)
         end
         
         -- If the tank is near enough from another tank, we drop a bomb
         if (safe) then
            for k, tank in ipairs(boombastic.tanks) do
               if (tank ~= self and tank:isAlive()) then
                  local tankTileX, tankTileY = convertPixelsToTile(tank.x, tank.y)
                  if ((tileX == tankTileX and math.abs(tileY - tankTileY) <= 1)
                        or (tileY == tankTileY and math.abs(tileX - tankTileX) <= 1)) then
                     self:dropBomb()
                  end
               end
            end
         end
      end
      
      -- Move the tank in order to reach the target-tile
      local dir = self:getDirectionToTarget()
      if (dir) then
         local nextTileX = tileX + dirs[dir + 1][1]
         local nextTileY = tileY + dirs[dir + 1][2]
         if (not tileIsInMap(nextTileX, nextTileY)
               or self.dangerousTiles[tileX][tileY] >= self.dangerousTiles[nextTileX][nextTileY]) then
            self:move(dir)
            shouldHaveMoved = true
         end
      end
      self.super:update(dt)
      
      -- If the tank should have moved but hasn't (i.e. it is blocked), we drop a bomb
      if (shouldHaveMoved and dt > 0.0 and dt < 0.2 and x == self.x and y == self.y) then
         self:dropBomb()
      end
      
      -- Animate the "AI" label
      self.aiLabelTime = self.aiLabelTime + dt
      if (self.aiLabelTime < 3) then
         self.aiLabelAlpha = 255
      elseif (self.aiLabelTime < 4) then
         self.aiLabelAlpha = (1 - (self.aiLabelTime - 3)) * 255
      else
         self.aiLabelAlpha = 0
      end
   end
   
   
   ---------------------
   -- Draws the bot-tank
   ---------------------
   function o:draw()
      self.super:draw()
      
      if (self:isAlive()) then
         self.aiLabelSprite:draw(boombastic.origX + self.x + 30, boombastic.origY + self.y,
                                 0, 1, 1, self.aiLabelAlpha)
      end
   end
   
   
   return o:construct(name, posX, posY, dir, color)
end
