Кибор :: Версия для печати :: Версия 5.25 Нахождение кратчайшего пути в лабиринте

1. Kibor - 22 Мая, 2017 - 03:41:18 - перейти к сообщению

В этой версии появилась функция которая позволяет находить кратчайший путь в лабиринте.

findpath(#labirint[0][0], #pyt[0][0], sizeX, sizeY)
Первый параметр указатель на двухмерный массив int в котором записан лабиринт в виде:
0 - свободный проход
1 - стена
2 - старт
3 - финиш

Второй параметр указатель на двухмерный массив int в который запишется кратчайший путь в виде нумерации от 0 (старт), до финишной позиции включительно:
0 1 2 3 4 5 и тд.
-1 - все остальное поле лабиринта

Третий - размер лабиринта по X
Четвертый - размер лабиринта по Y

Выделяемая память под первый и второй параметр может быть больше размера лабиринта.

Возвращает функция количество шагов.
-1 если размер лабиринта более чем выделено памяти в массивах.
0 - если пути нет.

========================

Массивы лабиринта и результата заполняются в соответствие:
Первый индекс X
Второй Y.
Нулевой индекс находится в левом верхнем углу лабиринта

Нажмите для увеличения

Пример:
Есть данный лабиринта. Они у нас записаны в фал в таком виде:

Цитата:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 0 0 1 1 1 0 0 3 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0
1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Код читающий файл лабиринта и находящий кратчайший путь:

CODE:

int labirint[330][11];
int pyt[330][11];
int sizeX=33;
int sizeY=11;

if (fopen ("D:\map.txt", "r")!=0)//открываем файл для чтения "r"
{//если открылся
for (int y=0; y<sizeY; y++)
{
for (int x=0; x<sizeX; x++)
{
fread(labirint[x][y]);
}
}
fclose();//закрываем файл
}

int k=findpath(#labirint[0][0], #pyt[0][0], sizeX, sizeY);
messagebox(k);

int xx=200, yy=200;
int n=0;
if (k>0)
{

for (y=0; y<sizeY; y++)
{
xx=200;
for (x=0; x<sizeX; x++)
{
textout(n, xx, yy, format(pyt[x][y]), 0);
n++;
xx=xx+25;
}
yy=yy+25;
}
loop()sleep(10);
}

=====================================================

Видео демострирующее анализ лабиринта по картинке, поск и прорисовку в паинте на нем кратчайшего пути.

Нажмите для увеличения

Скрипт:

CODE:

int labirint[180][180];
int pyt[180][180];
int sizeX, sizeY;

int kx[180][180];
int ky[180][180];

int sX=8;
int sY=145;
int fX=539;
int fY=675;

int image_start[1][1];
int image_finish[1][1];
int image_proxod[3][3];

int erskr[570][570];

int x, y, xxx, yyy, tx, ty;

image_start[0][0]=65280;
image_finish[0][0]=255;
for (x=0; x<3; x++)
{
for (y=0; y<3; y++)image_proxod[x][y]=16777215;
}

pause(1000);
screen (#erskr[0][0], sX, sY, fX, fY, -1);

x=0; y=0;
for (yyy=0; yyy<525; yyy=yyy+4)
{
x=0;
for (xxx=0; xxx<525; xxx=xxx+4)
{
labirint[x][y]=1;
if (findimage(1, #image_proxod[0][0], -1, #tx, #ty, xxx, yyy, xxx+4, yyy+4, #erskr[0][0])==1)labirint[x][y]=0;
if (findimage(1, #image_start[0][0], -1, #tx, #ty, xxx, yyy, xxx+4, yyy+4, #erskr[0][0])==1)labirint[x][y]=2;
if (findimage(1, #image_finish[0][0], -1, #tx, #ty, xxx, yyy, xxx+4, yyy+4, #erskr[0][0])==1)labirint[x][y]=3;
kx[x][y]=xxx+sX;
ky[x][y]=yyy+sY;
x++;
}
y++;
}
sizeX=x;
sizeY=y;

int k=findpath(#labirint[0][0], #pyt[0][0], sizeX, sizeY);

if (k>0)
{
for (y=0; y<sizeY; y++)
{
for (x=0; x<sizeX; x++)
{
if (pyt[x][y]>-1)mouse(LEFT, kx[x][y]+2, ky[x][y]+2);
}
}

if (fopen ("c:\ЛАБИРИНТ.txt", "w")!=0)
{
for (y=0; y<sizeY; y++)
{
for (x=0; x<sizeX; x++)
{
fwrite(labirint[x][y]);
fwrite(" ");
}
fwrite(ENDL);
}
fclose();
}

}

messagebox(k);

2. Kibor - 23 Мая, 2017 - 12:55:24 - перейти к сообщению

На этом видео показана работа доработанного скрипта.
Путь будет прорисовываться не построчно, а от точки старта до финиша.

Скрипт

CODE:

int labirint[180][180];
int pyt[180][180];
int sizeX, sizeY;

int kx[180][180];
int ky[180][180];

int sX=8;
int sY=145;
int fX=539;
int fY=675;

int image_start[1][1];
int image_finish[1][1];
int image_proxod[3][3];

int erskr[570][570];

int x, y, xxx, yyy, tx, ty;

int Xx[20000], Yy[20000];

image_start[0][0]=65280;
image_finish[0][0]=255;
for (x=0; x<3; x++)
{
for (y=0; y<3; y++)image_proxod[x][y]=16777215;
}

pause(1000);
screen (#erskr[0][0], sX, sY, fX, fY, -1);

x=0; y=0;
for (yyy=0; yyy<525; yyy=yyy+4)
{
x=0;
for (xxx=0; xxx<525; xxx=xxx+4)
{
labirint[x][y]=1;
if (findimage(1, #image_proxod[0][0], -1, #tx, #ty, xxx, yyy, xxx+4, yyy+4, #erskr[0][0])==1)labirint[x][y]=0;
if (findimage(1, #image_start[0][0], -1, #tx, #ty, xxx, yyy, xxx+4, yyy+4, #erskr[0][0])==1)labirint[x][y]=2;
if (findimage(1, #image_finish[0][0], -1, #tx, #ty, xxx, yyy, xxx+4, yyy+4, #erskr[0][0])==1)labirint[x][y]=3;
kx[x][y]=xxx+sX;
ky[x][y]=yyy+sY;
x++;
}
y++;
}
sizeX=x;
sizeY=y;

int k=findpath(#labirint[0][0], #pyt[0][0], sizeX, sizeY);

for (y=0; y<sizeY; y++)
{
for (x=0; x<sizeX; x++)
{
if (pyt[x][y]>-1)
{
Xx[pyt[x][y]]=kx[x][y];
Yy[pyt[x][y]]=ky[x][y];
}
}
}

if (k>0)
{
for (int n=0; n<k; n++)
{
mouse(LEFT, Xx[n]+2, Yy[n]+2);
}

if (fopen ("c:\ЛАБИРИНТ.txt", "w")!=0)
{
for (y=0; y<sizeY; y++)
{
for (x=0; x<sizeX; x++)
{
fwrite(labirint[x][y]);
fwrite(" ");
}
fwrite(ENDL);
}
fclose();
}

}

messagebox(k);

3. Skycrew - 23 Мая, 2017 - 14:37:18 - перейти к сообщению

Прикольно!
Это мне напоминает что-то по типу построения кратчайших путей в графах. Там же примерно такая же логика алгоритма вроде? Ты через алгоритм Дейкстры делал?

Вообще было бы очень круто расширить функционал для поиска коротких путей в любых произвольных графах, например:
Вершина А имеет связь с Б и длинна связи: 3
Вершина В имеет связь с Б длинна 1
И так далее, задача найти короткий путь от А к В например.

Данные бы задавались 2-мерным массивом, где по Х все вершины и по Y все вершины -1 связи нет, больше нуля указывается вес связи (типа "длинна" Подмигивание

0 там где вершина сопоставлена сам с собой. Вывод в виде общей длинны пути и массива последовательности шагов по вершинам.

4. tabletka - 23 Мая, 2017 - 17:09:47 - перейти к сообщению

нет слов, спасибо за ап... ))) Правда с длл решил вопрос по твоему совету) но щас будет удобней ))) И что же с блоками 128 блоков(

5. Kibor - 24 Мая, 2017 - 08:29:58 - перейти к сообщению

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

6. AlexM - 20 Июня, 2020 - 05:53:44 - перейти к сообщению

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

7. konctantin777 - 11 Декабря, 2020 - 11:47:57 - перейти к сообщению

Здравствуйте.
А можно пройти лабиринт и вернуться в ту же точку ? Т.е. в игре есть карта и надо где стартуешь, туда и возвращаться пройдя всю.

8. Dantes3000 - 11 Декабря, 2020 - 15:36:31 - перейти к сообщению

konctantin777 , можно

9. konctantin777 - 12 Декабря, 2020 - 01:52:38 - перейти к сообщению

Dantes3000 пишет:

konctantin777 , можно

Понятно, что можно просто ставить несколько точек, чтобы двигался от одно к другой )
А с помощью этой функции, чтобы просто "дал лабиринт" и нарисовало весь возможный путь ?

10. Paskuda - 27 Июня, 2022 - 23:13:19 - перейти к сообщению

Поделитесь скриптиком который бы передвигался по этому кратяайшему пути например с помощю кнопок WASD?