Differences

This shows you the differences between two versions of the page.

--- people:link [2014/10/06 20:12] – created vyross
+++ people:link [2014/10/06 20:16] (current) – removed vyross
@@ Line 1: / Line 1: @@
-====== Robust infinitely scalable pathfinding mechanisms for sparse communal structures ======
-===== Abstract =====
-When dealing with the problem of making highly scalable systems, we often have to forgo a number of luxuries present in other kinds of computing contexts. In the Movable Feast Machine (MFM), a simulated architecture for an infinite computer, some of these sacrifices make traditional computation difficult; a lack of global scope, a highly limited local scope, and asynchronous execution all complicate a number of traditional computing problems. One such problem that is made difficult to solve using traditional approaches is pathfinding; we can’t track any global state, nor can we guarantee any execution order, so knowing what the most optimal path from points A to B is becomes more complex. How do we know where the origin is? The destination? How do we track our path without overwriting data in such a limited environment?
-I proposed and implemented a system for pathfinding inside the MFM, using a backdrop of a virtual conflict between warring states in a sparsely populated environment, where the ability to find the enemy is vital to victory. //Scouts// from each nation are able to leave behind a trail of //breadcrumbs//, which self-optimize locally, resulting in semi-optimal paths globally between the wandering scout and its origin. Once a scout alerts their breadcrumb trail, an alert signal is sent from breadcrumb to breadcrumb, which persists for a certain amount of time before dissipating (an //alert cycle//). Assuming an obstacle-free environment, the path can optimize to a straight line; obstacles can result in a path that contains switchbacks. I used the effectiveness of the nations’ armies as a metric for gauging the success of the pathfinding algorithm.
-===== Conclusion =====
-This method for pathfinding works well for sparse structures, demonstrating both an ability for the concept to work with a clear goal in the context of a more complex system (the conflict) and an ideal density level for the system to allow pathfinding to work well. If the machine is too sparsely populated, it can take scouts far too long to find their adversaries, while in a densely populated system the optimization (and eventually, the movement of the scouts) is severely limited. Additionally, when breadcrumbs persist too long, they can contribute to system clutter; I found that giving them a built-in maximum age of [X] helped mitigate this, as well as causing them to die after they are finished functioning for a single alert cycle.