Implementing the A* Algorithm in Rust

So I am using Bevy to create some fun projects, and I wanted to share my code for making an A-star pathfinding.

There are plenty of optimizations that could be made, such as improving my lowest_f checking, searching diagonals, etc.

#[derive(Clone, Debug)]
struct Node {
    position: Position,
    g: i32,
    h: i32,
    f: i32,
    parent: Option<Position>,
}

let mut openlist: std::collections::HashMap<Position, Node> = std::collections::HashMap::new();
let mut closedlist: std::collections::HashMap<Position, Node> = std::collections::HashMap::new();
openlist.insert(start_position.clone(), Node { position: start_position.clone(), g: 0, h: 0, f: 0, parent: None });
while !openlist.is_empty() {
    let mut current_node = None;
    let mut lowest_f = -1;
    for (position, node) in openlist.iter() {
        if lowest_f == -1 || node.f < lowest_f {
            current_node = Some(node);
            lowest_f = node.f;
        }
    }
    if let None = current_node {
        break;
    }
    let current_node = current_node.unwrap().clone();
    let mut current_position = current_node.position.clone();
    openlist.remove(&current_position);
    // Add n to the CLOSED list
    let g = current_node.g + 1;
    let h = current_position.distance(&destination);
    let f = g + h;
    closedlist.insert(current_position.clone(), Node { position: current_position.clone(), g: g, h: h, f: f, parent: current_node.parent });
    // IF n is the same as the goal, we have a solution. Backtrack to find the path.
    if current_position == destination {
        let mut nodelist: Vec<Position> = vec![];
        loop {
            nodelist.push(current_position.clone());
            match closedlist.get(&current_position).unwrap().parent {
                None => break,
                _ => current_position = closedlist.get(&current_position).unwrap().parent.clone().unwrap(),
            }
        }
        pathing.path = nodelist;
        break;
    }
    let mut neighbors: Vec<Position> = vec![];
    neighbors.push(Position { x: current_position.x + 1, y: current_position.y, z: 0 });
    neighbors.push(Position { x: current_position.x - 1, y: current_position.y, z: 0 });
    neighbors.push(Position { x: current_position.x, y: current_position.y + 1, z: 0 });
    neighbors.push(Position { x: current_position.x, y: current_position.y - 1, z: 0 });

    for neighbor in neighbors {
        // This checks if the space is enterable. Change to whatever
        // determines "enterability" in your code.
        if tiletypes.get(&neighbor).unwrap().clone() == TileType::Wall {
            continue;
        }
        let h = neighbor.distance(&destination);
        let g = current_node.g + 1;
        let f = g + h;
        if openlist.contains_key(&neighbor) {
            if g > openlist.get(&neighbor).unwrap().g {
                continue;
            }
        }
        if closedlist.contains_key(&neighbor) {
            if g > closedlist.get(&neighbor).unwrap().g {
                continue;
            }
        }
        openlist.remove(&neighbor);
        closedlist.remove(&neighbor);
        openlist.insert(neighbor.clone(), Node { position: neighbor.clone(), g: g, h: h, f: f, parent: Some(current_position.clone()) });

    }
}

What is the A-Star algorithm?

Essentially, pathfinding optimized. The A* (A-star) algorithm is a popular search algorithm used for finding the shortest path between two points in a graph or a map. It combines the strengths of both breadth-first and depth-first search algorithms and is considered to be one of the most efficient algorithms for pathfinding and graph traversal.

The A* algorithm works by maintaining two lists, the open list, and the closed list. The open list contains the nodes that are yet to be evaluated and the closed list contains the nodes that have already been evaluated. The algorithm starts at the starting node and adds it to the open list. It then evaluates each node in the open list, calculates the cost to reach the goal node, and adds the node to the closed list if it has been fully evaluated. The cost is calculated using a combination of two factors: the actual cost from the starting node to the current node, and an estimate of the remaining cost from the current node to the goal node. This estimate is called the heuristic and it helps to guide the algorithm in the right direction towards the goal node.

