Pathfinding in a 2D platformer

I am making a game.

I’m not ready to talk about what it’s going to be like or what my aims for it are. It’s still in the very early stages of development and I may never finish it and be one of those people who talks about their ambitious project that they never complete.

But! In what little I’ve done so far I’ve had to find the solution to a problem that I don’t think anyone else has ever bothered to tackle, and there’s probably someone somewhere who will find that interesting.

Alright, without getting into too much detail, three facts about my game are completely set in stone:

  1. It will feature base construction as a core mechanic.
  2. It will be a platformer.
  3. There will be NPCs that you control indirectly (think of the dwarfs in Dwarf Fortress)

Points one and three were decided before I even began thinking about implementation details since they are tied to the kind of game I want to make (more on that if I ever actually get to it) but point two arose for a couple of other reasons.

The first is that I want the player to have an at-a-glance overview of their set up (buildings, passageways, machines, pipes etc) to make it easy to see and modify. This pretty much immediately eliminates any sort of three-dimensional game. Technically my complete lack of 3-D programming knowledge eliminated that before we even began but at least now I have a design justification as well. Anyone who’s tried to build something complicated in Minecraft will know how frustrating it is to not be able to see the other side of things. I think adding this much friction to what should be elementary tasks would probably be a bad thing.

The other obvious choice is a top-down view as in Dwarf Fortress, SpaceChem, and any number of tower defense games. The problem with this is that representing elevation becomes very tedious and compromises my goal of making the game world easily digestible.

The second concern is that I also want to have a player avatar character, with attendant abilities and attributes that runs around doing things other than sitting in a chair and watching your base go. As soon as you have the ability for the player to do something then you probably want to do it in the most satisfying way possible and I have never liked the way that top-down game characters feel. Even really well done top top-down games like Bastion or Hotline Miami still have interface and presentation problems that I don’t like.

In brief: A normal top-down camera looks dumb because you’re just seeing the top of people’s heads. An isometric camera sucks because input directions do not map directly to screen directions. In a top-down game you will inevitably get caught on the environment and some point which is super annoying.

(Yes, that last problem is solvable with good enough movement physics but if it happens even one time in a hundred then it wrecks the feel of the game. Systems where such things are impossible are preferable.)

Also while I was coming up with this I had just been playing a shit ton of Shovel Knight and fell in love with the way it felt to play.

Alright, nearly 500 words in and I have yet to define the problem so here it is: how do you get an NPC from point A to point B in a platformer?

It’s a deceptively simple problem, so simple that the first stupid thing I tried almost worked:

Game Maker's built in pathfinding makes a path that a stupid NPC can follow, but only over favorable terrain.

Yeah, that seems good enough.

Game Maker has a bunch of built-in pathfinding functions that are designed to work with a top-down two-dimensional environment (obstructions are marked in red on the above screenshot and free areas are blue. The yellow circles indicate the found path) I instructed my little ghost there on the left to jump constantly and hold the up button so it could climb ladders and it actually managed to navigate the level using the built-in pathfinding functions. It looked really stupid but it did manage to get there. Surely all I had to do was massage the way Game Maker generated paths a bit and I would have a workable system?

Yeah, not even close.

The problem is gravity. The example above only kind of works because there are not any large uncomfortable gaps in the level, if there were the ghost would fall into them immediately because the algorithm doesn’t understand that the ghost is constantly moving downwards against its will.

So clearly the built-in algorithm was no good, but it was built on the A* algorithm (which is fairly simple but badly-explained pretty much everywhere, especially Wikipedia) right? Surely I could just write my own version of A* which could take into account this restriction?

Those of you not familiar with A*, here is the incredibly simplified version:

You have a grid. Some of the squares on the grid are passable, the rest are impassable. Sort of. Each square knows which of its neighbouring squares an occupying entity is allowed to move to. So a completely impassable square would be a square with no links to its neighbours, but you can also have a square which could be moved out of to the right but not to the left (representing a cliff or something in an RTS)

A* grid layout showing connections between squares

All the white squares cannot be escaped from, they would be deep pits or something if this were a 2D map. Of the three squares that have outgoing links we could call them (moving left to right) 1. A staircase. 2. A tower from which you can jump in any direction. 3. A pit, adjoining two deeper pits.

You also have a starting square and a goal square, and then you just do the following over and over until you reach the goal or run out of squares:

1.For all squares that have not yet been marked “closed”, find the best one (best in this context is defined as a combination of “being close to the goal” and “having the shortest path back to the starting square”)

2.Is this square the goal? If yes, victory. If no, mark it as “closed” and then take all of the squares it connects to (which are not already pointing to another square) and have them point to this square.

Go back to step one and repeat until we find the goal. When we find the goal, we just follow the trail of squares pointing at each other to find the path back to the beginning, and that’s it.

Confused? Me too, and I wrote a working implementation of it. It’s a little clearer by video.

I left out a bunch of stuff but the basic gist is that this: you generate a graph of the environment before you run the algorithm which dictates which moves are valid in your attempts to find the goal. This works only as long as the list of valid moves for a given square does not change, which is not true in a platformer.

For example, as long as a character is standing on a platform they can freely move horizontally but as soon as they are airborne they can only move into squares that are adjacent and below them. You couldn’t move six squares horizontally without moving a bunch more vertically (i.e. falling) so squares that appear to be reachable under normal circumstances now aren’t. Let’s have a look at that first screenshot again.

