# How can I use graph traversal to generate a round region?

I was playing a tile-based game and noticed it used what appeared to be a circular shape for the light sources.

How can I generate something similar?

My understanding of cellular automata is that each cell's value is generated based on its neighbours. I had always assumed that every node had to have the exact same behavior, but it looks like the 4's have different behavior.

• I'm curious — why do you want to use cellular automata for this? Feb 9, 2015 at 16:55
• My same thought, explaining this as cellular automata vs procedural generation do have different descriptions in this context Feb 9, 2015 at 17:00
• I was always under the assumption that CA involved starting from a root node and expanding outward, hence the "flow" Feb 14, 2015 at 9:19
• CA doesn't start from a root node and expand; it evaluates all nodes equally. You may be thinking of graph traversal algorithms. Feb 14, 2015 at 19:50
• Good call, I just started reading about graphs and stuff, so I might've got my terminology confused -- edited title. Feb 16, 2015 at 9:38

In the context of cellular automata in second picture, it looks as though the 5 cell might represent a different cell type such that other cells recognize it as a source even if they are separated diagonally. (as @david van brink has shown).
In the context of procedural-generation, it looks rather that the the 5 tile has different behavior from the rest, propagating to not only adjacent tiles but also diagonals while all the rest propagate to just adjacent tiles.

Simple cellular automata might have a simple set of rules where each cell follows a given global behavior but there's nothing that says you must implement your propagation calculations in such simple terms. This is why the idea of cellular automata might not be what you actually want to ask about but just procedural generation in general.
To answer your question, you could define a separate type of tile, say a source tile, which propagates more strongly than just a normal tile. Instead of propagating to just strictly adjacent tiles, it would also propagate to diagonals as well and the rest would carry to adjacent tiles like normal.

• The "5" cell doesn't "push" to adjacent cells; cellular automata requires you to phrase the world such that each cell can compute its own next state, based on its "neighborhood". What the "neighborhood" contains can be defined arbitrarily, as long as all the cells follow the same rule. Feb 11, 2015 at 2:34
• I have updated my answer to reflect the difference between the two. Feb 14, 2015 at 18:19

IF this were generated by cellular automata -- It probably wasn't. But the question is sort of interesting, so -- then a plausible algorithm would be:

 start with a field empty but for a single cell marked "5".
each iteration apply the following algorithm to every cell simultaneously:
if not blank, do nothing,
// omit next line to get output on left, include for output on right
else, if you have a diagonal neighbor "5", mark yourself "4"
else
let N = max(non-diagonal neighbors) - 1
if N > 0, mark yourself N
else do nothing


Every cell can follow this algorithm, and end up with the pattern posted. And yeah... having a friend called "5" is special, but all cells follow the same rule.