Withdraw
Loading…
NAVIGATING THE METAVERSE: OPTIMIZATION OF MULTI-LAYER GRID TRAVERSAL USING GRAPH ALGORITHMS AND DEEP NETS
Pieter Svenson
Loading…
Permalink
https://hdl.handle.net/2142/114999
Description
- Title
- NAVIGATING THE METAVERSE: OPTIMIZATION OF MULTI-LAYER GRID TRAVERSAL USING GRAPH ALGORITHMS AND DEEP NETS
- Author(s)
- Pieter Svenson
- Issue Date
- 2021
- Keyword(s)
- virtual
- grid-like
- Minecraft
- graph-solving algorithms
- Language
- en
- 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.
- Graduation Semester
- 2022-10-14T09:54:53-05:00
- Type of Resource
- text
Owning Collections
Undergraduate Theses at Illinois PRIMARY
Manage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…