Pathfinding in a 2D platformer – part 2

It’s been quite a while since the first one of these so if you need a refresher: here is the first article.

TL;DR: Pathfinding for platformers is hard. One solution is to simplify the game world into a series of platforms and then attempt to find connections between them. Which is what we’re going to do.

A lot of computer programming consists of finding ways to ask complicated questions in such a way that the computer can:

-understand you.

-provide a useful answer.

Here the question is deceptively simple: is it possible to jump from one of these platforms to the other?

I don’t know.

Without knowing anything about the game this is hard to answer, but if you just eyeball it you can see that the gap doesn’t look all that wide compared to the width of the player character and there are no obvious obstructions. So yes, you can probably jump between these platforms.

Computers lack eyeballs and therefore cannot eyeball things, so are going to need a far more stringent definition. This leads naturally to the question: under what conditions can we guarantee that it is possible to jump from one platform to another?

Here is one possible answer:

Red boxes indicate successive player positions; objects in video games always move in discrete steps like this.

the definition I went with was: it is possible to jump between two platforms if there exists between them a trajectory (corresponding to a character’s jump arc) which if you slid the character’s collision box along it would not cause that box to touch any other terrain.

IMPORTANT NOTE

The above definition is correct and accurate but it is by no means the only or best way of testing for a possible jump. Most of the problems that I have in the later part of this article are due to this overly strict definition.

So how do we test for jumps using this definition? Well, the simplest way is just to have an AI character attempts to perform a jump and see whether they make it or not. My game was set up in such a way that all of the per-frame actions for an NPC were in a single script so I could simply call that script multiple times in a single frame in order to simulate jumps much faster than they could be performed in real time.

I’m going to jump ahead a little bit and show you a video of my final (sort-of) pathfinding system in action:

Notice that two second delay in between the second and third levels? That’s the game generating the pathfinding graph for the new level. The game is supposed to be running at 30 frames per second and that two second pause is all in the first frame of the new room, which means the graph builder is taking about 60 times longer to do its job than would be acceptable in a running game (the shape of a level can change at any time and the graph will be need to rebuild frequently and on-the-fly). Actually it is even worse than that because we have lots of other stuff that needs to be done each frame as well. It’s more like several hundred times too slow.

The system works, but is abominably slow. Why? For two basic reasons:

-I’m running too many jump tests.

-each jump test is taking too long.

To understand why, I’ll give you a brief rundown of how the graph builder works.

1. Choose a platform to start from.

2. From the remaining platforms, choose a target to jump to.

3. Simulate a series of jumps between the initial and target platforms, changing the starting position on the initial platform each time a jump fails.

4. Repeat until a successful jump is made or all starting positions are exhausted.

5. Repeat steps 2 to 4 until all target platforms are exhausted.

6. Go back to step one and repeat until all initial platforms are exhausted.

In case it isn’t immediately obvious why this is bad, let’s consider this room again:

I’m a popular room!

This room has 40 platforms in it, by my count, which vary in number of potential starting positions (width in grid squares, I’m not crazy enough to try varying the start by a single pixel each time) from 1 to 12 or so. That is, at minimum, 40×40 = 1600 simulated jumps. That’s if every single platform was one block wide, it gets a lot worse as the platforms get wider. That’s… just awful.

I built a system whose time to compute increases geometrically with both the number and size of the elements involved. It’s actually even worse than it appears, because each platform is made up of multiple block objects and the game’s movement physics work by constantly running collision checks against all objects in the room, which gets slower the more there are of them. That’s three interrelated systems of geometric failure.

I come out of this looking pretty incompetent, but I like to raise a few points in my defence. Initially, I just wanted to get something working and didn’t care how inefficient it was. My code is full of comments saying things like “just do it this way, worry about performance later”, so on some level I wasn’t expecting this to be amazing. This also took me a depressingly long time to implement and as time ground on and the irritating problems mounted up I lost sight of the overall goal. My biggest sin, however, was doing all my testing in an extremely tiny room. Remember this one?

Those red lines indicate successful links. Yes there are rather a lot of them, because the system was broken when I took this. Why do I never screenshot things when they aren’t sucking?

Yeah, three platforms. That’s what I did all my testing in. Terrible. Here is a picture of a debug mode I wrote to show how all the jump tests were going.

