2019 Global Game Jam: 2 Weeks Later

Exactly two weeks after submitting to the 2019 Global Game Jam, we presented the latest version of our game today at the Seattle Indies Show & Tell and Global Game Jam Showcase. Despite the snow that’s kept much of Seattle home this weekend, we still had a decent number of people able to stop by, and we’re very grateful to those that did! On display we had both Else Return Home and our previous game Good Night Rowan, for which we got both positive reception and good feedback on things we can focus on to improve. To that end, here are some of the things we’ve been working on over the past week, followed by what we have planned going forward:

LEVEL DESIGN

  • Update Home environment with new 3D models for fireplace, floor, and furniture
  • Update City environment with new 3D models for trees, fences, street signs, and various additional decorations
  • Add new landmarks in the City scene to assist with player navigation
  • Block off some more areas unintended for the player to reach
  • Replace colliders of some objects for more realistic rain drop collisions

SOUND DESIGN

  • Rebalance audio mixing, especially to make voice overs more audible
  • Sync up Door sound effects to better align with scene loading

PLAYER

  • Gradually reduce player speed when walking into park pond to give more realistic impression of wading into water
  • Prevent the player from walking all the way into the deep end of the water
  • Automatically show photo after bringing back an objective item to reiterate the game objectives and demonstrate progress
  • Fix bug to allow interaction with Dorg while holding an item

AI

  • Refactor AI of robot pet Dorg to operate on a Behavior Tree system to allow greater flexibility in adding and modifying behaviors
  • Make robot pet Dorg occasionally run ahead of player to make Dorg more dynamic and appear on screen more often
  • As the player collects more objective items, make Dorg run ahead further and more often to help the player feel increasingly more comfortable in the City and reinforce the feeling of the player gradually establishing their home
  • Prevent Dorg from running to “nearby” locations on the other side of a fence or unreachable areas that would produce either invalid or overly long paths
  • Make Dorg run around objective items but not avoid them while held by player (otherwise produces buggy behavior)

BACKEND

  • Refactor various chunks of code to enhance developers’ ease of use and facilitate new features and content
  • Add in editor visualizations to assist in debugging

Meanwhile, we’ve been building out content in the background on some in progress features that will be appearing in future builds:

IN PROGRESS

  • Add new ending cinematic including dynamic camera movements, animations, and particle effects
  • Build out a secondary collectable system for robot friend parts, offering player more to do in the City environment
  • Extend Dorg AI behaviors to call attention to objective items to help when player is nearby but has not noticed them for some time

2019 Global Game Jam: 7 Days Later

It’s now been one week since we submitted our game, Else Return Home, as an entry to the 2019 Global Game Jam. We were thrilled to be recognized for Best Use of Color out of nearly 40 teams at our local site in Seattle, and we’ve been very pleased with the attention it’s received so far. Already, the game is outperforming the first week of release of our previous most popular game! (Good Night Rowan)

Like many game jam games however, we knew it contained some bugs, and there were a handful of features we had in mind but did not have time to get to. We decided that in the first week following the jam, we’d focus most of all on bug squashing and improving overall usability. We’ve been making daily updates since the jam, and here are some of the things we tackled:

PLAYER

  • Reduce the chance of camera clipping
  • Sync up player spawning better with asynchronous scene loading
  • In case the player manages to reach an unintended area and falls off the map, spawn the player back at the starting location
  • Keep player from  moving or raising photo during intro sequence
  • Drain energy faster per unit distance while running (relative to walking)
  • Halt energy drain / gain while paused
  • Fix bug where player could not re-enter house empty handed after collecting first item
  • Gradually slow player movement to a halt while powering down
  • Drop held item on powering down

LEVEL DESIGN

  • Update some building models in City scene
  • Place some floating items flush with ground
  • Add colliders to buildings missing them
  • Block off areas unintended for the player to reach

UI / UX

  • Add text prompt telling player how to start game from title screen
  • Hide battery UI until after exiting title screen
  • Fix some HUD element positioning to handle different aspect ratios
  • Choreograph intro sequence better to sync up raising & lowering of photo with voice over lines
  • Add text prompt telling player how to show photo again
  • Render photo over rest of scene
  • Enhance power down glitch effect
  • Eliminate lingering frames between scene transitions
  • Add ability to Pause & Quit with an in game menu
  • Add end game text sequence with credits

