Генерация лабиринтов

← →
Soroka © (2004-10-27 15:41) [0]

Привет _профессора _игр !
Решила _вот_ спросить, _можно_ ли_ написать_ на_ ГЛ_сцене_ гнератор_ лабиринтов, _очень_ надо._Если _да, _тто_подскажите_где_взять_пример_того_что_нужно_для_этого_знать.
Заранее_всем_спасибочки.

← →
Darthman © (2004-10-27 16:13) [1]

генератор лабиринтов писать надо не на ГЛсцене. На ней только рисовать. Генерировать надо на делфи :)
А чего с подчеркиваниями? ТипаНастоящимПрограммистамПробелыНеНужны?

← →
П7 (2004-10-27 18:43) [2]

бот... (:

← →
Soroka © (2004-10-27 22:26) [3]

Пробелов небыло, так это что-то было с оперой, перегрузиться не могла, т.к. сливала файлы.
Интересно какже можно это сделать на делфи не рисуя ?

← →
DeadMeat © (2004-10-28 01:17) [4]

На http://delphigfx.mastak.ru кажись есть статьи по поиску пути. Там помойму было и такое
Плюс Portal из самого GLScene

---
...Death Is Only The Begining...

← →
Кто---то © (2004-10-28 07:04) [5]

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

← →
П7 (2004-10-28 07:24) [6]

Да их МОРЕ. Обратите свой взгляд на roguelike-игры. Половина из них генерит свои ровни (в основном подземелья) на лету. ADMO, DeadCold (к нему есть исходники на FreePascal) и др. В Сети есть ГОРЫ и ГРУДЫ статей на эту тему. Лентяи вы! (:

← →
Soroka © (2004-10-28 08:43) [7]

Незнаю _П7, _в_Яндексе_ничего_хорошего _не_ нашла._Странно_у_меня _на_работе_что_то_Опера_глючит, _пробелы_не _ставятся.
В_играх_конечно_да, _а_в_примерах_или_документации_?
DeadMeat,_в_портале_нет_генерации_лабиринта._Его_только_можно_построить_на_портале.

← →
Colt1978 (2004-10-28 15:51) [8]

Soroka, насколько я знаю в инете полно всяких формул генерации лабиринтов, просто их результат работы тебе придётся просто присандалить к порталу, хотя я не асс в этом но я думаю всё же за пару деньком это сделать можно...

← →
Colt1978 (2004-10-28 15:52) [9]

и кстати используй эксплорер в конце концов чтоли или оперу переставь, в глазах рябит от таких предложений и фраз с подчёркванием

← →
Darthman © (2004-10-28 16:44) [10]

можно_ ли_ написать_ на_ ГЛ_сцене_ гнератор_ лабиринтов или отрисовщик? Определись с задачей сначала. Генерация в GLScene не нуждается совсем.

← →
DeadMeat © (2004-10-28 23:12) [11]

> [7] Soroka © (28.10.04 08:43)

Я ж ссылку привел. Там статьи на эту тему есть. А портал очень хорошо подходит просто для реализации...

---
...Death Is Only The Begining...

← →
марсианин © (2004-10-28 23:40) [12]

http://algolist.manual.ru/games/maze.php

← →
П7 (2004-10-29 14:04) [13]

Блин.
Выкини свой яндекс. Извини, конечно, но тебе дали ОГРОМНУЮ тему для поиска. Когда я искал подобную инфу, то нашёл ГРУДЫ всякой инфы. С примерами и полными описаниями процессов генерации. Если ты не можешь искать информацию в Сети, то помочь тебе не может никто. Может ты перед тем, как учиться программировать, научишься искать информацию.
Кое кто тебе даже ссылки привёл, но ты, видимо, их тоже не нашла... (:
На сём прощаюсь...

← →
rts111 © (2004-10-29 16:42) [14]

Вот написал вроде работает

procedure TForm1.Button1Click(Sender: TObject);
var
lab:array of array of byte;
s,w,h:word;
y,x:integer;
pic:tbitmap;
xsm,ysm:integer;
tn,tx,ty:integer;
ttt:boolean;
begin

Randomize;
s:=4; // размер блока
w:=99;h:=69;// НЕ ЧЕТНЫЕ
setlength(lab,h,w);
for y:=0 to h-1 do for x:=0 to w-1 do
if(x=0)or(y=0)or(x=w-1)or(y=h-1)
then lab[y,x]:=1 else lab[y,x]:=0;
lab[0,1]:=0;lab[h-1,w-2]:=0;

for tn:=1 to 10000 do /////// Генерация ///////////////
begin
tx:=random(w div 2)*2;
ty:=random(h div 2)*2;
if lab[ty,tx]>0
then begin
case random(4)of
0:begin xsm:= 1;ysm:= 0;end;
1:begin xsm:=-1;ysm:= 0;end;
2:begin xsm:= 0;ysm:= 1;end;
3:begin xsm:= 0;ysm:=-1;end;
end;
ttt:=true;
while ttt
do begin
ttt:=false;
if(tx+xsm>0)and(tx+xsm<w-1)and(ty+ysm>0)and(ty+ysm<h-1)then
if(lab[ty+ysm,tx+xsm]=0)and(lab[ty+2*ysm,tx+2*xsm]=0)then
begin
lab[ty+ysm,tx+xsm]:=1;
ty:=ty+ysm;
tx:=tx+xsm;
ttt:=true;
end
end;
end;
end;/////////////////////////////////////////////////////

pic:=tbitmap.Create;
pic.Width:=w*s;pic.Height:=h*s;pic.Canvas.Brush.Color:=0;
for y:=0 to h-1 do for x:=0 to w-1 do
if lab[y,x]>0 then pic.Canvas.Rectangle(x*s,y*s,x*s+s,y*s+s);
canvas.Draw(10,10,pic);
pic.Free;

end;

← →
Darthman © (2004-10-29 18:26) [15]

а выход из этого лабиринта будет? :)

← →
Colt1978 (2004-10-30 17:53) [16]

Слушай... прикольно... Можешь добавить возможность распечатки я люблю проходить лабиранты.
Я думаю сможет ли кто теперь этот кусок к порталу прикрутить ??? Можно карты теперь на писать а такими вот герерирующимися уровнями себя баловать....

← →
Soroka © (2004-10-31 14:34) [17]

Код _проверила - отличный.
Все _лабиринты_проходимые,_т.е._нет _тупиковых,_здорово._Пытаюсь _пока_прикрутить_всё_этоэто_к_порталу._Правда_пока_нет_успехов_на_данном_поприще.
Заодно_решила_спросить_а _возможно_ли_построение_пути_прохождения_этогото_лабиринта_?

← →
rts111 © (2004-10-31 17:16) [18]

procedure TForm1.Button1Click(Sender: TObject);
var
lab:array of array of word;
s,w,h:word;
p:real;
j,i:integer;
xsm,ysm:integer;
tn,tx,ty:integer;
ShowWay,NeedCheck:boolean;
enterX,enterY,exitX,exitY:word;
begin

s:=3; // размер блока
w:=139; // ширина
h:=99; // высота
p:=3; // плотность, если много меньше 1 получаются комнаты
ShowWay:=true;

setlength(lab,h,w);
for j:=0 to h-1 do
for i:=0 to w-1 do
if(i=0)or(j=0)or(i=w-1)or(j=h-1)
then lab[j,i]:=1
else lab[j,i]:=0;

enterX:=0;enterY:=(h div 2)or 1;lab[enterY,enterX]:=0; // вход
exitX:=w-1;exitY:=(h div 2)or 1;lab[exitY,exitX]:=0; // выход

Randomize;

for tn:=1 to round(w*h*p) do /////// Генерация ///////////////
begin
tx:=random(w div 2)*2;
ty:=random(h div 2)*2;
if lab[ty,tx]>0
then begin
case random(4)of
0 :begin xsm:= 1;ysm:= 0;end;
1 :begin xsm:=-1;ysm:= 0;end;
2 :begin xsm:= 0;ysm:= 1;end;
else begin xsm:= 0;ysm:=-1;end;
end;
NeedCheck:=true;
while NeedCheck
do begin
NeedCheck:=false;
if(tx+xsm>0)and(tx+xsm<w-1)and(ty+ysm>0)and(ty+ysm<h-1)then
if lab[ty+2*ysm,tx+2*xsm]=0 then
begin
lab[ty+ysm,tx+xsm]:=1;
ty:=ty+ysm;
tx:=tx+xsm;
NeedCheck:=true;
end
end;
end;
end;/////////////////////////////////////////////////////

Refresh;
canvas.Brush.Color:=0;
canvas.Pen.Color:=0;
for j:=0 to h-1 do for i:=0 to w-1 do if lab[j,i]=1 then
Canvas.Rectangle(i*s+10,j*s+10,i*s+s+10,j*s+s+10);

if ShowWay then
begin /////////////////////////////////////////////////////////////
lab[enterY,enterX]:=3;
while lab[exitY,exitX]=0
do begin
for j:=0 to h-1 do
for i:=0 to w-1 do
if lab[j,i]>1
then begin
if i<w-1 then if lab[j,i+1]=0 then lab[j,i+1]:=lab[j,i]+1;
if i>0 then if lab[j,i-1]=0 then lab[j,i-1]:=lab[j,i]+1;
if j<h-1 then if lab[j+1,i]=0 then lab[j+1,i]:=lab[j,i]+1;
if j>0 then if lab[j-1,i]=0 then lab[j-1,i]:=lab[j,i]+1;
end
end;

tx:=exitX;
ty:=exitY;
tn:=lab[ty,tx];
lab[ty,tx]:=2;
while lab[enterY,enterX]=3
do begin
if tx>0 then if lab[ty,tx-1]=tn-1 then tx:=tx-1;
if tx<w-1 then if lab[ty,tx+1]=tn-1 then tx:=tx+1;
if ty>0 then if lab[ty-1,tx]=tn-1 then ty:=ty-1;
if ty<h-1 then if lab[ty+1,tx]=tn-1 then ty:=ty+1;
tn:=lab[ty,tx];
lab[ty,tx]:=2;
end;

canvas.Brush.Color:=$00ff00;
canvas.Pen.Color:=$00ff00;
for j:=0 to h-1 do for i:=0 to w-1 do
case lab[j,i] of
2:Canvas.Rectangle(i*s+10,j*s+10,i*s+s+10,j*s+s+10);
1:;
else lab[j,i]:=0;
end;//case

end;///////////////////////////////////////////////////////////////

end;

← →
Colt1978 (2004-11-01 16:21) [19]

Что-то глядя на код не понял ... перебором чтоли идёт ?

← →
П7 (2004-11-01 17:07) [20]

Лабиринты могжно представить 2 видов:
1. С комнатами
2. Без оных

В первом случае рисуются рендомные комнаты, затем соединяются
Во втором просто передором из рендомных точек прокладываем трассы до их пересечения... (: + Всякие условия, для большей красоты...

← →
Colt1978 (2004-11-01 20:47) [21]

Красивые лабиринты получаются... Прикольно

← →
rts111 © (2004-11-02 14:07) [22]

Если вы используете приведенный выше код, замените
...
tx:=random(w div 2)*2;
ty:=random(h div 2)*2;
...
на
...
tx:=random((w+1)div 2)*2;
ty:=random((h+1)div 2)*2;
...

← →
Soroka © (2004-11-02 16:27) [23]

Сорри_а_зачем_их_менять_? _Я_визуального_изменения_не_нашла_.
Можно_ещё_спросить_а _что_это_за_плотность_(переменная)_для_чего_она_я_так_и_не_поняла_?

← →
Colt1978 (2004-11-02 16:36) [24]

Поприколу будет если создавать сразу 2-е бээмпехи и закидывать лабиринт а в другую прохождение его.... Можно потом во всякие журналы слать головоломки... :-)

Soroka ты замутила лабирин уже на портале ? Интересно было бы глянуть...

Soroka
Менять нужно чтобы стены примыкали и к нижней и к правой стене,
получаются более запутанные лабиринты.

Попробуй p:=0.1;или еще меньше - сгенерируются комнаты.

-----------------------

Если вставить в цикл генератора while строчку {*} и увеличить p,
получаются более запутанные лабиринты,

if ...
if ...
begin
if not odd(tx+ty)then if random<0.3 then break;{*}
lab[ty+ysm,tx+xsm]:=1;
...

rts111
Незнаю. попробовала с такими вот величинами:
s:=3; // размер блока
w:=239; // ширина
h:=201; // высота
p:=300;
звёздочку добавила...
В результате почему то путь в 9 случаях из 10 практически прямой, т.е. идёт через центр с маленькими заворотами. Глянь на размер карты лабиринта - раньше лучше вродебы было.
Colt1978 - ты замутила лабирин уже на портале ? Интересно было бы глянуть...
Нет, у меня ничего не выходит, уже устала сидеть за компом.

s:=3; // размер блока
w:=139; // ширина
h:=99; // высота
p:=0.3 (+ -) 0.2;

(if not odd(tx+ty)then if random<0.3 then break;-если нужны коматы
эту сточку не вставляй)

Как результат?

(if not odd(tx+ty)then if random<0.3 then break; - эта строчка
влияет на длину стен попробуй например if random<0.01)

------------
от p - зависит количество стен.

Помоему ты что-то напутал...

Попробуй следующие значения:

s:=3; // размер блока
w:=239; // ширина
h:=139; // высота
p:=0.2;

if not odd(tx+ty)then if random < 0.02 then break; {*}
//... if random<0.02 <- чем больше это число, тем короче стены (0.02<<1)
//если тебе не понятно можешь строчку {*} совсем удалить.

Так _намного_ лучше...
Всёже_может _кто_подскажет_как_хотябы_написать_лабиринт_не_на_портале_в_ПДЫсуту_а_на_чистом_Open_GL_?

← →
Colt1978 (2004-11-11 13:51) [32]

Soroka, пиши сама.... Похоже тут никто не может, я сам както хотел разобраться с порталом, но потом остыл. Для своего проекта я не собираюсь использовать лабиринты, как хотел раньше. Что мне было необходимо нарисовал в Максе

← →
Mike_Vazowskyi (2004-11-29 00:05) [33]

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

Вчера было время, решил поправить код приведенный выше,
вынести в отдельные функции генерацию и поиск пути, засиделся,
получилась такая программа, пока сырая:

http://rts111.narod.ru/labcode.rar - 4Kb.- код
http://rts111.narod.ru/labexe.rar - 180Kb.- exe
http://rts111.narod.ru/d3.html - описание(2 строчки) :)

Mike_Vazowskyi

>...а как можно его подправить чтоб было несколько выходов???

lab[x,y]:=0; x,y-координаты еще одного выхода.

>..но проходился он, в тоже время, по самому оптимальному???

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

Посмотри программу, там все это реализовано.

← →
Colt1978 (2004-12-04 17:04) [35]

> rts111 © (04.12.04 04:40) [34]

Даваольно таки интересно у тебя получилось...
Слыш а прикинь как тут кто-то писал в 3D это засунуть.... Туман... Гдето проглядывается конец лабиринта... и 3D лабиринт... Над ним летает камера, идёт игрок...
Помоему круто бы вышло...

Генерация лабиринтов Найти похожие ветки