2D PHP template creation algorithm

Question

I am looking for an algorithm that will help me build rule-based 2D templates. The idea is that I could write a script using the given site parameters, and it will return a random two-dimensional sequence to a certain length.

My plan is to use this to create rule-based image templates. Things like image fractals or sprites for game levels could use this.

For example, let's say that you can use A, B, C, and D to create a template. The rule is that C and A can never be next to each other and that D always follows C. Next, say, I want a 4x4 template. The result may be the following, which complies with all the rules.

ABCD BBBB CDBB CDCD 

Are there existing libraries that can perform the calculations as follows? Are there any math formulas that I can read?

Answer 1

While a rather inefficient runtime, backtracking is a commonly used algorithm for such a problem.

This follows a simple pattern, and if it is spelled correctly, you can easily replace the ruleset in it.

Answer 2

Define the structure of these rules; that is, define a set of operations that can encapsulate rules, and determine the available cross-references that can be performed. After that, you should have a clearer idea of ​​what types of algorithms to use to apply these rules to a potential set of results.

Answer 3

Assuming your rules are limited to “type X is allowed to have type Y right to its left / right / top / bottom”, you may have situations where generating possible patterns is difficult in terms of computational complexity. Take a look at Wang Tiles (a good source is the book Tilings and Templates by Grunbaum and Shephard) Let's see that with sets of state rules you can define sets of Wang Tiles. The corresponding sets of them are Turing Complete.

For small rectangles or your rule sets, this may be of academic interest. As mentioned elsewhere, the backtracking approach may be appropriate for your rule set - in this case, you might want to consider the appropriate heuristics for the order in which new components are added to your grid. Again, different approaches may work depending on your rule sets. For instance. if your rule set has many solutions, you can go a long way by randomly distributing many elements in the grid before trying to fill in the remaining spaces.