Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a Model(I use the MVC pattern), that holds an 2D Array with Tile objects.

A tile object have a member, whether it burns or not, a member how long it takes until the neighboring tiles get fire too and a member with the elapsed time how long the fire already burns on this tile.

My problem is, that my only solution is, to iterate threw all tiles and check whether the tile burns. If yes, count down the elapsed time. Than check, whether the maximum time is reached and set the fire member of the neighboring tiles to true.

In small maps it works, but in bigger maps not(Too many computing power). Whats the fastest way to filter the burning tiles out of the array, so I can do logic with them ?

A idea from me was to create a extra list that holds a reference to burning tiles, but that's difficult, because the list can be get out of sync with the array(Because the MVC pattern the array is public so it can be modified without to change the list with the fire tiles).

I have problems to implement this. So maybe someone can show me a code example. Here my current state: I have a class Tile:

public class Tile 
{
    public static final int TILE_NORMAL = 0;


    private int type;
    private boolean burning;


    public Tile(int type)
    {
        this.type = type;

        burning = false;
    }


    public int getType()
    {
        return type;
    }
    public void setType(int type)
    {
        this.type = type;
    }

    public boolean getBurning()
    {
        return burning;
    }
    public void setBurning(boolean burning)
    {
        this.burning = burning;
    }
}

Than I have a class TileMap, too:

public class TileMap
{
    private Tile[][] tiles;


    public TileMap()
    {
            // That's only provisionally, later loading from a file
        tiles = new Tile[2][2];
        tiles[0] = new Tile[2];
        tiles[1] = new Tile[2];

        tiles[0][0] = new Tile(Tile.TILE_NORMAL);
        tiles[1][0] = new Tile(Tile.TILE_NORMAL);
        tiles[0][1] = new Tile(Tile.TILE_NORMAL);
        tiles[1][1] = new Tile(Tile.TILE_NORMAL);

        tiles[0][0].setBurning(true);
    }


    public Tile[][] getTiles() 
    {
        return tiles;
    }
    public void setTiles(Tile[][] tiles) 
    {
        this.tiles = tiles;
    }
}

This class(TileMap) is placed into another class named "World". The world class is the big Model that contains all other models like players enemies .... To render the world I have a world renderer, that has a reference to the world object and every time I call the render method from the renderer, the renderer take for example the tile map from the world reference and iterate threw all tiles to draw them.

At last, I have a tile map controller. This class have a reference to the world, too. Every time the update method from it is called it do the logic for all world objects/models.

So now back to the actual question. How would you implement the event queue for the fire and maybe for such things like that? I am sorry and thanks for the patience :)

share|improve this question
    
Just store a list with references to the burning tiles, not copies of the tiles. –  Byte56 Mar 9 at 16:43
    
But the Array where the tiles are stored can be modified directly.So, if I replace a old tile that has fire with a new tile, the list is not sync with the tile array. –  user2933016 Mar 9 at 18:41
    
Basically any time when you need to handle a multitude of upcoming events and you know the time they"ll occur in advance, then you should add these events to a priority queue and always handle the closest event. Once it occurs, the second closest event will become the closest one and you handle it and so forth until no events are left. –  Zehelvion Mar 9 at 19:17
add comment

3 Answers 3

up vote 1 down vote accepted

I have found that a list of burning tiles was an adequate solution. Here's how I solved the problem you mentioned, which was that list references can become stale:

Each item stored in the list is a reference to an object that is somehow "aware" of its own state. You accomplish this with your Tile.getBurning() method. This allows your TileMap to implement something like this:

private List<Tile> burningTiles;
public void BurnTileAt(int x, int y) { 
  getTileAt(x, y).setBurning(true);
  burningTiles.add( getTileAt(x, y) ); 
}
public void UpdateBurningTiles(float delta) {
  for (int i = burningTiles.length - 1; i >= 0; i--;){
    Tile t = burningTiles.get(i);
    // check that the Tile still belongs in this list (external changes)
    if (t.getBurning()) {  
      // contrived code scenario which priority queue would struggle to solve.  :)
      t.burnTime -= ( this.getRoomOxygen() * t.getBurnSpeed() * delta );
      if (t.burnTime <= 0) { 
        t.IgniteNieghbors(); 
        t.setBurning(false); //on the next pass, it will be removed.
      }
    } else {
      burningTiles.remove(i);
    }
  }
}

