The Beginning
I tend to have this dangerous habit involving projects and the time at which I choose to write them. Specifically, I get really into a project right when I'm about to have a handful of exams. This previous midterm batch was no exception. I found myself getting increasingly interested in the usage of Webassembly for creating advanced state machines that would then be exposed through a simple API into a static HTML frontend. At the same time as this, I wanted to make something spooky for Halloween. Lastly, and most importantly, I was really missing my dog this past semester. All of these seemed to accumulate into a perfect storm of project inspiration:
I should create Five Night's at Freddy's in the browser where all enemies are my dogsIt was a perfect idea.
A Quick Explanation of Five Night's At Freddy's
Before we dive into the code and all of the fun stuff I can't
wait to write about, we should probably quickly go over what
game I'm attempting to steal draw inspiration from. Five
Night's at Freddy's is an indie horror game involving 4 robot
mascots hunting down the player. The player is imobile, and must
instead use the plethora of security cameras at their disposal
and 2 electronically controlled metal doors to prevent the
monsters from getting into their office. The doors and cameras
both draw significant power from the office, and using all of
the power up will result in an outage, leaving the player
completely exposed to any enemies wandering nearby. In order to
win, the player must successfully ward off all enemies and
prevent them from getting in until the in-game clock hits 6 AM.
This is primarily how I want my game to function, however there are a few deviations between the official game and mine. Most specifically, in the original Five Night's at Freddy's the office layout is fixed. In creating my version, I wanted to play around with randomized office generation, as I had an hunch I would probably need to use graphs for this task and that sounded fun (I got nerd sniped).
Starting Development
To begin this project, I created a new Rust crate and scaffolded out the general structs I thought I would need. Primarily, a GameState struct responsible for ticking the game forward, managing power consumption, signalling enemy behavior, and declaring when the player has won/lost. A simplified version of this struct looks as follows:
/// The game's internal state, responsible for keeping track of what enemies we have, where they
/// are, if our doors are closed, what time it is, etc!
pub struct GameState {
/// The current time
ticks: u64,
/// The map as graph-like structure
pub map: Map,
/// If the left door is closed
left_door: bool,
/// If the right door is closed
right_door: bool,
/// Are the cameras on
cameras_on: bool,
/// How much power is left
power: i32,
/// The current power draw (per tick)
draw: i32,
/// Are we dead?
dead: bool,
/// What is our target ticks
ticks_needed_to_win: u64,
}
A lot of this struct is simply bool tags and tick tracking. This makes sense as this entire state machine is essentially a slightly more complicated counter. Every time tick() is called we increment the tick count by 1, and decrement the current power by whatever the draw is. Draw is determined by the amount of door shut and camera on flags that are on, and once the ticks reached is higher than the ticks required to win, we return that the game has been won!
From this perspective, the tick() method could be written simply as follows:
impl GameState {
pub fn tick(&mut self) -> bool {
self.ticks += 1;
self.power -= self.draw;
self.ticks == self.ticks_needed_to_win
}
}
Of course, this is an overly simplified perspective on the game, as we also need to have a reason why the player might be checking cameras or closing doors. We need enemies.
Enemies
Enemies(or as I named them in the source code, freaks) are inherently dynamic entities that should behave differently from one another. After all, if you had a game where every enemy simply b-lined it straight to you, you'd have a pretty monotonous game. For example, my dog Teller would likely prey and stalk directly towards me, whereas my cockapoo Frank would probably wander aimlessly in hopes that he may accidentally win. As such, enemy behavior would be better represented as a Trait.
The EnemyBehavior trait encapsulates this providing a single function, also named tick(). An enemies behavior should be determined based on the context of where they currently are in the map and what their previous actions were, therefore this method takes a reference to the existing GameState. From this, the behavior returns an Action enum with the following variants:
pub enum Action {
/// Move to room `RoomId`
Move(RoomId),
/// Perform some special action specific to the enemy
Special(Box<dyn SideEffect>),
/// Attack the player if close enough
Attack,
/// Or do nothing
Nothing,
}
Furthermore, as mentioned earlier with Frank, what if an enemy needs to do some sort of randomized operations? In this case, it's likely a better practice to include a mutable reference to some Rng for any implementation that may need it, preventing them from creating their own Rng once every tick (which does not sound very efficient). With all of these considerations in mind, here's what the final design for the EnemyBehavior trait looks like:
pub trait EnemyBehavior {
fn tick(&mut self, curr_state: &GameState, id: EnemyId) -> Vec<Action>;
}
Now, in order to dynamically hold all enemies with different behavior, we can hold onto a Box<dyn EnemyBehavior> to allow for dynamic usage of the trait objects! For the reason of borrow checker rules that involved the GameState owning the enemies and trying to mutate them and itself at the same time, I moved the enemy container out of GameState and into a new Game struct that would hold onto the enemies, the current game, and an Rng instance to send through during ticks. One more cool thing we do here is instead of holding the enemys in one spot and sharing references to them all over the place, the game actually stores them in a SlotMap<EnemyId, Freak> and shares the copyable EnemyId all over the place. Neat!
Note: SlotMaps are pretty much exactly the same as HashMaps, but upon insertion you are returned a generated key instead of needing to provide one. The Rust slotmap crate provides a macro for describing a attributeless struct as a slotmap key, which as far as I've seen essentially boils it down into a tagged u64. This EnemyId struct is one of these key types, and for map generation we do something similar with a RoomIdAdding Frank
Now that we have the blueprints for how an enemy's behavior is derived, let's go through the simplest enemy AI, Frank!
As previously stated, if Frank were a murderous beast bent on killing a player, he would probably do it by wandering aimlessly. To reflect this, Frank's AI behavior will move about randomly. A small part of Frank's implementation involves the Map struct that I haven't gone over yet and will not go over until after this section, so just know for now that all you need to know is that a Map is collection of Rooms where each Room has a collection of Ids that point to other rooms. With this knowledge of state in mind, implementing Frank is as easy as:
pub struct FrankBehavior<RNG: Rng> {
rng: RNG,
}
impl<RNG: Rng> EnemyBehavior for FrankBehavior<RNG> {
fn tick(&mut self, curr_state: &GameState, id: EnemyId) -> Vec<Action> {
if let Some(enemy_room) = curr_state.map.get_enemy_room(id) {
let rooms = curr_state[enemy_room].connections();
let goto = rooms.choose(&mut self.rng);
if goto == &curr_state.office.root {
vec![Action::Attack]
} else {
vec![Action::Move(*goto)]
}
} else {
vec![Action::Nothing]
}
}
}
Map Generation
Since we've been assuming this Map struct has existed, so we might as well jump into that now! The map itself will be yet another Slotmap, this time containing a special Room struct.
In this way, all a Map really is is a graph of nodes with Room data, with connections essentially acting as "hallways" between these rooms. This makes enemy AI for pathfinding nothing more than a simple graph traversal. As far as generating the actual map goes, there are a few ground rules that every Map should follow:
- Every Map should have a Root "office" that the player occupies and enemies target.
- Every office should have only a left and right hallway connection. These rooms signal to the player that an enemy is right outside their door
- All remaining rooms should connect in some way (either directly or through a sequence of rooms) to either the left or right higway. Why would we want a building that doesn't have rooms fully connected?
So with these rules in mind, map generation should start with a "root" batch of nodes, manually creating an office and it's adjacent hallways. From there, rng should take the wheel and create some N number of new rooms with connections to the previously existent rooms (any room but the office). In the actual implementation, we do this initial pass and then go back through and create a few extra random connections to reduce the tree-looking-ness of the office.
The method returns a RootOfficeInfo struct that bundles up the office and hallways nicely. It also returns a list of all Rooms where an enemy spawning is viable, to prevent enemies from spawing in a random room which would be pretty unfair. The code in all of its glory is as follows:
pub fn generate>RNG: Rng<(&mut self, rng: &mut RNG) -> (RootRoomInfo, Vec<RoomId>) {
let mut office = Room::default();
let mut left = Room::default();
let mut right = Room::default();
office.set_name("office");
left.set_name("left_entrance");
right.set_name("right_entrance");
let mut hallway_left = Room::default();
let mut hallway_right = Room::default();
hallway_left.set_name("left_hallway");
hallway_right.set_name("right_hallway");
let office = self.0.insert(office);
let left = self.0.insert(left);
let right = self.0.insert(right);
let hallway_left = self.0.insert(hallway_left);
let hallway_right = self.0.insert(hallway_right);
self.connect_rooms(office, left);
self.connect_rooms(office, right);
self.connect_rooms(left, hallway_left);
self.connect_rooms(right, hallway_right);
let additional_rooms: usize = rng.gen_range(7..=9);
let mut room_ids = vec![hallway_left, hallway_right];
for _ in 0..additional_rooms {
let new_room = self.0.insert(Room::default());
let existing_room = *room_ids.choose(rng).unwrap();
self.connect_rooms(new_room, existing_room);
room_ids.push(new_room)
}
let extra_connections: usize = rng.gen_range(1..=3);
for _ in 0..extra_connections {
let room_a = *room_ids.choose(rng).unwrap();
let room_b = *room_ids.choose(rng).unwrap();
if room_a != room_b && !self.0[room_a].conencts_to.contains(&room_b) {
self.connect_rooms(room_a, room_b);
}
}
// Generate viable rooms to spawn enemies in, cannot be directly connected to the main
// rooms
let mut viable_spawn_rooms: Vec<_> = room_ids
.into_iter()
.filter(|id| !self.0[*id].connects_to_any(&[&left, &right]))
.collect();
let mut spawn_rooms = vec![];
let spawn_rooms_count: usize = rng.gen_range(1..=4);
for _ in 0..spawn_rooms_count {
if let Some(popped) = viable_spawn_rooms.pop() {
spawn_rooms.push(popped);
}
}
(
RootRoomInfo {
root: office,
left,
right,
},
spawn_rooms,
)
}
This is definitely a lot of code, but nothing too crazy. In my experience Slotmaps have been a very nice paradigm for graph-based structures, as it keeps you away from throwing everything in boxes or refcells. With the graph designed like this, we can design a pretty simple pathfinding algorithm by attemtping to traverse the Room graph until we find the room with the target ID. This method keeps context of the previous rooms explored while checking every possible connection in a queue. This is my preferred paradigm of graph traversal in Rust, as it makes state management and comprehensibility much better for myself than a recursive function may (although I cannot lie and say recursive functions aren't awesome (although I cannot lie and say recursive functions aren't awesome (...)))
pub fn generate_path(&self, from: RoomId, to: RoomId) -> Option> {
let mut search_queue = VecDeque::new();
let mut seen = HashSet::new();
let mut predecessors = HashMap::new();
search_queue.push_front(from);
seen.insert(from);
while let Some(check_room) = search_queue.pop_back() {
if check_room == to {
let mut path = Vec::new();
let mut current = to;
while current != from {
path.push(current);
current = *predecessors.get(¤t)?;
}
path.push(from);
path.reverse();
return Some(path);
}
for &next_room in &self.0[check_room].conencts_to {
if seen.insert(next_room) {
search_queue.push_front(next_room);
predecessors.insert(next_room, check_room);
}
}
}
None
}
Updating tick()
Now that we have some more advanced game logic and data structures in place, we'll need to move all enemies forward every time they're supposed to. Going back to that simplified tick method from before, now is the time to get that a little more beefy. There isn't too much to add because the code is all segmented in a nice and cohesive way, we simply need to iterate over enemies, get their actions, perform their actions if possible, and check if those actions would kill us!
pub fn tick(&mut self, enemies: &mut SlotMap, rng: &mut RNG) -> bool {
self.ticks += 1;
if self.ticks == self.ticks_needed_to_win {
// WE WON
return true;
}
self.power -= self.draw;
// Check if power's out after the draw, opening all the doors if so
self.out_of_power();
for (id, enemy) in enemies {
if let Some(time) = self.cooldowns.get(&id) {
if self.ticks % time == 0 {
// It's action time
enemy.tick(id, self, rng);
}
} else {
let new_cooldown = enemy.gen_cooldown(rng);
self.cooldowns.insert(id, new_cooldown);
}
}
// Check if someone's in our office who isn't us
if self.map.room_has_enemies(self.office.root) {
self.dead = true
}
// We haven't won :(
false
}
And just like that, we have pretty much everything in place to play a game of Five Night's at Teller's! There's a bit more boring stuff I didn't include, mostly power draw mechanics and door closing interfaces, we'll focus more on the cool map and enemy AI bits.
Putting it All Together
Now that the Rust logic was finished, porting it into Webassembly was very very easy. Throwing a #[wasm_bindgen] proc macro atop a few structs and impl blocks here and there and we have access to the game state machine as an opaque type. Interfacing with it and moving forward the game logic did have it's slight JS challenges, such as translating the graph into a visual UI. These challenges weren't a part of my initial goal, but I still had a lot of fun figuring out how to fit all of the pieces together. As such, however, I won't go too in depth about them here. Maybe there's a world where they're covered more in a part 2 :)
Overall, I had a really fun time making this entire project. It demanded a lot of unique problems to be solved that really required me to whip out some good data structures to pull off. This and the portability of wasm made it a very cool experience. To play the game, either visit this link, check out the source code here, or play the embedded version below: