迷路 分岐なし

mazeNoGrid20251103.pde

// ===============================================
// 1本のロープで画面をなめる実験
// midpoint細分化
// + 空間グリッドで近い点だけ反発
// + 密度が高いところにはもう点を足さない
// + 角度バネで曲がりすぎを抑える ← NEW
// + スムージングでヒダヒダに
// 2025-11-02
// ===============================================

ArrayList<PVector> pts;

// --- 細分化・制約パラメータ ---
float maxLen = 70;          // これより長い区間は割る
float minLen = 26;          // これより短いと離す（反発距離）
int subdividePerFrame = 3;  // 毎フレーム細分化する本数
float smoothAmt = 0.32;     // スムージングの強さ（0〜1）
float normalOffset = 10;    // 中点を法線方向に出す量（ヒダの高さ）
float attractStrength = 0.0; // 中央に寄せる力
int maxPoints = 1500;       // 点を増やす上限
float margin = 30;          // 画面の余白

// ランダム挿入の基本確率
float baseRandomInsertChance = 0.25;

// --- 空間グリッド（ぶつかり防止用） ---
int cellSize = 40;           // グリッド1マスの大きさ（minLenと同じ〜少し大きい）
int gridCols, gridRows;
ArrayList<Integer>[][] buckets;
int densityLimit = 12;       // このマス周辺にこれ以上点がいたら挿入しない

// --- 角度バネ用パラメータ ---
float minAngleDeg = 65;      // これより鋭角だったら開く
float angleSpringStrength = 10; // どれくらい押し出すか（px）

void setup() {
  size(900, 900);
  frameRate(999);

  // 端点だけ持ったロープを作る
  pts = new ArrayList<PVector>();
  pts.add(new PVector(80, height * 0.5));
  pts.add(new PVector(width - 80, height * 0.5));

  // グリッド準備
  gridCols = width / cellSize + 2;
  gridRows = height / cellSize + 2;
  buckets = (ArrayList<Integer>[][]) new ArrayList[gridCols][gridRows];
}

void draw() {
  background(250);

  // ① いったんいまある点でグリッドを作る（密度を見るために先にやる）
  buildSpatialGrid();

  // ② ランダムな区間をいくつかだけ細分化（ただし密度を見てから）
  for (int k = 0; k < subdividePerFrame; k++) {
    subdivideRandomSegmentWithDensity();
  }

  // ③ 新しい点も含めてもう一度グリッドを作り直す
  buildSpatialGrid();

  // ④ 近い点だけで距離制約（ぶつかり防止）
  relaxSpatial();

  // ⑤ 角度バネ（曲がりすぎを開く） ← NEW
  applyAngleSpring();

  // ⑥ スムージングでギザギザをならす → ヒダヒダに
  smoothChain(smoothAmt);

  // ⑦ 中央に少し寄せる（端点以外）
  attractToCenter();

  // ⑧ はみ出さないようにする
  clampInside();

  // ⑨ 描画
  drawChain();

  // 情報表示
  fill(0);
  text("points: " + pts.size(), 10, 20);
}

// ----------------------------------------------------------
// 細分化：密度を見てから挿入する
// ----------------------------------------------------------
void subdivideRandomSegmentWithDensity() {
  if (pts.size() < 2) return;
  if (pts.size() > maxPoints) return;

  int i = int(random(pts.size() - 1));
  PVector a = pts.get(i);
  PVector b = pts.get(i + 1);
  float d = PVector.dist(a, b);

  // 中点の候補
  PVector mid = PVector.lerp(a, b, 0.5);
  int gx = floor(mid.x / cellSize);
  int gy = floor(mid.y / cellSize);
  gx = constrain(gx, 0, gridCols - 1);
  gy = constrain(gy, 0, gridRows - 1);

  int localCount = countNeighbors(gx, gy, 1);

  // もうぎゅうぎゅう & そんなに長くないなら無理に挿入しない
  if (localCount > densityLimit && d < maxLen * 1.2) {
    return;
  }

  // 中央に近いほどランダム挿入の確率を下げる
  float centerFalloff = centerFalloffAt(mid.x, mid.y);
  boolean forceInsert = random(1) < (baseRandomInsertChance * centerFalloff);

  if (forceInsert || d > maxLen) {
    // 本挿入する中点
    PVector m = PVector.lerp(a, b, 0.5);

    // 法線にずらしてヒダヒダにする
    PVector t = PVector.sub(b, a);
    if (t.magSq() > 0.0001) {
      t.normalize();
      PVector n = new PVector(-t.y, t.x);
      float sign = (i % 2 == 0) ? 1 : -1;
      m.add(PVector.mult(n, sign * normalOffset));
    }

    pts.add(i + 1, m);
  }
}

