· 4 years ago · Apr 15, 2021, 07:54 PM
1import scala.collection.mutable.Queue
2object ControlFunction
3{
4 def forMaster(bot: Bot) {
5
6 val (directionValue, nearestEnemyMaster, nearestEnemySlave) = analyzeViewAsMaster(bot.view)
7
8 val dontFireMissileUntil = bot.inputAsIntOrElse("dontFireMissileUntil", -1)
9 val dontFireMineUntil = bot.inputAsIntOrElse("dontFireMineUntil", -1)
10 var direction = BFS(bot, bot.view)
11 // jei BFS neveikia
12 if (XY(0,0) == direction) {
13 val lastDirection = bot.inputAsIntOrElse("lastDirection", 0)
14 directionValue(lastDirection) += 10 // try to break ties by favoring the last direction
15 val bestDirection45 = directionValue.zipWithIndex.maxBy(_._1)._2
16 direction = XY.fromDirection45(bestDirection45)
17 bot.set("lastDirection" -> bestDirection45)
18 }
19 // determine movement direction
20 bot.move(direction)
21
22 if (bot.energy > 100 && bot.time > dontFireMissileUntil) {
23 nearestEnemyMaster match {
24 case None => // no-on nearby
25 case Some(relPos) => // a master is nearby
26 val unitDelta = relPos.signum
27 val remainder = relPos - unitDelta // we place slave nearer target, so subtract that from overall delta
28 bot.spawn(unitDelta, "mood" -> "Missile", "target" -> remainder)
29 bot.set("dontFireMissileUntil" -> (bot.time + relPos.stepCount + 1))
30 }
31 } else
32 if (bot.energy > 100 && bot.time > dontFireMineUntil) {
33 bot.spawn(direction.negateX.negateY, "mood" -> "Mine")
34 bot.set("dontFireMineUntil" -> (bot.time + 100))
35 }
36 }
37
38
39 def forSlave(bot: MiniBot) {
40 bot.inputOrElse("mood", "Lurking") match {
41 case "Missile" => reactAsMissile(bot)
42 case "Mine" => reactAsMine(bot)
43 case s: String => bot.log("unknown mood: " + s)
44 }
45 }
46
47 def reactAsMine(bot: MiniBot) {
48 bot.view.offsetToNearest('b') match {
49 case Some(delta: XY) =>
50 if (delta.length <= 2) {
51 bot.explode(4)
52 }
53 case None =>
54 bot.log("Waiting for enemies to move closer.")
55 }
56 }
57
58 def reactAsMissile(bot: MiniBot) {
59 bot.view.offsetToNearest('s') match {
60 case Some(delta: XY) =>
61 // another slave is visible at the given relative position (i.e. position delta)
62 // move closer!
63 bot.move(delta.signum)
64 bot.set("rx" -> delta.x, "ry" -> delta.y)
65
66 case None =>
67 // no target visible -- follow our targeting strategy
68 val target = bot.inputAsXYOrElse("target", XY.Zero)
69
70 // did we arrive at the target?
71 if(target.isNonZero) {
72 // no -- keep going
73 val unitDelta = target.signum // e.g. CellPos(-8,6) => CellPos(-1,1)
74 bot.move(unitDelta)
75
76 // compute the remaining delta and encode it into a new 'target' property
77 val remainder = target - unitDelta // e.g. = CellPos(-7,5)
78 bot.set("target" -> remainder)
79 } else {
80 // yes -- but we did not annihilate yet, and are not pursuing anything?!? => switch purpose
81 bot.set("mood" -> "Lurking", "target" -> "")
82 bot.say("Lurking")
83 }
84 }
85 }
86 def BFS(bot: Bot, view: View) : XY = {
87 var discovered = Set[XY]()
88 val queue = new Queue[XY]()
89 var path = Map[XY,XY]()
90 queue.enqueue(XY(0,0))
91 // Mapo isprintinimas
92 for (j <- -15 to 15){
93 var newString = ""
94 for (i <- -15 to 15){
95 bot
96 newString = newString+view(XY(i,(j))).toString()
97 }
98 bot.log(newString)
99 }
100
101 while(!queue.isEmpty){
102 var current = queue.dequeue()
103 for (i <- -1 to 1; j <- -1 to 1) {
104 var naujasCheck = current + XY(i,j)
105 bot.log(naujasCheck.toString())
106 // didziausias bot view
107 if(naujasCheck.x >= -15 && naujasCheck.y >= -15 && naujasCheck.x <= 15 && naujasCheck.y <= 15){
108 var cellValue = view(naujasCheck)
109 var exactlyNow = current
110 if(cellValue == 'P' || cellValue == 'B'){
111 if(naujasCheck.length < 1.4){
112 return naujasCheck
113 }
114 if(current.length > 1.5){
115 current = path(current)
116 }
117 }
118 if(cellValue == '_' && !discovered.contains(naujasCheck)){
119 queue.enqueue(naujasCheck)
120 discovered += naujasCheck
121 path += (naujasCheck -> current)
122 }
123 }
124 }
125 }
126 return XY(0,0)
127 }
128
129
130 /** Analyze the view, building a map of attractiveness for the 45-degree directions and
131 * recording other relevant data, such as the nearest elements of various kinds.
132 */
133 def analyzeViewAsMaster(view: View) = {
134 val directionValue = Array.ofDim[Double](8)
135 var nearestEnemyMaster: Option[XY] = None
136 var nearestEnemySlave: Option[XY] = None
137
138 val cells = view.cells
139 val cellCount = cells.length
140 for(i <- 0 until cellCount) {
141 val cellRelPos = view.relPosFromIndex(i)
142 if(cellRelPos.isNonZero) {
143 val stepDistance = cellRelPos.stepCount
144 val value: Double = cells(i) match {
145 case 'm' => // another master: not dangerous, but an obstacle
146 nearestEnemyMaster = Some(cellRelPos)
147 if(stepDistance < 2) -1000 else 0
148
149 case 's' => // another slave: potentially dangerous?
150 nearestEnemySlave = Some(cellRelPos)
151 -100 / stepDistance
152
153 case 'S' => // out own slave
154 0.0
155
156 case 'B' => // good beast: valuable, but runs away
157 if(stepDistance == 1) 600
158 else if(stepDistance == 2) 300
159 else (150 - stepDistance * 15).max(10)
160
161 case 'P' => // good plant: less valuable, but does not run
162 if(stepDistance == 1) 500
163 else if(stepDistance == 2) 300
164 else (150 - stepDistance * 10).max(10)
165
166 case 'b' => // bad beast: dangerous, but only if very close
167 if(stepDistance < 4) -400 / stepDistance else -50 / stepDistance
168
169 case 'p' => // bad plant: bad, but only if I step on it
170 if(stepDistance < 2) -1000 else 0
171
172 case 'W' => // wall: harmless, just don't walk into it
173 if(stepDistance < 2) -1000 else 0
174
175 case _ => 0.0
176 }
177 val direction45 = cellRelPos.toDirection45
178 directionValue(direction45) += value
179 }
180 }
181 (directionValue, nearestEnemyMaster, nearestEnemySlave)
182 }
183}
184
185
186
187// -------------------------------------------------------------------------------------------------
188// Framework
189// -------------------------------------------------------------------------------------------------
190
191class ControlFunctionFactory {
192 def create = (input: String) => {
193 val (opcode, params) = CommandParser(input)
194 opcode match {
195 case "React" =>
196 val bot = new BotImpl(params)
197 if( bot.generation == 0 ) {
198 ControlFunction.forMaster(bot)
199 } else {
200 ControlFunction.forSlave(bot)
201 }
202 bot.toString
203 case _ => "" // OK
204 }
205 }
206}
207
208
209// -------------------------------------------------------------------------------------------------
210
211
212trait Bot {
213 // inputs
214 def inputOrElse(key: String, fallback: String): String
215 def inputAsIntOrElse(key: String, fallback: Int): Int
216 def inputAsXYOrElse(keyPrefix: String, fallback: XY): XY
217 def view: View
218 def energy: Int
219 def time: Int
220 def generation: Int
221
222 // outputs
223 def move(delta: XY) : Bot
224 def say(text: String) : Bot
225 def status(text: String) : Bot
226 def spawn(offset: XY, params: (String,Any)*) : Bot
227 def set(params: (String,Any)*) : Bot
228 def log(text: String) : Bot
229}
230
231trait MiniBot extends Bot {
232 // inputs
233 def offsetToMaster: XY
234
235 // outputs
236 def explode(blastRadius: Int) : Bot
237}
238
239
240case class BotImpl(inputParams: Map[String, String]) extends MiniBot {
241 // input
242 def inputOrElse(key: String, fallback: String) = inputParams.getOrElse(key, fallback)
243 def inputAsIntOrElse(key: String, fallback: Int) = inputParams.get(key).map(_.toInt).getOrElse(fallback)
244 def inputAsXYOrElse(key: String, fallback: XY) = inputParams.get(key).map(s => XY(s)).getOrElse(fallback)
245
246 val view = View(inputParams("view"))
247 val energy = inputParams("energy").toInt
248 val time = inputParams("time").toInt
249 val generation = inputParams("generation").toInt
250 def offsetToMaster = inputAsXYOrElse("master", XY.Zero)
251
252
253 // output
254
255 private var stateParams = Map.empty[String,Any] // holds "Set()" commands
256 private var commands = "" // holds all other commands
257 private var debugOutput = "" // holds all "Log()" output
258
259 /** Appends a new command to the command string; returns 'this' for fluent API. */
260 private def append(s: String) : Bot = { commands += (if(commands.isEmpty) s else "|" + s); this }
261
262 /** Renders commands and stateParams into a control function return string. */
263 override def toString = {
264 var result = commands
265 if(!stateParams.isEmpty) {
266 if(!result.isEmpty) result += "|"
267 result += stateParams.map(e => e._1 + "=" + e._2).mkString("Set(",",",")")
268 }
269 if(!debugOutput.isEmpty) {
270 if(!result.isEmpty) result += "|"
271 result += "Log(text=" + debugOutput + ")"
272 }
273 result
274 }
275
276 def log(text: String) = { debugOutput += text + "\n"; this }
277 def move(direction: XY) = append("Move(direction=" + direction + ")")
278 def say(text: String) = append("Say(text=" + text + ")")
279 def status(text: String) = append("Status(text=" + text + ")")
280 def explode(blastRadius: Int) = append("Explode(size=" + blastRadius + ")")
281 def spawn(offset: XY, params: (String,Any)*) =
282 append("Spawn(direction=" + offset +
283 (if(params.isEmpty) "" else "," + params.map(e => e._1 + "=" + e._2).mkString(",")) +
284 ")")
285 def set(params: (String,Any)*) = { stateParams ++= params; this }
286 def set(keyPrefix: String, xy: XY) = { stateParams ++= List(keyPrefix+"x" -> xy.x, keyPrefix+"y" -> xy.y); this }
287}
288
289
290// -------------------------------------------------------------------------------------------------
291
292
293/** Utility methods for parsing strings containing a single command of the format
294 * "Command(key=value,key=value,...)"
295 */
296object CommandParser {
297 /** "Command(..)" => ("Command", Map( ("key" -> "value"), ("key" -> "value"), ..}) */
298 def apply(command: String): (String, Map[String, String]) = {
299 /** "key=value" => ("key","value") */
300 def splitParameterIntoKeyValue(param: String): (String, String) = {
301 val segments = param.split('=')
302 (segments(0), if(segments.length>=2) segments(1) else "")
303 }
304
305 val segments = command.split('(')
306 if( segments.length != 2 )
307 throw new IllegalStateException("invalid command: " + command)
308 val opcode = segments(0)
309 val params = segments(1).dropRight(1).split(',')
310 val keyValuePairs = params.map(splitParameterIntoKeyValue).toMap
311 (opcode, keyValuePairs)
312 }
313}
314
315
316// -------------------------------------------------------------------------------------------------
317
318
319/** Utility class for managing 2D cell coordinates.
320 * The coordinate (0,0) corresponds to the top-left corner of the arena on screen.
321 * The direction (1,-1) points right and up.
322 */
323case class XY(x: Int, y: Int) {
324 override def toString = x + ":" + y
325
326 def isNonZero = x != 0 || y != 0
327 def isZero = x == 0 && y == 0
328 def isNonNegative = x >= 0 && y >= 0
329
330 def updateX(newX: Int) = XY(newX, y)
331 def updateY(newY: Int) = XY(x, newY)
332
333 def addToX(dx: Int) = XY(x + dx, y)
334 def addToY(dy: Int) = XY(x, y + dy)
335
336 def +(pos: XY) = XY(x + pos.x, y + pos.y)
337 def -(pos: XY) = XY(x - pos.x, y - pos.y)
338 def *(factor: Double) = XY((x * factor).intValue, (y * factor).intValue)
339
340 def distanceTo(pos: XY): Double = (this - pos).length // Phythagorean
341 def length: Double = math.sqrt(x * x + y * y) // Phythagorean
342
343 def stepsTo(pos: XY): Int = (this - pos).stepCount // steps to reach pos: max delta X or Y
344 def stepCount: Int = x.abs.max(y.abs) // steps from (0,0) to get here: max X or Y
345
346 def signum = XY(x.signum, y.signum)
347
348 def negate = XY(-x, -y)
349 def negateX = XY(-x, y)
350 def negateY = XY(x, -y)
351
352 /** Returns the direction index with 'Right' being index 0, then clockwise in 45 degree steps. */
353 def toDirection45: Int = {
354 val unit = signum
355 unit.x match {
356 case -1 =>
357 unit.y match {
358 case -1 =>
359 if(x < y * 3) Direction45.Left
360 else if(y < x * 3) Direction45.Up
361 else Direction45.UpLeft
362 case 0 =>
363 Direction45.Left
364 case 1 =>
365 if(-x > y * 3) Direction45.Left
366 else if(y > -x * 3) Direction45.Down
367 else Direction45.LeftDown
368 }
369 case 0 =>
370 unit.y match {
371 case 1 => Direction45.Down
372 case 0 => throw new IllegalArgumentException("cannot compute direction index for (0,0)")
373 case -1 => Direction45.Up
374 }
375 case 1 =>
376 unit.y match {
377 case -1 =>
378 if(x > -y * 3) Direction45.Right
379 else if(-y > x * 3) Direction45.Up
380 else Direction45.RightUp
381 case 0 =>
382 Direction45.Right
383 case 1 =>
384 if(x > y * 3) Direction45.Right
385 else if(y > x * 3) Direction45.Down
386 else Direction45.DownRight
387 }
388 }
389 }
390
391 def rotateCounterClockwise45 = XY.fromDirection45((signum.toDirection45 + 1) % 8)
392 def rotateCounterClockwise90 = XY.fromDirection45((signum.toDirection45 + 2) % 8)
393 def rotateClockwise45 = XY.fromDirection45((signum.toDirection45 + 7) % 8)
394 def rotateClockwise90 = XY.fromDirection45((signum.toDirection45 + 6) % 8)
395
396
397 def wrap(boardSize: XY) = {
398 val fixedX = if(x < 0) boardSize.x + x else if(x >= boardSize.x) x - boardSize.x else x
399 val fixedY = if(y < 0) boardSize.y + y else if(y >= boardSize.y) y - boardSize.y else y
400 if(fixedX != x || fixedY != y) XY(fixedX, fixedY) else this
401 }
402}
403
404
405object XY {
406 /** Parse an XY value from XY.toString format, e.g. "2:3". */
407 def apply(s: String) : XY = { val a = s.split(':'); XY(a(0).toInt,a(1).toInt) }
408
409 val Zero = XY(0, 0)
410 val One = XY(1, 1)
411
412 val Right = XY( 1, 0)
413 val RightUp = XY( 1, -1)
414 val Up = XY( 0, -1)
415 val UpLeft = XY(-1, -1)
416 val Left = XY(-1, 0)
417 val LeftDown = XY(-1, 1)
418 val Down = XY( 0, 1)
419 val DownRight = XY( 1, 1)
420
421 def fromDirection45(index: Int): XY = index match {
422 case Direction45.Right => Right
423 case Direction45.RightUp => RightUp
424 case Direction45.Up => Up
425 case Direction45.UpLeft => UpLeft
426 case Direction45.Left => Left
427 case Direction45.LeftDown => LeftDown
428 case Direction45.Down => Down
429 case Direction45.DownRight => DownRight
430 }
431
432 def fromDirection90(index: Int): XY = index match {
433 case Direction90.Right => Right
434 case Direction90.Up => Up
435 case Direction90.Left => Left
436 case Direction90.Down => Down
437 }
438
439 def apply(array: Array[Int]): XY = XY(array(0), array(1))
440}
441
442
443object Direction45 {
444 val Right = 0
445 val RightUp = 1
446 val Up = 2
447 val UpLeft = 3
448 val Left = 4
449 val LeftDown = 5
450 val Down = 6
451 val DownRight = 7
452}
453
454
455object Direction90 {
456 val Right = 0
457 val Up = 1
458 val Left = 2
459 val Down = 3
460}
461
462
463// -------------------------------------------------------------------------------------------------
464
465
466case class View(cells: String) {
467 val size = math.sqrt(cells.length).toInt
468 val center = XY(size / 2, size / 2)
469
470 def apply(relPos: XY) = cellAtRelPos(relPos)
471
472 def indexFromAbsPos(absPos: XY) = absPos.x + absPos.y * size
473 def absPosFromIndex(index: Int) = XY(index % size, index / size)
474 def absPosFromRelPos(relPos: XY) = relPos + center
475 def cellAtAbsPos(absPos: XY) = cells.charAt(indexFromAbsPos(absPos))
476
477 def indexFromRelPos(relPos: XY) = indexFromAbsPos(absPosFromRelPos(relPos))
478 def relPosFromAbsPos(absPos: XY) = absPos - center
479 def relPosFromIndex(index: Int) = relPosFromAbsPos(absPosFromIndex(index))
480 def cellAtRelPos(relPos: XY) = cells.charAt(indexFromRelPos(relPos))
481
482 def offsetToNearest(c: Char) = {
483 val matchingXY = cells.view.zipWithIndex.filter(_._1 == c)
484 if( matchingXY.isEmpty )
485 None
486 else {
487 val nearest = matchingXY.map(p => relPosFromIndex(p._2)).minBy(_.length)
488 Some(nearest)
489 }
490 }
491}
492
493