Автоматизация и боты

 Помощь      Поиск      Пользователи
Сайт Кибор     Программируемый кликер Кибор     Видео обучение     Заказать бот

 Страниц (2): [1] 2 »   

> Описание: Нахождение кратчайшего пути в лабиринте. В двухмерном массиве.
Kibor
Отправлено: 22 Мая, 2017 - 11:41:18
Post Id



Администратор
Эксперт


Покинул форум
Сообщений всего: 8095
Дата рег-ции: Март 2013  
Откуда: Одесса
Репутация: 355




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

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);




 
 Top
Kibor
Отправлено: 23 Мая, 2017 - 20:55:24
Post Id



Администратор
Эксперт


Покинул форум
Сообщений всего: 8095
Дата рег-ции: Март 2013  
Откуда: Одесса
Репутация: 355




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



Скрипт
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);

 
 Top
Skycrew
Отправлено: 23 Мая, 2017 - 22:37:18
Post Id



Пользователь
Мастер


Покинул форум
Сообщений всего: 123
Дата рег-ции: Июль 2014  
Репутация: 0




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

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

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

(Отредактировано автором: 23 Мая, 2017 - 22:38:33)

 
 Top
tabletka
Отправлено: 24 Мая, 2017 - 01:09:47
Post Id



Пользователь
Прохожий


Покинул форум
Сообщений всего: 20
Дата рег-ции: Окт. 2016  
Откуда: msk
Репутация: 0




нет слов, спасибо за ап... ))) Правда с длл решил вопрос по твоему совету) но щас будет удобней ))) И что же с блоками 128 блоков(
 
 Top
Kibor
Отправлено: 24 Мая, 2017 - 16:29:58
Post Id



Администратор
Эксперт


Покинул форум
Сообщений всего: 8095
Дата рег-ции: Март 2013  
Откуда: Одесса
Репутация: 355




Простой волновой алгоритм, если учесть что сканирование экрана делать по клеткам, то вполне подходит для движения по разным траекториям.
 
 Top
AlexM
Отправлено: 20 Июня, 2020 - 13:53:44
Post Id



Пользователь
Прохожий


Покинул форум
Сообщений всего: 3
Дата рег-ции: Март 2019  
Репутация: 0




нужно запилить параметр включения артогонально-диагонального алгоритма.
Мнем б щас очень пригодился.
 
 Top
konctantin777
Отправлено: 11 Декабря, 2020 - 19:47:57
Post Id



Пользователь
Эксперт


Покинул форум
Сообщений всего: 1136
Дата рег-ции: Окт. 2017  
Откуда: Архангельск
Репутация: 6




Здравствуйте.
А можно пройти лабиринт и вернуться в ту же точку ? Т.е. в игре есть карта и надо где стартуешь, туда и возвращаться пройдя всю.
 
 Top
Dantes3000
Отправлено: 11 Декабря, 2020 - 23:36:31
Post Id



Пользователь
Эксперт


Покинул форум
Сообщений всего: 1465
Дата рег-ции: Июнь 2016  
Репутация: 58




konctantin777 , можно
 
 Top
konctantin777
Отправлено: 12 Декабря, 2020 - 09:52:38
Post Id



Пользователь
Эксперт


Покинул форум
Сообщений всего: 1136
Дата рег-ции: Окт. 2017  
Откуда: Архангельск
Репутация: 6




 Dantes3000 пишет:
konctantin777 , можно


Понятно, что можно просто ставить несколько точек, чтобы двигался от одно к другой )
А с помощью этой функции, чтобы просто "дал лабиринт" и нарисовало весь возможный путь ?
 
 Top
Paskuda
Отправлено: 28 Июня, 2022 - 07:13:19
Post Id



Пользователь
Участник


Покинул форум
Сообщений всего: 61
Дата рег-ции: Янв. 2021  
Репутация: 0




Поделитесь скриптиком который бы передвигался по этому кратяайшему пути например с помощю кнопок WASD?
 
 Top
Страниц (2): [1] 2 »
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« О программе Кибор »


Все гости форума могут просматривать этот раздел.
Только администраторы и модераторы могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 




Powered by