// ----------------------------------------------------------
// 中央からの距離でランダム挿入を減らす
// ----------------------------------------------------------
float centerFalloffAt(float x, float y) {
  float cx = width * 0.5;
  float cy = height * 0.5;
  float dx = (x - cx) / (width * 0.5);
  float dy = (y - cy) / (height * 0.5);
  float distNorm = sqrt(dx * dx + dy * dy); // 0〜1くらい

  float f = map(distNorm, 0.0, 1.0, 0.35, 1.0);
  return constrain(f, 0.25, 1.0);
}

// ----------------------------------------------------------
// グリッドを作る
// ----------------------------------------------------------
void buildSpatialGrid() {
  for (int gx = 0; gx < gridCols; gx++) {
    for (int gy = 0; gy < gridRows; gy++) {
      if (buckets[gx][gy] == null) {
        buckets[gx][gy] = new ArrayList<Integer>();
      } else {
        buckets[gx][gy].clear();
      }
    }
  }

  for (int i = 0; i < pts.size(); i++) {
    PVector p = pts.get(i);
    int gx = floor(p.x / cellSize);
    int gy = floor(p.y / cellSize);
    gx = constrain(gx, 0, gridCols - 1);
    gy = constrain(gy, 0, gridRows - 1);
    buckets[gx][gy].add(i);
  }
}

// ----------------------------------------------------------
// 近傍マスに何点あるか数える
// ----------------------------------------------------------
int countNeighbors(int gx, int gy, int r) {
  int cnt = 0;
  for (int ox = -r; ox <= r; ox++) {
    for (int oy = -r; oy <= r; oy++) {
      int nx = gx + ox;
      int ny = gy + oy;
      if (nx < 0 || nx >= gridCols || ny < 0 || ny >= gridRows) continue;
      cnt += buckets[nx][ny].size();
    }
  }
  return cnt;
}

// ----------------------------------------------------------
// グリッド近傍だけで距離制約をかける
// ----------------------------------------------------------
void relaxSpatial() {
  int n = pts.size();
  for (int i = 0; i < n; i++) {
    if (i == 0 || i == n - 1) continue; // 端点は固定

    PVector pi = pts.get(i);
    int gx = floor(pi.x / cellSize);
    int gy = floor(pi.y / cellSize);
    gx = constrain(gx, 0, gridCols - 1);
    gy = constrain(gy, 0, gridRows - 1);

    for (int ox = -1; ox <= 1; ox++) {
      for (int oy = -1; oy <= 1; oy++) {
        int ngx = gx + ox;
        int ngy = gy + oy;
        if (ngx < 0 || ngx >= gridCols || ngy < 0 || ngy >= gridRows) continue;

        ArrayList<Integer> list = buckets[ngx][ngy];
        for (int idx = 0; idx < list.size(); idx++) {
          int j = list.get(idx);
          if (j == i) continue;

          boolean iFixed = (i == 0 || i == n - 1);
          boolean jFixed = (j == 0 || j == n - 1);

          PVector pj = pts.get(j);
          float dx = pj.x - pi.x;
          float dy = pj.y - pi.y;
          float dd = sqrt(dx * dx + dy * dy);

          if (dd < 0.0001) {
            if (!iFixed) {
              pi.x += random(-1, 1);
              pi.y += random(-1, 1);
            }
            if (!jFixed) {
              pj.x += random(-1, 1);
              pj.y += random(-1, 1);
            }
            continue;
          }

          if (dd < minLen) {
            float diff = (minLen - dd) * 0.5;
            float ux = dx / dd;
            float uy = dy / dd;
            if (!iFixed) {
              pi.x -= ux * diff;
              pi.y -= uy * diff;
            }
            if (!jFixed) {
              pj.x += ux * diff;
              pj.y += uy * diff;
            }
          }
        }
      }
    }
  }
}

