contrib/friendz/src/solver.nit

   1 # Monsterz - Chains of Friends
   2 #
   3 # 2010-2014 (c) Jean Privat <jean@pryen.org>
   4 #
   5 # This program is free software; you can redistribute it and/or
   6 # modify it under the terms of the Do What The Fuck You Want To
   7 # Public License, Version 2, as published by Sam Hocevar. See
   8 # http://sam.zoy.org/projects/COPYING.WTFPL for more details.
   9
  10 # Basic game solver
  11 module solver
  12
  13 intrude import grid
  14 import ai::backtrack
  15
  16 # The modelization of the friendzs problem.
  17 class FriendzProblem
  18         super BacktrackProblem[Grid, Action]
  19
  20         redef var initial_state
  21
  22         redef fun actions(state, node)
  23         do
  24                 var last_action = node.action
  25                 if state.won then return null
  26                 if last_action != null then
  27                         var res = state.frees(last_action.tile)
  28                         if not res.is_empty or last_action.tile.nexts != 2 then
  29                                 var a = new Array[Action]
  30                                 for t in res do a.add t.to_action(last_action.kind)
  31                                 return a
  32                         end
  33                 end
  34                 return state.look_start
  35         end
  36
  37         redef fun apply_action(state, action)
  38         do
  39                 action.tile.update(action.kind)
  40         end
  41
  42         redef fun backtrack(state, action)
  43         do
  44                 action.tile.update(0)
  45         end
  46
  47         redef fun is_goal(state)
  48         do
  49                 return state.won
  50         end
  51 end
  52
  53 redef class Grid
  54         # Return true if grid accepts kind at tile t.
  55         # Accepts means that
  56         # * the tile is playble (free and not fixed)
  57         # * the new monster will not be angry
  58         # * the new monster will not make neighbor angry
  59         fun accepts(t: Tile, kind: Int): Bool
  60         do
  61                 var grid = t.grid
  62                 if t.kind != 0 or t.fixed then return false
  63                 #if t.x<0 or t.x>=grid.width or t.y<0 or t.y>=grid.height then return false
  64                 var cpt = 0
  65                 for i in [-1..1] do
  66                         for j in [-1..1] do
  67                                 if i==0 and j==0 or i!=0 and j!=0 then continue
  68                                 var x2 = t.x+i
  69                                 var y2 = t.y+j
  70                                 if x2<0 or x2>=grid.width or y2<0 or y2>=grid.height then continue
  71                                 var t2 = grid.grid[x2][y2]
  72                                 if t2.kind == kind then
  73                                         if t2.nexts >= 2 then return false
  74                                         cpt += 1
  75                                         if cpt>=3 then return false
  76                                 end
  77                         end
  78                 end
  79                 return true
  80         end
  81
  82         # Return the list of accepting neighbors of t
  83         # see `accepts`
  84         fun frees(t: Tile): Array[Tile]
  85         do
  86                 var grid = t.grid
  87                 var res = new Array[Tile]
  88                 for i in [-1..1] do
  89                         for j in [-1..1] do
  90                                 if i==0 and j==0 or i!=0 and j!=0 then continue
  91                                 var x2 = t.x+i
  92                                 var y2 = t.y+j
  93                                 if x2<0 or x2>=grid.width or y2<0 or y2>=grid.height then continue
  94                                 var t2 = grid.grid[x2][y2]
  95                                 if accepts(t2, t.kind) then res.push(t2)
  96                         end
  97                 end
  98                 return res
  99         end
 100
 101         # Search free tiles next to lonely monsters
 102         fun look_start: Array[Action]
 103         do
 104                 var grid = self
 105                 var start = new Array[Tile]
 106                 var min = 1
 107                 var kind = 0
 108
 109                 for x in [0..grid.width[ do
 110                         for y in [0..grid.height[ do
 111                                 var t = grid.grid[x][y]
 112                                 var k = t.kind
 113                                 if k == 0 or grid.monsters[k].chain then continue
 114                                 var n = t.nexts
 115
 116                                 if n > min then continue
 117
 118                                 var fs = frees(t)
 119                                 var l = fs.length
 120                                 if l == 0 then continue
 121
 122                                 if n == 0 then
 123                                         if min == 1 or start.length > l then
 124                                                 start = fs
 125                                                 kind = k
 126                                         end
 127                                 else if kind == 0 or kind == k then
 128                                         start.add_all fs
 129                                         kind = k
 130                                 end
 131
 132                                 min = n
 133                         end
 134                 end
 135                 var res = new Array[Action]
 136                 for t in start do
 137                         res.add t.to_action(kind)
 138                 end
 139                 #print "-------------"
 140                 #print grid
 141                 #dump
 142                 #print "START: {tile} -> {start.join(",")}"
 143                 #print "-------------"
 144                 return res
 145         end
 146
 147         # compute and print some metrics about the problem
 148         fun size_problem
 149         do
 150                 var grid = self
 151                 var free = 0
 152                 for x in [0..grid.width[ do
 153                         for y in [0..grid.height[ do
 154                                 var t = grid.grid[x][y]
 155                                 if t.kind == 0 and not t.fixed then free += 1
 156                         end
 157                 end
 158                 print "FREE: {free}"
 159                 var ms = 0
 160                 for m in grid.monsters do
 161                         if m.number > 0 then ms += 1
 162                 end
 163                 print "KINDS: {ms}"
 164                 print "SIZE: {(ms+1).to_f.pow(free.to_f)}"
 165         end
 166 end
 167
 168 class Action
 169         var tile: Tile
 170         var kind: Int
 171         redef fun to_s do return "{tile}->{kind}"
 172 end
 173
 174 redef class Tile
 175         fun to_action(kind_to_play: Int): Action do return new Action(self, kind_to_play)
 176 end