This is an optimization algorithm and is used to find optimum solutions in a complex graph. Ants or other agents are left to explore and discover good solutions.

For a game world, I think A-star algorithm is better for shortest path finding.

Ant Colony Optimization

The Algorithm

1. We start with a grid. Each cell in the grid has variable ‘trace’ that is a float value telling how much this cell is covered by recent travelers (or how much recent travelers have left their trace here). If a traveler passes through a cell, it increases its trace. The more a cell is covered, the more traced it is.

2. An agent starts at a starting cell & follows a randomized path initially. As he travels, he leaves its trace behind as an increment of the current cell’s trace by 1. He then checks all 8 neighbors except the already followed list of cells from starting node & selects the one, probabilistically, with the highest probability of selecting the one with most trace. He keeps traveling unless he has either found the destination cell or if there are no legal neighbors to jump to anymore (all neighbors have been travelled or there are walls all around.

3. In another variation, if he founds no neighbor legal, he back travels to previous neighbor from where it came, and discarding the current one, he again checks all neighbors from the previous one (except the current one). This way, it keeps finding solutions. But i doubt this appraoch, but it will be useful if some other limiting factor has been added (max-iterations).

4. Continuing 2: The probability of selecting a neighbor is based on how much the trace is. If all neighbor have equal trace, probability of selecting any neighbor is equal. So probability of selecting any neighbor is based on its trace relative to trace of others (or average trace?).

4.1: At each iteration, the trace on all the cells will be decreased by some amount (evaporated based on a formula).

5. After finding the solution, the agent will go back to source node immediately following the same path it took (back tracking the visited list?). And it will again leave trace as it travels backward. When reaching source, the visited list will have been cleared now (as visiting each node backward, the list will be popped on cell at a time).

6. Repeat step 1 on the agent.

ultimately, the many agents will converge to path consisting of cells which are the most common between all the paths taken by the agents as well as the paths which are have abundant trace. the shortest paths are likely to have abundant trace as agents moving through it will be cross faster and thus their back and forth movement will cause more fresh/abundant trace then distant paths.

Pseudocode

function initialize_grid():
    create a grid with cells
    initialize each cell's trace to 0

function travel_to_destination(starting_cell, destination_cell):
    current_cell = starting_cell
    path = [starting_cell]
    visited_cells = [starting_cell]

    while current_cell != destination_cell and there are legal neighbors to explore:
        update_trace(current_cell)
        neighbors = get_legal_neighbors(current_cell, visited_cells)
        next_cell = select_next_cell_based_on_trace(neighbors)
        
        if next_cell is not None:
            move_to_next_cell(next_cell)
            current_cell = next_cell
            path.append(next_cell)
            visited_cells.append(next_cell)
        else:
            backtrack_to_previous_cell()
            current_cell = path[-1]

    if current_cell == destination_cell:
        return path
    else:
        return None

function update_trace(cell):
    decrease_trace_on_all_cells()
    cell.trace += 1

function get_legal_neighbors(cell, visited_cells):
    legal_neighbors = []
    for each neighbor of cell:
        if neighbor is legal and neighbor is not in visited_cells:
            legal_neighbors.append(neighbor)
    return legal_neighbors

function select_next_cell_based_on_trace(neighbors):
    total_trace = sum(trace for neighbor in neighbors)
    probabilities = [neighbor.trace / total_trace for neighbor in neighbors]
    next_cell = select_neighbor_based_on_probabilities(neighbors, probabilities)
    return next_cell

function decrease_trace_on_all_cells():
    for each cell in grid:
        cell.trace *= evaporation_rate

function move_to_next_cell(next_cell):
    // Perform movement to the next cell

function backtrack_to_previous_cell():
    // Backtrack to the previous cell

function select_neighbor_based_on_probabilities(neighbors, probabilities):
    // Select a neighbor based on given probabilities

function main():
    initialize_grid()
    agents = [agent1, agent2, ..., agentN]
    paths = []

    for each agent in agents:
        path = travel_to_destination(starting_cell, destination_cell)
    
    // After many iterations, the path will be fairly same for all
    // agents & it will approximately be optimum path

More

1. There are some ant colony algorithms such as Ant System (AS). My approach is much simplified though.
2. I plan to later implement, show and modify it.
3. Good text on ACO: https://web2.qatar.cmu.edu/~gdicaro/15382/additional/aco-book.pdf