The A* algorithm uses the concept of a f-value to determine which node to evaluate next. The f-value is the sum of the actual cost and the estimated cost. The node with the lowest f-value is selected as the next node to evaluate. This process continues until the goal node is found or until all nodes have been evaluated.

One of the key advantages of the A* algorithm is its ability to handle a large number of nodes and still produce efficient results. This is because it uses a priority queue to maintain the open list, which allows it to quickly find the node with the lowest f-value. Additionally, it uses the heuristic function to make informed decisions about which nodes to evaluate next, which reduces the number of nodes that need to be evaluated and speeds up the search process.

Another important aspect of the A* algorithm is its ability to handle dynamic environments. The algorithm can be adapted to handle changes in the graph by updating the cost of each node as the environment changes. This makes it well suited for applications in robotics, computer games, and autonomous navigation systems, where the environment is constantly changing.

The efficiency of the A* algorithm depends on the quality of the heuristic function used. A good heuristic function should be able to accurately estimate the remaining cost from the current node to the goal node. If the heuristic function is too optimistic, the algorithm may end up exploring many nodes that are not useful. On the other hand, if the heuristic function is too pessimistic, the algorithm may miss the optimal path.

A-Star algorithm from Wikipedia.

Generally, the A* algorithm is a powerful and efficient search algorithm that is widely used for pathfinding and graph traversal. It combines the strengths of breadth-first and depth-first search algorithms and is well suited for dynamic environments. The efficiency of the algorithm depends on the quality of the heuristic function used, and careful consideration should be given to the design of this function to ensure optimal results.

How it works in my code.

Each “Position” is just an X/Y/Z location, so calculating the distance from one X/Y/Z to another is just simple triangulation, and that is done in an implementation on the Position struct. This distance is used in the algorithm “heuristic” to determine what node to check next.

What is a heuristic?

It’s like, a “best guess”. In this case, the “best guess” for the shortest distance to the next Position is a straight line. So we use that “best guess” to determine which node to check next. If there are no obstacles, in this case no “TileType::Wall” in the way, then the best guess will always be a straight line (or, in this case there are no diagonals, so likely an “L” shape).

Why Rust?

I like using Rust because of the lack of memory leaks and a pretty clear syntax when using Results and Options. Rust is a modern “systems programming language” that offers several advantages over other programming languages. It is designed for performance, safety, and concurrency, making it well suited for a wide range of applications, from low-level systems programming to web development.

One of the key benefits of Rust is its memory safety guarantees. Unlike many other programming languages, Rust helps prevent common memory-related bugs such as null pointer dereferences and buffer overflows, through the use of strict ownership and borrowing rules. This not only makes Rust code more reliable, but it also helps developers write more secure code, which is especially important in the development of systems software and critical applications.

Rust also provides excellent performance, often outperforming C and C++ in terms of speed and memory usage. This is due to Rust’s efficient memory management and support for low-level programming, which enables developers to write code that is both fast and efficient.

Another advantage of Rust is its strong focus on concurrency. Rust provides powerful abstractions for concurrency, including lightweight threads and message-passing, which make it easier to write concurrent code that is both safe and efficient.

Finally, Rust has a growing and supportive community, making it easy for developers to find help and resources when needed. The Rust language and ecosystem are constantly evolving, and the community is actively working on improving the language and its libraries, making Rust a great choice for future-proof software development.

In conclusion, Rust is a modern systems programming language that offers several advantages over other programming languages, including memory safety guarantees, excellent performance, strong support for concurrency, and a growing and supportive community. Whether you’re developing low-level systems software or high-performance web applications, Rust provides a safe, efficient, and future-proof choice for your development needs.

What game dev platform?

I am using Bevy right now, as it is the most supported game-dev platform actively maintained in Rust.