The Cell's Cost

The safe and short path in multi-player game is calculated based on the "cost" of the cell. the robot chooses the path which has the lowest total of the cell costs. The cost of each cell is calculated as follows:

Static Cost: (maximal 8.2)

The cell's static cost is calculated as a sum of the following:

• 1.0: the base cost.
• Looking around the adjacent 8 cells, sums up the all "blocking" cost of the patterns matching:
  • Entrance of a narrow gate : cost = 0.2.

     #.#
     _@_
     ___  
    

    ("#" : wall or water "." : a open cell)
    ("_" : don't care "@" : the current location)

  • "Knight's move" gate : cost = 0.4.

     __#
     _@.
     _#_ 
    

  • "Diagonal" gate : cost = 0.6.

     __#
     _@_
     #__ 
    

  • Inside a narrow gate : cost = 0.8.

     _#_
     _@_
     _#_ 
    

  Each type of cost is only added once for one cell. The maximal cost for blocking is therefore 2.0.

"Water-side" cost: if the cell is adjacent to the water, and the cell of the opposite side is open, 3.0 is added to the cost. If this condition happens both horizontally and vertically, 6.0 is added.

 _._
 _@_
 _~_ 

Examples:

 ###
 .@.
 ###

cost = 3.0 (entrance, narrow, diagonal, knight)

 ~.~
 .@~
 ~~~

cost = 8.2 (entrance, diagonal, knight, double water)

Dynamic Cost:

• If a cell is occupied by an enemy robot, the following value is multiplied to the static cost.
  
  max(5.0, 16.0 - distance²),
  where distance is the lowest path cost between the cell and the current robot location.

  If the blocked cell is near the current location, the path going through that cell is strongly discouraged. If it is far away, however, the blocking robot may move to another location before the robot reaches there. So we added the quadratic decay to the equation above.

• If a cell is adjacent to enemy robots, the following value is multiplied to the static cost.
  
  max(1.25, 4.0 - distance²)
• Otherwise, the static cost is used as is.

"zigzag"-walk preference:

When the Dijkstra's algorithm traverses the field, 1.01 is multiplied to the dynamic cost if two successive steps are in the same direction. This penalty is relatively small, but it makes the robot's move more zigzag-like rather than "L"-shaped. We added this small hack expecting to avoid taking the same congested path as the paths of other robots.