Rover Instruction Sets

21 Mar

Rover Instruction Sets

Josh Cooper

Abstraction, Algorithms, Arrays, Instruction-Set

A recursive pathfinding algorithm finds a path by growing & backtracking a path. You can’t evaluate multiple routes, you only have the one, and you explore it til you reach a dead end or the goal. So, how pray tell does one optimize a recursive pathfinding algorithm?

The simple answer is instruction sets. If you take a look at A* you can see the basic logic we need. A node closer to our goal is more valuable than a node farther away.

Let’s just run with that. We’ll give our rover an optimized instruction set, we’ll optimize it based on the rover’s distance from the destination. We want a delta x & delta y.
\[\Delta =\vert Destination – Current\vert\\\begin{bmatrix}\Delta x\\ \Delta y\end{bmatrix}=\vert\begin{bmatrix}dx\\ dy\end{bmatrix}-\begin{bmatrix}cx\\ cy\end{bmatrix}\vert\]

Pretty simple we just take the absolute value of the difference between our destination and current position.
What do we do with that?
We compare the delta x against the delta y, whichever is closest is deprioritized. Well, as you’ll see it can be deprioritized, it depends how you want to optimize the algorithm (short paths vs. short searches).

You could code the instruction set code directly into the algorithm, but why do that when I’ve got this lovely method.

//Something went wrong if we're backtracking so the hell with the instruction set, else the caller can deal with it
__int8* Rover::Get_Search_Order()
{
	static int static_stack_data;
	
	// Above we make a static variable here we turn it into an array of smaller variables
	__int8* search_order = (__int8*)( &static_stack_data );


	enum { Down = 0, Up = 2, Right = 1, Left = 3};

#ifdef SHORT_PATHS
	// Should we prioritize X or Y ( delta X > delta Y )
	if ( abs( current_x - dest_x ) > abs( current_y - dest_y ) )
	{
		search_order[0] = current_x > dest_x ? Left	: Right;	// X Towards Goal
		search_order[1] = current_y > dest_y ? Down	: Up;			// Y Towards Goal
		search_order[2] = current_x > dest_x ? Right	: Left;		// X Away from Goal
		search_order[3] = current_y > dest_y ? Up		: Down;		// Y Away from Goal
	}
	else
	{
		search_order[0] = current_y > dest_y ? Down	: Up;			// Y Towards Goal
		search_order[1] = current_x > dest_x ? Left	: Right;	// X Towards Goal
		search_order[2] = current_y > dest_y ? Up		: Down;		// Y Away from Goal
		search_order[3] = current_x > dest_x ? Right	: Left;		// X Away from Goal
	}
#else
#ifdef SHORT_SEARCHES
	// Should we prioritize X or Y ( delta X > delta Y )
	if ( abs( current_x - dest_x ) > abs( current_y - dest_y ) )
	{
		search_order[0] = current_x > dest_x ? Left	: Right;	// X Towards Goal
		search_order[1] = current_y > dest_y ? Down	: Up;			// Y Towards Goal
		search_order[2] = current_y > dest_y ? Up		: Down;		// Y Away from Goal
		search_order[3] = current_x > dest_x ? Right	: Left;		// X Away from Goal
	}
	else
	{
		search_order[0] = current_y > dest_y ? Down	: Up;			// Y Towards Goal
		search_order[1] = current_x > dest_x ? Left	: Right;	// X Towards Goal
		search_order[2] = current_x > dest_x ? Right	: Left;		// X Away from Goal
		search_order[3] = current_y > dest_y ? Up		: Down;		// Y Away from Goal
	}
#endif
#endif

	//Return the array we made
	return search_order;
}

Now in that method you can see two potential instruction set permutations, and each is guarded by preprocessors. I couldn’t account for every permutation, all 40,320 of them, but I did account for 9. The permutations I tested were hand crafted according to some logical and intuitive assumptions I made regarding pathfinding. For example, it simply makes sense to first try going towards your goal, than away from it. Since I have them though, I might as well share my test results.

Note: The first half of each permutation is the ordering output when delta X is less than delta Y.
Note2: Y1 indicates a direction toward the Y goal ordinate. Respectively Y2 represents moving away from the goal(increasing delta Y).