Navigation using a Navigation Mesh

In this tutorial we will shorty touch on how to use a navigation mesh, how we create a level is part of a different tutorial. The result of this tutorial should look something like this:


We start with the usual initialisation:

#ifdef _WIN32
int WINAPI WinMain(HINSTANCE hInstance,
    HINSTANCE hPrevInstance,
    LPSTR cmdLine,
    int cmdShow)
    int argc = 0;
    char** argv = NULL;
int main(int argc, char** argv)

    DreadedPE::Window* window = DreadedPE::Window::createWindow(1024, 768, "", false);
    if (window == NULL)
        return 1;

Next we create the scene manager and add a camera. These are then used to create the camera renderer:

    DreadedPE::SceneManager* scene_manager = new DreadedPE::SceneManager();

    // Initialise the camera:
    DreadedPE::FreeMovingCamera* camera = new DreadedPE::FreeMovingCamera(*scene_manager, &scene_manager->getRoot(), glm::translate(glm::mat4(1.0f), glm::vec3(0.0f, 1.7f, 0.0f)), 90.0f, 1024, 768, 0.1f, 60.0f);
    new DreadedPE::CameraRenderer(*scene_manager, *camera);

    // Initialise the sky box to render.
    DreadedPE::MaterialLightProperty skybox_ambient(0.2f, 0.2f, 0.2f, 1.0f);
    DreadedPE::MaterialLightProperty skybox_diffuse(0.8f, 0.8f, 0.8f, 1.0f);
    DreadedPE::MaterialLightProperty skybox_specular(0.0f, 0.0f, 0.0f, 1.0f);
    DreadedPE::MaterialLightProperty skybox_emmisive(0.7f, 0.7f, 0.7f, 1.0f);

    std::shared_ptr<DreadedPE::Material> skybox_material(std::make_shared<DreadedPE::Material>(skybox_ambient, skybox_diffuse, skybox_specular, skybox_emmisive));
    DreadedPE::Texture* skybox_texture = DreadedPE::TargaTexture::loadTexture("data/textures/skybox/sp3left.tga", "data/textures/skybox/sp3right.tga", "data/textures/skybox/sp3top.tga", "data/textures/skybox/sp3bot.tga", "data/textures/skybox/sp3back.tga", "data/textures/skybox/sp3front.tga");

    std::shared_ptr<DreadedPE::SkyBox> inverted_cube(std::make_shared<DreadedPE::SkyBox>(5.0f));
    new DreadedPE::SkyBoxLeaf(*camera, inverted_cube, DreadedPE::SkyBoxShader::getShader(), skybox_material);

Next we load the level that has been created before and saved using our PLF format. How a level can be created is part of another tutorial.

    // Initialise the texture to use.
    DreadedPE::MaterialLightProperty wfl_ambient(0.4f, 0.4f, 0.4f, 1.0f);
    DreadedPE::MaterialLightProperty wfl_diffuse(0.8f, 0.8f, 0.8f, 1.0f);
    DreadedPE::MaterialLightProperty wfl_specular(0.3f, 0.3f, 0.3f, 1.0f);
    DreadedPE::MaterialLightProperty wfl_emmisive(0.6f, 0.6f, 0.6f, 1.0f);

    std::shared_ptr<DreadedPE::Material> wfl_material(std::make_shared<DreadedPE::Material>(wfl_ambient, wfl_diffuse, wfl_specular, wfl_emmisive));
    DreadedPE::Entity* terrain_node = new DreadedPE::Entity(*scene_manager, &scene_manager->getRoot(), glm::mat4(1.0), DreadedPE::OBSTACLE, "terrain");
    DreadedPE::PortalLevelFormatLoader plf;
    DreadedPE::SceneNode* level_node_ = plf.importLevel("DPE Demos/navigation/levels/slope-bridge.plf", wfl_material, &DreadedPE::BasicShadowShader::getShader(), *scene_manager, *terrain_node);
    if (level_node_ == NULL)
#ifdef _WIN32
        MessageBox(NULL, "Could not load the level!", "Error", MB_OK);
        std::cout << "Could not load the level!" << std::endl;

