ornicar/vindinium — pull request #26 by magv (2014-09-27 22:25:47+00:00)
Title: Fix two problems in turn resolution

Hi. I've looked into the turn resolution logic in app/Arbiter.scala,
and it currently has two problems related to respawning heroes:

1. infinite recursion that aborts the game if detected
2. a bug that can put different heroes into the same location

Both of these problems can be avoided with the patches I propose;
let me explain in detail.

## Infinite recursion problem

The first problem comes from this method:

```scala
private def reSpawn(game: Game, h: Hero, rec: Int = 0): Game = {
val pos = game spawnPosOf h
(game hero pos match {
case Some(opponent) if opponent.id != h.id =>
// play.api.Logger("Arbiter").info(s"reSpawn rec:$rec game:${game.id} hero:${h.id} ${h.pos} -> $pos")
if (rec > 4) throw new Exception(s"Arbiter.reSpawn recursion")
reSpawn(game.withBoard(_.transferMines(opponent.id, Some(h.id))), opponent, rec + 1)
case _ => game
}) withHero h.reSpawn(pos, game.turn)
```

If a hero is getting respawned and it's spawning position is
occupied by an enemy hero, this routine first respawns the enemy,
and only then moves the original hero to his spawning point.

In some situations this may lead to the following cascade of events:

1. hero A is getting respawned
2. hero B is found in hero's A spawning point
3. thus, hero B is getting respawned
4. hero A is found in hero's B spawning point
5. thus, hero A is getting respawned
6. goto 2

So, infinite recursion. This recursion is detected with the `rec`
counter; if it is detected, the game is forcibly aborted.

There doesn't have to be infinite recursion here though. The way
to handle this is to first move hero A to his spawning position
(thus making both A and B temporarily at the same spot), and
then respawn hero B. This way, when B is respawned, it will not
find A in his spawning point (because A is already in his own
spawning point, and all spawning points are distinct), thus there
will be no infinite cycle here.

The proposed patch implements this. I've tested it extensively
on small maps with no taverns, and it works well. Note that this
change does not break backward compatibility, only games that
previously where forcibly aborted are affected.

## Exclusion violation problem

The second problem needs a bit of an illustration. So, here are
two events from a test game:

data: {"id":"b3vtnh4j","turn":62,"maxTurns":80,"heroes":[{"id":1,"name":"test1","userId":"ynbqxx3d","elo":1217,"pos":{"x":1,"y":2},"life":58,"gold":21,"mineCount":1,"spawnPos":{"x":2,"y":2},"crashed":false},{"id":2,"name":"random","pos":{"x":0,"y":1},"life":17,"gold":21,"mineCount":3,"spawnPos":{"x":1,"y":2},"crashed":false},{"id":3,"name":"random","pos":{"x":1,"y":1},"life":100,"gold":14,"mineCount":0,"spawnPos":{"x":1,"y":1},"crashed":false},{"id":4,"name":"random","pos":{"x":3,"y":1},"life":99,"gold":8,"mineCount":0,"spawnPos":{"x":2,"y":1},"crashed":false}],"board":{"size":4,"tiles":"##@2 ##$2@3@1$2$2 $1##@4 ##"},"finished":false}

data: {"id":"b3vtnh4j","turn":63,"maxTurns":80,"heroes":[{"id":1,"name":"test1","userId":"ynbqxx3d","elo":1217,"pos":{"x":1,"y":2},"life":38,"gold":21,"mineCount":0,"spawnPos":{"x":2,"y":2},"crashed":false},{"id":2,"name":"random","pos":{"x":1,"y":2},"life":100,"gold":21,"mineCount":1,"spawnPos":{"x":1,"y":2},"crashed":false},{"id":3,"name":"random","pos":{"x":1,"y":1},"life":99,"gold":17,"mineCount":3,"spawnPos":{"x":1,"y":1},"crashed":false},{"id":4,"name":"random","pos":{"x":3,"y":1},"life":99,"gold":8,"mineCount":0,"spawnPos":{"x":2,"y":1},"crashed":false}],"board":{"size":4,"tiles":"## ##$3@3@1$3$3 $2##@4 ##"},"finished":false}

Or, in a simpler format:

turn 62
+--------+
|##@2 ##| @1 hp:58
|$2@3@1$2| @2 hp:17
|$2 $1| @3 hp:100
|##@4 ##| @4 hp:99
+--------+

turn 63
+--------+
|## ##| @1 hp:38
|$3@3@1$3| @2 hp:100
|$3 $2| @3 hp:99
|##@4 ##| @4 hp:99
+--------+

Where did `@2` go? It's actually now at the same spot as `@1`,
which should normally not happen.

So, the problem comes from this method:

```scala
private def fights(game: Game, id: Int): Game =
(game.hero(id).pos.neighbors map game.hero).flatten.foldLeft(game) {
// stop the fighting if the attacking hero has been respawned
case (game, enemy) if game.hero(id).lastRespawn != Some(game.turn) => attack(id, game, enemy)
case (game, _) => game
}
```

As you can see, the list of neighboring enemies is first created,
and then heroes from that list are attacked in order. In our
case, `@3` does the attacking, and the enemy list consists of
`@2` and `@1` (in that order). When `@3` attacks `@2`, `@2` gets
respawned -- but since it's spawning position is currently
occupied by `@1`, `@1` also gets respawned and is moved to his
spawning position at `(2, 2)` (one cell south of his current
location). After this respawning is done, the next enemy from
the neighbor list is attacked -- this enemy is `@1`, but not the
respawned `@1` that is now at `(2, 2)`, but an old copy of `@1`
that was at `(1, 2)`. This copy is attacked, so it's life gets
decreased from 58 to 38, and it is placed back onto the board
at the coordinates that the copy holds, `(1, 2)` -- exactly the
place where `@2` currently resides.

Now, there are more than one way to fix this. One way is to
repeat neighbor lookups after attack in each direction. This
however will lead to `@2` being attacked twice in the example
above.

Another way is to check each enemy hero in order of their ID,
and attack them if they are determined to be in the neighborhood.
This will avoid double attacking -- and is actually easier to
implement (no need for intermediate lists of enemies) -- but
this does change fight resolution in a few rare cases, and that
may be too much of a regression.

Finally, it's possible to skip attacking an enemy from the
neighbor list, if that enemy was recently respawned. I think
this option minimizes compatibility changes, while still fixing
the problem. This is what the second proposed patch does.

Again, the patch was tested and seems to work well.