A* Pathfinding Visualization

This is my first attempt at creating an efficient A* pathfinding algorithm. This was made from scratch without any UI/algorithmic library. If there is a path, it will always find the shortest way to reach it and then renders it.

Basic Controls

You must create a map to start the pathfinding. The start node is blue, end node is red and the walls are black.

To create nodes:

• Start: press 'S'
• End: press 'E'
• Wall: left click

To delete nodes:

• Right click on top of node

Diagonal

My algorithm supports both diagonal and non diagonal pathfinding.

Simply check the "diagonal" box at the bottom left of the screen.

Timed Efficiency

The algorithm after a successful attempt at pathfinding will show the amount of time it took to compute the fastest path along with the amout of open and closed nodes.

Generated Walls

Random Maze

I've also developed a random maze generator(it only generates walls so you have to choose where you want the open and end nodes).

Scenes

Exporting/Importing Scene

You can export your current scene or import someone else's scene in the menu strip "Import/Export".

Presets

There are custom made scene presets that you can try and edit on your own. You can find them in the presets folder, download them and import whichever one you want.

Complicated Stuff

Euclidean Heuristic Function for Diagonal Movement:

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * sqrt(dx * dx + dy * dy)

4-Way Heuristic Function(D=10, D2=14):

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

Get Path Pseudo-Code:

int newG, dx, dy;
bool newPath;
Node lowestCost;
List<Node> neighbours, open = new()
{
    new Node(globals.start_ij, null)
}, close = n

// While there are nodes to explore
while (open.Count > 0)
{
    // Get lowest f cost in open list
    lowestCost = getLowestFCost(open);

    open.Remove(lowestCost);
    close.Add(lowestCost);

    // Found end
    if (lowestCost.ij[0] == globals.end_ij[lowestCost.ij[1] == globals.end_ij[1])
    {
        pathCount = retracePath(lowestCost, close);
        openCount = open.Count;
        closeCount = close.Count;
        return true;
    }

    // Get neighbours
    neighbours = getNormalizedNeighbours(lowestCost);
    for (int i = 0; i < neighbours.Count; i++)
    {
        if (close.Contains(neighbours[i]))
        {
            continue;
        }

        // Recalculate node values in runtime
        newPath = false;
        dx = lowestCost.ij[0] - neighbours[i].ij[0];
        dy = lowestCost.ij[1] - neighbours[i].ij[1];
        newG = (dx != 0 && dy != 0) ? lowestCos14 : lowestCost.g + 10;
        if (open.Contains(neighbours[i]))
        {
            if (newG < neighbours[i].g)
            {
                neighbours[i].g = newG;
                newPath = true;
            }
        }
        else
        {
            neighbours[i].g = newG;
            newPath = true;
            open.Add(neighbours[i]);

        if (newPath)
        {
            neighbours[i].updateHeuristic();
            neighbours[i].parent = lowestCost;
        }
    }
}

return false;

a project by lipeeeee.