Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

View All     RSS
August 24, 2019
View All     Post     RSS
August 24, 2019
Press Releases
August 24, 2019
Games Press
View All     RSS

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

# The Hobbyist Coder #3 : 2D platformers pathfinding - part 1/2

by Yoann Pignole on 04/27/15 12:32:00 pm

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

# Introduction

When I was thinking about the enemies behavior of the game project I’m working on, I just typed in my design document “follow the player”. And these 3 words almost drove me crazy ! I had an idea about the difficulty of implementing a pathfinding system including jump, but I was really far from the complexity I ran into as a hobbyist coder.

But I finally succeeded and  I write this article to show you the way I did it and, maybe, have some feedbacks about my method.

My project is a tile-based game so all this method is based on “tiles”. I used Unity 3D, in C# language, but I’ll try to give “pseudo-code” examples to stay “generic”.

This article is also linked to the custom platformer controller I use. So, I encourage you to read my previous article about it here.

For the exercise, I’ll use this prototype tilemap :

# The navmesh or where and how to move inside the level ?

First thing I had to do was to create a “map” of the walkable points of the level with “link information” on each points (which points are reachable from this one and how ?).

Having worked as a level designer in the industry with different game engines, I use to work with this “map”, which is called a “navmesh” (abbreviation for “navigation mesh”). Basically, they are two methods to create this navmesh :

• construct it manually, placing the different points and making the links directly on the level collisions → more (all) work for the Level Designer
• generate it automatically from the level collisions → more (all) work for the coder work

In the case of a top-down view game with no jump, the first method can be a good option, the Level Designer just having to colorize walkable “squares” for example.

However, in my project, it would be very tricky and time-consuming for the designer to reference all the possible jump and fall links. Of course, it was possible to “limit” the links number but I didn’t want to have all my enemies taking obviously the same way : I think it breaks the “magic”.

For all these reasons, and because it was an exciting challenge for me, I decided to chose the second option : generate the navmesh automatically !

# Base classes

To compute my navmesh and “communicate” with it in the game loop, I first had to define all the tiles of my map.

So, I first created a new navPoint class, stocking 4 values:

• Tile coordinates (using a specific class implementing itself x and y coordinates and some methods) : to define the related tile
• A platform index : useful to define if two navpoints are a part of the same “platform”.
• A navpoint type : an enumeration with 5 possible values
• none →  a free navpoint
• platform → a platform navpoint (on the tile above a ground tile)
• leftEdge → the left navpoint of the platform
• rigthEdge → the right one
• solo → a only one navpoint platform
• Navlinks (see just below)

Next, I created a navlink class. The navlinks are always referenced in a navpoint(see above) and keeps informations about the other(s) navpoint(s) it can lead to :

• Destination coordinates : to find the destination navpoint
• Link score : we will see that later, in the second part of this article.
• Jump trajectory values : if relevant, the needed values to perform the jump (height, speed, acceleration, etc..). We’ll come back to this later.

# Navmesh generation

For this purpose, I made a specific class in function which generate it inside the editor.

This solution impose a “static navmesh” but the computation is quite slow and can’t be performed ingame. So it dismiss all possibility of evolutive/moving collisions for the pathfinding (but I’ll talk about that later in the conclusion).

Let’s see piece by piece how it works…

## Parameters

The generator function takes only two parameters :

• The tilemap the navmesh will be based on
• The “jumping” AI from which the navmesh is generated

I need a specific navmesh for each kind of AI as they could have specific jump skills and different collider sizes.

These jumping AI contain 4 important move constants:

• run acceleration
• run max speed
• jump base speed
• jump max height

## Initialization

The first step is to create a 2 dimensional navpoints array, one for each map tile. By default, the navpoint are none types, which means there are not use to navigate.

## Define “walkable” navpoints

