How to iterate tiles around an index tile?

Question

I am not exactly sure how to state this question, what I basically want to do is to seed a tile based map with some values. So I asked myself how I could spread some values outgoing from a start tile, with values being reduced the further I get away from that start tile. Does that make any sense? What algorithms are there to calculate spreading of fire for example, or pollution?

[0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,
 0,0,0,0,S,0,0,0,
 0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,
 0,0,0,0,0,0,0,0,]

[0,0,0,0,0,0,0,0,
 0,0,2,2,2,2,2,0,
 0,0,2,3,3,3,2,0,
 0,0,2,3,X,3,2,0,
 0,0,2,3,3,3,2,0,
 0,0,2,2,2,2,2,0,
 0,0,0,0,0,0,0,0,]

And what if I have another starting tile, can the values be added?

[2,3,3,3,2,0,0,0,
 2,3,Y,5,4,2,2,0,
 2,3,5,6,5,3,2,0,
 2,2,4,5,X,3,2,0,
 0,0,2,3,3,3,2,0,
 0,0,2,2,2,2,2,0,
 0,0,0,0,0,0,0,0,]

Maybe it's like an explosion. Not sure what to look for though, I cannot find anything in my endless searches on tile based games.

Answer 1

This looks like a job for Breadth-First Search. The algorithm in this case would work like this...

1. Initialize a "Concentration" value for each tile to 0.

2. For each source tile, initialize its Concentration value to your desired peak at that point, and add it to a Queue of tiles.

3. While the queue is non-empty...

   i) remove the first tile from the queue and call it the "Parent" for this round

   ii) for each (passable) "Child" tile neighbouring the Parent...

   if the Child tile's Concentration is less than the Parent's Concentration minus one:

   • Set the Child tile's Concentration to the Parent's Concentration minus one, and...
   • Add the Child tile to the end of the Queue (Optionally: only do this if its concentration is > 1, so we skip redundant iteration at the outermost edges)

This will give you a linear falloff by hopcount from the nearest source. Note that doing it this way, the space between two sources will choose the larger of the concentration values from the two sources affecting it, rather than summing them together.

If you'd prefer to sum the concentration values, you'd make the following changes to the algorithm above:

• Also track a "Total Concentration" value for each tile.

• Whenever you set the Concentration value, add that number to the Total Concentration

• Process your sources one at a time. Ie. Add your first source to the queue, iterate until it's empty, then clear your Concentration values and add your second source to the queue...

---

Note that this handles the most general case of arbitrary tile connections, where tiles could be obstructed and the concentration needs to "flow around".

If instead all you need is to stamp a pyramid values in a square region of your grid, ignoring obstacles, you could do this by...

• iterating over the square region (startX - range, startX + range)x(startY - range, startY + range) and...

• adding the value (range - max(abs(x - startX), abs(y - startY)) + 1) at each tile