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