I recently found a patent for "rule-based procedural terrain generation", applied by Sony Online Entertainment Inc. Is there any prior art for this patent (i. e., the procedural generation of video game terrain in real time)? Many roguelike video games use real-time terrain generation in gameplay, and I want to know whether this could be considered prior art.

US Patent 8115765

European Patent EP1763846A2

  • If this patent were enforceable, then could the developers of games such as Minecraft, Terraria, Angband, Dwarf Fortress, and Infiniminer be sued for their independent co-discovery of similar methods? I find this possibility to be slightly alarming - I am currently developing a 2D fractal terrain generator for my own video game, and I don't want to risk being sued. Dec 18 '12 at 18:37
  • Take a look at the claims. Is there anything about the claims that would concern you, remembering that infringement requires that every element of the claim be present?
    – m3lvn
    Dec 18 '12 at 19:04

The first claim reads:

  1. A non-transitory computer readable medium including a computer-implemented system for generating terrain in a virtual world, the system comprising:

    • a plurality of procedural rules configured to generate a virtual terrain in the virtual world,

    • wherein said plurality of procedural rules is organized into hierarchical layers such that a single location in the terrain can have multiple procedural rules that overlap and the terrain has at least one location that has overlapping rules, each hierarchical layer defining boundaries, filters, and affectors; and

    • a terrain generator configured to process the plurality of procedural rules so as to generate a virtual representation of the terrain,

    • wherein when multiple procedural rules overlap the terrain generator specifies a blend region and initiates a boundary influence computation to blend heights and colors to prevent hard, visible discontinuities at the overlap of the procedural rules,

    • wherein the plurality of procedural rules is textually represented so that the boundaries, filters, and affectors are assigned numeric values that represent desired attributes in a logical, textual format, and

    • wherein the terrain is modified by adding or deleting at least one rule from the plurality of procedural rules.

I think it's a pretty readable claim, and it doesn't seem too broad. Remember: you need to perform each and every element of each and every bullet point to infringe. So the claim certainly does not cover the broad idea of procedural terrain generation.

Seems to me that the key element of this claim is the clause that talks about "blend regions" where "boundary influence computations" are used to automatically mitigate "visible discontinuities" caused by overlapping rules. As a simplified example (which I'm making up on the spot): if a rule for generating desert terrain overlaps with a rule for generating mountains, you wouldn't want the desert to abruptly end at the boundary and have steep mountains start immediately after; you'd rather have a transition region where the desert gradually ends and the terrain height begins to increase, so that the desert terrain blends into the mountain terrain. This claim covers doing so automatically.

So the element that is covered is somewhat significant; nobody would want to have drastic, unblended transitions in regions. However, the claim is also rather narrow: it specifically mentions blending heights and colors. So it won't apply if you have to transition between drastically different terrains, e.g. from deserts to jungles, where you'd need to manipulate many more parameters than just heights and colors, such as the number and density of trees.

The claim is also narrow in other ways. Even if you happen to do everything required by that clause, I can think of a few trivial work arounds to avoid infringement (not foolproof, since legal theories like the "Doctrine of Equivalents" complicate things):

  • You could simply handle "blend regions" by finding them and editing manually.

  • You could represent your procedural rules in binary format, as the claim requires rules to be "textually represented".

  • You could organize the rules in a fashion other than hierarchical layers (even if they actually are hierarchical.)

So essentially, you are trading off a little development convenience to remove infringement liability. Contrary to what you may read on the web, there are very few patents that are so broad that they cannot be worked around.

And finally, even if you directly infringe the claims, you may be safe because the patent owners, Sony, may:

  1. never find out that you are using this method (for example, if you release pre-generated terrains with the game instead of the generator itself);

  2. and/or they may simply not care.

I am not aware of Sony suing game developers over patent infringement, and I doubt they will want to start doing so, as that would only alienate developers from their platform.

  • ah, but what if @Anderson Green is an xbox developer? :)
    – m3lvn
    Dec 20 '12 at 3:53
  • 1
    Heh heh, true... but that still won't keep him from being a potential PS3 developer! But as this issue merits serious discussion -- I'd guess the game dev community, as a whole, won't be concerned with that distinction; Sony can expect a massive backlash no matter which game dev they sued. It's a finely balanced symbiotic relationship they cannot afford to upset.
    – kinkfisher
    Dec 20 '12 at 19:39
  • @m3lvn I'm actually a JavaScript/Java/HTML developer. :) The generated fractal terrain is displayed using the HTML canvas element. Jan 14 '13 at 21:42
  • @kinkfisher My fractal terrain generator is actually based on a cellular automaton that modifies the map at each level of magnification. After each magnification, a cellular automaton is run for one iteration, and the process can be repeated indefinitely. Different rules can be used at each level of magnification: for example, pixels that represent galaxies are generated at one level, then pixels that represent star clusters are generated at the next level, then individual stars are generated at the next zoom level, and so on. Jan 14 '13 at 23:23
  • @AndersonGreen I can't tell from your limited description, but do you have cases where two or more rules with different pixel effects overlap/collide causing a visual incongruity? If so, do you do something with colors and/or heights (specifically) to "blend" them such that the differences are less visible / more smoothed out? And if you so, do you handle that automatically? If you're not doing all of that (and my hunch is that you're not,) you're nowhere near what these claims cover.
    – kinkfisher
    Jan 16 '13 at 20:08

On first brush, the claim talks about a way to handle the visible discontinuities at the overlap of the procedural rules.

You need to:

1) read the patent

2) see if the prior art you have in mind reads onto each and every feature of the claim(s).

Ignore the patent title! It has no meaningful bearing on claim scope.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.