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 :

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 :

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:

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 :

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 :

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:

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.

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:

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 :

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 :

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