Elevator Saga – An elevator programming game | Hacker News Reader

Elevator Saga – An elevator programming game

play.elevatorsaga.com

411 pointssandebert104 comments

A project during my graduate work was to solve this problem. You can read my write up, which includes pseudo-code for the best algorithm I found[1].

Long story short: a simple, rules-based algorithm defeated my best efforts at having multiple elevators working together to coordinate their action.

[1]: https://clarkmoody.com/Moody_AgentBasedElevatorControl.pdf

Slightly related - SimTower was originally created as an elevator simulator - if you right click on an elevator engine room in the game you get a wealth of programming options

mind: blown

Never even knew all those years playing SimTower... I knew other tricks, but never this.

The people in that game were a lot smarter though; if the only path to a floor required switching elevators, they would do it.

Well Sim tower had range limit elevators. This game doesn't.

Damn I miss this game

Developer here! Thanks for all the feedback. Appreciate all of it, including bug reports! Pull requests also welcome.

Especially I would appreciate help with adding more challenges, and/or making them all balanced and interesting, for a good and reasonable difficulty curve.

It is very simple to tweak them - they are defined at the bottom of challenges.js: https://github.com/magwo/elevatorsaga/blob/master/challenges...

What I would've loved to have seen in some of the later levels is a very clear "you now need to use this new API call to accomplish the goal. Here's how that call works."

For example: in level 2, what if people only ever came to the second floor trying to go to the third floor, so you had to look at where buttons were being pushed and where they wanted to go?

hi, why leaving the elevator at a floor doesn't pick up additional passengers? i.e.

http://pastebin.com/xA4NJbas @ http://play.elevatorsaga.com/#challenge=2

