NAVIGATING THE METAVERSE: OPTIMIZATION OF MULTI-LAYER GRID TRAVERSAL USING GRAPH ALGORITHMS AND DEEP NETS

Svenson, Pieter

Permalink

https://hdl.handle.net/2142/124976 Copy

Description

Title

NAVIGATING THE METAVERSE: OPTIMIZATION OF MULTI-LAYER GRID TRAVERSAL USING GRAPH ALGORITHMS AND DEEP NETS

Author(s)

Svenson, Pieter

Issue Date

2021-12-01

Keyword(s)

navigation of virtual grid-like spaces, algorithm structure

Abstract

The goal of this project was to assist in the navigation of virtual grid-like spaces. Among other video games, Minecraft is increasingly being used as both a recreational and an educational platform, so our team used this as the target of our implementation. We used a combination of graph-solving algorithms to find a path across a multi-layer network in which the layers are grids. The most difficult and titular task of this project was to explore and develop methods of effectively combining two sub-algorithms — A* and Dijkstra’s — by reducing path distance, execution time, and memory consumption. We developed and explored two options: top-down and bottom-up. Ultimately, top-down doesn’t result in optimal results but instead gives nearoptimal results at a much faster rate. Additionally, to improve the runtime of the A* sub-algorithm, we developed a deep neural network whose forward pass replaces its standard approximation function. The inclusion of the neural network yielded roughly 50% longer execution times and 1% larger memory consumption for scenarios with conditions very similar to those in testing. The worsened performance is likely due to the more extensive calculations required in the forward pass of the deep neural network, therefore rendering this solution unfeasible. With more research, maybe neural networks can replace the approximations of grid-solving algorithms, but we found the greatest improvements by altering the overall algorithm structure.

Type of Resource

text

Language

eng

Owning Collections