Наложение фигур Опции

[ТОХА]

Здравствуйте!
при написании одного из модулей программы я столкнулся с такой проблемой как наложение фигур друг на друга. Как сделать так чтоб последующая фигура рисовалась на свободном месте экрана и не накладывалась на другие?

 uses Crt, Graph;
const k=100;
var
 GraphDriver, GraphMode: Integer;
 X1,y1, r: Integer;ch:char;
begin
 GraphDriver := Detect;
 InitGraph(GraphDriver, GraphMode, ' ');
 if GraphResult<> grOk then
   Halt(1);
repeat
 ch:=readkey;
 if ch=chr(13) then begin
  X1 := Random(640-k)+k;
   y1 := Random(480-k)+k;
  r:=Random(k)+1;
  circle(X1,y1,r);
 end;
until ch=chr(27);
CloseGraph;
end.

[мисс_граффити]

фигуры - только круги? а что делать, если свободных мест не осталось вообще?

[ТОХА]

да, только круги
это просто часть моей игры на запоминание, сделаю их такого размера чтоб в районе 50 вмещалось, больше запомнить будет просто невозможно)

[volvo]

Если только круги - то можно сделать

что-то типа вот такого... (Показать/Скрыть)

uses
  Crt, Graph;

const
  k = 100;
  maxCircles = 50;

var
  GraphDriver, GraphMode: Integer;
  X1,y1, r: Integer; ch: char;

  i, curr : integer;
  ok : boolean;
  C : array[1 .. maxCircles] of
      record
        X, Y, R : longint;
      end;

begin
  GraphDriver := Detect;
  InitGraph(GraphDriver, GraphMode, ' ');
  if GraphResult<> grOk then Halt(1);

  curr := 0;
  repeat
    ch := readkey;
    if ch = chr(13) then
    begin
      repeat
        X1 := Random(GetMaxX - k) + k; { Не надо привязываться к "магическим числам" }
        Y1 := Random(GetMaxY - k) + k;
        r := Random(k) + 1;

        ok := true;
        for i := 1 to curr do
          ok := ok and (sqr(C[i].X - X1) + sqr(C[i].Y - Y1) >
                        sqr(R + C[i].R));
      until ok;

      inc(curr);
      C[curr].X := X1;
      C[curr].Y := Y1;
      C[curr].R := R;

      Circle(X1, Y1, R);
    end;
  until ch = chr(27);
  CloseGraph;
end.

Не забудь добавить проверку, чтоб цикл заканчивался после отрисовки максимум maxCircles кругов, иначе будут проблемы.

[ТОХА]

uses
           (sqr(C[i].X - X1) + sqr(C[i].Y - Y1) > sqr(R + C[i].R))

Откуда такая интересная формула, если не секрет
З.Ы. спасибо, сам бы не додумался

[volvo]

Чего ж тут такого особенного? Чистая логика. Когда новая окружность не будет пересекаться с уже отрисованной? Правильно, когда расстояние между центрами окружностей больше суммы их радиусов. Причем это должно проверяться для ВСЕХ уже отрисованных объектов.

Чтоб не вычислять квадратный корень, я оставил квадрат расстояния между центрами. Значит, сравнивать его надо с квадратом суммы радиусов. Всё просто.

[ТОХА]

точно это ж геометрия за 8 класс

[TarasBer]

> repeat
random...
until ok;

Предлагаю придумать не потенциально-бесконечный алгоритм.

[volvo]

Предлагаю придумать не потенциально-бесконечный алгоритм.

Не проблема. Только не надо мне рассказывать ,что "в некотором царстве, в некотором государстве" Random может бесконечно возвращать значения, большие некоего порога. Давай будем реалистами: Random - это генератор, который возвращает равномерно-распределенные случайные числа. То есть, в какой-то момент времени он вернет и 1, и 2, и 4, и 10.