(yes that's only a stub, but has logging as I was trying to understand the event order)

at least elevator.goToFloor(elevator.currentFloor());

doesn't count as a move and unlocks the passenger to onboarding

btw, when you start you get 2 moves per elevator in the moves count

The last one about moves has been fixed.

The additional-people-not-getting-on is kind of an architectural problem with the game, working on it.

This is incredible. I've been successfully nerd-sniped away from work. Also nice touch w/ the time-scale factors being Fibonacci numbers :) Great work.

Likewise.

Nitpick. Accidentally programming an infinite loop kills the page. Refreshing restores the offending code and immediately does it again. Had to clear cookies to get going again?

Just drop in a while (1) {} to reproduce.

Slightly related question: are there any standard workloads and tools out there for experimenting with elevator programming?

My apartment building has a utility elevator and two normal elevators. Each floor has two sets of call buttons. These have been programmed in different ways over the years, and I've always been curious if there was a good way to quantify the changes.

http://www.quora.com/Is-there-any-public-elevator-scheduling...

Here's a fairly simple strategy for beating challenges 1 - 5. Basically drop off people in the elevator according to whoever's floor is closest. Then once the elevator is empty go to the closest floor that has people waiting to be picked up.

https://gist.github.com/cspags/93f18a2fe505bf4f1686

Nitpick: it breaks the browser's back button

Sure does

Yea, the super wide screen is super annoying. Is there some reason for the big width? A little stealth at work would be nice, hard to hide something that huge.

Another nitpick: it's 1360 px wide.

Yeah, I just had a little difficulty with that. It doesn't fit on my crappy projector.

came to the comments to say this

For someone like me who knows zero Javascript, this is exactly the sort of puzzle I need to get started. Elevator programming has always interested me. Thanks also to SeoxyS for posting some code - I was struggling a lot to get started without a few examples.

This is built with Riot.

https://news.ycombinator.com/item?id=8928433

v1. Not the same version as that HN article.

A couple of problems with the API.

First, why do you have to call checkDestinationQueue after modifying the queue? It's awfully redundant. I assume this is due to some kind of limitation.

And second, goingUpIndicator and goingDownIndicator are kind of sketchy. Can you activate both at the same time? What effect would that have? There should be a single property, directionIndicator of an enum type with the possible values up, down, and none. I don't think you can make enums in javascript though, but I don't know the language very well. I'm just explaining this in terms that I know; there probably is a suitable javascript equivalent or replacement.

I'm not a developer of the game but:

DestinationQueue handling: It is not redundant, those are different options. Just to give an valid example: Add something to the queue, sort the queue, make the elevator run the updated and sorted queue.

Having both goingUpIndicator and goingDownIndicator is probabaly necessary to get this abritrary third state (both enabled / both disabled) which essentially indicates that the elevator will go in both directions.

Yeah this is basically correct. There is nothing really preventing an elevator from reporting that it's going both up and down. The up/down indicators are used for two things: 1. To shut off the up/down request indicators correctly on the floor when the elevator arrives. 2. By passengers to decide whether to get on an elevator or not.

Thanks, I'm having a hard time with those indicators as well. One question. If I never set the indicators in my code, do they automatically get set? Or are the passengers getting on the car when there is no indicator?. (So far I've been having a lot of people refuse to get on my car, and I assume it's because my code is setting the wrong indicator).

BTW, this is a game that will haunt me for a long time to come. Even when I pass a level, I stay on it trying to reduce the metrics rather than accept that I "lucked out" with my naive algorithm. You did a fantastic job on this.

I think they are automatically set to true at the start, and will never change unless you change them.

correct, those works as flag with 'accept passenger in these direction' meaning. also note that if you change those values while you are at a floor, you need to go to that floor again for passenger to notice.

I got to Challenge #5 by just having the elevators go to every floor like in the first example. It'd be nice to have an earlier challenge with only a single elevator force you to have a more complex controller. With 4 elevators going at a time, it's harder for me to "debug" and figure out how to use the API.

> I got to Challenge #5 by just having the elevators go to every floor like in the first example.

Strange, that strategy doesn't allow me to get past challenge 2 (just going to every floor one after the other).

Guess, I got lucky, haha. I should probably go back to challenge 2 and learn how to program these then.

On six it takes you back to 4 floors with 2 elevators and the challenge is 40 people in under 60 elevator moves.

The first 5 are easy to "brute force" but six is making me think a bit more.

I cheated with #6. My elevators wait on the ground floor until they fill up, then they deliver the patrons to their floors. Everyone not on the ground floor... is stuck forever.

Wow. I want so many more of these kind of things for my kids. It's so close to using code to solve real problems. How about an assembly line version where many parts have to come together in the correct order? Or an air traffic control one? Subway scheduling? Pizza delivery? More please!

It isn't quite programming, but your assembly line comment reminded me of http://pleasingfungus.com/Manufactoria/ which is a game about making state automata.

Yeah! Something I think about occasionally is traffic-light optimization problems, optimizing for throughput, wait-time, safety etc. I think it could work well in a packaging similar to Elevator Saga.

Markus Mattinen submitted the best solution so far: https://github.com/MarkusMattinen/elevatorsaga-solutions/blo...

And here's my solution, not too bad, had lots of fun: https://github.com/tasuk/elevatorsaga-solver

  {init:function(){world.transportedCounter=999999},update:eval}

oh man, both clever and evil. love it!

In challenge 3, I got the following error:

There is a problem with your code: .init@http://play.elevatorsaga.com/app.js line 66 > eval:12:9 createWorldController/controller.start@http://play.elevatorsaga.com/world.js:185:13 app.startChallenge@http://play.elevatorsaga.com/app.js:175:9 @http://play.elevatorsaga.com/app.js:216:13 riot.observable/el.trigger@http://play.elevatorsaga.com/libs/riot.js:45:1 pop@http://play.elevatorsaga.com/libs/riot.js:89:31

The error messages are bad because eval()...but rest assured there is a problem in your code.

I wonder how much more efficient you could be, if people didn't just call for going up/down, but their destination floor.

ahead of time optimization!

They have that at work and it takes far longer to get an elevator. It's always annoying going to those buildings and using those elevators.

I like it much more. Yes, getting an elevator might take longer, but total travel time should be reduced. (Otherwise, the system is programmed wrong.)

As well as the overall throughput of the elevator system should be improved a lot.

In more than a few buildings I've worked in, these 'destination controlled' elevators shine the moment after a fire-drill and a couple of hundred people attempt to get back upstairs. It must be quicker, how else to justify what I'd imagine to be a far higher cost of operation.

I'd love to see a version of the game that does this, for comparison.

This is awesome, however is there any way to get better syntax errors? Damnit Jim, I'm a C programmer not a Javascript coder!

Try looking in the dev tools? I've been able to debug a few runtime errors this way.

I think it would be a lot easier if idle elevators have idle fire every time someone presses a button.

That way the elevator can evaluate the new situation. Now you have to look up an elevator in the button event, and the API does not specify many properties, only events.

Need help on this. I tried registering a handler for the up_button_pressed and down_button_pressed events, but the handler doesn't seem to be passed any arguments.

Is this correct?

    floor.on("up_button_pressed", function(event) { ... } );

I don't think you need an argument. Within the callback function you still hold a reference to floor, and you know the up button has been pressed. There doesn't seem to be any more information. Note that there is also down_button_pressed

Is it just me, or is programming more than one elevator buggy?

I used a for( var i =0;i < elevators.length;++i) statement to apply my code to each elevator, but people only keep using the last one. Could someone give me a hint? ;)

