Archived

This topic is now archived and is closed to further replies.

Firestar_Jesper

Problem in my game

Recommended Posts

Hi I'm new to these forums, but i hope you guys can help me I'm creating a game where the object is to remove "Gems" that are the same color from the game area. You click on one gem, and then every gem that has the same color and is connected to the one you click disappear. Probably should mention that it is a 2D game, and that only "Gems" that are above,below, left and right of the gem will be removed. Now my problem is how do you determine which gems are connected I can't for the life of it figure out how to do this. Firestar_Jesper [edited by - Firestar_Jesper on March 21, 2004 9:48:44 AM]

Share this post


Link to post
Share on other sites
Penten    620
If your game is tile based you could just brute-force through every tile around the one clicked on and see if there's a gem of the same color next to it, then start again on that tile, and again and again untill there are no more gems of that color connected.
[edit]typo[/edit]


[edited by - PenTen on March 21, 2004 9:52:58 AM]

Share this post


Link to post
Share on other sites
Yes the game is Tilebased and that was one of the ideas i considered

Was just wondering if there wasn't a better way to do it

But i guess i could just do it by Brute force

[edited by - Firestar_Jesper on March 21, 2004 10:00:25 AM]

Share this post


Link to post
Share on other sites
Kafeen    122
Store all their positions in a 2D array and then just add and subtract 1 from the x and y indicies into the array to check the gems on each side.

Share this post


Link to post
Share on other sites
bangz    119
You could do something kinda swanky whereby you store your data in a linked list and each element stores pointers to the elements left, right, up and down from it (pointer = NULL if there isn''t a connected element in that direction). You would also store another array with pointers to each element, kinda like an index. If you clicked on an element it would look it up in the index, get the pointer to the linked list element and recurse its way to a solution.

I think with this data specification you could code quite an elegent recursive solution (although prehaps not the easiest to implement).


Good luck,
bangz.

http://www.bangz.co.uk

Share this post


Link to post
Share on other sites
BdR    177
I once programmed a similar problem in BlitzBasic, i used a 2D array and then used recursive function calls. I'll try to explain in pseudo code. Note that you'll ofcourse have to take into acount that you stay within the array limits 10x10 but that is irrelevant here, i'll leave that up to you :D


Dim ArrayColours(10, 10) ; the colours of the gems
Dim ArrayTags(10, 10) ; helper array

Function TagColourGroupStartAt(StartX, StartY)

; clear the tags array
For y = 1 to 10
For x = 1 to 10
ArrayTags(x, y) = False
Next x
Next y

; start
TagAllConnectingColours(StartX, StartY)

End Function

Function TagColours(StartX, StartY)

; if gem was already tagged as part of the colour-group
; then exit, else an infinit loop will occur (program locks up)
If (ArrayTags(StartX, StartY) = True) Then Exit Function

; remember the colour and tag this grid position
iColour = ArrayColour(StartX, StartY)
ArrayTags(StartX, StartY) = True

; check above, if same colour do a recursive function call
If (ArrayColour(StartX, StartY-1) = iColour) Then TagColours(StartX, StartY-1)

; check below, if same colour do a recursive function call
If (ArrayColour(StartX, StartY+1) = iColour) Then TagColours(StartX, StartY+1)

; check left, if same colour do a recursive function call
If (ArrayColour(StartX-1, StartY) = iColour) Then TagColours(StartX-1, StartY)

; check right, if same colour do a recursive function call
If (ArrayColour(StartX+1, StartY) = iColour) Then TagColours(StartX+1, StartY)

End Function


hope it helps

edit: added source-tags

[edited by - BdR on March 21, 2004 4:06:16 PM]

Share this post


Link to post
Share on other sites
Xai    1838
the details of how you to the item above / below / let /right of a current item should "ideally" be wrapped in one place, and hidden from the rest of the code ... inline functions jump out at me as a good compromise - giving you performance AND clarity ...

if you ever find yourself writing code like:

Visit(board[current->y][current->x]);

in multiple places in your program, you will find inline functions that do something like:

inline Item* GetLeft(current);

can help your code readability a lot ... and of course, then you have a simple place to put boundry checking (you know, when they are at the edges of the board) .. you can return 0 (NULL).

Share this post


Link to post
Share on other sites
Xai    1838
As for the intial question, this algorithm is recursive (although all recursive algorithms can be written as iterative algorithms using a stack - they are just a special case of general iterative algorithms)

the easiest way I see to break the problem down is to do something like this:


//create an empty visited list.

std::set<Item*> visitedNodes;
//create an empty connected list.

std::set<Item* connectedNodes;
//call Visit to start the process;

Visit(initialGem, visitedNodes, connectedNodes, initialGem->GetColor());

//that's it ... now of course inside of Visit.


void Visit(Item *currentNode, std::set<Item*> &visitedNodes, std::set<Item*> &connectedNodes, SomeType somePropertyToMatch)
{
if(visitedNodes.find(currentNode) == visitedNodes.end())
{
visitedNodes.insert(currentNode);

if(currentNode->GetSomeProperty() == somePropertyToMatch)
{
connectedNodes.Insert(currentNode);
if(currentNode->GetLeftItem() != 0)
Visit(currentNode->GetLeftItem(), visitedNodes, connectedNodes, somePropertyToMatch);
if(currentNode->GetRightItem() != 0)
Visit(currentNode->GetRightItem(), visitedNodes, connectedNodes, somePropertyToMatch);
if(currentNode->GetAboveItem() != 0)
Visit(currentNode->GetAboveItem(), visitedNodes, connectedNodes, somePropertyToMatch);
if(currentNode->GetBelowItem() != 0)
Visit(currentNode->GetBelowItem(), visitedNodes, connectedNodes, somePropertyToMatch);
}
}
}


well, that is highly UN-optimized - but it should be a start ... assuming I didn't miss any boundry conditions and such ...

good luck.


[edited by - Xai on March 21, 2004 4:32:42 PM]

Share this post


Link to post
Share on other sites
oliii    2196
the recursive method is simple enough. Start off one point, check the neighbours of that point, then check the neighbours of those points, and so on...



enum { eMaxLinkedGems = 256 };
Gems LinkedGems[eMaxLinkedGems];
int iNumLinkedGems = 0;

void FindLinkedGems(CGem Gem)
{
iNumLinkedGems = 0;
ProcessGem(Gem);
}

bool AddGemToList(CGem Gem)
{
if (iNumLinkedGems == eMaxLinkedGems)
return false;

for(int i = 0; i < iNumLinkedGems; i ++)
{
if (LinkedGems[i] == Gem)
return false;
}

LinkedGems[iNumLinkedGems++] = Gem;
return true;
}

void ProcessGem(CGem Gem)
{
if (!AddGemToList(Gem))
{
return;
}

float point[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, {0, 1} };

for(int i = 0; i < 4; i ++)
{
CGem* pGem = Board.GetGem(Gem.x + point[i][0], Gem.y + point[i][1]);

if (pGem && pGem->Color == Gem.Color)
{
ProcessGem(*pGem);
}
}
}

Share this post


Link to post
Share on other sites