Last night my friend and I beat the last level of Halo 2 (“The Great Journey”). That same friend has been working towards a coding interview, and I’ve been helping them along by giving them mock interviews. Recently, we’ve become interested in pathfinding algorithms - so, naturally, when we finished the level, we discussed how Tartarus' algorithm might be designed and how it might be improved.
At first, I complained. “He gets stuck at the bottom level of the platform! How can he not know he needs to step into the grav lift and come back up!”
It’s complicated.
The lift has three levels. Tartarus' goal in life is to kill the Arbiter (and accompanying Elites/humans). His only weapon is a melee weapon (of sorts) called a “gravity hammer.”
So he needs to basically run around on this platform thing, chasing the good guys around and swinging this hammer at them. The problem is that the lift in the middle of the three platforms only has one drop-off location: the top platform.
If Tartarus is on the bottom level and you’re on the middle level, he’d have to ride the lift to the top level, then jump down to the middle level. It gets worse if you’re standing across the lift from Tartarus on the bottom level with him, since he can’t get to you without crossing through the lift or walking around a long wall.
So after thinking this through, I decided the pathfinding wasn’t bad - it was just hard!
I mean, he can decide whether to jump across or walk around a big hold in the ground. He can find his way over/around obstacles very well if everybody is on the middle platform. So in a 2D search, he’s good to go. Which makes sense - that should be much faster/easier than a 3D search.
I remember reading about Dijkstra at some point - I wonder if that’s related somehow….
[EDIT on Feb 9, 2021] I’d be willing to bet that Tartarus moves around based on some intelligently-optimized A* algorithm. I’m thinking that the board is probably laid out in some kind of graph, and the various paths are weighted by difficulty (like obstacles in the way) and distance. Then the heuristic weights of each path can be added up and he decides where to go. I wonder if another heuristic weighting has to do with where his enemies are (us) - maybe that lowers the score? Since there are several enemies for him to choose between, maybe the target just switches based on the total weight to each target?