Walk Boxes!

by Ron Gilbert
Apr 27, 2015

Here's a quick video I did narrating walk boxes, how they work, and how they are used with doors and other blocking objects... enjoy.

As the video shows (You did watch the video? I spent hours making it, the least you can do is actually watch it!) walk boxes can be turned on and off via script control and that was one of my basic requirements for the system.

That introduces some complexity into the path finding, but that complexity is worth it in how easy it makes blocking players with closed doors, gates, etc.

Right now, walk boxes must be convex polygons, but I plan on making it so actors can navigate around the interior of concave polygons.

That's a slightly more complex problem because with convex polygons, you can draw a straight line/path between any two points inside the polygon, so if the actor is walking within it, there's no pathfinding. With concave polygons, the actor will need to path find around the edges of the polygon.

Not a huge problem, but I wanted to get walk boxes working and then move on to other tasks in the engine and game. I'll revisit path finding in a few months. As I mentioned on last week's podcast, path finding is a task you can get lost in very easily. It's a rabbit hole of refinements. My goal is to get everything working in the engine, then go back and refine what needs refining.

Here is the code for the jail seen in the video above (You did watch it? Right?).

SheriffsOffice <-
{
    background = "SheriffsOffice"

    enter = function()
    {
        if (sheriffsOfficeJailDoor.jail_door_state == OPEN) {
            walkboxHidden("jail_door"NO)
        } else {
            walkboxHidden("jail_door"YES)
        }
    }

    exit = function()
    {
    }

    jail_close_duration = 1.5

    function openJailDoor() {
        objectOffsetTo(sheriffsOfficeJailDoor, -600, SheriffsOffice.jail_close_duration)
        objectTouchable(sheriffsOfficeJailDoor, NO)
        breaktime(jail_close_duration)
        objectTouchable(sheriffsOfficeJailDoor, YES)
        sheriffsOfficeJailDoor.jail_door_state = OPEN
        walkboxHidden("jail_door"NO)
    }

    function closeJailDoor() {
        walkboxHidden("jail_door"YES)
        objectOffsetTo(sheriffsOfficeJailDoor, 00, SheriffsOffice.jail_close_duration)
        objectTouchable(sheriffsOfficeJailDoor, NO)
        breaktime(jail_close_duration)
        objectTouchable(sheriffsOfficeJailDoor, YES)
        sheriffsOfficeJailDoor.jail_door_state = CLOSED
    }

...

    sheriffsOfficeJailDoor =
    {
        name = "Jail Door"
        useDist = 20
        jail_door_state = CLOSED
        verbLookAt = function()
        {
            if (jail_door_state == CLOSED) {
                sayLine("The door is closed.")
            } else {
                sayLine("The door is wide open.")
            }
        }
        verbOpen = function()
        {
            if (actorInWalkbox(currentActor, "jail")) {
                sayLine("I can't open it from in here.")
                return
            }
            if (jail_door_state == OPEN) {
                sayLine("The door already open.")
            } else {
                startthread(openJailDoor)
            }
        }
        verbClose = function()
        {
            if (jail_door_state == CLOSED) {
                sayLine("The door is already closed.")
            } else {
                startthread(closeJailDoor)
            }
        }
    }

...

}

- Ron



Damian - Apr 27, 2015 at 14:54
Wonderful!

One's inclined to think there should be an efficient pathfinding algorithm already? Why I keep seeing devs trying to make their own? Is this some "dev coming-of-age" thing? ("You're not considered a true dev until you develop your own efficient pathfinding algorithm, little grasshopper!")

:P

Ron Gilbert - Apr 27, 2015 at 15:01
There are existing algorithms and we all use them, it's just that the code is often different because of internal requirements, data structures, etc of the game. Or sometimes, the algorithm is unnecessarily complex/slow for the task.  This isn't an issue of NOT knowing how to navigate around a concave polygon, it's the time to implement it. I'll get back to it once other important tasks are done. One of the worst mistakes a dev can make is to iterate too much on a single task before moving on to the next. You could spend months perfecting a feature that is going to change or be cut.

Miguel - Apr 27, 2015 at 15:17
Great video Ron! The current system of convex  4-point polygons is simple and works great. On top of that, even though I'm sure it's a time consuming process, it can scale up easily. If it worked for Monkey 2 it should work for Thimbleweed Park! I actually think that these are pieces of art: http://imgur.com/IE5H8TC

