How can my party improve our overland travel speed?

Question

I'm playing a (modified) Serpent's Skull campaign. We're L4, and about to start off through the jungle. We know there are others trying to beat us to our destination, so speed matters. I'm looking for (affordable) strategies to improve our net overland speed. Here's what I've considered so far:

• Wear light (or no) armor so we don't slow our base speed below 30'
• Oxen to carry our gear - they have a 40' base speed, and will keep us at a light load.
• Trekking poles add +10% to our overland speed (cost 15 GP)
• Walking >8 hours / day covers more ground...but at the risk of fatigue and nonlethal damage if they fail a DC 12 CON check. Going at least 9 hours seems safe, as folks can hopefully sleep off the nonlethal, and we do have a healer with us too. Or...
• Marching coffee lets you go 9 hours without risking nonlethal (cost: 1 GP / day)
• Hustle 1 hour / day this doubles our walking speed for 1 hour.
• Hustle a 2nd hour / day this will give everyone 1 nonlethal, and fatigue us...but if we're willing to go to bed fatigued (and risking an evening encounter fatigued) we can get an extra 3.33 miles / day (assuming we have our trekking poles).
• Hire a L3+ skald an L3 Skald with 12 CHA will have 8 rounds of raging song, which can be 8 hours of marching song, which DOUBLES our speed for 8 hours (and we can hustle the 9th without penalty) (no idea what the cost or availability of this is, but it might be pricey or impossible)

At this stage, my thought is that we plan for 9 hours, with poles + coffee. If we can't get a Skald, we only hustle for one of them. If we get a Skald, we hustle all nine!

What've I missed?

Things that don't work:

• We don't expect to be able to ride mounts because of the difficult jungle terrain: our GM has ruled that horses aren't trained for this purpose.
• We have a collective budget of 100s of GP to spend on this, but not 1000s.

Answer 1

There is actually still a slight field for improvement

tl;dr

• RAW, you should be able to buy horses, and they should be skeletal horses. They can tirelessly hustle at 10 mph. Creating them would cost you anywhere between 525 and 900 gp, and this is the fastest option you can have at these levels.
• If you cannot use horses, combine the things you listed in your answer with having a forced march for an hour or two and removing fatigue with a wand of Lesser Restoration.

My assumptions

You have listed pretty much every affordable way of increasing your land speed. However, it is still possible to improve your travel a little bit, assuming that:

1. Your DM actually follows the rules and doesn't introduce house rules
2. You have no more than 900 gold for your party of 4-5 characters to spend on the adventure.

Using the trekking pole

This indeed multiplies your overland travel speed by 10%, but if your movement is impaired, it gives you a 25% increase instead. Your speed will be 110% on a jungle "highway", but 93.75% on a jungle road or trail (the usual speed there is 75%).

We have spent 15 gp per person so far.

Hiring a Skald

There are no rules given for hiring an NPC with levels in a PC class. The cost is to be determined by the GM. The best you can find is this level 1 Foot Soldier who can join a party for a share of loot. I have never played in such a party, but you can just introduce such a character as a full NPC with class levels that will join your party via role play, earn XP and money, and generally act as and be a fully-fledged character.

Your other option is the Leadership feat, which would allow you to have a level 3 Skald once you hit level 3 yourself. If you don't aim to abuse this feat and are quick with your decisions, it's not going to break your game.

This allows you to march for 8 hours per day and pretty much max your overland speed and effectively move at 220% speed over jungle highway and 187.5% through jungle road or trail.

Healing away that damn non-lethal damage from hustling&forced marching

Actually, you don't need a Skald, because all that happens when you march too quickly is:

1. You get non-lethal damage.
2. This damage makes you fatigued.

If you heal the damage, the fatigue goes away:

"Eliminating the nonlethal damage also eliminates the fatigue."

Note that the rule says "eliminate", not heal, so not every GM would agree with this way of reading the rule book.

A healing wand could heal this damage away very cheaply, for 15 GP per use.

Casting Lesser Restoration to remove the fatigue