This code would depend on a few extra properties in your Tile class:

// public class Tile { ...
public int x, y;  // a Tile knows its own position
public float burnTime;
public static final float TOTAL_BURN_TIME;
public float burnSpeed;
public TileMap tileMap; // a Tile knows its container

public void setBurning(boolean burning){
  this.burning = burning;
  this.burnTime = TOTAL_BURN_TIME;
}

public void IgniteNeighbors(){
  tiles.add(tileMap.getTileAt(x - 1, y)).setBurning(true);
  tiles.add(tileMap.getTileAt(x + 1, y)).setBurning(true);
  tiles.add(tileMap.getTileAt(x, y - 1)).setBurning(true);
  tiles.add(tileMap.getTileAt(x, y + 1)).setBurning(true);
}
// ...

This should solve your problem of large maps; only the burning tiles need burning updates. And by removing tiles that have already burned through their timer, you can (feasibly) keep the list short enough to update each frame.

Just for fun, here's my prototype in which I faced this problem: My clone of PyroII, which was a clone of Firebug


Aside, about your TileMap. By doing this:

private Tile[][] tiles;
public Tile[][] getTiles() { return tiles; }
public void setTiles(Tile[][] tiles) { this.tiles = tiles; }

You are gaining no encapsulation whatsoever. This is a semi-famous programming style opinion. But the real problem is that all your other code will still be tightly bound to that 2d array structure, so you won't be able to change it. If instead, you did this:

public getTileAt(int x, int y) { return tiles[x][y]; }

...you would have freedom to change implementation later. Performance would probably suffer if you iterated every tile this way. But you could expose other methods to operate on large chunks of the data all at once.

share|improve this answer
    
I edited my question, because I have still problems to implement this, maybe you understand my problem or can show me a code example. –  user2933016 Mar 10 at 15:40
    
Of course, I think I can express my answer in terms of the code you posted. I will edit later in the day. –  Seth Battin Mar 10 at 17:39
    
Thanks :D very much ! –  user2933016 Mar 10 at 19:32
    
There you go. I put a lot of my opinion in there, but hopefully I covered the particular problem you faced. Good luck. –  Seth Battin Mar 11 at 4:53
    
Ok thanks for help:D –  user2933016 Mar 11 at 13:18
add comment
  1. You should create a priority queue binary heap to keep track of burning tiles. The priority here is determined by the amount of time left until the event of interest occurs, in this case from what you asked I presume that is the time when the neighbouring tiles will be set ablaze.

  2. You shouldn't loop and decrease the delta from each of them. You should pre-calculate the time in which the tile will set neighbouring tiles on fire in advance and save that time as the tiles priority value.

  3. You should check if that condition is met with the tile of the highest priority (the one of the top of the heap). If that time was reached you delete it (from the heap). Then check the new (best) tile with the highest priority.

    This is much more computationally efficient. Also, like Byte56 said, you could store pointers to tiles or do whatever workaround is needed to avoid the issue you describe with modifying the array. Besides, the array shouldn't be public, it should only be accessed with accessors.

share|improve this answer
    
This is the data structure class: docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html –  Zehelvion Mar 9 at 17:14
    
I read the doc, but I dont understand for what i need the priority queue binary heap? What did you mean with items ? –  user2933016 Mar 9 at 18:48
    
@user2933016 I modified the answer, items in this case are tiles that are on fire. You don't check all of them all the time. You put them in a heap and only need to check the ones that are closest to the point in time they"ll begin burning other tiles. –  Zehelvion Mar 9 at 19:01
add comment

Have you considered using an array list adding the co-ordinates as you go

Firelist Firea = ...
Firelist Fireb = ...

List<Firelist> Fires = new ArrayList<Firelist>();
lines.add(Firea);
lines.add(Fireb);
...
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.