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