You're probably hitting an issue with the way that closures work in javascript (and many other languages).

    for(var i = 0; i < elevators.length; ++i) {
        elevator[i].on("floor_button_pressed",
             function(floorNum){ elevator[i].goToFloor(floornum)});
    }

Doesn't do what one might expect. When the anonymous function is invoked, it looks up the value of the 'i' identifier, which will have changed it's value to elevators.length by the end of the loop. To get the behavior you want, I've seen people do

    for(var i = 0; i < elevators.length; ++i) {
        (function(i){
            elevator[i].on("floor_button_pressed",
                function(floorNum){ elevator[i].goToFloor(floornum)});
        })(i);
    }

This creates a new scope, which ensures that 'i' has the value that was passed in. I'm afraid I'm a little too tired to look up the parts of the spec that make the semantics clear.

Thank you! Your suggestion makes sense indeed and works fine!

You can also use:

  elevators.forEach(function(elevator, elevatorNumber) {...});

This will provide each elevator with its index in the elevators array.

How are the passengers generated? Do they follow a realistic distribution, or are they just completely random?

The game would be a lot more fun with realistic or even real measured workloads.

Dev here. :)

They spawn at a fixed rate, but at random floors, with 50% spawning at the bottom floor.

I agree it would be more interesting if there were patterns, distributions, more popular floors etc. Haven't gotten around to implementing it. There's a small unused bit of code here intended for this: https://github.com/magwo/elevatorsaga/blob/master/challenges...

Pretty cool concept. Had a little trouble working out how to get started because on my 1024px wide monitor, the 'apply' button was not visible.

// works well enough:

{ currentFloor: 0,

    init: function(elevators, floors) {
        var elevator = elevators[0]; // Let's use the first elevator
        elevator.on("idle", function() {
            // The elevator is idle, so let's go to all the floors (or did we forget one?)
            var nextFloor; 
            do nextFloor = Math.round(Math.random() * 2); while (nextFloor == this.currentFloor); 
            elevator.goToFloor(this.currentFloor = nextFloor);
        });
    },
    update: function(dt, elevators, floors) {
        // We normally don't need to do anything here
    }, 
    vendor: 'Sirius Cybernetics Corporation'
}

Okay, didn't read or look (currentFloor is already defined) and this won't work in this context.

