1 # Monsterz - Chains of Friends
3 # 2010-2014 (c) Jean Privat <jean@pryen.org>
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.
16 # The modelization of the friendzs problem.
18 super BacktrackProblem[Grid, Action]
20 redef var initial_state
22 redef fun actions
(state
, node
)
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
)
34 return state
.look_start
37 redef fun apply_action
(state
, action
)
39 action
.tile
.update
(action
.kind
)
42 redef fun backtrack
(state
, action
)
47 redef fun is_goal
(state
)
54 # Return true if grid accepts kind at tile t.
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
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
67 if i
==0 and j
==0 or i
!=0 and j
!=0 then continue
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
75 if cpt
>=3 then return false
82 # Return the list of accepting neighbors of t
84 fun frees
(t
: Tile): Array[Tile]
87 var res
= new Array[Tile]
90 if i
==0 and j
==0 or i
!=0 and j
!=0 then continue
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
)
101 # Search free tiles next to lonely monsters
102 fun look_start
: Array[Action]
105 var start
= new Array[Tile]
109 for x
in [0..grid
.width
[ do
110 for y
in [0..grid
.height
[ do
111 var t
= grid
.grid
[x
][y
]
113 if k
== 0 or grid
.monsters
[k
].chain
then continue
116 if n
> min
then continue
120 if l
== 0 then continue
123 if min
== 1 or start
.length
> l
then
127 else if kind
== 0 or kind
== k
then
135 var res
= new Array[Action]
137 res
.add t
.to_action
(kind
)
139 #print "-------------"
142 #print "START: {tile} -> {start.join(",")}"
143 #print "-------------"
147 # compute and print some metrics about the problem
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
160 for m
in grid
.monsters
do
161 if m
.number
> 0 then ms
+= 1
164 print
"SIZE: {(ms+1).to_f.pow(free.to_f)}"
171 redef fun to_s
do return "{tile}->{kind}"
175 fun to_action
(kind_to_play
: Int): Action do return new Action(self, kind_to_play
)