The process is quite simple and start by parsing all the tiles row by row. If a platform is not started, for a free tile with a collision tile juste below, add a leftEdge navpoint. Then, check if the platform ends on the same navpoint, if it does switch the navpoint to a solo type, if it doesn’t continue to the next navpoint : if the platform continues(lower right tile is a collision and right tile is free), add a platform navpoint, if it doesn’t, add a rightEdge navpoint and end the actual platform.

Let’s write this in pseudo-code :

actualPlatformIndex = 0
platformStarted =  false

FOR EACH tile row

platformStarted = false

FOR EACH tile in row

IF NOT platformStarted

IF target tile is free AND lower one is

add a leftEdge navpoint related to target tile
navpoint platform index = actualPlatformIndex
platformStarted =  true
actualPlatformIndex = actualPlatformIndex  + 1

ENDIF
ENDIF

IF platformStarted

IF lower right tile is a collision AND right tile is not AND navpoint type is not leftEdge

add a platform navpoint related to target tile
navpoint platform index = actualPlatformIndex

ENDIF

IF  lower right tile is free OR right tile is a collision

IF navpoint is a leftEdge

navpoint type = solo

ELSE

navpoint type = rightEdge

ENDIF

platformStarted  = false

ENDIF
ENDIF
ENDFOR
ENDFOR


Now all the “walkable” navpoints are defined :

We can now move to the generation of the links between these navpoints.

## Run links

There are the easy ones. The pseudo-code should be clear enough :

FOR EACH navpoints

IF target navpoint is not a none type AND is not at the extreme right

IF the next right navpoint type is not none

add a new floor link from target navpoint to next right navpoint

ENDIF

ENDIF
ENDFOR

Are you still following ? OK, let’s talk about a little bit more complicated ones : the fall links.

## Fall links

To simplify the fall links computation, I chose to consider only the “straight” vertical falls from a platform edge, and not the “diagonal” ones (with an initial horizontal speed).

The idea here is, for each edge navpoints, check the next column (left one for leftEdge type, right one for rightEdge type and both for solo type), going down from the edge height, until reaching a walkable navpoint (any not “none” type).

Here is the pseudo-code :

FOR EACH navpoints

IF target navpoint type is leftEge OR righEdge OR solo

CASE navpoint type OF

rightEdge :

a = 1

b = 1

leftEdge :

a = 0

b = 0

solo :

a = 0

b = 1

ENDCASE

FOR i from a to b

IF i = 0

sideTile = next left tile

ELSE

sideTile = next right tile

ENDIF

IF sideTile not a collision

targetRow = sideTile row - 1

WHILE targetRow > 0

navPointToCheck = navpoint at sideTile column and targetRow row

IF navPointToCheck type is not none

add a new fall link from target navpoint to navPointToCheck

BREAK WHILE LOOP

ENDIF

targetRow = targetRow - 1

ENDWHILE

ENDIF

ENDFOR
ENDIF
ENDFOR

OK, done for run and fall links :

Let’s talk about jump links now, the essence of a platformer pathfinding !

## Jump links

### Define a jump trajectory

A jumpTrajectory is  a class containing 3 variables:

• jump height : as it’s used to compute my jumps vertical speed impulsion
• jump speed : the horizontal speed to reach (max speed) while jumping
• points array : it’s an array of the discrete trajectory points coordinates

The constructor (for non-coders, a constructor is a method executed when a class is created. Better explanations here if you want.)  of this class takes a start point value, the first 2 values mentioned above and 2 of the AI move constants to compute the trajectory points array :

jumpTrajectory(start point, jump height, jump speed, AI base speed, AI acceleration)

The length of the trajectory and the interval between points depends on 2 other constants : jump duration and time between point. Bigger is the first and smaller is the second and more time it will take to compute a trajectory, so it’s a balance between needed complexity and performance (this being computed in the editor, it’s more a designer’s work comfort).

I won’t explain in detail (pseudo-code) the computation itself because I think it’s not the purpose here.

### Compute all possible jump trajectories from navpoints