Even if your GM doesn't agree that healing removes the fatigue, a wand of Lesser Restoration costs 750 gp if created by a Paladin, or the same 15 gp per use. You can march, become fatigued, heal non-lethal damage, and cast Lesser Restoration upon yourself.

Combine a Skald's bonus with trekking poles, forced march, and Lesser Restoration

A properly-built Skald could give you (practically) unlimited hustling per day, essentially doubling your speed, which is 3 mph usually or 6 mph when marching. If we assume failing every Constitution check to start a forced march, here is what you can do:

1. Hustle for 8 hours.
2. Hustle for an additional your.
3. If you fail your Constitution check, heal those 1d6 points of non-lethal damage (15 gp) and take one use of Lesser Restoration (15 gp).
4. Go to 2.

Each additional hour of marching costs you 30 gp per person. Of course, you are not actually going to fail every single Constitution check, so you can just march until one of you fails a check, restore yourselves, and go to bed. Assuming that everyone has CON 14 (and you probably shouldn't have less), each of you has a 35% chance of failing the first Con check, and a party of 5 characters will expand 1.75 points of their "restoration kit", paying 52.5 gp for a party's average first hour of a forced march. This allows for 17-18 days of marching given the budget listed at the beginning, minus 125 gp for the trekking poles, which gives us a total of about 15 days in this traveling mode.

If your party has better Consitution scores, you will be able to take a little bit more risks for the same price.

Now, I do understand that you can't buy half a wand with 25 charges, and a full wand costs 750 gp, but you should be carrying a healing wand anyway, while a wand of Lesser Restoration is still not a must at this level, so I assume you to be able to have both.

Doing the math

You march for a total of 9 hours. The Skald allows you to hustle for this whole time. You get a speed of 54 miles per day on a highway. A trekking pole adds another 5.4 miles, giving you a speed of 59.4 miles per day. That's actually quite impressive, given that a normal party without marching coffee only traverses 27 miles per day.

If moving through a trail, your speed is 54*3/4=40.5 miles per day, multiplied to 50.63 miles by your trekking pole.

For a completely Trackless Jungle, just divide this speed by 3 for 16.77 miles per day.

But... what about animals?

Aurochs have a Con score of 17 (+3) and Endurance as a feat, which gives another +4 to a roll to avoid the fatigue, for a total of +7. Their individual chance to fail the first Con check is 10%, giving you an average cost of 3 gp per hour of marching. You probably do need to take this into account if you have more than one.

And what if my GM does not ban horses as mounts in the jungle?

Horses will automatically fail any checks to avoid fatigue, so it should either be Skeleton Mounts, who ignore the checks, or summoned horses, who are disposable.

Summoned horses cost 15 gp per 2 hours of marching per person if you use wands, and it's probably a bit too much. If you have a level 4 Summoner in your party, they can expand their spell slots to summon Phantom Steeds and Mounts, but it is going to pretty much exhaust their magic reserves every day.

I have not found a price for a skeleton horse, but it has 2 HD, costing 50 gp in onyx to Animate it. At level 4, you also can't cast this spell yourself. You need to seek service of a level 10 Cleric, who will cast it for you for 10*3*10=300 gp, where 10 is his Caster Level, 3 is the Spell Level, and 10 gp is a fixed multiplier. A light horse costs 75 gp, plus 50 gp in onyx, for a total of 600 gp per party of 5 adventurers. Of course, you might argue that a light horse's body is worth a lot less than a healthy, alive horse, but I am giving you a maximum price. This exhausts your travel budget immediately, but it's actually the fastest mode of movement you can have.

A skeletal horse moves at 5 miles per hour and can hustle without any problems, and force march, too. Just move at 10 mph as much as you guys can. Don't take any oxen, the undead mounts will carry stuff on themselves.

Answer 2

Dire Bats, Riding

Each of those beasts costs 300 gp to purchase. Bargaining rules can allow you to buy them for as low as 75% of their value if you roll well, costing you 225 gp per bat. Feeding them costs 10-20 copper pieces (0.1-0.2 gp) per day; ask your GM about the exact amount.

Since those beasts can fly 40 ft. per round, you can fly up to 32 miles per day in any terrain. While this is certainly less than what you can cover if you just go with a Skald, a trekking pole, and marching coffee, this speed is not reduced by flying over trackless jungle. As an additional benefit, you are immune to most encounters, because even ranged troops will suffer big penalties to hit you from the ground: you can fly as high as you want. Also, roads are often curved, not straight, so going more directly to your destination when you know where to go can save you plenty of time.

If your objective is scouting for a larger group of NPCs, and your overall speed is more limited by this larger group, you are definitely better of using flying mounts than anything else.

There are, certainly, downsides in this approach:

1. Those animals will eat most of your traveling budget, specified as "hundreds" of gold pieces for a party. Although, if you are Small, one bat will probably be enough for two riders.
2. You won't be able to carry too much gear with you: a Dire Bat can hold no more than 172 lbs to treat her load as Light, and a typical human weighs anywhere from 130 to 220 lbs. Again, less of a problem if you are Small.
3. Those mounts aren't combat-trained. However, if you are skilled in Handle Animal, you can perform combat training yourself.
4. If you plan to use those mounts in combat, even if it is for running away from the enemy, you would require ranks in Ride.

Consult your GM if they are OK with your party circumventing large parts of the plot via flying.

Answer 3

Teleport

A scroll of teleport typically costs 1000 gp and can teleport you and 3 other creatures and all your gear to wherever, with a small but potentially significant chance of failure. A scroll of teleport crafted by an Arcane Savant who added the Summoner's teleport spell to a full-caster list costs only 700 gp, but can teleport only 3 creatures.

This is probably the best option, because it is by far the fastest, but below are some other options:

• Buy horses. A horse has a land speed of 50 ft, which is better than pretty much any other cheap mount. A horse, having 2 HD, gets a feat. That feat can be Additional Traits, with which it can purchase the Adopted social trait to gain access to the Wild Stride race trait which lets it ignore natural difficult terrain in one sort of terrain, for example jungle. This also leaves it with a trait free. Alternatively, if you prefer a mount like a giant chameleon or similar which the GM may not arbitrarily hamper in forests, you can have it take the Wanderlust trait which increases its speed for the purpose of overland movement by 10 feet (which would make it tied with the horse's base speed). We can't put wanderlust on a horse because it is also a social trait so you have to pick between that and adopted. The horse also gets an extra 5' of movement speed if it was ever an animal companion for a character with the Thoroughbred race trait. That's potentially 55 ft of difficult-terrain-ignoring base movement, which lets us travel 6.875 mph with trekking poles. A horse with its Endurance feat retrained to Additional Traits costs either the same price as a regular horse or 50-150 gp more than that, depending on how your GM is feeling, and thus should be available in any settlement the size of a hamlet and is definitely available in anything larget than that (e.g. a village).

• summoned creatures don't need not to die. Undead creatures don't need to rest. A Skeleton Horse gets no non-bonus feats, and a mount is unlikely to have Additional Traits with the right traits, but they can both run instead of walking-- the skeleton horses forever and the summoned horses until they poof or die. That said, you can't run through difficult terrain. If there's a way around said terrain, a skeleton horse can let you go 22 mph, 24 hours a day, non-stop (the trekking poles only give 10% in this case). That's 528 miles per day!

• Tree Stride costs the same as teleport (with the same options for more or less expensive versions) and is only slightly less fast-- ~172 thousand miles per hour in a jungle for the cheapest version-- but requires you to purchase one scroll per character rather than just one scroll. This means that every character in the party who's going needs to be able to use DC 27 UMD scrolls, which may be difficult if you have some really weak party members-- full casters are only going to be able to grant sufficient bonuses to themselves at 4th level to accomplish such a DC cross-class, though a 4th level Bard with gallant inspiration can probably make up the difference. If you have people who can't make the DC reliably, you may need to spend an additional few hundred gold on scrolls for the personal spells the full casters can't share with weaker characters, like fallback strategy and hermean potential and embrace destiny. The (only) advantage of using tree stride over teleport is that there's no chance of failure, both because you don't roll a d100 to see if there's a mishap and because if the destination is warded against teleportation you can get right up to the edge of such wards and then walk in rather than just failing entirely.