Minecraft 1.16 Nether Fortress Location/Generation

1.16 changed the Nether Fortress spawning algorithm quite a bit.

First off, their layout has been significantly more randomized:

The best patterns I can spot are occasional lines of 3-5 fortresses at random angles, so if you found two, traveling in the same direction as the line connecting the two (or opposite direction) can yield another.

Another problem is frequency of their spawning. Not only is the generation more rare, it's now biome-dependent. Specifically, generation of a fortress may begin only in Nether Wastes, Basalt Deltas and Soulsand Valley. Fortresses may encroach into Warped Forest and Crimson Forest, if their generation process expands them into these biomes, but they won't be found in the middle of these - so if you encounter large instances of these biomes, avoid - likely the "bald patches" in the attached example map correspond to these biomes.

As for the most efficient strategy of locating the fortresses, that largely depends on how cheaty you want to get - other than trying to extrapolate two fortress locations into a line, or Elytra with unbreaking III and a couple stacks of fireworks for flying randomly, I don't think there are any entirely un-cheaty ways.

An easy way is to paste the world seed into the Fortress Finder app. Using the Minihud mod with structure bounding boxes enabled will let you spot the bounding box of a fortress long before its structures enter your view. Traveling over the Nether roof on Elytra or horseback allows you to cover massive distances safely, and either using freecam mode e.g from the Tweakeroo mod, or the composter Xray glitch to peer through the roof and see what structures are underneath in the Nether proper. Or just use the /locate command.

There are infinite nether fortresses in the nether. They spawn in rows every 200-400 blocks along the world's North/South axis. Once you find the first one, just keep walking north or south from it to find another

Hope this helps