Sign in to follow this  

avoiding infinite loop

This topic is 4856 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm making a game with a board and some pieces. There are two players. In turn, they put a pice on the board, in an empty cel or in a cel owned by themself. When a cel contains more than their critical mass, it explodes, and the closest cels gain a piece and are conquered by this player. I have a problem with the algorithm that performs these explosions: sometimes it enters in a infinite loop. Here's the code:
  public void Explode(int _x, int _y, boolean player)
  {
    LinkedList list = new LinkedList();
    String move; //move[0] is the x coord e move[1] is y coord int x = _x, y = _y;
    move = new String(Integer.toString(x)+Integer.toString(y));
    
    list.addLast(move);
    //Let's begin with the explosion loop
    for(int i = 0; i < 500; i++)
    {  
      if(list.isEmpty()) break; //There are no more elements
      move = (String)list.getFirst();
      x = Character.getNumericValue(move.charAt(0));
      y = Character.getNumericValue(move.charAt(1));
      System.out.println(list.size());
      list.removeFirst();
            
      SetCelCurrent(x, y, 0);
      //Distribuiamo le pedine
      if(x - 1 >= 0)
      {
        SetCelCurrent(x-1, y, GetCurrent(board[x-1][y]) + 1);
        SetCelOwner(x-1, y, player);
        if(GetCelCurrent(x-1, y) > GetCelMax(x-1, y))
        {
          move = new String(Integer.toString(x-1)+Integer.toString(y));   
          list.addLast(move);
        }
      }
      if(x + 1 <= 5)
      {
        SetCelCurrent(x+1, y, GetCelCurrent(x+1, y) + 1);
        SetCelOwner(x+1, y, player);
        if(GetCelCurrent(x+1, y) > GetCelMax(x+1, y))
        {
          move = new String(Integer.toString(x+1)+Integer.toString(y));   
          list.addLast(move);
        }          
      }
      if(y - 1 >= 0)
      {
        SetCelCurrent(x, y-1, GetCelCurrent(x, y-1) + 1);
        SetCelOwner(x, y-1, player);
        if(GetCelCurrent(x, y-1) > GetCelMax(x, y-1))
        {
          move = new String(Integer.toString(x)+Integer.toString(y-1));   
          list.addLast(move);
        }
      }
      if(y + 1 <= 4)
      {
        SetCelCurrent(x, y+1, GetCelCurrent(x, y+1) + 1);
        SetCelOwner(x, y+1, player);
        if(GetCelCurrent(x, y+1) > GetCelMax(x, y+1))
        {
          move = new String(Integer.toString(x)+Integer.toString(y+1));   
          list.addLast(move);
        }
      }    
    }
  }

In short, it since the thing is intrinsecally recursive (but I cannot use recursion due to specifics) I do a breadh-first-search using a queue. Could someone tell me how to avoid infinite loop? Sorry for the length, and thank you!

Share this post


Link to post
Share on other sites
Your problem is a design problem, not really a programming problem.

It depends on this: if the critical mass is less or equal than the total mass generated by an explosion, you are bound to have an infinite loop at some moment or another (when the total mass on the board becomes greater than the sum of all critical masses), where explosions will cause other explosions without ever stopping. The game will enter an infinite loop, because this is the normal, expected behavior. You cannot prevent this infinite loop without changing the game rules.

On the other hand, if the critical mass is bigger than the total mass generated by an explosion, no problem there: the sum of all masses in all cells will decrease at each explosion, eventually there won't be enough mass to cause any more explosions, so there will not be infinite loops.

There is, however, one more case. If the cells on the edges have the same critical mass as other cells, you will not have infinite loops either: an edge cell gets to distribute less mass than a center cell, which causes a decrease in total mass when explosions occur on the edges.

Remember, without loss of mass somewhere in your system, you cannot prevent infinite loops.

Share this post


Link to post
Share on other sites
You also have a programming problem. Well, some.

1- You don't take into account simultaneous explosions. A good way to manage this is to determine all the cells that should be exploding, remove mass from the exploding cells and adding all potential explosions to a list, and then once you have detected all the explosions, perform them, thus generating a new board. Repeat this process for the new board until there are no more cells that need to explode. ONLY add items to your list during the explosion-detection phase, NOT when you actually compute the results of the explosions in the list:

- Compute list of cells that are above the critical mass.
- If the list is empty, you're done.
- Remove all mass from each cell in the list.
- For each cell in the list, add some mass to the nearby cells, and remove from the list.
- Go back to beginning.

2- In your current code, you add an explosion more than once to the list. If three cells explode near a cell at nearly-critical mass, each cell will add a mass unit to it, causing it to be added to the explosion list. This will make the cell explode three times, which is incorrect. Always compute the effects of all explosions in the list before searching for new explosions to add to the list.

EDIT: if you want to keep your current code system, you could perform the following instead of my previous algorithm:

1- When a move is performed, add the target cell to list A.
2- If list A and list B are empty, you're done.
3- For each cell in list A, find if it should explode by looking at its Mass. If it should explode, set its mass to 0, and add it to list B.
4- Empty list A.
5- For each cell in list B, add some mass to nearby cells, and add those nearby cells to list A.
6- Empty list B.
7- Goto 2.

Share this post


Link to post
Share on other sites
Although it could be a design problem, I don't see any infinite loop in the code you posted. The for loop starts, finishes, and increments correctly, and there are no recursive calls shown.

Share this post


Link to post
Share on other sites
I assume the for loop was put in there to avoid infinite looping in the first place. However, it's an ugly ugly hack. The "correct" code should look like:

while( !list.isEmpty() ) {

(note the position of the opening brace ;) )

In which case it's understandable that he can get infinite loops.

Share this post


Link to post
Share on other sites
Thank you very much!! Even if I have already solved the problem using another algorithm (the third!!) I'll implement your tips because my current algo doesn't work exactly as the specs say it should (little differences).

to ToohrVyk: The mass generated from an explosion is the same as the mass removed from the cell exploded. Hey, my code was very bugged! Great work, and thank you!

to iMalc: sorry, I didn't noticed that I didn't removed that for: ToohrVyk was right: I added it just to prevent from infinite loop. The right code was while(true) (as I exit with the break) or the instruction posted by ToohrVyk.

Thank you again!

Share this post


Link to post
Share on other sites
Your entire board can hold only a maximum number of masses before there is an explosion. Once the total mass on the board is greater than this maximum mass, no matter how you spread the mass around, there will always be another explosion. Without a way to remove mass from the system, it's only a matter of time before you create an infinite loop.

Share this post


Link to post
Share on other sites
Once the number of masses reaches the constant-explosions level, you will probably see one or the other player winning. So you could add a test after each iteration to see whether a player has won, and exit the loop if so.

Share this post


Link to post
Share on other sites
Quote:
Original post by King of Men
Once the number of masses reaches the constant-explosions level, you will probably see one or the other player winning. So you could add a test after each iteration to see whether a player has won, and exit the loop if so.


Yes, it's what I did. Since my previous algo was bugged, it didn't worked, but with the current one, it works... thank you!

Share this post


Link to post
Share on other sites

This topic is 4856 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this