Here is another approach that brought me through till challenge #7:

    {   
        init: function(elevators, floors)  // hook up events
        {
            // these are the global wish lists that idle elevators choose from (key are floor numbers, values are number of people): 
            var wishListUp = {}, wishListDown = {}; 

            for (var i = 0, l = elevators.length; i < l; i++)
            {
                var elevator = elevators[i];
                // API: goToFloor(n) [enqueues], stop() [clears queue], currentFloor(), 
                //      goingUpIndicator([set]), goingDownIndicator([set]), loadFactor() [0..1], 
                //      destinationQueue[], checkDestinationQueue() [after manual update]

                elevator.on("idle", function()  // elevator destination queue finished
                {
                    processWishList();
                }); 

                elevator.on("floor_button_pressed", function(floorNum)  // passenger indicates where to go
                {
                    if (this.destinationQueue.filter(function (d) { return d == floorNum; }).length == 0)  // if not already enqueued
                        this.goToFloor(floorNum);  // enqueue
                    // note: passengers coming first need to be delivered first (or at least at all)
                    //       however, the elevator will check by passing, whether one destination
                    //       can be approached before the others since it comes on the way. 
                }); 

                elevator.on("passing_floor", function(floorNum, direction/*"up"/"down"*/)  // if not in destination queue
                {
                    updateIndicators(this);  // indicate next destination from here
                    // we stop here if the queue contains this destination, 
                    // or if a passenger on the global wish list want to go in our direction. 
                    // we can only hope that people check where the elevator is going. 
                    if (this.destinationQueue.filter(function(d) { return d == floorNum; }).length > 0)
                    {
                        this.destinationQueue = this.destinationQueue.filter(function(d) { return d != floorNum; });  // remove from later
                        this.destinationQueue.unshift(floorNum);  // add as immediate next destination
                        this.checkDestinationQueue();  // announce modification
                    }
                    else if (this.loadFactor() < 1.0)  // if there is some space left
                    {
                        switch (getDirection(this))
                        {
                            case 1:  // going up
                                if (wishListUp[floorNum])  // are people waiting to go up from here?
                                {
                                    //if ((1.0 - this.loadFactor()) * 10.0 - wishListUp[floorNum] > 0)  // assume capacity for 10 people with regular weight
                                    //    delete wishListUp[floorNum];  // mark as visited
                                    this.destinationQueue.unshift(floorNum);  // add as immediate next destination
                                    this.checkDestinationQueue();  // announce modification
                                }
                                break;
                            case -1: // going down
                                if (wishListDown[floorNum])  // are people waiting to go down from here?
                                {
                                    //if ((1.0 - this.loadFactor()) * 10.0 - wishListDown[floorNum] > 0)  // assume capacity for 10 people with regular weight
                                    //    delete wishListDown[floorNum];  // mark as visited
                                    this.destinationQueue.unshift(floorNum);  // add as immediate next destination
                                    this.checkDestinationQueue();  // announce modification
                                }
                                break;
                            case 0:  // final destination
                            default: 
                                break; 
                        }
                    }
                }); 

                elevator.on("stopped_at_floor", function(floorNum)  // one destination reached
                {
                    processWishList(); 
                    updateIndicators(this);  // next direction
                });
            }

            for (var i = 0, l = floors.length; i < l; i++)
            {
                var floor = floors[i];
                // API: floorNum()

                floor.on("up_button_pressed", function()  // somebody wants to go up from a certain floor
                {
                    // elevators are choosing their next best destination, 
                    // we just enqueue this into the global wish list queue: 
                    var f = this.floorNum(); 
                    if (wishListUp[f])
                        wishListUp[f]++; 
                    else
                        wishListUp[f] = 1;
                    processWishList(); 
                }); 

                floor.on("down_button_pressed", function()  // somebody wants to go down from a certain floor
                {
                    // elevators are choosing their next best destination, 
                    // we just enqueue this into the global wish list queue: 
                    var f = this.floorNum();
                    if (wishListDown[f])
                        wishListDown[f]++;
                    else
                        wishListDown[f] = 1;
                    processWishList();
                });
            }


            function processWishList()  // give idle elevators a new destination
            {
                for (var i = 0, l = elevators.length; i < l; i++)  // idle
                {
                    var elevator = elevators[i]; 
                    if (elevator.destinationQueue.length == 0)
                    {
                        var next = chooseFloor(elevator.currentFloor(), true);  // find closest wish
                        if (elevator.currentFloor() != next)
                            elevator.goToFloor(next); 
                    }
                }
            }

            function getDirection(elevator)
            {
                if (elevator.destinationQueue.length == 0)
                    return 0;  // nowhere
                else if (elevator.currentFloor() < elevator.destinationQueue[0])
                    return 1;  // up
                else
                    return -1;  // down
            }

            function chooseFloor(currentFloor, dequeue)
            {
                // choose next destination from the global wish lists for up and down, 
                // depending on a) closest distance and b) number of waiting passengers: 
                var wishList = {};  // joined up and down lists with passenger counts
                var floors = [];  // array of distinct floor numbers
                for (var i in wishListUp)
                {
                    wishList[i] = wishListUp[i]; 
                    floors.push(i); 
                }
                for (var i in wishListDown)
                    if (wishList[i])
                        wishList[i] += wishListDown[i];
                    else
                    {
                        wishList[i] = wishListDown[i];
                        floors.push(i); 
                    }
                floors.sort(function(a, b)
                    { 
                        var res = Math.abs(currentFloor - a) - Math.abs(currentFloor - b);  // by closeness asc
                        if (res == 0)
                            res = wishList[b] - wishList[a];  // by passengers waiting desc
                        return res; 
                    }); 
                if (floors.length == 0)
                    return 0;  // nothing to do, go back to base
                var next = floors[0];
                if (dequeue)
                {
                    if (wishListUp[next])
                        delete wishListUp[next]; 
                    if (wishListDown[next])
                        delete wishListDown[next];
                }
                return next; 
            }

            function updateIndicators(elevator)
            {
    return;  // there seems to be a bug if announcing, people do not react ..
                switch (getDirection(elevator))
                {
                    case 1:  // up
                        if (!elevator.goingUpIndicator())
                            elevator.goingUpIndicator(true);
                        if (elevator.goingDownIndicator())
                            elevator.goingDownIndicator(false);
                        break; 

                    case -1:  // down
                        if (elevator.goingUpIndicator())
                            elevator.goingUpIndicator(false);
                        if (!elevator.goingDownIndicator())
                            elevator.goingDownIndicator(true);
                        break; 

                    case 0:  // nowhere
                    default: 
                        if (elevator.goingUpIndicator())
                            elevator.goingUpIndicator(false);
                        if (elevator.goingDownIndicator())
                            elevator.goingDownIndicator(false);
                        break; 
                }
            }
        },

        update: function(time, elevators, floors)  // loop during operation, called each frame
        {
        }, 

        vendor: 'frevd'
    }

