A while back, a friend showed me the programming game "Elevator Saga". It currently consists of 18 challenges with different configurations of floors and elevators. Each challenge poses certain criteria, for instance to transport X people within Y seconds, or to transport X people without letting any single person wait for their elevator longer than Y seconds. The goal is then using the game's javascript API to program the behavior of the elevators so that the given challenge's criteria are met.
In this post, I'd like to show how to implement a relatively simple algorithm that passes the first 12 of the 18 challenges. The solution is mostly event-driven, having the elevators react to certain events that occur over the course of a challenge being run.
Pressing Floor Buttons Inside An Elevator
First things first: Let's set up what happens when someone gets into one of our elevators and presses the button of the floor they want to go to. Let's start simple and add the requested floor to then end of the queue. This makes sure everyone will (eventually) get to their floor, but it might end up with the same floor being requested multiple times.
Obviously the passengers would all get off the first time the elevator stops at their floor, but we might end up later going to the same floor again because it is still in the queue, even though there are no passengers left who want to go there. Preventing this problem is no big challenge - instead of just adding the pressed floor to the queue, we first check if it is already enqueued and only add it if it is not.
elevator.on("floor_button_pressed", function(floorNum) {
if (elevator.destinationQueue.indexOf(floorNum) == -1) {
elevator.goToFloor(floorNum);
}
});
Requesting An Elevator From A Floor
Next up, people wating for an elevator on any floor have the option of pressing the usual "up" and "down" buttons, depending an what direction they want to go in. We could write code to react to every button press on a floor, but this would be unnecessary since all that interests us for a given floor is whether or not there is currently someone waiting to go up and/or down from that floor.
To keep track of this, we add the respective boolean attributes for whether or not there is a request to go up or down to each floor object in the game. We can then tell the game to simply set these attributes to true for a floor whenever the corresponding button is pressed by someone.
These attributes will later be used to service these floors whenever it makes sense to do so, but we'll get to that in a second.
floors.forEach(function(floor, index) {
floor.requestedUp = false;
floor.requestedDown = false;
floor.on("up_button_pressed", function() {
floor.requestedUp = true;
});
floor.on("down_button_pressed", function() {
floor.requestedDown = true;
});
});
No More Floors To Go To
Currently, if there are no people in the elevator requesting a floor, it just waits wherever it is currently stopped until someone gets in and presses a floor button again. Let's change this.
In the previous step, we started keeping track of what floors people were waiting on - so let's just pick the closest floor where there is a request to go down or up (or both), pick everyone up (we are ignoring whether they want to go down or up for now) and reset the request attributes for that floor until someone new comes along and waits for an elevator (otherwise we might end up with multiple elevators idling and going there).
But what if there is no one waiting on any floor? We'll keep it simple for now and tell the elevator to return to the ground floor in that case.
elevator.on("idle", function() {
var requestedFloors = floors.filter(function(f) {
return f.requestedUp ||
f.requestedDown;
});
var distances = requestedFloors.map(function(f) {
return Math.abs(f.floorNum() -
elevator.currentFloor());
});
var floorIndex = Math.min.apply(null, distances);
if (requestedFloors[floorIndex]) {
var floorNum = requestedFloors[floorIndex].floorNum();
floors[floorNum].requestedUp = false;
floors[floorNum].requestedDown = false;
elevator.goToFloor(floorNum);
} else {
elevator.goToFloor(0);
}
});
Making The Queue More Efficient
Let's recap our current algorithm: We go to each floor requested by a passenger, and if there are no more floors, we go to the closest one where someone is waiting for an elevator to pick them up. This is fine, but it has one huge inefficiency. Let's say we are on the ground floor, and two people get in. The first one wants to go up five floors, and the second one wants to go up one floor. With our current implementation, we would go up five floors first, and then go down again to drop off the second passenger, resulting in a huge detour and an unnecessarily long trip for our second passenger. In addition, we might go up five floors from the ground floor with just one passenger on board, while there are other people that want to go up too and could have been picked up waiting along the other floors in between.
Luckily, the game's API provides a simple event that is triggered right before the elevator passes a floor which lets us improve this without having to sort the queue of requested floors every time we add one or implement some sort of scheduling to send elevators to requested floors before they become idle and go there on their own.
Let's implement three simple rules to decide whether the elevator should stop on a floor it passes while en route to its destination:
- If the elevator still has enough capacity and is currently going upwards, stop if there is someone waiting to go up from the floor.
- If the elevator still has enough capacity and is currently going downwards, stop if there is someone waiting to go down from the floor.
- If the floor has already been requested by a passenger currently on the elevator, stop there now and remove the floor from the queue so we don't end up going there again later.
elevator.on("passing_floor", function(floorNum, direction) {
if (elevator.loadFactor() <= 0.7) {
if (direction == "up" && floors[floorNum].requestedUp) {
elevator.goToFloor(floorNum, true);
}
if (direction == "down" && floors[floorNum].requestedDown) {
elevator.goToFloor(floorNum, true);
}
}
if (elevator.destinationQueue.indexOf(floorNum) != -1) {
elevator.destinationQueue.splice(elevator.destinationQueue.indexOf(floorNum), 1);
elevator.goToFloor(floorNum, true);
}
});
One Small Thing...
Finally, we need to set the request attributes for a floor to false whenever we stop there and pick people up. For this, we just set the request corresponding to the current travel direction of our elevator to false whenever we stop.
elevator.on("stopped_at_floor", function(floorNum) {
if (elevator.destinationDirection() == "up") {
floors[floorNum].requestedUp = false;
} else {
floors[floorNum].requestedDown = false;
}
});
Going Further
The algorithm outlined above currently passes twelve of the eighteen challenges provided by the game. Right now, there are two additions I can think of which would bring further improvements to the efficiency.
The first one concerns picking up people when stopping at a given floor - the game provides a way of setting the indicator lights to tell the passengers whether the elevator is going to go up or down, so we could make use of these to prevent picking up someone while going in the wrong direction.
The second improvement concerns the behavior of the elevator when it is idle. We currently only check for requested floors once when going idle. Instead, we might implement some sort of load balancing / scheduling solution which assigns a floor request to a suitable elevator either by distance or current load whenever it occurs.
The full source code of my current solution can be found at https://github.com/bschne/elevator-saga/