[C++ OpenGL] Pathfinding : Dijkstra and A*

I implemented two of the most popular technique use in video game to help a artificial agent navigates on the map : Dijkstra and A *

Dijkstra

Dijkstra is use so for a pathfinding process. The idea of the Dijkstra algorithm to start from the start node and scan all his neighbor until its find the destination route.

Dijkstra advantage it that he will always find the shortest route, but his weakness is that Dijkstra over exploring, and sometime we don't need it

A *

A* is I think it's the most use pathfinding technique in video game. Like on the previous subject, Dijkstra is good but it's over exploring to get the shortest path, it's can be an optimization issue

Sometime we don't need the shortest path, we just need a path to the destination, and that what A* does.

The main difference with A* and Dijkstra is A* Heuristic system which influence a lot about calculation of the path. On my project I use distance between the current scan node and the destination

Demo

He is the map

And some results

Source code

Link to this project : https://github.com/NicolasBunn/Pathfinding

[C++ OpenGL] Autonomously Moving Actor

Introduction

This projet made in C++ OpenGL show some 2D gemotry mathematics and "Steering Behaviors" IA

On this project ,the user can move a triangle player actor and give some commands to an ia actor

Here is the mains behaviors for the Ia actor

Seek

The agent goes to a specific location

Wander

The agent randomly patrol a round his location

Flee

When the player try to reach the agent, he goes to the opposite direction

Follow Path

The agent follow a way point node which are sort in a specific ordr . If the agent is near one a waypoint, he directly go to this waypoint instead to go from the first way point

Pursue

When an agent try to catch the player, if he goes to the current location, it is not optimize solution because the player is constantly moving. So one solution is to try to anticipate where the player is going, for doing that, the agent will try the "direction vector " that the player goes.

When the agent is close enough of the player , he will go directly on the player position.

Wall Avoidance

When a agent try to goes to a destination, if there is a wall between them, naturally the agent can't go there. The solution is to avoid the wall and goes to the destination. The agent will rotate and will find a path which are not colliding with the wall, then he goes to the destination and finally try to reach the final destination

Source and version can be found on this github : https://github.com/NicolasBunn/MovingAgent