Làm thế nào tôi có thể tạo ra một mẫu giả ngẫu nhiên từ X/Y phối hợp xác định?

Question

Tôi đang viết một bóng đổ mà thỉnh thoảng làm cho một điểm lấp lánh trên bản đồ 2D. Tôi muốn các khối lấp lánh xuất hiện ngẫu nhiên và phân bố đồng đều trên mặt phẳng (vô hạn), nhưng tôi muốn sự lấp lánh được xác định dựa trên tọa độ X và Y. Tôi đã thử tạo hạt giống từ các tọa độ và tạo một Java Random từ hạt giống đó, nhưng nỗ lực của tôi cho đến nay đã dẫn đến các mẫu có thể nhận ra. Chức năng này sẽ được gọi thường xuyên (nhiều triệu lần) để hiệu suất là rất quan trọng.

Lần đầu tiên tôi cố gắng bắt chước triển khai hashCode(), sử dụng hệ số số nguyên tố để tránh va chạm. Điều này dẫn đến một phát ban có thể nhìn thấy trên bản đồ, nơi một loạt các điểm chia sẻ cùng một hạt giống.

sau đó tôi đã cố gắng để tạo ra một hạt giống bằng cách kết hợp các tọa độ như sau:

long seed = ((long) x << 32) | (long) y; 
Random rand = new Random(seed); 

Điều này dường như dẫn đến dữ liệu khuôn mẫu là tốt, mặc dù mô hình không phải là rõ ràng. Các tọa độ được chọn xuất hiện trong các đường thẳng, không được phân bố đồng đều.

Tôi đã tránh sử dụng MD5 hoặc các thuật toán băm mật mã khác vì tôi sợ tác động hiệu suất.

Answer 1

linear congruential generator được triển khai trong java.util.Random có lợi thế là có thể lặp lại cho bất kỳ số được chọn SEED. Với những tờ khai,

private static final int SEED = 42; 
private static final int N = 128; 
private static final int MAX_X = 1024; 
private static final int MAX_Y = 1024; 
private final Random rnd = new Random(SEED); 
private final List<SparklePoint> list = new ArrayList<SparklePoint>(N); 

Bạn có thể khởi tạo một (lặp lại) danh sách các N điểm được chọn ngẫu nhiên trong hình chữ nhật (0, 0, MAX_X, MAX_Y) như sau:

public void init(int seed) { 
    for (int i = 0; i < N; i++) { 
     int x = rnd.nextInt(MAX_X); 
     int y = rnd.nextInt(MAX_Y); 
     list.add(new SparklePoint(x, y)); 
    } 
} 

Nó có thể được thuận tiện để cung cấp cho mỗi điểm một thời gian Timer mà được chọn từ cùng một trình tự:

private class SparklePoint implements ActionListener { 

    private static final int MAX_DELAY = 1000; 
    private final Point p; 
    private final Timer t; 
    private boolean bright; 

    public SparklePoint(int x, int y) { 
     p = new Point(x, y); 
     t = new Timer(rnd.nextInt(MAX_DELAY), this); 
     t.setRepeats(false); 
     t.start(); 
    } 

    @Override 
    public void actionPerformed(ActionEvent e) { 
     t.stop(); 
     if (bright) { 
      // darken p 
     } else { 
      // brighten p 
     } 
     bright = !bright; 
     t.setDelay(rnd.nextInt(MAX_DELAY)); 
     t.start(); 
    } 
} 

Answer 2

Sau đây là một chức năng rất hiệu quả để trộn bit trong một ps eudo-ngẫu nhiên nhưng thời trang xác định:

public static final long xorShift64(long a) { 
    a ^= (a << 21); 
    a ^= (a >>> 35); 
    a ^= (a << 4); 
    return a; 
} 

Vì vậy, nếu bạn muốn có một kết quả lâu giả ngẫu nhiên từ x và y tọa độ bạn có thể làm một cái gì đó như:

long mix = xorShift64(x) + Long.rotateLeft(xorShift64(y),32) + 0xCAFEBABE; 
    long result = xorShift64(mix); 

Tôi đã sử dụng phương pháp này thành công trong đồ họa trước đây, cho kết quả khá tốt! Chất lượng của các số ngẫu nhiên là tốt như java.util.Random nhưng nó nhanh hơn nhiều ....

Answer 3

Đây là thứ tôi đã làm, tạo ra hiệu ứng mong muốn nhưng chắc chắn không hoàn hảo.

MessageDigest md5; 
try { 
    md5 = MessageDigest.getInstance("MD5"); 
} catch (NoSuchAlgorithmException e) { 
    e.printStackTrace(); 
    return null; 
} 
md5.update(new byte[] { 
    (byte)(x >>> 24), 
    (byte)(x >>> 16), 
    (byte)(x >>> 8), 
    (byte)x, 
    (byte)(z >>> 24), 
    (byte)(z >>> 16), 
    (byte)(z >>> 8), 
    (byte)z 
}, 0, 8); 
byte[] digest = md5.digest(); 
long seed = digest[0] + (digest[1] << 8) + (digest[2] << 16) + (digest[3] << 24) + (digest[4] << 32) + (digest[5] << 40) + (digest[6] << 48) + (digest[7] << 56); 
Random random = new Random(seed); 

VOSCO không chỉ là đặc biệt tiết, việc sử dụng các Random có lẽ là quá mức vì tôi chỉ kéo gọi nextInt() hai lần. Nó rất hữu ích cho việc tạo ra các giá trị trong một phạm vi cụ thể, nhưng tôi sẽ có thể làm điều đó với số học modulo anyway.

Tôi thích MD5 đó là một thuật toán được hiểu rõ và bảo mật mã hóa không quan trọng đối với ứng dụng này. Tôi chắc chắn sẽ thích thứ gì đó nhanh hơn (và ít lộn xộn hơn).