2D PHP Pattern Creator Altgorithm

Question

I'm looking for an algorithm to help me build 2D patterns based on rules. The idea is that I could write a script using a given site of parameters, and it would return a random, 2-dimensional sequence up to a given length.

My plan is to use this to generate image patterns based on rules. Things like image fractals or sprites for game levels could possibly use this.

For example, lets say that you can use A, B, C, & D to create the pattern. The rule is that C and A can never be next to each other, and that D always follows C. Next, lets say I want a pattern of size 4x4. The result might be the following which respects all the rules.

A B C D
B B B B
C D B B
C D C D

Are there any existing libraries that can do calculations like this? Are there any mathematical formulas I can read-up on?

Just basic rules for now about symbols to the North/East/South/West of the current symbol. I suppose support for symbols within X number of spaces would be neat also (but probably a lot slower). — Xeoncross, Jun 08 '11 at 22:40

score 2 · Accepted Answer · answered Jun 08 '11 at 22:35

2

While pretty inefficient concering runtime, backtracking is an often used algorithm for such a problem.

It follows a simple pattern, and if written correctly, you can easily replace a rule set into it.

answered Jun 08 '11 at 22:35

Femaref

60,705
7
138
176

1

I found this great [example written in JavaScript](http://www.hbmeyer.de/backtrack/backtren.htm). – Xeoncross Jun 08 '11 at 22:43
There also seems to be many [single dimension versions of backtracking](http://stackoverflow.com/questions/2617055/how-to-generate-all-permutations-of-a-string-in-php). – Xeoncross Jun 08 '11 at 22:48
There seems to be a lot of mention of [8-Queens](http://paulbutler.org/archives/n-queens-in-a-tweet/) for this topic so I found a [PHP solution in 303 characters](http://files.dropbox.com/u/396326/nqueens.txt). – Xeoncross Jun 08 '11 at 22:52
I found a great sample using PHP and JavaScript to generate a [heightmap using midpoint](http://procedural.tapirpirates.net/). – Xeoncross Jun 10 '11 at 15:50

score 1 · Answer 2 · answered Jun 08 '11 at 22:39

Define your rule data structures; i.e., define the set of operations that the rules can encapsulate, and define the available cross-referencing that can be done. Once you've done this, you should have a clearer view of what type of algorithms to use to apply these rules to a potential result set.

score 1 · Answer 3 · answered Jun 15 '11 at 12:41

Supposing that your rules are restricted to "type X is allowed to have type Y immediately to its left/right/top/bottom" you potentially have situations where generating possible patterns is computationally difficult. Take a look at Wang Tiles (a good source is the book Tilings and Patterns by Grunbaum and Shephard) and you'll see that with the states sets of rules you might define sets of Wang Tiles. Appropriate sets of these are Turing Complete.

For small rectangles, or your sets of rules, this may only be of academic interest. As mentioned elsewhere a backtracking approach might be appropriate for your ruleset - in which case you may want to consider appropriate heuristics for the order in which new components are added to your grid. Again, depending on your rulesets, other approaches might work. E.g. if your ruleset admits many solutions you might get a long way by randomly allocating many items to the grid before attempting to fill in remaining gaps.

2D PHP Pattern Creator Altgorithm

3 Answers3