Generate Green Spray Paint Patterns

Question

This challenge is about creating these neat "green spray paint" patterns: (more pictures below)

Loosely explained, they are generated by starting with a black image and a point in the center. That point is successively moved by a randomly chosen offset or delta in x and y. Every pixel the point visits has 1 added to its green color channel. This process is then repeated with many many more points, all starting from the center, generating an entire green pattern.

Your task is to write the shortest program possible that takes in the necessary parameters and displays or outputs the resulting green spray paint image. This is code golf so the shortest code in bytes wins!

Specifics

The images require the following parameters, which must be inputs to your program in any order you choose:

• Positive integer S is the width and height (Size) of the output image in pixels.

• Non-negative integer N is the number of points to move over the image one by one, each adding a trail of green.

• Non-negative integer M is the maximum number of moves that each point can take. (Without this they'd never stop.)

• D is a list of pairs of integers [(dx1, dy1), (dx2, dy2), ...] that are deltas each point may be offset by each move.

  • You may also take this flattened [dx1, dy1, dx2, dy2, ...] or as two lists [dx1, dx2, ...] and [dy1, dy2, ...].

Generate the patterns by starting with a pure black S×S pixel image. Then repeat the following process N times, after which your image will be ready to be output:

1. Start a point in the center of the image. (This means (floor(S/2), floor(S/2)) for most image coordinate systems.)
2. Add 1 to the green color channel of the pixel currently below the point (up to a max of 255).
3. Consider moving the point by each of the deltas in D so it becomes like (x + dx, y + dy). Keep track of the valid moves.
   • A valid move is one that keeps the point inside the bounds of the image, i.e. over a pixel.
4. If there are no valid moves or the current point has taken M moves then stop and restart at step 1 with a new point.
5. Otherwise, have the current point take a random valid move. Every valid move should have an equal chance.
6. Go to step 2 to move the current point again.

Your implementation does not need to follow these precise steps as long as the results produced are the same. Of course they won't be exactly the same due to randomness, but it's easy to visually tell when things are working as expected.

Be sure to keep these corner cases in mind:

• When N is 0 there are no points so the output should always be a totally black S×S image.

• When M is 0 or D is empty it means no moves can be made, so only the starting pixel will have color. (See example 5.)

• D may contain duplicate values that are valid moves, effectively meaning that move is more likely. (See example 7.)

Reference Program

Ungolfed reference code in Python 3. Not strictly a solution since it is hardcoded to output the first example from above.

S = 250
N = 800
M = 7000
D = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)] # chess knight moves

import random
from PIL import Image
img = Image.new('RGB', (S, S), 'black')
pix = img.load()
for i in range(N):
    if (i + 1) % 10 == 0: print(f'{(i + 1)/N:.1%}') # progress tracker, not required output
    x, y, = S//2, S//2
    m = 0
    while True:
        pix[x, y] = 0, pix[x, y][1] + 1, 0
        valid = [(x + dx, y + dy) for dx, dy in D if 0 <= x + dx < S and 0 <= y + dy < S]
        if m >= M or not valid: break
        x, y = random.choice(valid)
        m += 1
#img.save('spraypaint.png') # uncomment to save image
img.show()

Examples

1. S = 250
   N = 800
   M = 7000
   D = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)]
   

   (from above)

2. S = 250
   N = 1000
   M = 3000
   D = [(2, -1), (-2, -1), (-3, 0), (4, 0), (0, 2), (0, -1)]
   

   (from above)

3. S = 250
   N = 400
   M = 10000
   D = [(60, 59), (60, -59), (-59, 60), (-59, -60)]
   

   (from above)

4. S = 400
   N = 600
   M = 10000
   D = [(0, 1), (-1, 0), (0, -1), (1, 0)]
   

   

5. S = 51
   N = 1000
   M = 1000
   D = []
   

   

6. S = 51
   N = 1000
   M = 1
   D = [(-5, 5), (9, 9), (-15, 1), (20, -25)]
   

   

7. S = 300
   N = 1000
   M = 1000
   D = [(1, 0), (1, 0), (1, 0), (1, 0), (-3, 0), (0, 3), (0, -3)]
   

   (from above)

8. S = 345
   N = 123
   M = 21212
   D = [(1, -4), (2, -3), (3, -2), (4, -1), (-9, 9)]
   

   

9. S = 200
   N = 1
   M = 1500000
   D = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
   

   

10. S = 300
    N = 4000
    M = 1000
    D = [(7, 1), (-4, 3), (-4, -3)]
    

    

11. S = 300
    N = 1500
    M = 1000
    D = [(10, -10), (-10, 10), (5, 5), (-5, -5), (1, 0), (-1, 0)]
    

    

12. S = 240
    N = 1000
    M = 10000
    D = [(80, 81), (80, -81), (-81, 80), (-81, -80)]
    

    

All example inputs together.

Bonus

This isn't required but I would love to see what other neat patterns are possible. Put any cool images you make in your answer!