I stopped writing javascript for work at 10pm and then for fun immediately started writing javascript for imaginary elevators until way too late o'clock

I can't help but feel like there is something deeply wrong with me

If you accidentally make an infinite loop, you can no longer load the page :(

Good find!

Clearing cookies/localstorage should fix that for you, at least until the devs figure out a fix :)

My attempt at a basic smart algorithm. Not so easy...

https://gist.github.com/kballenegger/e275a99d50de2ee07f97

Why do you have conditionals written like this: if (elevator.goingUpIndicator() == true)? Why not just: if (elevator.goingUpIndicator())?

I believe some people really need think in term of comparations and, for those, adding a "==" symbol make sense, even if the resultant code doesn't make any sense at all!!

Also, I can never understand why people write ..

    if (foo()) {
        return true;
    } else {
        return false;
    }

.. or things like extra parens on conditionals, or weird styles like:

    return (false);

I strongly believe people write as they talk, and talk as they think; which not clearly translates linearly when what you write is code ;)

Many languages are expressions (as opposed to statements) including C-like languages. I've always thought that 'return' itself was redundant. If a compound statement was defined to return the value of the final (executed) statement, then functional methods would get much simpler. And remove the need for the '?' operator for instance.

e.g.

   int foo(int x) {   bar(x,y); }

   x = {if (foo() > 9) true; else false; }