Implementing the Medusa Gang - Part 1

Medusas are a staple of the Eggerland and Adventures of Lolo series, waiting stoically for Lolo to stroll into their gaze. Our mission is simple: when Lolo walks into the same horizontal or vertical as a Medusa, Lolo instantly turns to stone, a jarring sound jump-scares the player, and Lolo gets assailed by a wave of snakes. Medusas can catch Lolo through trees and over water but not through rocks or Emerald Frames, so the player can use rocks and Emerald Frames for cover.

Simple, right? Why blog about this? Not so fast, because collision and checking line-of-sight in games is way more complicated than it appears, and like many computational problems the devil is in the details. Join me and we’ll implement this jawn together.

In Eggerland and Adventures of Lolo, every entity is on a grid. Many older games are on a grid, and even today’s most complicated games use grids to simplify collision detection and locational comparisons. Here is what Lolo’s world looks like with a grid overlay.

The game world is made of an 8x8 pixel grid, and the tiles that make up characters and obstacles are 16x16 tiles

One naive method of calculating Medusa’s line of sight is to compare Lolo’s position coordinates with Medusa’s coordinates. If Lolo’s x coordinate is equal to Medusa’s x coordinate or if his y coordinate is equal to Medusa’s y coordinate, then Lolo is definitely within Medusa’s row or column on the grid. This isn’t the whole calculation but it still might be useful because it is quick and easy, and if it returns false i.e. no coordinates are equal then we shouldn’t waste time and computational power doing more precise checks.

The yellow area represents Medusa’s “line of sight”. If Lolo wanders entirely within that yellow area, Lolo is petrified and he gets the snakes. If Lolo goes in that yellow area, he’s gonna have a bad time.

Okay, so let’s say we did the naive calculation and Lolo is within “line of sight”. What if Lolo is behind cover? Well, at first blush, we might check every other entity and validate none of them are between Medusa and Lolo. The size of the grid complicates this check because entities are larger than a single square of the walkable grid. An Emerald Frame can provide half-cover, which is still enough to block Medusa’s line of sight in-game.

Depiction of Medusa’s line of sight being checked in yellow. The emerald frame is within Medusa’s check and so provides Lolo with sweet sweet cover.

Okay, so now we have to check for obstacles that are on Medusa’s line of sight, but also obstacles that are one step above or below that line. More than that, we now have to care which direction the check is happening in. For example, if Lolo is on Medusa’s left, then we only want to consider every Emerald Frame to Medusa’s left and to Lolo’s right i.e. between them. But if Lolo is to the right of Medusa, then we care about Emerald Frames to Lolo’s left and Medusa’s right. Yike.

It’s tempting to write conditional logic that checks if Lolo is either above, below, to the left, or to the right. I like to avoid branching code so I suggest a generic solution instead; I built a helper method to encapsulate the branching logic. It takes two points and produces the most “significant” Direction, making Medusa’s logic cleaner. I’m sure even this branching logic can be avoided, but it’s good enough for now

/** * Gets the most prominent Direction between two Points. Most prominent means the direction of greatest distance * between the two points, where diagonal points compare x coordinates and y coordinates to determine if the points * are further from each other horizontally or vertically. If the points are more distant on the vertical than on * the horizontal, then that vertical direction is chosen as the most "prominent" direction. If the distance between * the x and y coordinates is equal, then the horizontal directions are considered more "prominent". If the from and * to points are equal, then a direction of NONE is returned. * * @param fromPoint The point to begin at, for purposes of determining direction * @param toPoint The point to end at, for purposes of determining direction * @return The direction that best represents the greatest distance from fromPoint to toPoint */ public static Direction getDominantDirectionFromPointToPoint(Point fromPoint, Point toPoint) {    if (fromPoint.x == toPoint.x && fromPoint.y == toPoint.y) {        return Direction.NONE;    }    int xDiff = toPoint.x - fromPoint.x;    int yDiff = toPoint.y - fromPoint.y;    if (xDiff >= 0) {        if (Math.abs(xDiff) >= Math.abs(yDiff))            return Direction.RIGHT;        else if (yDiff >= 0)            return Direction.UP;        else            return Direction.DOWN;    } else {        if (Math.abs(xDiff) >= Math.abs(yDiff))            return Direction.LEFT;        else if (yDiff >= 0)            return Direction.UP;        else            return Direction.DOWN;    } }

