Is there a binary function f(x,y) where x,y are integers and result is 0 or 1, and result 1 in 2d plane are "continous" and "irregular" enough

user_15610547 0
Viewed 78

That is, if f(x,y)=1, then f(x-1,y),f(x+1,y),f(x,y-1),f(x,y+1) at least one results 1.

I'm thinking about a technology to define game map, neither predefined nor random generated each time, but bind to 2d binary function, so the map data will never be saved to disk and each time entering game, the map keeps the same.

If 1 means land and 0 means ocean, I want the lands keep continous, all are reachable, no islands, and of course, the map must be enough irregular. I'm not good at maths, is it possible? thanks.

What I need is only a simple function, no recursions, eg. once xy is given, the result is out, which has nothing to do with other values, only xy.

algorithm
1 Answers

Guaranteeing connectivity with local considerations only is a very strong constraint on what we can do. I agree with the comments that suggest traditional map generation from a fixed seed.

Nevertheless, to answer the question as framed, my first thought would be star-shaped land. This idea requires a continuous function f(θ) > 0 with period 2π. We take every point (x, y) such that hypot(x, y) < f(atan2(y, x)).

This works great if x and y are real numbers -- every (x, y) in the land is connected by a straight line segment back to the origin (0, 0), hence "star-shaped". Over the integers, we have to put an extra condition on f: the function log(f(θ)) should be Lipschitz continuous (can't wiggle too much).

(You can skip this paragraph.) Assume without loss of generality that x > 0 and y > 0 are integers. If (x, y) is land, then we need (x-1, y) or (x, y-1) to be land. On one hand, one of these squares is closer, which is good since we're using a threshold: min(hypot(y, x-1), hypot(y-1, x)) <= hypot(y, x) - (sqrt(2) - 1), which is tight for (x, y) = (1, 1). On the other hand, the angle changes. We've deviated from the line segment by distance at most 1/sqrt(2). Let r = hypot(x, y). The change in angle is at most 1/sqrt(2) / (r - 1/sqrt(2)), which since r >= sqrt(2) is at most 1/sqrt(2) / (r - r/2) == sqrt(2) / r. Therefore a Lipschitz constant of (sqrt(2) - 1) / sqrt(2) = 1 - 1/sqrt(2) should suffice (probably this can be tightened).

So far this is very abstract. The classic way to get a periodic function that doesn't wiggle too much is by adding sine waves (with varying phases). I've provided a Python implementation and sample output below. The land is not 100% guaranteed to be connected, but it should be extremely unlikely.

import math
import os
import random


def make_parameters(n=20):
    return [
        (random.random() / (i + 1), 2 * math.pi * random.random()) for i in range(n)
    ]


width = 100


def is_land(parameters, x, y):
    if (x, y) == (0, 0):
        return True
    theta = math.atan2(y, x)
    return math.hypot(x, y) < 0.1 * width * math.exp(
        sum(
            amp * math.sin((i + 1) * theta + phase)
            for i, (amp, phase) in enumerate(parameters)
        )
    )


def main():
    dir = "lands"
    os.mkdir(dir)
    for i in range(10):
        for j in range(10):
            with open(os.path.join(dir, "%02d_%02d.pbm" % (i, j)), "w") as f:
                parameters = make_parameters()
                x0 = y0 = width // 2
                print("P1", file=f)
                print(width, width, file=f)
                for y in range(width):
                    print(
                        *(
                            int(is_land(parameters, x - x0, y - y0))
                            for x in range(width)
                        ),
                        file=f
                    )


if __name__ == "__main__":
    main()

enter image description here

user_21446690
Related