Тогда для того, чтоб алгоритм стал НЕ потенциально бесконечным, достаточно, чтобы выполнялось условие
maxCircles * Pi * K² < GetMaxX * GetMaxY

То есть, либо уменьшаем K до [Sqrt(GetMaxX * GetMaxY / (50 * Pi))] = 44

, либо уменьшаем MaxCircles до [GetMaxX * GetMaxY / (50 * K²)] = 9

, либо увеличиваем GetMaxX * GetMaxY так, чтобы их произведение превышало 1570797. С современными мониторами и компиляторами это ни разу не проблема: любой широкоформатный монитор выдаст разрешение 1920*1024, и GetMaxX * GetMaxY = 1963137. Опять никакого шанса алгоритму стать бесконечным...

Я уж не говорю о том, что можно одновременно уменьшить и радиус и maxCircles...

[TarasBer]

> Random - это генератор, который возвращает равномерно-распределенные случайные числа

Не случайные, а ПСЕВДОслучайные.
Будут ли тройки последовательно возвращаемых значений равномерно распределены?
Позволяют ли внутренние особенности именно данной реализации алгоритма надеяться на отсутствие возможности зацикливания?

[ТОХА]

смысл игры в том, что нужно запомнить какой шарик появился на поле и щелкнуть на него(пока вместо мыши энтер), я сомневаюсь что есть люди которые дойдут до зацикливания
TarasBer, надеюсь я ответил на твой вопрос


осталось добавить мышку и небольшое мигание перед появлением каждого из шариков для усложнения запоминания, как закончу скину

[TarasBer]

> TarasBer, надеюсь я ответил на твой вопрос

Нет, вопрос был не об этом. Вопрос был в том, что сама концепция выполнения случайного действия до выполнения какого-то условия мне видится сомнительной. Кто сказал, что условие когда-либо выполнится, мало ли как случайное действие себя вести будет?

[volvo]

сама концепция выполнения случайного действия до выполнения какого-то условия мне видится сомнительной

Это твои заморочки. Оно ОБЯЗАНО отработать по изложенным выше причинам. А отработает оно за 0.0002 сек. или за 0.05 сек - это дело десятое (в данном конкретном случае), время реакции человека все равно гораздо больше.

Проверил на своей машине: сгенерировал (без вывода на экран) 50 окружностей, в цикле. Цикл прогнал 10000 раз. А потом - полтора миллиарда раз. И в первом и во втором случае среднее время генерации всех 50 окружностей приблизительно одно и то же. Если алгоритм за полтора миллиарда испытаний не дает не только сбоя (коим здесь является "вечный цикл"), но даже ощутимого увеличения времени выполнения - я бы его использовал без сомнений... Но если очень хочется пойти другим путем - изобретайте очередной велосипед... Меня эта отрасль машиностроения не интересует уже давно...

[ТОХА]

небольшой оффтоп
как пользоваться коммандой MouseIn для кругов и эллипсов?представлять их в виде многоугольников и ставить условие под каждый угол или же есть способ проще?
просто точность попадания в многоугольник будет зависеть от количества углов, а проверок получается очень много)

[TarasBer]

> Это твои заморочки. Оно ОБЯЗАНО отработать по изложенным выше причинам.

Причины недостаточно доказаны.

> А отработает оно за 0.0002 сек. или за 0.05 сек - это дело десятое (в данном конкретном случае)

Лишь бы раз в год оно не заработало за 50 сек.

> Проверил на своей машине: сгенерировал (без вывода на экран) 50 окружностей, в цикле. Цикл прогнал 10000 раз. А потом - полтора миллиарда раз. И в первом и во втором случае среднее время генерации всех 50 окружностей приблизительно одно и то же.

Возьми не среднее, а максимальное. А потом возьми другой ГСЧ, для него придётся доказывать всё по новой.

