кто рискнет ?

[nm]

Так. люди. вы какие-то пассивные ,программеры :)

для начинающих предлагаю занять свое свободное время (послесессионное) следующим:

написание игры 'Life', которая умеет играть на бесконечном поле
и
написание алгоритма, который бы умел генерить
лабиринты (все линии под углами 90 градувос к друг другу, косых линий нет), которые проходимы из любой точки в другую.

для желающих потренировать мозги и размяться - вперед ;)
если есть вопросы - пишите сюда или в приват

[Agregat]

Меня вот что волнует в первой задачке - я же могу сгенерить такую популяцию, которая разрастется до бесконечности - и никакого озу тебе не хватит... ;)

[greka]

Originally posted by Agregat
Меня вот что волнует в первой задачке - я же могу сгенерить такую популяцию, которая разрастется до бесконечности - и никакого озу тебе не хватит... ;)

а ты свапуй на диск, в файлы :)

а что, идейка некосмическая, можна пораскинуть у кого чем есть...

а каковы правила этой игры ?

[Agregat]

Гарик, могу объяснить и на пальцах, но лучше пусть Гугл найдет тебе хорошие ссылки.
Автор игры - Конвей. Игра - жизнь.
Первая приличная ссылка вот
http://www.elvisti.kiev.ua/skl/conwey1/w_life_n.htm
Я делал ее еще на паскале на первом курсе и для ограниченного поля. :)

[nm]

Originally posted by Agregat
Гарик, могу объяснить и на пальцах, но лучше пусть Гугл найдет тебе хорошие ссылки.
Автор игры - Конвей. Игра - жизнь.
Первая приличная ссылка вот
http://www.elvisti.kiev.ua/skl/conwey1/w_life_n.htm
Я делал ее еще на паскале на первом курсе и для ограниченного поля. :)


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

[Agregat]

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

[nm]

Originally posted by Agregat
Гаспар, ты можешь доказать или привести ссылку на доказательство, но не существует неограниченно растущих популяций? ;)

я говорил что то подобное ? попытайся перечитать мой пост еще раз ;)

хотя . все равно . как я вижу программеры у нас более важными делами заняты :)

[Agregat]

Я понял о чем ты.
Но все же если существуют такие популяции ("она скорее всего у тебя" - не совсем устраивает :) ) - то никакое сжатие тебе не поможет.
А делом на самом деле заняты другим... :)

[DaNYer]

menya zainteresovala eta zadachka. popodrobnee pls. mne nikogda ne prixodilos' s takim stalkivat'sya. kak doljen bil predstavlen labirint? kakaya texnika? matrica?

[nm]

Originally posted by DaNYer
menya zainteresovala eta zadachka. popodrobnee pls. mne nikogda ne prixodilos' s takim stalkivat'sya. kak doljen bil predstavlen labirint? kakaya texnika? matrica?

bez raznicy, kak tebe udobno , tak i predstawljaj ... nu . dlja konkretizacii skazhu -
labirint prjamougol'nyj, NxM kletok (podskazka - (2n+1 na 2m+1 kletok) wse stenki idut pod uglami 0,90,180,270 gradusow drug k drugu :)
esli predstawljaesh w wide matricy -
skazhem wse stenki pomechaesh 1 , wse pustye mesta 0 ... nado sozdat'/pridumat' algoritm, kotoryj pozwolit stroit' labirinty, iz ljuboj pustoj (0) tochki kotorogo w ljubuju druguju pustuju tochku mozhno projti...

[[ Xelgen ]]

Originally posted by nm
кто рискнет?

ну я... рискну.. :rolleyes: :)

вообще то как выходить их лаюиринта имеющего выход, думаю все знают, модет здесь это как то задействовать...:rolleyes:

кстати "проходимы из любой точки в другую" означает что во всем лабиринте один общий "коридор"? :)

[nm]

Originally posted by [ Xelgen ]
ну я... рискну.. :rolleyes: :)

вообще то как выходить их лаюиринта имеющего выход, думаю все знают, модет здесь это как то задействовать...:rolleyes:

кстати "проходимы из любой точки в другую" означает что во всем лабиринте один общий "коридор"? :)


da

[Agregat]

pro labirint ya dumayu - volnovoj algoritm daet reshenie na ura :)

[armeng]

Поле может быть бесконечным только в теории, а так в данном примере MinInt .. MaxInt (можно конечно поменять на int64).
Сразу говорю пример написан с руки (не оптимизирован и могут быть логические ошибки).

interface
uses Classes;

type
TItemState = (sEmpty, sStable, sNew, sDying);
TDirection = (dNone, dLeft, dLeftTop, dTop, dRightTop, dRight, dRightBottom, dBottom, dLeftBottom);

PItem = ^TItem;
TItem = record
X: integer;
Y: integer;
State: TItemState;
end;

TPopulation = class(TList)
private
procedure CalculateDirections(Direction: TDirection; var X, Y: integer);
function GetItemState(X, Y: integer; Direction: TDirection = dNone): TItemState;
procedure MarkNeighbours;
public
procedure AddItem(X, Y: integer);
procedure ClearPopulation;
procedure Run(Step: integer = 1);
end;

implementation

