MovingAI pathfinding benchmark parser in Rust

You know I worked a lot with pathfinding. In academia, the MovingAI benchmark created by the MovingAI Lab of the University of Denver is a must for benchmarking pathfinding algorithms. It includes synthetic maps and maps from commercial videogames.

Parsing the benchmark data, the maps, creating the map data structure and more, is one of the most boring thing I needed to do for testing my algorithms. For this reason, I think a common library for working with the maps specifications it is a must.

For this, and because I enjoy a lot coding in Rust, I did a MovingAI map parser for rust.

Repository is here. The library is also on crates.io. It is still unstable because I want to be sure that the public AI is consistent with the requirements. I also not very solid on the needs of Rust APIs. So, I welcome some help here. :)

Example

However, look how it is convenient for writing pathfinding algorithms! All the important stuff (neighbors, map, and so on) are just out of the box. This is an A* algorithm I wrote in literally 5 minutes.

// A* shortest path algorithm.

fn shortest_path(map: &MovingAiMap, start: Coords2D, goal: Coords2D) -> Option<f64> {

    let mut heap = BinaryHeap::new();
    let mut visited = Vec::<Coords2D>::new();

    heap.push(SearchNode { f: 0.0, g:0.0, h: distance(start, goal), current: start });

    while let Some(SearchNode { f: _f, g, h: _h, current }) = heap.pop() {

        if current == goal { return Some(g); }

        if visited.contains(&current) {
            continue;
        }

        visited.push(current);

        for neigh in map.neighbors(current) {
            let new_h = distance(neigh, goal);
            let i = distance(neigh, current);
            let next = SearchNode { f: g+i+new_h, g: g+i, h: new_h, current: neigh };
            heap.push(next);
        }
    }

    // Goal not reachable
    None
}

 

One Reply to “MovingAI pathfinding benchmark parser in Rust”

Leave a Reply

Your email address will not be published. Required fields are marked *

Enter Captcha Here : *

Reload Image

To respond on your own website, enter the URL of your response which should contain a link to this post's permalink URL. Your response will then appear (possibly after moderation) on this page. Want to update or remove your response? Update or delete your post and re-enter your post's URL again. (Learn More)