# 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? – amitp Feb 9 '15 at 16:55
• My same thought, explaining this as cellular automata vs procedural generation do have different descriptions in this context – Coburn Feb 9 '15 at 17:00
• I was always under the assumption that CA involved starting from a root node and expanding outward, hence the "flow" – Kyle Baran Feb 14 '15 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. – amitp Feb 14 '15 at 19:50
• Good call, I just started reading about graphs and stuff, so I might've got my terminology confused -- edited title. – Kyle Baran Feb 16 '15 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. – david van brink Feb 11 '15 at 2:34
• I have updated my answer to reflect the difference between the two. – Coburn Feb 14 '15 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.