Easily the best thing to come out of this project so far.

For all its flaws, the system does work. It successfully generates graphs indicating links between platforms and AI characters can navigate using the A* function I wrote. Heck, if I wasn’t set on a game with mutable terrain this would probably be good enough. Tragically I am stuck on a game with mutable terrain so let’s consider ways that this disaster can be mitigated. Related to my two points above, this can be done by either reducing the number of tests run or increasing the efficiency of each test.

Reducing the number of tests run is actually pretty simple, we just need a list of conditions under which it is obviously impossible to jump between two platforms, as shown in the below image:

Most of these platforms are inaccessible, also my MS-Paint skills are incredible.

Here is that list of conditions directly from my code:

/*===============================

EXHAUSTIVE LIST OF FAILURE STATES

=================================

Okay, here’s the deal. We don’t want to run tests. Tests are expensive, and the more of them that we have to run the bigger the pain in my ass.

SO we want to perform assloads of logic (comparatively cheap) to FAIL tests instantly without having to simulate them.

Here are all the things that should AUTOMATICALLY prohibit a link

1. The target is the same as the current surface. DONE

2. The target is higher than the maximum jump height. DONE

3. The target is further away that the maximum jump distance. DONE

4. The target’s edges have the same x values as the current surface. DONE

5. The target is higher than us, but another surface is in the way.

6. The target is off to the side, but there is a wall between us and them.

7. The target is lower than us, but there are other surfaces in the way

8. If the target is higher than us, in the same spot but WIDER. DONE

9.if the target is lower than us, in the same spot but NARROWER. DONE*/

Spoiler: the ones without “DONE” next to them are the ones I didn’t get round to implementing before I gave up. Yes, I gave up. I ended up writing tonnes of helper functions to do things like finding vertical walls between two platforms and identify shafts of empty space that I could use to terminate jump tests early (thereby simulating fewer frames). It definitely got faster over time but the code also got uglier and more cluttered till working on it became a pain. Then my ongoing battle with RSI left me unable to type for a few months and I left the project to moulder.

With the benefit of hindsight (and some advice from an actual programmer) I can see that almost all of my problems arose from two things (this article is full of lists of two items, I don’t know why):

-my initial, overly strict definition of a successful jump and

-my decision to use Game Maker’s built-in collision functions (and objects) for movement physics.

For the first point: you don’t actually need to run a full collision check for each point along the jump arc. You can just sample a few points along it and see if any of them are inside a wall, if none of them are than the jump is probably legal. If you are madly ambitious, you could update the navigation graph during gameplay when a character tries and fails a jump to indicate that the link was a false positive. Either way you end up wasting way less time building the damn thing.

The second point: objects inside Game Maker come with an awful lot of baggage. They have a lot of default variables that you can’t remove and placing them generally involves using the GM room editor, which is one of the worst tools made by a human. So much of this first attempt was me bodging things together with no regard for long-term stability until it fell over. The place_meeting() function, which I was using for all collision checks, is particularly notorious for being an inefficient cow of a thing but at the time it basically worked and I didn’t see any easier alternatives.

Next time: easier alternatives.

Just kidding, let’s do it now!

So, to recap: My pathfinding code was slow primarily because it used inefficient collision detection and used it way too frequently. Rewriting the pathfinding code to not use place_meeting() and instead just use the sampling approach I’ve outlined above wouldn’t be particularly difficult, but I think changing the game’s underlying collision logic might be even more rewarding.

There are several areas we can improve on just by replacing this collision code.

The most obvious is that the pathfinding will get immensely faster (I hope!) Without me having to rewrite any of its awful, tangled code. I’m probably going to have to rewrite this at some point anyway, but staying motivated to finish this project is at least as important as doing things in the right order and if I sit down to rewrite the system now I probably won’t finish it.

Secondly, as mentioned above, GM’s room editor is almost physically painful to use. It is no coincidence that one of the first things most people working in GM do is design their own level editor just so they can get away from the damn thing. One thing it is particularly terrible about is dealing with objects that occupy the same coordinates but on different depths. Short of viewing the room’s instance list I don’t think there is any way to see things that are behind other things without moving the things in front out of the way, which is absolute lunacy if you’re intending to have multiple layers of level data in your game (which I certainly am, not that I’ve mentioned it up till now).

