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 Motivations

A couple notes:

• Minecraft only has 65536 angles, so there is such a thing as an optimal solution.
• For sanity's sake, we'll ignore Half angles, and glitches in general.

Initially, we restrict the problem to ground movement, with zero initial speed.

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)
• Branch & Bound

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