Tile map propagating fire

Question

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 :)

Answer 1

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:

---

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.

Answer 2

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.

Answer 3

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);
...