Look up `Children of Orc.'
The player can give assignments to the other Orcs, and the action plans for those assignments are displayed in-game. The Orcs are smart enough to find cheap plans. When tasked with procuring stone, e.g. they will see what the quickest way is. Sometimes scavenging for discarded stone may be cheaper, other times, with pickaxe in hand near a quarry, quarrying is the way to go of course. They adapt. But whatever plan they come up with, it is communicated to the player in an info-window.
The search space for the plans is ridiculously large, so testing pre-conditions needs to be insanely fast. With AVX, you get to test up to 256 boolean preconditions in one go!
To give you an idea about search space: the Orcs have a repertoire of 115 possible actions. Stringing together a plan of let's say 12 actions (some plans are longer), gives 115 12 possible plans. That is a scary big number: 5350250105473711181640625
A* helps guiding the search through this space, but can only do so much. So every A* operation needs to be as fast as possible.