Optimizer

The goal of this page is to document ideas and progress on designing an algorithm for optimizing jump strats, with the ultimate goal of creating a mathematically optimal parkour bot, unlike other projects such as BaritoneParkour which use a coarser pathfinding for more general purposes.

Presentation and Definitions

Optimizing linear jumps is fairly easy, but it gets complicated when we add obstacles to the mix.

To start things off, we restrict the problem to ground movement, with zero initial speed. It's the bare minimum, but it isn't trivial.

A couple notes:

• Minecraft considers a finite number of angles (65536), so there is such a thing as an optimal solution.
• We'll ignore half angles (though they could be added later as standalone angles, though the integration wouldn't be very elegant).

The goal is to optimize a recursive function with threshold.

• The recursive function is the player's speed, which takes an angle as input

• The threshold represents a built-in mechanic-in that limits how little momentum can be conserved over ticks.

Formally, we have:

• ${\textrm {threshold}}(v)=v\mathbb {1} _{|v|<\varepsilon }$
• $Vx_{0}(\theta _{0})=0.1\cdot \sin(\theta _{0})$
• $Vx_{n+1}(\theta _{n+1})={\textrm {threshold}}(0.546\cdot Vx_{n}(\theta _{n}))+0.1\cdot \sin(\theta _{n+1})$
• Analogous definition for $Vz$

The function we want to optimize is the player's X position after N ticks (alternatively Z, with Vz instead):

• $X(\theta _{0},...,\theta _{N-1})=\sum _{k=0}^{N-1}Vx_{k}(\theta _{k})$

In Minecraft, the threshold constant is 0.005 (changed to 0.003 in 1.9)

Two observations about the threshold function in general:

• If $\varepsilon =0$, the function can be made nonrecursive. In that case, the function is differentiable, so finding a maximum isn't too complicated.
• If $\varepsilon =\infty$, the velocity is constant, and the problem can be reduced to a simpler pathfinding problem. (with these constants, $\varepsilon >0.1831...$ suffices)

For any value in between, the problem becomes quite a bit harder. In our case, because the threshold constant is low (0.005), the approximation with $\varepsilon =0$ is quite good (and even perfect in the case the threshold isn't activated to begin with), so it can be used as a base for the true solution.

Initial approach:

• A* algorithm, with implicit states (x,z,Vx,Vz) - optimizes minimum duration, but no guarantee on optimal path.
• Branch & Bound - optimizes path, assuming the duration is given

A good heuristic we can use is one that ignores walls and angles, and goes straight towards the goal (constant angle)