AI

  • Prevent robot pet Dorg from walking through park fence
  • Have robot pet Dorg move around scene props (e.g. lamp posts, benches, debris piles, etc.)
  • Add interaction with Dorg, prompting voice over lines and barking responses

Now that we’ve squashed the majority of the existing bugs and enhanced the usability of the game, we’re turning next toward adding more content and features. This following week should include some significant updates as we prepare to exhibit the game at the Seattle Indies Show & Tell and Global Game Jam Showcase. If you happen to be in Seattle, we hope to see you there!

Finding Edges from the Vertices of a Convex Quadrilateral

While working on the AI player for a real-time strategy game, I came upon a rather specific problem and discovered a nifty solution. I had been considering using the data in Unity’s pathfinding NavMesh with the aim of extracting the edges from the sets of vertices that composed it. However, when looking in Scene View, I found that the NavMesh appeared to be made up of not only triangles but also other polygons with more sides. This posed a potential problem as well as an interesting geometric question: Given only the vertices of a convex quadrilateral, how do you determine which pairs of vertices form the edges? While I ultimately did not need it for my AI implementation, I thought I’d share the solution in the article below.

Convex Quadrilaterals in Unity's NavMesh
Some parts of Unity’s NavMesh display contain convex quadrilaterals like these.

How to Find the Edges of a Convex Quadrilateral Given the Vertices?

Let’s say you’re given four points as coordinates which define the corners of a quadrilateral. You also happen to know that this quadrilateral is convex (in the context of the NavMesh display, all polygons are convex). So how can you determine which pairs of points form the outer edges of this polygon? After all, some pairs could turn out to be the interior diagonals, so we need some method to choose the correct pairs.

If you were to choose four edges at random, you could get lucky and happen to choose all the outer edges of the quadrilateral. But with six edges to choose from and four chosen, there are 15 possible combinations of which only one is correct.

Edge Combinations
The pictured formula gives us the number of possible combinations of edges when chosen at random.

However, we can significantly reduce the problem space if we imagine that we choose four vertices in order. Furthermore, we’ll consider only the three consecutive edges between them, since the fourth can be easily inferred by connecting the last vertex to the first. When we do this, we find there are essentially three resulting scenarios: one interior diagonal occurs in the sequence, two diagonals occur, or none i.e. an ordering of vertices that correctly outlines the quadrilateral. These scenarios are illustrated here:

Three scenarios
Three general arrangements of three consecutive edges

We’re now one significant step closer to our solution having better defined the problem space. But how can we distinguish between these using only math? It’s easy enough to figure out using only our eyes, but we need a way to distinguish between these scenarios in code.

Consider the fact that we know the quadrilateral is convex. Consequently, we can deduce that following the outline of the quadrilateral will always result in the same turn direction from one edge to the next (i.e. clockwise or counter-clockwise). It turns out the cross product is perfect for calculating the turn direction between three points. Putting this calculation to use, we see that our target scenario of zero diagonals passes this turn direction test whereas the scenario with one diagonal does not — the angles change direction from the first half of the Z- or N-shape to the second half. Great! We’re nearly there.

But wait, using this turn direction test, our scenario with two diagonals would still pass: the angles ABC and BCD take the same turn direction (counter-clockwise in the illustration above). However, there is another feature of this case that is unlike the others: the two diagonals wind up intersecting each other. Coincidentally, we can again use the cross product to detect this intersection.

So we now have the two tests needed to determine which of the three scenarios an order of vertices results in, both of which happen to use the cross product. Depending on the scenario, we can then flip the order of the appropriate pair of vertices to get the correct sequence that outlines the quadrilateral. Our final algorithm thus looks like this:

Check the turn direction of ABC versus BCD
    If unequal flip C & D
    Else, check whether AB intersects CD
        If intersects, flip B & C
        Else, order is correct
After any flips, our edges are now AB, BC, CD, and DA

And that’s it! While perhaps a niche problem, the solution winds up being quite efficient and elegant if I do say so myself. I hope you find this helpful, either directly or indirectly, in your own geometric adventures!

In future posts, I’ll elaborate on other handy uses of the cross product, as well as describe in much detail how I wound up using the NavMesh data in my AI solution.