Thirdly, pathfinding isn’t the only system that will be using these collision checks. The game world should also be full of NPCs, both friendly and hostile, all of which are going to need to be running collision checks for their movement code. More efficient collisions will enable us to have any many more of these than would otherwise be possible.

So, having established that we need better collision, what do we do to get it?

Way back in part one (back in time, I mean. Not in article count) I mentioned I was using Game Maker’s built-in pathfinding functions to generate grid structures that held information about which parts of the level were walls and which weren’t. This is because it’s difficult to ask questions about the state of an area of space if you’re using GM objects. You can basically either run a collision function or loop through each and every “wall” object and ask it whether it’s occupying a given point – both of which scale poorly as the number of wall objects increases. This is what makes collision checks so expensive.

The aforementioned real programmer (hi Zeb!) Pointed me to this tutorial by the makers of N+

Which is a super nifty way of getting cheap, precise collision detection provided your world adheres to a few conditions. Aaaand I going to be ignoring most of it since my world is only made up of blocks, not various kinds of slope. Actually I should probably add ramps, those would be cool. Anyway.

Instead of building a world out of GM objects and then creating a grid structure to tell me things about where those objects are, I just store the level data in an array and refer to that directly.

Ta-dah!

That is a 16 x 16 grid, which would work out to 256 objects were they all being created manually in the room editor. Instead I am using 16 grid objects (represented by the yellow outlines in the screenshot) each of which holds the data for a 4×4 area and filling it in using code.

Walking on grids!

And here is a player running around on it. Well, standing anyway.

The small grids are just for testing purposes, in practice they would be much larger (178 x 178 is the largest square grid you can have before you overrun GM’s array index limit of 32,000. Why does Game Maker have an array index limit of 32,000? Magic!).

So why is this faster than the old way? Because objects in a game have no inherent sense of where they are in relation to each other. Although in the screenshot above you can see long rows of grey bricks next to each other, from the perspective of the game they are just objects in memory (or they would be if they weren’t using my nifty new system). The concept of adjacency doesn’t exist unless you expressly program it in somehow. So in order to know if a player object is colliding with a wall object we basically have to go through each and every wall object and check its position and size relative to the player. As previously explained this scales very badly as the number of wall objects increases.

The blocks in my new level on the other hand are stored in an array, and have a fixed relationship to each other which means that for a given set of XY coordinates you can find the index of the block that contains them with a simple look up function:

/*takes a point, returns its INDEX within its grid
*/
pointx = argument0;
pointy = argument1;
var GRID = point_grid(pointx,pointy);

var rel_x = abs(GRID.x – pointx);
var rel_grid_x = floor((rel_x/32) );
var rel_y = abs(GRID.y – pointy);
var rel_grid_y = floor((rel_y/32) );
var INDEX = rel_grid_x + (rel_grid_y * GRID.grid_height);
if (INDEX >= 0)
{return INDEX;}

Suddenly the computational cost of finding out whether the character is touching the scenery or not no longer scales. The duration of the look up is the same regardless of how big the world is. It still scales for the number of grids, because you need to find out which grid you should be looking at, but it’s easy enough to store the grids themselves in another array and turn that into a second fixed cost look up.

Also, after about five minutes work I get the ability to delete blocks and place them from inside the game. That’s like 90% of the level editor right there.

As for layers, check this out:

Layers: impossible to illustrate in a still image. Note that this room is made from two identical, 16×16 grids.

It’s not super obvious but we are operating on a five layer system: brickwork, air ducts, interior decoration, walls/floors, ladders. Each layer can be rendered and manipulated separately, and I even made it so that you can switch movement collision from one layer to another. So if you enter the heating ducts you’ll be able to move through walls that you previously couldn’t pass:

I’m also intending to put in layers for water pipes, electrical wiring, pneumatic tubes – the system is extensible enough that I can basically add stuff in as I want and the same index restriction that limits my grids to 1 78 x 1 78 means I can have a grid 32,000 layers deep if I really want to. That would probably use a quite a bit of memory though.

The next course of action is to re-implement my pathfinding system and see if I actually get the huge speed gain I predicted. More on that next time.