Answer 1

Ruby, ^263...150 147 bytes

->s,n,m,d{c=[0]*3*s*s;n.times{x=y=s/2;0.upto(m){c[3.*x+y*s]+=1;d.shuffle.find{|p,q|(g=x+p,y+q)-[*0...s]==[]&&(x,y=g)}||break}};puts:P3,s,s,255,0,c}

Try it online! (Times out on four of the test cases and truncates output for all but two of the others.)

Explanation

Takes d as an array of arrays and outputs in PPM format to STDOUT. Two features of PPM are exploited:

1. No attempt is made to avoid G values greater than 255: PPM treats any such values as if they were equal to 255.
2. Extraneous bytes at the end of the file (i.e. beyond the specified pixel count) are ignored. This allows a byte to be saved by working internally with the red channel rather than green, then shifting all the RGB values by one place on output.

->s,n,m,d{
  c=[0]*3*s*s;         # initialise all pixels to black
  n.times{
    x=y=s/2;           # set initial position
    0.upto(m){
      c[3.*x+y*s]+=1;  # add 1 to red channel at current position (x+y*s is single-digit pixel index, starting from 0 at top left)
      d.shuffle        # randomise moves
       .find{|p,q|     # if there is a move such that
         (g=x+p,y+q)   # the new co-ordinates
         -[*0...s]==[] # are both in [0, s) (i.e. within the image)
         &&(x,y=g)     # take that move
       }            
      ||break          # otherwise restart with a new point
    }
  };
  puts:P3,s,s,255,0,c  # print PPM file to STDOUT, inserting 0 to get green output
}

Sample outputs for test cases

Composite image including all test cases, ordered as follows:

1, 2, 3
4, 8
5, 6, 7, 9
10, 11, 12

Bonus

'Excalibur'
S = 400, N = 5000, M = 5000, D = [[1, -1], [1, -1], [-2, 10], [-10, 2]]

'Aurora'
S = 400, N = 2500, M = 2500, D = [[11, 13], [13, -11], [-29, 31], [31, 29], [41, 43], [43, -41], [-59, 61], [-59, -61]]

Answer 2

Java 10, 516 513 508 504 bytes

import java.awt.*;(S,N,M,D)->new Frame(){{add(new Panel(){public void paint(Graphics g){var G=(Graphics2D)g;G.setPaint(Color.BLACK);G.fillRect(0,0,S,S);int c[][]=new int[S][S],x,y,d[],r,n=N,m;for(;n-->0;)for(x=y=S/2,m=M;m-->0;){c[x][y]++;var L=new java.util.Stack<int[]>();for(var q:D)if(q[0]>~x&x+q[0]<S&q[1]>~y&y+q[1]<S)L.add(q);r=L.size();if(r<1)break;d=L.get(r*=Math.random());x+=d[0];y+=d[1];}for(x=S*S;x-->0;G.drawLine(x,y,x,y))G.setPaint(new Color(0,Math.min(c[r=x/S][y=x%S],255),0));}});show();}}

-4 bytes thanks to @ceilingcat.

Some example outputs:

Input: S=250; N=800; M=7000; D=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]
Output:

Input: S=200; N=10000; M=5000; D=[[1,1],[2,2],[30,30],[1,-1],[2,-2],[30,-30],[-1,1],[-2,2],[-30,30]]
Output:

Input: S=200, N=5000, M=5000, D=[[10,11],[11,10],[25,26],[26,25],[50,51],[51,50],[-75,-75]]
Output:

Explanation:

import java.awt.*;            // Required import for almost everything
(S,N,M,D)->                   // Method with the 4 parameters and Frame return-type
  new Frame(){                //  Create the Frame
   {                          //   In an inner code-block:
     add(new Panel(){         //    Add a Panel we can draw on:
       public void paint(Graphics g){
                              //     Overwrite its paint method:
         var G=(Graphics2D)g; //      Cast interface to object so we can use it to draw
         G.setPaint(Color.BLACK);
                              //      Set the color to black
         G.fillRect(0,0,S,S); //      Create the square of size `S` by `S`
         int c[][]=new int[S][S],
                              //      Create an integer-matrix of the same size,
                              //      filled with 0s by default
             x,y,             //      Temp integers for the current coordinates
             d[],             //      Temp integer-array for the randomly selected delta
             r,               //      Temp integer for the random index
             n=N,             //      Copy of the input `N` (since we are in a
                              //      code-block, it has to be effectively final..)
             m;               //      Temp integer
         for(;n-->0;)         //      Loop `n` amount of times:
           for(x=y=S/2,       //       Start `x,y` at the center
               m=M;m-->0;){   //       Inner loop `M` amount of times:
             c[x][y]++;       //        Increase the value at the current `x,y` by 1
             var L=new java.util.Stack<int[]>(); 
                              //        Create an empty list
             for(var q:D)     //        Loop over the deltas:
               if(q[0]>~x&x+q[0]<S&q[1]>~y&y+q[1]<S)
                              //         If `x,y` + this delta is within bounds:
                 L.add(q);    //          Add the current delta to the list
             r=L.size();      //        Set `r` to the amount of valid deltas left
             if(r<1)          //        If there are no valid deltas:
               break;         //         Stop the inner loop
             d=L.get(r*=Math.random());
                              //        Pick a random delta from the list
             x+=d[0];y+=d[1];}//        And update the `x,y` coordinate with it
         for(x=S*S;x-->0      //      Then loop over all coordinates:
             ;                //        After every iteration:
              G.drawLine(r,y,r,y))
                              //         Draw the current pixel
           G.setPaint(new Color(0,Math.min(c[r=x/S][y=x%S],255),0));}});
                              //       Set the green color based on the value in `c`,
                              //       or 255 if it's exceeding that
     show();}}                //    And finally show the Frame

