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