// ----------------------------------------------------------
// 角度バネ：3点の角度が狭すぎたら開く
// ----------------------------------------------------------
void applyAngleSpring() {
  int n = pts.size();
  if (n < 3) return;

  float minAngleRad = radians(minAngleDeg);

  for (int i = 1; i < n - 1; i++) {
    // 端点は動かさない
    if (i == 0 || i == n - 1) continue;

    PVector A = pts.get(i - 1);
    PVector B = pts.get(i);
    PVector C = pts.get(i + 1);

    // ベクトル BA, BC （Bから見たときの2方向）
    PVector v1 = PVector.sub(A, B);
    PVector v2 = PVector.sub(C, B);

    float len1 = v1.mag();
    float len2 = v2.mag();
    if (len1 < 0.0001 || len2 < 0.0001) continue;

    v1.normalize();
    v2.normalize();

    float dot = v1.dot(v2);
    dot = constrain(dot, -1, 1);
    float ang = acos(dot);  // 0〜PI

    // 角度が狭すぎるときだけ処理
    if (ang < minAngleRad) {
      // 今の曲がりの“内側”を示すベクトル：v1 + v2
      PVector inside = PVector.add(v1, v2);
      if (inside.magSq() > 0.0001) {
        inside.normalize();
        // どれだけ開くか（狭いほど強く）
        float t = (minAngleRad - ang) / minAngleRad;  // 0〜1
        float moveDist = angleSpringStrength * t;

        // 内側に向かっているので、逆方向に押し出す
        B.sub(PVector.mult(inside, moveDist));
      }
    }
  }
}

// ----------------------------------------------------------
// 角をならす
// ----------------------------------------------------------
void smoothChain(float amt) {
  int n = pts.size();
  if (n <= 2) return;

  PVector[] buf = new PVector[n];
  for (int i = 0; i < n; i++) {
    buf[i] = pts.get(i).copy();
  }

  for (int i = 1; i < n - 1; i++) {  // 端点は動かさない
    PVector prev = pts.get(i - 1);
    PVector cur  = pts.get(i);
    PVector next = pts.get(i + 1);

    PVector avg = PVector.add(prev, next).mult(0.5);
    PVector sm = PVector.lerp(cur, avg, amt);
    buf[i].set(sm);
  }

  for (int i = 1; i < n - 1; i++) {
    pts.get(i).set(buf[i]);
  }
}

// ----------------------------------------------------------
// 中央に寄せる
// ----------------------------------------------------------
void attractToCenter() {
  float cx = width * 0.5;
  float cy = height * 0.5;
  int n = pts.size();
  for (int i = 1; i < n - 1; i++) { // 端点以外
    PVector p = pts.get(i);
    p.x += (cx - p.x) * attractStrength;
    p.y += (cy - p.y) * attractStrength;
  }
}

// ----------------------------------------------------------
// はみ出し防止
// ----------------------------------------------------------
void clampInside() {
  for (PVector p : pts) {
    p.x = constrain(p.x, margin, width - margin);
    p.y = constrain(p.y, margin, height - margin);
  }
}

// ----------------------------------------------------------
// 描画
// ----------------------------------------------------------
void drawChain() {
  stroke(120, 60, 180);
  strokeWeight(10);
  noFill();
  beginShape();
  for (PVector p : pts) {
    vertex(p.x, p.y);
  }
  endShape();

  // 点を描く
  noStroke();
  fill(120, 60, 180);
  for (PVector p : pts) {
    circle(p.x, p.y, 5);
  }

  // 端点を目立たせる
  fill(0, 200, 0);
  PVector s = pts.get(0);
  circle(s.x, s.y, 12);

  fill(220, 0, 0);
  PVector e = pts.get(pts.size() - 1);
  circle(e.x, e.y, 12);
}