Answer 3

Wolfram Language (Mathematica), 216 bytes

(s=Table[{0,0,0}~Table~S,S=#];t=1;Do[s[[##&@@(d=Floor[{S/2,S/2}])]]={0,t++,0};Do[s[[##&@@(c=RandomChoice[If[(z=Select[d+#&/@If[#4=={},{0,0},#4],Max@#<S-1&&Min@#>1&])=={},d,z]])]]+={0,1,0};d=c,#3],#2];s~Image~"Byte")&

[400, 600, 10000, {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}]

[1000, 2000, 2000, {{5, 5}, {2, 3}, {1, -1}, {-3, -4}, {4, 5}, {-5, -5}}]

Answer 4

JavaScript (ES6), 279 269 bytes

f=
(c,s,n,m,d)=>{c.width=c.height=s
c=c.getContext('2d',{alpha:0})
i=c.getImageData(0,0,s,s)
for(;x=y=s/2|0,n--;)for(o=m;i.data[(x+y*s)*4+1]++,l=o--&&(e=d.map(([a,b])=>[x+a,y+b]).filter(([a,b])=>a>=0&b>=0&a<s&b<s)).length;)[x,y]=e[l*Math.random()|0]
c.putImageData(i,0,0)}

Size: <input id=s type=number min=1 value=250><br>Pixels: <input id=n type=number min=0 value=800><br>Moves: <input id=m type=number min=0 value=7000><br>Deltas: <input id=d value=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]><br><input type=button value=Go! onclick=f(c,+s.value,+n.value,+m.value,JSON.parse(d.value))><br><canvas id=c>

Takes a fifth parameter which is the canvas element on which to draw the resulting image. Byte count does not include the test driver, which comprises the f= line of JavaScript and all of the HTML. Edit: Saved 10 bytes thanks to @Kaiido. Ungolfed version with incremental rendering:

b.onclick = async function() {
  b.disabled = true;
  try {
    await f(c, +s.value, +n.value, +m.value, JSON.parse(d.value));
  } catch (ex) {
    console.error(ex);
  }
  b.disabled = false;
}
async function f(canvas, size, number, moves, deltas) {
  canvas.width = canvas.height = size;
  let context = canvas.getContext('2d', { alpha: false });
  context.fillRect(0, 0, size, size);
  let image = context.getImageData(0, 0, size, size);
  for (let i = 0; i < number; i++) {
    let x = size / 2 | 0, y = x, j = moves;
    for (;;) {
      image.data[(x + y * size) * 4 + 1]++;
      if (!j--) break;
      let valid = deltas.map(([dx, dy]) => [x + dx, y + dy]).filter(([x, y]) => x >= 0 && y >= 0 && x < size && y < size);
      if (!valid.length) break;
      [x, y] = valid[valid.length * Math.random() | 0];
    }
    context.putImageData(image, 0, 0);
    await new Promise(requestAnimationFrame);
  }
}

<div>Size: <input id=s type=number min=1 value=250></div>
<div>Pixels: <input id=n type=number min=0 value=800></div>
<div>Moves: <input id=m type=number min=0 value=7000></div>
<div>Deltas: <input id=d value=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]></div>
<div><input id=b type=button value=Go!></div>
<canvas id=c>

Answer 5

Python 2 + PIL, 217 214 211 bytes

A golf of the reference implementation, but a lot less efficient. Instead of using loops, this generates many many lines of code (N*(M+2)) that will run once.

import random,PIL.Image as I
S,N,M,D=input()
i=I.new('RGB',(S,S))
p=i.load()
exec('v=[[S//2]*2]\n'+'if v:x,y=random.choice(v);p[x,y]=0,p[x,y][1]+1,0;v=[(x+a,y+b)for a,b in D if-1<x+a<S>y+b>=0]\n'*-~M)*N
i.show()

Output for S=51, N=1000, M=1, D=[(-5, 5), (9, 9), (-15, 1), (20, -25)]:

Output of an older version for S=300, N=1500, M=1000, D=[(10, -10), (-10, 10), (5, 5), (-5, -5), (1, 0), (-1, 0)], don't try such a large example with the current version: