Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
January 22, 2018
arrowPress Releases






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   Expert Blogs   Featured Blogs

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

 

This is the first part of the article, centered on creating the “navmesh”, the matrix on which the AI will move. The move itself will be approach in the second part, coming soon !

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 :

tilemap_empty.PNG

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

These values are related to the custom platformer character controller I made previously (one again, you can reach the related article here). To make it short, the AI have a base speed at jump start (jump base speed) and accelerate (run acceleration), but with a maximum speed (run max speed) during a jump which can exceed a certain height (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.

platforms_process.png

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 :

tilemap_platforms.PNG

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).

fall_process.png

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 :

tilemap_groundFall.PNG

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).

jumpComplexity_process.png

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.

jumpDivisions.png

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 basespeed, 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

jumpDestination_process.png

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.

jumpValid_process.png

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 :

tilemap_jumps.PNG

Thanks to read me ! I hope you enjoyed this first part and I would be glad to read your comments on my navmesh generation solution (and maybe how to improve it) ! Soon the second and last part of this article, about how I did to move the AIs from a navpoint to another one and give them some “life”.


Related Jobs

Remedy Entertainment
Remedy Entertainment — Helsinki - Capital Area, Finland
[01.22.18]

Senior AI Programmer
Giant Enemy Crab
Giant Enemy Crab — Seattle, Washington, United States
[01.21.18]

Gameplay Engineer
Lucky Charm Games
Lucky Charm Games — Altadena, California, United States
[01.19.18]

Web Developer - Front End
Blackstorm
Blackstorm — Mountain View, California, United States
[01.19.18]

Studio Game Engineer





Loading Comments

loader image