Game Maker's built in pathfinding makes a path that a stupid NPC can follow, but only over favorable terrain.

Not seeming that good any more

In this completely naive A* implementation, that algorithm assumes it can move an infinite horizontal distance, look at the path along the bottom half of the room.

Even worse, it assumes infinite vertical movement (look at the first vertical segment, that’s about three times higher than a character can actually jump).

It gets even worse when you consider that which squares you can reach are dependent not only on the current square but upon your speed and direction carried over from previous squares. In short, this would require the graph of connections between squares to be recalculated many, many times based on a system of rules far more complicated than the basic A* implementation.

Now, I am by no means a good programmer, if I put in my absolute best work I might be able to aspire to mediocrity. What I am is extremely lazy and pretty good at spotting when something is not going to worth it. This whole approach reeked of wasted effort.

There had to be an easy way to go about this, so I went to see how other people had solved this problem.

Let’s start at the beginning.

Super Mario Bros

Sonic the Hedgehog.

Alright, Mario is a 2-D game. It has characters, they move around, someone must have at some point written rules on how to get from place to place. Unfortunately, Mario’s enemies are pretty dumb and never really have any objective that is not on the current screen.

Pictured: Dumb goombas falling off a ledge.

Pictured: Dumb goombas falling off a ledge.

They are rules governing their movement (they are affected by gravity and can move left or right) but generally all they do is move in a predetermined direction until they fall into a pit or are killed by Mario. Bouncing off a wall is the most exciting thing these things will ever need to do.

Pictured: dumb koopas bouncing off a wall.

Pictured: dumb koopas bouncing off a wall.

Significantly, with the exception of the parakoopas and airborne fish, enemies have no ability to gain height (something my NPCs will frequently need to do).

There are still lessons we can learn here, for example along a platform (requiring no jumps to neighbouring platforms) is pretty straightforward. If my little pink ghost needed to grab something that was already on the same platform it wouldn’t even need to calculate a path. It would just move left or right, so that’s some work saved.

The other fly in this ointment is that our environments are going to be completely mutable. Apart from blocks getting broken, nothing ever changes about a Super Mario level. Let’s look at how someone working with a similar game solved the issue:

Relevant section starts at around 1:55.

The developers of Terraria solve the problem by cheating. Terraria has a huge number of flying enemies that either don’t need to worry about intricate pathfinding because they can just fly around obstacles or (in the case of many of the bosses) they can just fly through terrain with no trouble.

There are some ground abound enemies, but they seem to obey the same “move forward and jump a lot” logic that my ghost currently does which is not super useful. Terraria enemies also only exist while the player is near them and never have anywhere far away that they need to get to, my NPC is by comparison may need to travel quite some way so this approach is pretty much a dead-end.

(The sequel, Starbound, is much the same.)

So I couldn’t find any examples of the game that had a character that moved like the ones I want. Maybe I could find someone else who has written about pathfinding in a platformer?

Nope!

About the closest I could find was this:

which is cool and all but requires a handcrafted navigation map.

RETROACTIVE INCREDULITY FROM PRESENT CHRIS:

When I was originally working on this (which was some time ago) I couldn’t find any resources on platformer pathfinding. The first page of google is now fucking full of them. It’s almost certain that the approach I eventually settled on is, to put it mildly, utter garbagepants compared to whatever the real programmers are doing. This is both irritating, as I’ve wasted a lot of effort, and awesome, as I can now probably rewrite my pathfinding to be much more effective. Or not, we’ll see. I’m going to finish out this series on how I got to where I am, then have a look at the alternatives.

BACK TO WASTED EFFORT

The most promising thing I was able discover was this video, which does seem to be trying to solve a similar problem to me. They have a character moving through a two-dimensional side scroller the needs to navigate hazards and get to the next platform. My excitement quickly bottomed out however when I got to the end of the video and discover they had never actually found a working implementation of that system. Also that video is like three years old now and the game never came out so maybe it wasn’t all that promising. But they did give me an idea, specifically that while the world of the game may to be divided into squares that isn’t necessarily the unit we need to care about for pathfinding. The way that A* is traditionally formulated, that is on graph paper, misled me into thinking about it is only being valid for grids – but it works for any system where you have a series of nodes with links between them. The problem we originally had was that we couldn’t express the game world in this way, but the developer of Boss didn’t see the world as a grid of squares, he saw it as a series of platforms.

Well, platforms and ladders.

Well, platforms and ladders.

This was actually extremely simple, if you’re curious. I just used GM’s built in 2-D pathfinding functions to make a grid representing the world with all of the sections that are floors and walls marked as impassable. Then I translated that information into screen co-ordinates in order to figure out where the platforms were. This approach also works for ladders or any other class of objects that you want to navigate around.

We’re halfway there! We figured out what the “squares” on our graph should be, all we have to do is figure out what connects to what.

Next time: how do I get to there from here?

Advertisements

About nooneiverse

I am on the interbuts, look at me go!
This entry was posted in game dev and tagged . Bookmark the permalink.

2 Responses to Pathfinding in a 2D platformer

  1. Sean says:

    ♫Whoa! We’re halfway there! WhoAh, Jumping on some squares!♫

  2. Pingback: Pathfinding in a 2D platformer – part 2 | TPK

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s