This is my implementation of A* path finding algorithm. It tries to find the shortest way from green square to red square, found way is not necessarily the shortest but as long as the goal is reachable, a way is found.
Source code: GitHub
Demo: Google Drive
The gray squares in the picture above represents blocks. Green square is the starting point and the red one is the goal. Dark blue squares are the processed nodes until a way is found and the yellow line is the way found.
Some Technical Details
- This project was written purely in OpenGL and C++. Nvidia Nsight was used for graphics debugging.
- A new scene is rendered only when we got an input from the mouse. So technically we have fps of <1.
- Diagonal movements are not allowed. But the code is scaleable and can easily be modified to allow diagonal movement.
- Euclidian distance is used as heuristic value.
- Screen dimensions are 800×800 and node dimensions are 20×20, so there are 1600 node in total.
- Since performance is not an issue for this project, for node picking, I rendered every node in a different color and and wrote a function that converts their RGB values to integer values and used that value as node’s ID to identify individual nodes. In a performance critical project an algorithm of ray casting from screen space to view space and from there to world space should be used.
This is how behind the scene looks. There are 1600 square nodes in the picture. And even though some of them looks the same, every node has unique RGB.