Tron Bot – Nuts & Bolts – Queue

As I mentioned in my previous post, I entered a Tron bot into the University of Waterloo Google AI Challenge. My bot is currently hovering the top ten in the preliminary rounds.

I plan to post all the code to my bot, but not the interesting pieces until after the final tournament has taken place.  Entries are allowed up until the end of the day this Friday.

But here is some code that I don’t really think gives me away any secrets so I will post it here.  Also, I doubt too many entrants will read this post.

As part of my bot, I needed to be able to figure out the minimum number of moves to squares on the board.  As you may recall from an algorithms course, minimum path = breadth first search = use a queue. My first pass at this used the std::queue provided by the STL, but I thought it might be too slow, mainly due to the potential to allocate memory dynamically. So I wrote my own queue functions using a statically allocated array. Allocating the array statically is not a problem because the tournament rules state that the largest tron field will be 50×50.

The structure of each queue item is 3 integers, the coordinates of the square and the depth reached in the search.

I think this is probably considerably faster than using the STL queue.

Without further ado, here’s the code:

struct queue_item { int x; int y; int d; } foo_queue[50*50*4];
int q_top = 0;
int q_bot = 0;

void queue_clear()
{
	q_top = 0;
	q_bot = 0;
}

void queue_add( int x, int y, int d )
{
	foo_queue[q_bot].x = x;
	foo_queue[q_bot].y = y;
	foo_queue[q_bot].d = d;
	q_bot++;
}

int queue_take( int * x, int * y, int * d )
{
	*x = foo_queue[q_top].x;
	*y = foo_queue[q_top].y;
	*d = foo_queue[q_top].d;
	q_top++;
}

int queue_emptyp()
{
	return ( q_top == q_bot );
}

Leave a Reply

Your email address will not be published. Required fields are marked *