Ron Gilbert - Apr 27, 2015 at 15:20
The current Thimbleweed walk boxes can deal with n-sided polygons, they just need to be convex. All the tools were built to handle n-sided, so all I need to be to replace some code and concave polygons should be working.

Augusto - Apr 27, 2015 at 16:52
You could triangulate in your tool, and index the resulting triangles with the logical name of the original walk box so that the engine function that checks whether you are in a walk box or not still works, hiding those details from the script.

JJ - Apr 27, 2015 at 15:19
What happens if an actor is inside the jail door walkbox when it disappears?

Ron Gilbert - Apr 27, 2015 at 15:22
They will stay in it, but once they walk to a polygon, they will be stick in it. It's not a perfect solution, but it fails gracefully. Each time the room is entered, all actors will get pushed into valid polygons, so if a polygon was turned off while not in the room, when you enter, they will be moved.

Rum Rogers - Apr 27, 2015 at 16:07
I've been waiting for this post for a long time, wonderful!
How do you apply pathfinding BETWEEN boxes? Do you have some kind of precompiled adjacency matrix, or do you apply some pathfinding algorithm like A* or similar, treating every box as a node of the search graph?
Please Ron, enlighten me!

Rum Rogers - Apr 28, 2015 at 11:41
Ouch, my technical question was the only one left unanswered. That hurts.

Mattias Cedervall - Apr 27, 2015 at 16:18
Very interesting video, Master Ron, but I still root for Silly Walks-boxes! ;P

The file polygons.png must be amongst Gary's finest work! :P

Ron Gilbert - Apr 27, 2015 at 16:23
That art is ALL me.

Mattias Cedervall - Apr 27, 2015 at 19:52
I guessed it was you so I was just kidding. I'm sorry. I hope you and Gary will forgive me! I can't forgive myself. Who am I? Thank you for your comment, Ron! :-) You're the best!

Brian S - Apr 27, 2015 at 16:29
What does ObjectTouchable control?  Does it prevent any verbs from being used on the object when it is set to NO?  I could see that being important, you wouldn't want to have a situation where you have to support the Open or Close verbs on the Gate while it's moving.

Ron Gilbert - Apr 27, 2015 at 16:32
Yes, that's what it does.

Kim Jørgensen - Apr 27, 2015 at 16:32
So, you can lock yourself up in jail. Still test code I guess.
Are the verbs hardcoded in the engine?
/Kim

Ron Gilbert - Apr 27, 2015 at 16:37
You can't because the you close the door, the actor will walk to the object's use position, which is outside.

Kim Jørgensen - Apr 27, 2015 at 16:41
OK makes sense. What about the verbs?

Kim Jørgensen - Apr 27, 2015 at 16:58
Now I'm wondering how the special case for open can be activated while you are in jail? Will the actor not try to walk to the object's use position?

Ron Gilbert - Apr 27, 2015 at 17:05
In the case of open, the use position is within reach of the actor, so the verb is run, then does the walk box check to see if they are stuck in jail. When the door is open, the actor just walks out of the jail and to the use position. As you said in an earlier comment, this is early. There are likely to be edge cases we need to trap for, or better yet, make the system robust enough to handle them so we're not writing special case code.

PrinzJohnny99 - Apr 27, 2015 at 16:35
This video somehow destroyed some of the magic of all the Lucasfilm Games adventures. Couldn't watch it till the end. This is like showing the tricks of some awesome David Copperfield show. When you are a programming n00b like me, you simply don't want to know anything about walk boxes. Door is closed, you can't go through it. This is how my world works.

Mattias Cedervall - Apr 27, 2015 at 19:54
I've seen David Copperfield live once! :-) He's my favorite illusionist.

Franklin - Apr 28, 2015 at 02:17
I agree.

wedge - Apr 27, 2015 at 16:49
Very interesting, I'm seeing lots of stuff I might use later. I had done quite some time ago some basic 2D advenutre engine.  I remember spending quite some time with these walking "boxes". I believe in the end I went using triangles as the easiest way at that time for me to get something working. As I thought at that time, well what forms could I use to make it easy to both program and place.
First thing where rectangles, but it was giving quite "ugly" walking box though working. As it was easy to get from a point to another as inside a rectangle you can go directly to any point in the rectangle, so just needed links between rectangles and there you go. But well it was not that nice, so I added triangles and mixed triangles and rectangles as you can also go anywhere frome inside a triangle to any other point inside the same triangle, which give me a rough basic working pathfinding and with some depth illusion playing on the character size following movement.
I should get back to that at some point, I still have the cource code and a demo I made might share it if some want a look as well as source code. But it is "very old" I did that almost 10 years ago, using SDL for graphics and audiere for sound though. The rest was my own work no editor but easy to make text file to configure everything :p

