CODEWITHSUNDEEP
algorithmdesign-patterns
Xeoncross
Xeoncross

Reputation: 57254

2D PHP Pattern Creator Altgorithm

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?

Upvotes: 4

Views: 390

Answers (3)

borrible
borrible

Reputation: 17376

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.

Upvotes: 1

Paul Sonier
Paul Sonier

Reputation: 39510

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.

Upvotes: 1

Femaref
Femaref

Reputation: 61477

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.

Upvotes: 2

Related Questions