procedure TPopulation.CalculateDirections(Direction: TDirection; var X, Y: integer);
begin
case Direction of
dLeft: dec(X);
dLeftTop: begin
dec(X);
dec(Y);
end;
dTop: Dec(Y);
dRightTop: begin
inc(X);
dec(Y);
end;
dRight: inc(X);
dRightBottom: begin
inc(X);
inc(Y);
end;
dBottom: inc(Y);
dLeftBottom: begin
dec(X);
inc(Y);
end;
end;
end;

function TPopulation.GetItemState(X, Y: integer; Direction: TDirection = dNone): TItemState;
var
i: integer;
begin
result:= sEmpty;
CalculateDirections(Direction, X, Y);
for i:= 0 to Count - 1 do
if (PItem(Self[i])^.X = X) and (PItem(Self[i])^.Y = Y) then
begin
result:= PItem(Self[i])^.State;
break;
end;
end;

procedure TPopulation.MarkNeighbours;
var
i: integer;
Dir, Dir1: TDirection;
Item: PItem;
NewItem: PItem;
NeighboursCount: byte;
NeighboursCountForEmptyItem: byte;
X, Y: integer;
begin
i:= 0;
while i < Count do
begin
NeighboursCount:= 0;
Item:= PItem(Self[i]);
if Item^.State = sStable then
begin
for Dir:= dLeft to dLeftBottom do
case GetItemState(Item^.X, Item^.Y, Dir) of
sStable, sDying: inc(NeighboursCount);
sEmpty: begin
NeighboursCountForEmptyItem:= 0;
new(NewItem);
X:= Item^.X;
Y:= Item^.Y;
CalculateDirections(Dir, X, Y);
NewItem^.X:= X;
NewItem^.Y:= Y;
for Dir1:= dLeft to dLeftBottom do
case GetItemState(NewItem^.X, NewItem^.Y, Dir1) of
sStable, sDying: inc(NeighboursCountForEmptyItem);
end;
if NeighboursCountForEmptyItem = 3 then
begin
NewItem^.State:= sNew;
Self.Add(NewItem);
end else
dispose(NewItem);
end;
end;
if (NeighboursCount < 2) or (NeighboursCount > 3) then
Item^.State:= sDying;
end;
inc(i);
end;
end;

procedure TPopulation.Run(Step: integer = 1);
var
i, j: integer;
begin
for i:= 1 to Step do
begin
MarkNeighbours;
j:= 0;
while j < Count do
begin
case GetItemState(PItem(Self[j])^.X, PItem(Self[j])^.Y) of
sNew: begin
PItem(Self[j])^.State:= sStable;
inc(j);
end;
sDying: begin
Dispose(Self[j]);
Self.Delete(j);
end;
else inc(j);
end;
end;
Pack;
end;
end;

procedure TPopulation.AddItem(X, Y: integer);
var
P: PItem;
begin
new(P);
P^.X:= X;
P^.Y:= Y;
P^.State:= sStable;
Add(P);
end;

procedure TPopulation.ClearPopulation;
var
i: integer;
begin
for i:= 0 to Count - 1 do
Dispose(Self[i]);
Clear;
end;

[Agregat]

А Pack это метод класс TList?
И что он представляет собой? Связанный список?

[armeng]

Originally posted by Agregat
А Pack это метод класс TList?
И что он представляет собой? Связанный список?

Да TList это фактически связанный список, элемент которого - указатель (динамический массив указателей).

Pack - упаковка списка (стирает все null указатели, в моем примере он лишний, так как я null указатели снимаю с помощью delete).

Вот и пошла оптимизация.:)

[armeng]

Вот у меня идея,
а что, если реализовать 3D Life? :confused:

[Agregat]

наверное можно как-то сортировать список тогда тоже можно будет как-нибудь оптимизировать поиск. Точнее сортировать в двух направлениях. Сначала по X, а среди X уже по Y. Вот :)

[Agregat]

для 3Д придется как-то менять правила...

[nm]

Armen!
rech shla o nachinajushih! :)

[armeng]

Originally posted by nm
Armen!
rech shla o nachinajushih! :)
Ой, извини, я подумал, что там есть что то хитрое.

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

[armeng]

Originally posted by Agregat
наверное можно как-то сортировать список тогда тоже можно будет как-нибудь оптимизировать поиск. Точнее сортировать в двух направлениях. Сначала по X, а среди X уже по Y. Вот :)

Правильно.
А вообще надо сортировать так, чтоб физически близкие элемены в списке находились максимально ближе друг другу. (Теория графов?)

[Agregat]

ну собственно, если сортировать по координатам, то близкие друг к другу элементы и окажутся близки друг к другу.
А так... вся игра это либо однокомпонентный или несвязный граф :) :)

[Agregat]

Originally posted by armeng

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

еще есть интересный вариант, я его делал, когда поле циклическое - то есть если фигура движется вниз, потом она появляется сверху и т.д. - развертка глобуса :)

[armeng]

Опять про оптимизацию.
TList имеет метод Sort (там реализован алгоритм QuickSort) который из себя представляет указатель на callback функцию с правилами, назначенными программистом (может чуть плохо объясняю, но думаю суть понятен)). Там надо писать всего несколько строк кода для сортировки.
Благодаря этому во все наследники TList-а (в частности TStringList) можно впихать свой алгоритм сортировки.

p.s. Программисты Borland-а все таки красиво написали VCL.

[Agregat]

задаешь предикат, короче :)

не знаю... дело привычки... ;) по мне вцл так не очень :) он же переписанный owl :)