Traversal Algorithm of rocket mania

[daniel955]

Hi I am a beginner in game programming and would like to make
a rocketmania clone using opengl, the display and interaction part is done.
I also have a classes named gameboard and tiles with their properties.
but I am having problems on game logic,
where the fuel flows into a pipe opening,
then fuel spreads to adjacent pipes with opening.

can anyone tell me what traversal algorithm should I use?

any help or clues would be appreciated.

[gusano79]

You probably want a breadth-first search, with the tiles as nodes and edges between adjacent tiles in each of the four cardinal directions.

If you only have one fuel source in the game, that's your root node. If you have multiple fuel sources, just mark each of them as 'visited' to start with.

[daniel955]

Hi, I already tried searching through the array of tiles/pipes,
but I encountered a problem, since my current loop only searches downward,
I thought, what if the fuel is .. flowing up/ going northward(caused by tile/pipe orientation)

I think the solution requires adding another array search, but in a different direction
this requires more "for loops", making the code long/messy, and might make the game run slow.

as for breadth-first search, Im still confused and cant think of a way to put my tiles/pipes into a tree...
bec. of the possibility that a child can have 3 parents and the child can also have 3children. my destination is the rockets,
if a connection is made between the fuel and the rocket, then
I remove the nodes that are connected.

Is there a better way to do my array search, or anyone can teach me how to put tiles/pipes into a tree?

thanks for the replies

[sfuo]

Here is a method using recursion that you could use.

If you would want this to work with rocket mania then you would need to do checking to see if the two pipes line up rather than just replacing the character like the function does below.

#include <iostream>
#include <cstdlib> //remove this if you are not using windows/dont want time delay redraw
#include <cstring>
#include <ctime> //remove this if you are not using windows/dont want time delay redraw

using namespace std;

void Print(char[][5]);

size_t resetTime = clock(); //remove this if you are not using windows/dont want time delay redraw

void Search(int x, int y, char board[][5])
{
	if(board[x][y] != 'o')
		return;
	board[x][y] = '*';
	Print(board); //remove this if you are not using windows/dont want time delay redraw
	if( x > 0 )
		Search(x-1, y, board);
	if( y > 0 )
		Search(x, y-1, board);
	if( x < 4 )
		Search(x+1, y, board);
	if( y < 4 )
		Search(x, y+1, board);
}

void Print(char board[][5])
{
	while( clock() - resetTime < 500 ){}; //remove this if you are not using windows/dont want time delay redraw
	resetTime = clock(); //remove this if you are not using windows/dont want time delay redraw
	system("CLS"); //remove this if you are not using windows/dont want time delay redraw
	for( int i = 0; i < 5; i++ )
	{
		for( int c = 0; c < 5; c++ )
			cout << board[c][i] << " ";
		cout << endl;
	}
	cout << endl << endl;
}

int main()
{
	char board[5][5];
	memset(board, 'x', 25);

	board[0][2] = 'o';
	board[1][2] = 'o';
	board[2][2] = 'o';
	board[2][3] = 'o';
	board[2][1] = 'o';
	board[3][1] = 'o';

	Print(board);
	Search(0,2,board);
	//Print(board); //add this if you are not using windows/dont want time delay redraw

	return 0;
}

If you run this you will see that the flow at junctions is odd because it goes off on one path then comes back and takes the other after the first one is completed.

[gusano79]

sfuo provided some concrete code examples; here's some theory:

Hi, I already tried searching through the array of tiles/pipes,
but I encountered a problem, since my current loop only searches downward,
I thought, what if the fuel is .. flowing up/ going northward(caused by tile/pipe orientation)

Right. This is why you should start thinking of your tiles as a graph, not an array. The actual implementation might be an array, but the graph concept provides a better perspective for spreading fuel throughout the system.

I think the solution requires adding another array search, but in a different direction
this requires more "for loops", making the code long/messy, and might make the game run slow.

You're on the right track with the "different direction" idea, but it's not an additional array search with a bunch of for loops. It's one search through the whole system, but not ordered by the shape of the array.

as for breadth-first search, Im still confused and cant think of a way to put my tiles/pipes into a tree...
bec. of the possibility that a child can have 3 parents and the child can also have 3children.

It's not a tree, it's a graph. A tree is a type of graph, but it's not what you want. A graph has no explicit root node, and there are no children, just connections between nodes. The article on graphs I linked above has a nice example of a graph. Yours would have the nodes arranged in a rectangular grid, with edges between nodes in the cardinal directions.

my destination is the rockets,
if a connection is made between the fuel and the rocket, then
I remove the nodes that are connected.

Is there a better way to do my array search, or anyone can teach me how to put tiles/pipes into a tree?

The basic process is this:

1. Keep track of tiles you've checked. This list starts empty.
2. Keep track of the next tiles to check. This list starts with just the fuel tile.
3. With each "next" tile:
   • Add it to the "checked" list.
   • Look at the four connected tiles (N, E, S, & W) to see if they're already in the "checked" list; ignore the ones that are.
   • If there are any connected tiles that haven't been checked yet, check to see if fuel will flow to them (pipes line up), and let if flow if it can.
   • Add all of the unchecked tiles to the "checked" list, if any.
   • Add all of the newly-fueled tiles to the "next" list, if any.
4. As long as there are tiles in the "next" list, go back to step 3. If the "next" list is empty, you're done.
5. If the rocket tile got fueled, *BOOM*!

There are other methods to do the search, recursion being one example; this is the loop version.

This may seem a little overkill for what you're working on now, but graphs and graphing algorithms show up all sorts of places in software. I recommend you get comfortable with the concepts so you have them in your programming toolbox.

[daniel955]

@gusano
sorry, I didnt notice it said graph, because I saw the picture that looked like a tree :(
plus I only experienced breadth-first on tree traversal.
For now I will research on graph theory.

I'm pretty busy with other subjects right now, but I'll bring news on applying what you have taught me.
Thanks all ^^

[daniel955]

Hello again, I have succesfully applied breadth-first with the use of arrays
here is the result of the rocket mania clone
[IMG]http://img838.imageshack.us/img838/3435/successn.jpg[/IMG]

it goes like this
every time rotateTile is called.
1. clear tile's fuel property
2. clear checklist
then call search

search loop
1. start at the left most part of the gameboard
2. check if current tile is in checked list, if it is checked then break.
3. check if there is a link b/w the four adjacent tiles.
4. if linked then give fuel to the four adjacent tiles.
5. send the current tile to the checked list.
6. do the search again to the adjacent tiles.

guys thank you so much for you help
thank you sfuo for giving samples, it really helped a lot
and thank you gusano for your time and for teaching me about graph theory
and the fueling process.

:*:*:*

[Nisa_1]

Are you still work on this game?

[JamesCherrill]

After 4 years???

[Nisa_1]

Because i'm a newbie in programming, and i found the same problem with daniel955, that's why im asking T_T