Yep, NONE is a valid direction. This assertion is already obvious to anyone who has no idea what they’re doing with their life.

There’s still the matter of actually using the Direction to math out whether an entity is in position to count as cover for Lolo. You can see above that Direction is an enum with the values UP, DOWN, LEFT, RIGHT, and NONE. I gave the Direction enum a method that takes a point of origin and a distance, returning a Rectangle object protruding in that Direction. With this, we can ask the returned Direction to produce a Rectangle representing the space between Lolo and Medusa, and we can do it without any additional branching logic.

Do you remember this image, with the Rectangle representing the space between Medusa and Lolo? You should, it was only, like, three paragraphs ago.

Awesome, we have the line of sight Rectangle, so let’s iterate over every entity in the game world and determine which entities intersect it. Every entity also represents a Rectangle made of their bottom-left point and their width and height, so we can calculate if there’s an intersection between the line of sight Rectangle and each entity’s Rectangle. Java is an object-oriented language, so a Rectangle object can have a method to take another Rectangle and return true if they intersect. Yes, I did give it that method, it looks like this:

public class Rectangle {     /* These numbers represent the cartesian coordinates for the Rectangle      * such that the “left” is the smallest x coordinate, the “right” is the      * largest x coordinate, the “bottom” is the smallest y, and the “top”      * is the largest y.      */     private int top;     private int bottom;     private int left;     private int right;     /**Determines whether the given Rectangle intersects this one.      * Intersection means that the Rectangles are not just touching edges      * but occupy shared space.      */     public boolean intersectsOtherRectangle(Rectangle other) {         return (this.top > other.bottom) &&                (this.bottom < other.top) &&                (this.left < other.right) &&                (this.right > other.left);     } }

I have a degree with honors in both Computer Science and Mathematics, with focuses on Higher Geometry, Distributed Computation, and Special Relativity. And still my most effective strategy for braining this out was sitting on the floor in my jammies writing “top”, “bottom”, “left”, and “right” in Tickle Me Pink crayon on two pieces of construction paper and overlapping them a bunch.

By the way, this is Java code. I’ll get into why I chose Java for game programming in another post. For now, let’s just take it for what it is and use Java’s strengths, specifically the Stream API, to filter out any entities that don’t have the “provides cover” attribute. Then let’s use this intersectsOtherRectangle() method to further filter out entities that don’t intersect the line of sight. If we are left with any entities, then we know they are cover entities that block Medusa’s line of sight, so Medusa can’t shoot a wave of snakes.

There’s one more thing that Medusa has been doing in all Eggerland games and I want to implement it to get that authentic Eggerland feel. Whenever Lolo steps even partially into Medusa’s line of sight, Medusa will freak out, like this:

This is usually the most exciting part of Medusa’s day

Since we already have this fancy Rectangle class, the Medusa freak-out implementation is actually super easy. Every Medusa has that “line of sight” we keep talking about; let’s define that line of sight with Rectangles. Our Medusa code can create and store line of sight Rectangles at game start, and whenever Lolo intersects that Rectangle, we can draw Medusa with the “awake” sprite, otherwise we draw Medusa with the “asleep” sprite. Medusa’s line of sight extends infinitely, but these Rectangles don’t have to be infinite, they just need to be longer than the game world and they will effectively be infinite as far as the game world is concerned. Once we combine that with our existing Medusa shooting mechanics, we have a fully functioning Medusa enemy! We did it!

Almost. There’s one special case we haven’t accounted for, can you see it? If not, then stay patient, I’m pretty sure it will be more clear when we talk about this guy:

Who is this mystery Medusa? Looks like a “Donald” to me. Definitely got a Donald face.

But that is a post for another time. Stay tuned!