Rotating galaxy game simulation

# MIT License
#
# Copyright (c) 2020 William Beason
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
#   The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

# Generate 100 stars
n <- 100
# Number of players
players <- 6
# stars.m holds our galaxy
stars.m <- matrix(0, n, 5)

# Add a star to the galaxy.
genStar <- function(m) {
  # Try 20 times to find a new spot for a star.
  for (tries in 1:20) {
    # Pick a radius and angle.
    # Roughly, stars are a randomly-chosen integer distance from the center.
    # Larger radii have a larger chance of being chosen than smaller.
    radius <- 3+floor((1 - runif(1)) * 20)
    angle <- runif(1)*2*pi

    collision = FALSE
    for (i in 1:n) {
      # Check all current stars in the galaxy to make sure there aren't
      # any too close since it looks bad.
      if (m[i, 1] == radius & (abs(m[i, 2] - angle) < (1.0 / radius))) {
        # Too close to a star in the same ring, so try another.
        collision = TRUE
        break
      }
    }
    if (!collision) {
      # No collision, so we've found a new location for a star.
      return(c(radius, angle))
    }
  }
  return(c(0, 0))
}

for (i in 1:n) {
  # Assign radius/angle for the new star.
  stars.m[i, 1:2] = genStar(stars.m)

  # Calculate x, y positions.
  stars.m[i, 3] = stars.m[i, 1]*sin(stars.m[i, 2])
  stars.m[i, 4] = stars.m[i, 1]*cos(stars.m[i, 2])
  # Every star begins unowned.
  stars.m[i, 5] = 1
}
for (i in 1:players) {
  stars.m[i, 5] = i + 1
}

# White, Red, Yellow, Green, Teal, Blue, Purple
cols=c("#FFFFFF", "#FF0000", "#FFFF00", "#00FF00", "#00FFFF", "#0000FF", "#FF00FF")

# Advance the galaxy by some time.
advance <- function(m, t) {
  for (i in 1:n) {
    # Stars closer to the center move faster.
    m[i, 2] = m[i, 2] + (t / m[i, 1])

    # Update x, y positions.
    m[i, 3] = m[i, 1]*sin(m[i, 2])
    m[i, 4] = m[i, 1]*cos(m[i, 2])
  }
  return(m)
}

calcCenter <- function(m) {
  # Get the geometric center of a set of stars.
  cmx <- mean(m[, 3])
  cmy <- mean(m[, 4])
  return(c(cmx, cmy))
}

getClaims <- function(m) {
  # Figure out what star the player should attack next.
  claims <- matrix(0, players, 2)
  for (i in 1:players) {
    id <- i+1
    stars <- m[m[, 5] == id,, drop=FALSE]
    # This player has no stars, so don't simulate them.
    if (dim(stars)[1] == 0) next

    # Get the geometric center of the player's stars.
    center <- calcCenter(stars)
    cmx <- center[1]
    cmy <- center[2]

    claimValue <- -Inf
    # Consider each star to figure out the best next one to claim.
    for (j in 1:(dim(m)[1])) {
      # The star is already owned, so ignore it.
      if (m[j, 5] == id) next

      newValue <- 0
      claimDistance <- ((m[j, 3]-cmx)^2 + (m[j, 4] - cmy)^2)

      # Value unclaimed stars more than claimed stars.
      # Also, value stars closer to the geometric center of the empire more.
      #
      # Could do with balancing, but the point is to ensure
      # most stars get claimed before fighting starts.
      if (m[j, 5] == 1) {
        newValue <- 1 / (claimDistance + 1)
      } else {
        newValue <- 1 / (claimDistance + 1)^2
      }

      # If this system's value is better than the best previously
      # considered, it is now the best option.
      if (newValue > claimValue) {
        claimValue <- newValue
        claims[i, 1] <- j
        claims[i, 2] <- claimDistance
      }
    }
  }

  return(claims)
}

playgame <- function(m) {
  # Each player gets to attack at most one star each turn.
  claims <- getClaims(m)

  # Resolve claims. Later players technically have a slight advantage, but
  # this simulation is just to give a general idea of how things play out.
  for (i in 1:players) {
    id <- i+1

    # Didn't claim any stars or is dead.
    if (claims[i, 1] == 0) next

    oid <- m[claims[i, 1], 5]
    if (oid == 1) {
      # Unowned star, automatically claimed.
      m[claims[i], 5] <- id
      next
    }

    # Fight over star.
    # Roughly, strength is proportional to the number of owned stars and
    # decreases with distance from the faction's center.
    iDist <- claims[i, 2]
    oCenter <- calcCenter(m[m[, 5] == oid,, drop=FALSE])
    oDist <- sqrt((oCenter[1] - m[i, 3])^2 + (oCenter[2] - m[i, 4])^2)

    iStrength <- sum(m[, 5, drop=FALSE] == id) / (iDist + 1)
    oStrength <- sum(m[, 5, drop=FALSE] == oid) / (oDist + 1)

    if (runif(1) < iStrength / (iStrength + oStrength)) {
      # Player won the battle, so claim star.
      m[claims[i, 1], 5] <- id
    }
  }

  return(m)
}

# Plot the initial galaxy.
png(filename="game/tick_0.png")
par(bg = "black")
plot(stars.m[, 3:4], col=cols[stars.m[, 5]], main="Tick 0", col.main="white", xlim=c(-23, 23), ylim=c(-23, 23))
dev.off()

for (i in 1:160) {
  # Advance the galaxy in quarter-day-increments and plot.
  tick <- 6*i
  fn <- paste0("game/tick_", as.character(tick), ".png")


  png(filename=fn)
  # Have players act for one turn, then simulate star movement.
  stars.m <- playgame(stars.m)
  stars.m <- advance(stars.m, 0.25)
  par(bg = "black")
  plot(stars.m[, 3:4], col=cols[stars.m[, 5]], main=paste("Tick", tick), col.main="white", xlim=c(-23, 23), ylim=c(-23, 23))
  dev.off()
}