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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// 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
}