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