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 # Provides basic game logic utilities using buckets to coordinate and
  18 # optimize actions on game turn ends. Supports both action at each
  19 # end of turn as well as actions on some end of turns.
  20 #
  21 # Allows for fast support of a large number of entities with rare actions,
  22 # such as a forest with many individual trees.
  23 module bucketed_game
  24
  25 # Something acting on the game
  26 class Turnable[G: Game]
  27
  28         # Execute `turn` for this instance.
  29         fun do_turn(turn: GameTurn[G]) is abstract
  30 end
  31
  32 # Something acting on the game from time to time
  33 class Bucketable[G: Game]
  34         super Turnable[G]
  35         private var act_at: nullable Int = null
  36
  37         # Cancel the previously registered acting turn
  38         #
  39         # Once called, `self.do_turn` will not be invoked until `GameTurn::act_next`
  40         # or `GameTurn::act_in` are called again.
  41         fun cancel_act do act_at = null
  42 end
  43
  44 # Optimized organization of `Bucketable` instances
  45 class Buckets[G: Game]
  46         super Turnable[G]
  47
  48         # Bucket type used in this implementation.
  49         type BUCKET: HashSet[Bucketable[G]]
  50
  51         private var buckets: Array[BUCKET] is noinit
  52
  53         private var next_bucket: nullable BUCKET = null
  54         private var current_bucket_key: Int = -1
  55
  56         init
  57         do
  58                 var n_buckets = 100
  59                 buckets = new Array[BUCKET].with_capacity(n_buckets)
  60
  61                 for b in [0 .. n_buckets [do
  62                         buckets[b] = new HashSet[Bucketable[G]]
  63                 end
  64         end
  65
  66         # Add the Bucketable event `e` at `at_tick`.
  67         fun add_at(e: Bucketable[G], at_tick: Int)
  68         do
  69                 var at_key = key_for_tick(at_tick)
  70
  71                 if at_key == current_bucket_key then
  72                         next_bucket.as(not null).add(e)
  73                 else
  74                         buckets[at_key].add(e)
  75                 end
  76
  77                 e.act_at = at_tick
  78         end
  79
  80         private fun key_for_tick(at_tick: Int): Int
  81         do
  82                 return at_tick % buckets.length
  83         end
  84
  85         redef fun do_turn(turn: GameTurn[G])
  86         do
  87                 current_bucket_key = key_for_tick(turn.tick)
  88                 var current_bucket = buckets[current_bucket_key]
  89
  90                 var next_bucket = new HashSet[Bucketable[G]]
  91                 buckets[current_bucket_key] = next_bucket
  92                 self.next_bucket = next_bucket
  93
  94                 for e in current_bucket do
  95                         var act_at = e.act_at
  96                         if act_at != null then
  97                                 if turn.tick == act_at then
  98                                         e.do_turn(turn)
  99                                 else if act_at > turn.tick and
 100                                         key_for_tick(act_at) == current_bucket_key
 101                                 then
 102                                         next_bucket.add(e)
 103                                 end
 104                         end
 105                 end
 106         end
 107 end
 108
 109 # Game related event
 110 interface GameEvent
 111
 112         # Apply `self` to `game` logic.
 113         fun apply( game : ThinGame ) is abstract
 114 end
 115
 116 # Event raised at the first turn
 117 class FirstTurnEvent
 118         super GameEvent
 119 end
 120
 121 # Game logic on the client
 122 class ThinGame
 123
 124         # Game tick when `self` should act.
 125         #
 126         # Default is 0.
 127         var tick: Int = 0 is protected writable
 128 end
 129
 130 # Game turn on the client
 131 class ThinGameTurn[G: ThinGame]
 132
 133         # Game tick when `self` should act.
 134         var tick: Int is protected writable
 135
 136         # List of game events occured for `self`.
 137         var events = new List[GameEvent] is protected writable
 138 end
 139
 140 # Game turn on the full logic
 141 class GameTurn[G: Game]
 142         super ThinGameTurn[G]
 143
 144         # Game that `self` belongs to.
 145         var game: G
 146
 147         # Create a new game turn for `game`.
 148         init (game: G) is old_style_init do
 149                 super(game.tick)
 150                 self.game = game
 151         end
 152
 153         # Insert the Bucketable event `e` to be executed at next tick.
 154         fun act_next(e: Bucketable[G]) do game.buckets.add_at(e, tick + 1)
 155
 156         # Insert the Bucketable event `e` to be executed at tick `t`.
 157         fun act_in(e: Bucketable[G], t: Int) do game.buckets.add_at(e, tick + t)
 158
 159         # Add and `apply` a game `event`.
 160         fun add_event( event : GameEvent )
 161         do
 162                 event.apply( game )
 163                 events.add( event )
 164         end
 165 end
 166
 167 # Full game logic
 168 class Game
 169         super ThinGame
 170
 171         # Game type used in this implementation.
 172         type G: Game
 173
 174         # Bucket list in this game.
 175         var buckets: Buckets[G] = new Buckets[G]
 176
 177         # Last turn executed in this game
 178         # Can be used to consult the latest events (by the display for example),
 179         # but cannot be used to add new Events.
 180         var last_turn: nullable ThinGameTurn[G] = null
 181
 182         # Execute and return a new GameTurn.
 183         #
 184         # This method calls `do_pre_turn` before executing the GameTurn
 185         # and `do_post_turn` after.
 186         fun do_turn: GameTurn[G]
 187         do
 188                 var turn = new GameTurn[G](self)
 189
 190                 do_pre_turn(turn)
 191                 buckets.do_turn(turn)
 192                 do_post_turn(turn)
 193
 194                 last_turn = turn
 195
 196                 tick += 1
 197
 198                 return turn
 199         end
 200
 201         # Execute something before executing the current GameTurn.
 202         #
 203         # Should be redefined by clients to add a pre-turn behavior.
 204         # See `Game::do_turn`.
 205         fun do_pre_turn(turn: GameTurn[G]) do end
 206
 207         # Execute something after executing the current GameTurn.
 208         #
 209         # Should be redefined by clients to add a post-turn behavior.
 210         # See `Game::do_turn`.
 211         fun do_post_turn(turn: GameTurn[G]) do end
 212 end