lib/bucketed_game.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   3 # Copyright 2011-2013 Alexis Laferrière <alexis.laf@xymus.net>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # Game framework with an emphasis on efficient event coordination
  18 #
  19 # Provides basic game logic entities to manage a game where the logic is executed by turns:
  20 # `Game`, `GameTurn`, `GameEvent`, `Turnable`.
  21 # Also offers a bucket system to plan future events at a known number of turns in the future:
  22 # `Bucketable` and the services `act_next` and `act_in`.
  23 #
  24 # Efficiently support large number of entities with rare or sparse actions,
  25 # such as a forest with many individual trees growing slowly.
  26 module bucketed_game is serialize
  27
  28 import serialization
  29
  30 # Something acting on the game
  31 abstract class Turnable[G: Game]
  32
  33         # Execute `turn` for this instance.
  34         fun do_turn(turn: GameTurn[G]) is abstract
  35 end
  36
  37 # Something acting on the game from time to time
  38 abstract class Bucketable[G: Game]
  39         super Turnable[G]
  40
  41         private var act_at: nullable Int = null
  42
  43         # Cancel the previously registered acting turn
  44         #
  45         # Once called, `self.do_turn` will not be invoked until `GameTurn::act_next`
  46         # or `GameTurn::act_in` are called again.
  47         fun cancel_act do act_at = null
  48 end
  49
  50 # Optimized organization of `Bucketable` instances
  51 class Buckets[G: Game]
  52         super Turnable[G]
  53
  54         # Bucket type used in this implementation.
  55         type BUCKET: HashSet[Bucketable[G]]
  56
  57         private var next_bucket: nullable BUCKET = null
  58         private var current_bucket_key: Int = -1
  59
  60         # Number of `buckets`, default at 100
  61         #
  62         # Must be set prior to using any other methods of this class.
  63         var n_buckets = 100
  64
  65         private var buckets: Array[BUCKET] =
  66                 [for b in n_buckets.times do new HashSet[Bucketable[G]]] is lazy
  67
  68         # Add the Bucketable event `e` at `at_tick`.
  69         fun add_at(e: Bucketable[G], at_tick: Int)
  70         do
  71                 var at_key = key_for_tick(at_tick)
  72
  73                 if at_key == current_bucket_key then
  74                         next_bucket.as(not null).add(e)
  75                 else
  76                         buckets[at_key].add(e)
  77                 end
  78
  79                 e.act_at = at_tick
  80         end
  81
  82         private fun key_for_tick(at_tick: Int): Int
  83         do
  84                 return at_tick % buckets.length
  85         end
  86
  87         redef fun do_turn(turn: GameTurn[G])
  88         do
  89                 current_bucket_key = key_for_tick(turn.tick)
  90                 var current_bucket = buckets[current_bucket_key]
  91
  92                 var next_bucket = new HashSet[Bucketable[G]]
  93                 buckets[current_bucket_key] = next_bucket
  94                 self.next_bucket = next_bucket
  95
  96                 for e in current_bucket do
  97                         var act_at = e.act_at
  98                         if act_at != null then
  99                                 if turn.tick == act_at then
 100                                         e.do_turn(turn)
 101                                 else if act_at > turn.tick and
 102                                         key_for_tick(act_at) == current_bucket_key
 103                                 then
 104                                         next_bucket.add(e)
 105                                 end
 106                         end
 107                 end
 108         end
 109 end
 110
 111 # Game related event
 112 interface GameEvent
 113
 114         # Apply `self` to `game` logic.
 115         fun apply( game : ThinGame ) is abstract
 116 end
 117
 118 # Event raised at the first turn
 119 class FirstTurnEvent
 120         super GameEvent
 121 end
 122
 123 # Game logic on the client
 124 class ThinGame
 125
 126         # Game tick when `self` should act.
 127         #
 128         # Default is 0.
 129         var tick: Int = 0 is protected writable
 130 end
 131
 132 # Game turn on the client
 133 class ThinGameTurn[G: ThinGame]
 134
 135         # Game tick when `self` should act.
 136         var tick: Int is protected writable
 137
 138         # Game events occurred for `self`.
 139         var events = new Array[GameEvent] is protected writable
 140 end
 141
 142 # Game turn on the full logic
 143 class GameTurn[G: Game]
 144         super ThinGameTurn[G]
 145
 146         # Game that `self` belongs to.
 147         var game: G
 148
 149         # Create a new game turn for `game`.
 150         init (game: G) is old_style_init do
 151                 super(game.tick)
 152                 self.game = game
 153         end
 154
 155         # Insert the Bucketable event `e` to be executed at next tick.
 156         fun act_next(e: Bucketable[G]) do game.buckets.add_at(e, tick + 1)
 157
 158         # Insert the Bucketable event `e` to be executed at tick `t`.
 159         fun act_in(e: Bucketable[G], t: Int) do game.buckets.add_at(e, tick + t)
 160
 161         # Add and `apply` a game `event`.
 162         fun add_event( event : GameEvent )
 163         do
 164                 event.apply( game )
 165                 events.add( event )
 166         end
 167 end
 168
 169 # Full game logic
 170 class Game
 171         super ThinGame
 172
 173         # Game type used in this implementation.
 174         type G: Game
 175
 176         # Bucket list in this game.
 177         var buckets: Buckets[G] = new Buckets[G]
 178
 179         # Last turn executed in this game
 180         # Can be used to consult the latest events (by the display for example),
 181         # but cannot be used to add new Events.
 182         var last_turn: nullable ThinGameTurn[G] = null
 183
 184         # Execute and return a new GameTurn.
 185         #
 186         # This method calls `do_pre_turn` before executing the GameTurn
 187         # and `do_post_turn` after.
 188         fun do_turn: GameTurn[G]
 189         do
 190                 var turn = new GameTurn[G](self)
 191
 192                 do_pre_turn(turn)
 193                 buckets.do_turn(turn)
 194                 do_post_turn(turn)
 195
 196                 last_turn = turn
 197
 198                 tick += 1
 199
 200                 return turn
 201         end
 202
 203         # Execute something before executing the current GameTurn.
 204         #
 205         # Should be redefined by clients to add a pre-turn behavior.
 206         # See `Game::do_turn`.
 207         fun do_pre_turn(turn: GameTurn[G]) do end
 208
 209         # Execute something after executing the current GameTurn.
 210         #
 211         # Should be redefined by clients to add a post-turn behavior.
 212         # See `Game::do_turn`.
 213         fun do_post_turn(turn: GameTurn[G]) do end
 214 end