With the level loaded, we can now create the navigation mesh that will be used for navigation.

DreadedPE::NavigationMesh* navigation_mesh = plf.createNavigationMesh(scene_manager, 0.0f);

We are now ready to initialise the A* pathfinder.

    DreadedPE::NavMeshAStar* ai = new DreadedPE::NavMeshAStar(navigation_mesh->getAreas());

    // Visualise the path.
    DreadedPE::Line* line = new DreadedPE::Line();
    // Create a material.
    DreadedPE::MaterialLightProperty dummy(0.0f, 0.0f, 0.0f, 0.0f);
    DreadedPE::MaterialLightProperty emissive(1.0f, 0.0f, 0.0f, 1.0f);
    std::shared_ptr<DreadedPE::Material> line_material(std::make_shared<DreadedPE::Material>(dummy, dummy, dummy, emissive, 1.0f));

    new DreadedPE::SceneLeafModel(*navigation_node, NULL, line, line_material, DreadedPE::LineShader::getShader(), true, true);

We added a line to the scene, this will be used to visualise the paths found. Finally we can finalise the scene. We create a WaypointSelector that reacts to user mouse clicks and generate paths between the points where the users have clicked.

    // Visualise the path.
    WaypointSelector* ws = new WaypointSelector(*camera, *line, *ai);

    // Start the game engine.
    DreadedPE::Game* game = new DreadedPE::Game(0.02f);

    return EXIT_SUCCESS;

The WaypointSelector is detailed below:



#include <glm/glm.hpp>
#include <sstream>

#include <dpengine/entities/Entity.h>
#include <dpengine/game/GameComponent.h>

namespace DreadedPE
    class Camera;
    class Line;
    class NavMeshAStar;

class WaypointSelector : public DreadedPE::GameComponent
    WaypointSelector(DreadedPE::Camera& camera, DreadedPE::Line& line, DreadedPE::NavMeshAStar& ai);


    void tick(float dt);

    void prepareForRendering(float p) {}
    DreadedPE::Camera* camera_;
    DreadedPE::Line* line_;
    DreadedPE::NavMeshAStar* ai_;
    glm::vec3 waypoint1_, waypoint2_;
    bool set_wayoint1_;
    float last_input_;



#include "WaypointSelector.h"

#include "GL/glew.h"
#include "GL/glfw.h"

#include <dpengine/entities/camera/Camera.h>
#include <dpengine/shapes/Line.h>
#include <dpengine/ai/pathfinding/NavMeshAStar.h>

WaypointSelector::WaypointSelector(DreadedPE::Camera& camera, DreadedPE::Line& line, DreadedPE::NavMeshAStar& ai)
    : camera_(&camera), line_(&line), ai_(&ai), waypoint1_(0, 0, 0), waypoint2_(0, 0, 0), set_wayoint1_(true), last_input_(0)




void WaypointSelector::tick(float dt)
    last_input_ += dt;
    // Handle user input.
    if (window->isMouseButtonPressed(GLFW_MOUSE_BUTTON_LEFT) && last_input_ > 0.25f)
        glm::vec3 intersection;
        int mouse_x, mouse_y;
        window->getMouseCursor(mouse_x, mouse_y);
        DreadedPE::Entity* picked_entity = camera_->pickEntity(mouse_x, mouse_y, intersection);
        if (picked_entity != NULL)
            std::vector<glm::vec3> waypoints;
            if (set_wayoint1_)
                waypoint1_ = intersection;
                waypoint2_ = intersection;
            set_wayoint1_ = !set_wayoint1_;

            ai_->findPath(waypoint1_ + glm::vec3(0.0f, 0.1f, 0.0f), waypoint2_ + glm::vec3(0.0f, 0.1f, 0.0f), waypoints);
            // Visualise the path.
            last_input_ = 0;
    int width, height;
    window->getSize(width, height);
    window->setMouseCursor(width / 2, height / 2);

The waypoint selector keeps track of 2 waypoints, where the user has clicked. When it has two waypoints it calls the A* pathfinder and visualises the found path by updating the Line's vertex points.