Really great blog and lot of memories on my own like having sound playing on specific frame of an animation for the walk to make sure the sound would play when the foot would it the ground :) Looking forward next devsblog :)

Peter Campbell - Apr 27, 2015 at 17:55
So a few questions, one has sorta been answered but i'm still wondering, and I'm well aware that this is still a very very early build of the game engine...

1) Can a player stand on the little walkbox that's in-between the inside and outside of the jail cell?  If yes, then what happens if Reyes is standing on it and Rey goes to shut the cell door? Does the walkbox disappear causing Reyes to get pushed into the jail cell walkbox, outside the jail cell walkbox, or does a message appear saying "i can't do that right now" when trying to "close" the door.

2) When a player does activate a jail door to close or open, or activates some other type of mechanism with a very brief half a second animation, does the animation have to finish before the player can move an actor or use a verb or can the player do stuff in that half a second while those animations are happening?

Ron Gilbert - Apr 27, 2015 at 18:01
I answered #1 above. It's an edge case and probably not worth spending a lot of time fixing. It would only be a small graphical glitch. Worth a few minutes to solve, not worth spending a day. At some point, all this comes down to trade-offs.

#2: In the case of the door, it doesn't really matter if the actor walks around while the door is opening or closing (the walk box is changed when the action starts). In other cases if there is a small window of "danger", the input is silently turned off and then back on. 99.9% of the time, players won't notice. We did this all the time in MI.

stderr - Apr 27, 2015 at 19:12
It should be easy to turn a concave polygon into a series of convex polygons and since you already have function in place to move from one polygon to another, you could just use the series of convex polygons instead of the original concave polygon.

In some kind of weird pseudo-code this should do the trick:

function turn_concave_polygon_into_a_series_of_convex_polygons(Polygon concave) /* TODO: Find better name... */
{
    Polygon convex_array[];

    while(concave.number_of_vertexes > 3)
    {
        /* Create a new polygon from the first 3 vertexes of "concave". A triangle is, by definition, convex */
        Polygon convex = new Polygon(concave.vertex[0] , concave.vertex[1] , concave.vertex[2]);

        /* Add it to the series of convex polygons */
        convex_array.push(convex);

        /* Remove vertex 1 from the list of vertexes in the concave polygon, thereby connecting the old vertex[0] directly with vertex[2] */
        concave.remove_vertex(1);
    }

    /* At this point concave will only have 3 vertexes left and since triangles are convex, we might as well add it to the convex_array and forget it even existed... */
    convex_array.push(concave);

    return(convex_array);
}

Actually, you could probably use that function on polygons that are already convex without any problems, so you don't even have to check if the polygon is already a convex hull or not.

walkboxHidden() would need to know that it might need to change the state of more than one polygon, but that's just small details.

BTW: In verbOpen, wouldn't it be a good idea to check if the door is already open BEFORE you check if the currentActor is in the jail or not?

Something like:

        verbOpen = function()
        {
            if (jail_door_state == OPEN) {
                sayLine("The door already open.")
                return
            }

            if (actorInWalkbox(currentActor, "jail")) {
                sayLine("I can't open it from in here.")
                return
            }

            startthread(openJailDoor)
        }

Duphus - Apr 27, 2015 at 21:15
Ron, could you do a live-stream where you program and explain some of what you're doing?

Alex - Apr 28, 2015 at 01:12
LOOK AT walk box.
"It's a walk box."

OPEN walk box.

T. Benjamin Larsen - Apr 28, 2015 at 01:49
Interesting to see how you tie snippets of character dialogue directly to the objects/items (I believe you mentioned it in an earlier post as well).

Are you planning to also have the objects handle the earlier mentioned give/receive logic in a similar manner? It seems this would make sense contextually, but perhaps at the risk of making the objects somewhat bloated(?)

Ciantic - Apr 28, 2015 at 04:49
I have a random idea for path finding algorithm: Generate sufficient amount points (randomly for fun) inside, and on the borders of the walk boxes, connect them to graph and use dijkstra.

Evan - Apr 28, 2015 at 07:41
Hey nice stuff!
I just couln't hold myself on how relevant the following tool and especialy the video showing it, is to this post and the man posting it :P
https://www.youtube.com/watch?v=k8RH1jFYHEA

Mike - Apr 28, 2015 at 12:50
geia sou re file

