Abstract:
A navigation mesh (or Navmesh)
is a data structure that allows characters to plan and traverse paths through 2D and 3D
environments.
Most Navmesh generators create a separate Navmesh for each fixed agent radius
by subtracting that radius from the traversable space.
Methods that generate a unified Navmesh are currently too limited to be used in a standard game
development workflow.
In this thesis, we work towards letting a state-of-the-art Navmesh (Recast) support arbitrary
agent radii.
For this, we have defined a new concept, Local Clearance Minimum (LCM),
a specific line segment that allows us to unify all Navmeshes into one.
We show how to extract all LCMs of an environment in Recast using a new watershed
implementation.
We show that the performance of this new watershed algorithm is on par with Recast’s built-in
watershed algorithm.
We also show that the algorithm can extract most LCMs accurately,
but there are some limitations due to the current (voxel-based) Recast pipeline.
Because these issues can be resolved in future work,
we argue that LCMs are a promising practical concept for enabling any-radius pathfinding on a
single Navmesh.
In this contest, we had to be in a team of three. You got five problems, and you had to solve them
using programming. The twist is that only one screen, keyboard and mouse were allowed. Only one
person could do the programming. The other two had to figure out how to solve the problem and tell
the typing programmer what to do.
The goal was to follow a white line with a small autonomous car via one or more optical
sensor(s).
Because of some mechanical problems, we had to rewrite the entire program one
minute before the start of the competition.
I had an internship at Unity Technologies back in Q1 and Q2 of 2022. I was part of the texture API
team.