Это хорошо, что полтора миллиарда испытаний отработали как надо, но всё-таки само понятие случайного числа противоречит понятию алгоритма, и завязывание жизненно важных участков алгоритма на случайные числа лишает алгоритм права называться алгоритмом, поскольку делает его поведение непредсказуемым.
Ты математически можешь доказать, что алгоритм гарантировано даст нужный результат не более, чем за эн тактов процессора (или итераций цикла, или ещё каких-то условных единиц)? Нет, не можешь. Поэтому с такими алгоритмами надо быть очень осторожными. И если есть обходные пути, работающие за разумное время - то надо их искать. Иначе на этом алгоритме надо огромными красными буквами писать, что так как он основан на случайных событиях, то он ничего не гарантирует.

Добавлено через 2 мин.
> как пользоваться коммандой MouseIn для кругов и эллипсов?

Чтобы узнать, что точка с координитами mx, my попала в эллипс с центром в точке x, y и полуосями rx, ry, надо сравнить

sqr((mx-x)/rx) + sqr((my-y)/ry)

с единицей.

[ТОХА]

Спасибо )

[ТОХА]

немного запутался и возникло 2 проблемы:
мышь ползает только по верхней половине экрана
программа виснет после появления 8 шарика, почему именно 8 я без понятия
буду благодарен если кто-нить посмотрит))

[volvo]

Возьми не среднее, а максимальное

Максимальное время различается не больше, чем на 20%. С учетом того, что речь идет о тысячных долях секунды - это не критично. Я тебе уже говорил, где нужна шлифовка тактов. В прикладной программе, которая ожидает реакции пользователя, я этим заниматься не собираюсь. И тебе не советую.

А потом возьми другой ГСЧ, для него придётся доказывать всё по новой.

Вот когда мне понадобится другой ГСЧ, и я получу его реализацию - я буду думать над этим. Решаем проблемы по мере поступления. А то ведь теоретически можно придумать такой ГСЧ, что он ЛЮБОЙ алгоритм (вообще любой, не только по этой задаче) запорет. Вот и сиди, и доказывай правильность алгоритма для ВСЕХ ВОЗМОЖНЫХ генераторов. У меня есть более интересные занятия.

А пока - перечитай первый абзац этого сообщения и первый абзац сообщения №9. Вот ты и начал мне рассказывать, что "где-то существует другой ГСЧ, который..." Я не пользуюсь другим. Я использую стандартный Random (который использовал еще в 1987 году, и до сих пор в учебных программах он меня более чем устраивает. В реальных - используются совершенно другие генераторы, и совершенно другие алгоритмы). Если б я написал свою функцию GetRandomNumber (пусть даже в ней был бы вызов того же Random-а) - у тебя был бы повод придраться, ибо я хоть какую-то возможность смены генератора предполагаю. Сейчас у тебя его нет, ибо я однозначно дал понять: использовать другой генератор не собираюсь, в коде жестко прописан тот, что есть. Так что про "другой ГСЧ" - это даже не обсуждается...

программа виснет после появления 8 шарика, почему именно 8 я без понятия

Потому что у тебя генерация X, Y, R должна быть внутри repeat/until, а ее там нет. И что получилось? Сгенерированы значения, проверено по формуле, получено Ok = False. Ты опять присваиваешь Ok := True, и для тех же X, Y, R что и прежде, начинаешь проверку. Это неправильно. Надо сгенерировать другие значения для новой окружности, и проверять уже для них...

[ТОХА]

нашел, исправил, а что делать с мышкой?

[TarasBer]

> Максимальное время различается не больше, чем на 20%.

Ну если ты перебрал при этом все 4 млрд возможных стартовых состояния ГСЧ, то это подойдёт, как доказательство.

> Я тебе уже говорил, где нужна шлифовка тактов.

Как будто мне она тут нужна. Чё сразу - раз ТарасБер, значит шлифовка тактов?
Мне не нужно, чтобы раз в год программа затупливала на минуту. Конечно, когда пишешь игрушку, на это вообще все кладут - у 10 игроков игра упала, у 90 отработала, вот и зашибись. А в серьёзном программировании так нельзя.