ConjoinedCats - Apr 28, 2015 at 09:11
I really enjoyed these technical dives focused on individual features. Please continue!

The cell door animation is a linear object movement.  I wondered if you could add an easing function (so that the cell door slams shut instead of gliding gently) and of course you CAN... now. But could you then, and if not will you now?  

I'm wondering if simple things like easing functions (especially elastic bounce, or any computationally intensive one) were avoided on the games back in the day because of CPU power.  You're limiting things like color palettes for vintage aesthetics so I wondered: would excluding "fancy animations" fall under the same goal  of 'maintaining authenticity'? Thanks!

Ron Gilbert - Apr 28, 2015 at 09:18
The doors are power by something in my engine called Motors. They can move a object's property from one state to another (position, scale, rotation, color, etc).  My motors have about 10 different types, from linear, sin, bounce, pop, etc.  Currently I've only exposed the linear to the scripts. In the final game, objects like the door would get a small bounce motor type.

DZ-Jay - Apr 28, 2015 at 18:05
Hi, Ron,

That's very interesting.  Can you elaborate how these "motors" work, from a technical perspective?  Is it just a method that is called on every tick for each actively moving object which applies a function to the some attribute (e.g., position, scale, rotation, color, etc.)?

      -dZ.

Ron Gilbert - Apr 28, 2015 at 18:19
Yes, they just iterate from a START to an END value over a TIME using various functions like linear, easeIn, easeOut, sin, bounce, etc. You attach the motor to a property (position, scale, color, alpha, rotation, etc) and they get called every frame and do their work. Once you start a motor, you don't have to worry about it until it's done. It can die on it's own, or it can do a callback when it finishes. They are magical.

DZ-Jay - Apr 30, 2015 at 05:33
Of course! I love magical motors. :)  I use a similar mechanism to I implement basic physics in my own games.  The beautiful thing is that the "motor" doesn't care whether the value it is modifying represents, say, the vertical velocity of an object (i.e., to apply gravity), or the pitch of a sound oscillator (i.e., to apply frequency modulation or a downward sweep).

Thanks for sharing! :)

      -dZ.

Jammet - Apr 28, 2015 at 18:05
On the C64, this would have probably been done in such a way that it looks like a black bar is being drawn, one to three at a time, with a nice, drawn out, bassy SID sound effect. :)

I wonder if it would be possible to put styles into MOTOR that would look and feel like that. Of course back in the day, there were technical limitations stopping you from doing it the way you do it now. It's just a thought.

Imagine the game had one mode where it would go to great lengths to act like the old games on a technical level, too. No smooth animations of big objects. Doors that open and close in 1-frame. Things like that.

DZ-Jay - Apr 30, 2015 at 05:27
I can surely imagine that.  In fact, it's done all the time.  Just look for new games written to run on an emulated C=64. ;)

Why go through the trouble of building the limitations into your game when running an emulated ancient computer will enforce it for you?

     -dZ.

Jammet - Apr 30, 2015 at 06:43
Well, for fun of course. For the style. It would even more feel like it were made on a computer with such limitations. Some people like that very much, and I'm both boats.

Jammet - Apr 28, 2015 at 18:00
It is absolutely exciting being part of this and watching your videos or reading about what's going on, Ron!

Duphus - Apr 28, 2015 at 19:32
Will the final game be open-source?

Ralph Upton - Apr 28, 2015 at 20:48
Would it make sense to just give up on graphics programming and just make it text-only?

Zak Phoenix McKracken - Apr 29, 2015 at 12:43
First of all, I DID watch the video :-)
Really interesting, so that's how someone could get stuck... they erase the walkable area under their feet!

Guga - Apr 30, 2015 at 01:32
This post comes at the right time! I just published my first, very small "adventure game" for Android (not gonna spam here, but I'm extremely proud :D ), but since I wanted to get started as soon as possible I just focused on the basic features, implementing new aspects of the engine anytime they became necessary. Long story short, I came up with a game where the character only moves on a line, and my engine only supports "walklines". Now I want to expand it to 2D, and this post will help me a lot.

I have a question, however. I use the feet of the character as the position reference, and if I have to scroll right, left or down it's easy: if the character is near the screen and there's still some background left in that direction, scroll. But when going up? It should be dependent on the height of the character, or the distance between the top of the background and the highest walking point... nothing impossible, but still, nothing as trivial as the horizontal scrolling.

How do you handle vertical scrolling in the rooms?

badde - Apr 30, 2015 at 17:06
Thanks for enjoy - first time spirit of the game ; - ) Can´t wait any more...