Then, I chose to compute a set of possible jumps : the idea is to compute, for each navpoint, a series of jump trajectories with different heights and horizontal speeds, to the right and to the left.

I use 2 constants, height divisions and speed divisions. These constants will define respectively the divisions of the “jumping” AI jump max height and run max speed properties which will be used to compute possible jumps. Again, more divisions means more complexity but more computation time.

Here the pseudo-code to generate the list of all the possible jumps :

jumpTrajectoriesToValidate = new list of jump trajectories lists

FOR EACH navpoints

IF target navpoint is not a none type

navpointTrajectories = new list of jump trajectories

FOR i from 1 to jump height divisions

jumpHeight = Ai jump height * (i / jump height divisions)

FOR j from 1 to jump speed divisions

jumpSpeed = AI max speed * (j / jump speed divisions)

rightTrajectory = new jumpTrajectory

(start point, jumpHeight, jumpSpeed, AI base speed, AI acceleration)

leftTrajectory = new jumpTrajectory

(start point, jumpHeight, jumpSpeed, - AI base speed, - AI acceleration)

add rightTrajectory to jumpTrajectories

add leftTrajectories to jumpTrajectories

ENDFOR

ENDFOR

add navpointTrajectories to jumpTrajectoriesToValidate

ENDIF
ENDFOR

### Discard non valid jump trajectories

Last step to finish the navmesh generation is to only keep valid jump trajectories.

For this purpose, for each trajectory, I test successively all its points from start to end. The first test being to know if the point reaches a valid destination platform, that’s to say :

• the point is above a ground (not none type navpoint)
• the trajectory is in its falling phase
• the points is enough close to the ground (using a distanceMax constant)
• there is enough place on the ground for the AI collider (using a specific custom function isEnoughSpace(collider, position in world) returning a boolean)
• the point is above a different platform than the start point
• the point is above a platform not already reached from the start point

If the point matches all these requirements, there is a valid destination, so the jump trajectory is valid and a jump link can be added between the two navpoints.

If a point doesn’t matches all these requirements, I just check if there’s enough place for the AI collider. If yes, the trajectory is still ok (not blocked) and I move on to the next trajectory point. If no, I break the process and no jump link will be added.

Here all the trajectory validation process in pseudo-code :

FOR EACH navpointTrajectories in jumpTrajectoriesToValidate

platformsReached = new list of platform index

startNavpoint = related navpoint

FOR EACH jumpTrajectory in navpointTrajectories

FOR EACH point in jumpTrajectory

pointNavpoint = navpoint related to the point position

IF pointNavpoint different from startNavpoint

IF relatedNavpoint different from none type

AND point y coordinates < previous point y coordinates

AND point y coordinates - relatedNavpoint y coordinates <= distanceMax

AND isEnoughtSpace(AI collider, relatedNavpoint)

AND startNavpoint platform index different from relatedNavpoint platform index

AND pointNavpoint platform index not in platformsReached

add a new jump link from startNavpoint to pointNavpoint

reference the 4 jumpTrajectory values for this jump link

(jump height, base speed, acceleration, max speed)

add pointNavpoint platform index to platformsReached

ELSE IF isEnoughtSpace(AI collider, relatedNavpoint) is false

OR point is the last one of the trajectory

BREAK FOR LOOP

ENDIF

ENDIF

ENDFOR

ENDFOR
ENDFOR

And that’s it, the navmesh is now ready, with all the navpoints and the links between them :

### Related Jobs

Deep Silver Volition — Champaign, Illinois, United States
[08.23.19]

Senior Engine Programmer
HB Studios — Lunenburg/Halifax, Nova Scotia, Canada
[08.23.19]

Experienced Software Engineer
Square Enix Co., Ltd. — Tokyo, Japan
[08.23.19]

Experienced Game Developer
iGotcha Studios — Stockholm, Sweden
[08.22.19]

(Senior) Unity Developer