Pathfinding algorithm insanely slow

1

Hi there everyone, I'm trying to program a game in Rust. I'm a roughly intermediate level Rust programmer but not super good at data structures or algorithms. I'm using what is roughly a greedy BFS pathfinding algorithm, with a few modifications of my own. It should (ostensibly) be much faster than almost any other pathfinding algorithm, but it can't take having more even five AI's trying to path-find without tanking the framerate of my application. I've tried to multithread this several times but I've never been able to successfully get multithreading to work, so I'd rather not. Here's the code, can anyone help me try to improve the performance?

pub fn find_path<'a>(map: &WorldMap,
                     start: Point3D,
                     goal: Point3D,
                     can_move: Box<Fn(Point3D) -> bool + 'a>)
    -> Option<Vec<Point3D>> {
    let mut frontier = BinaryHeap::new();
    frontier.push(State {
                      cost: 0,
                      pos: start,
                  });

    let mut came_from = HashMap::new();
    came_from.insert(start, None);

    while frontier.len() != 0 {
        let current = frontier.pop();
        if current.unwrap().pos == goal {
            break;
        }
        for next in strict_3d_adjacent(current.unwrap().pos, map) {
            if !came_from.contains_key(&next) && can_move(next) {
                frontier.push(State {
                                  pos: next,
                                  cost: distance3_d(goal, next) as
                                      isize,
                              });
                came_from.insert(next, current.map(|a| a.pos));
            }
        }
    }

    let mut current = goal;
    let mut path = vec![current];
    while current != start {
        if let Some(c) = came_from.get(&current) {
            if let Some(c) = *c {
                current = c;
                path.push(current);
            } else {
                return None;
            }
        } else {
            return None;
        }
    }
    path.push(start);
    Some(path)
}

Just some notes, Point3D is a type alias for a 3-tuple, and strict_3d_adjacent just gives all the points adjacent to the point on a 2D plane, with their highest 3d point (I have a 2D plane containing stacks of 3D tiles).

Please help, thanks!

2

You're testing with --release flag, right?

while let Some(current) = frontier.pop() would help you avoid unwraps. Unwrap changes control flow, so compiler might avoid some optimizations around it.

When you construct vec/heap, you could try using with_capacity() to give them size you expect them to have, so that they don't have to reallocate as they grow.

If inlining of can_move would help, try impl Fn(Point3D) -> bool + 'a instead of Box<Fn(Point3D) -> bool + 'a>.

There are faster hashers for the hashmap.

1 Like
3

You can quite easily profile rust code via perf on Linux. It basically boils down to running it with perf record -g and then having a look at perf report.

Also, maybe a BTreeMap might be more performant via data locality? If your points implement a spatial Ord having them in a b-tree might help.

Other than that you can pre-allocate memory as suggested by @kornel. Don't forget to use Vec::with_capacity as well.

It's also possible to change the nested if let to a single match like this (untested):

match came_from.get(&current) {
  Some(Some(c)) => {
    current = c;
    path.push(current);
  },
  _ => return None
}

Shouldn't make any difference, but it's much easier to read.

Other than that, keep in mind that most games don't require pathfinding for every frame. Usually calculating them every half a second or so is more than enough. It's also possible to cache the results of previous runs and start from there.

2 Likes
4

Thanks a ton guys! I’ll try your suggestions and see if the pathfinding gets any faster. Incidentally I actually haven’t been using the release flag.

1 Like
5

You should definitely use --release when evaluating performance, first and foremost.

If you're open to an existing implementation, try the pathfinding crate. The petgraph crate also has a bfs visitor, but you have to be using their graph type.

3 Likes
6

I’m always open to existing implementations! But —release made performance fast enough where this isn’t really a problem. I incorporated some of he previous suggestions for improvements to my code, too. I’ll look at the pathfinding crate though, thanks for the info.

1 Like
7

In addition to building with --release - Rust by default uses a cryptographically sound hashing in HashMap which is unnecessary overhead for something like your path finder. See this FAQ https://www.rust-lang.org/en-US/faq.html#why-are-rusts-hashmaps-slow. There's a separate crate with a fast but not cryptographically safe hash https://crates.io/crates/fnv - this is what the Rust compiler uses.

2 Likes
8

Doesn't rustc use fxhash nowadays?

1 Like
9

Awesome, thank you. I didn’t realize that was the case.