От 6 до 0
To: 7
To: 8
To: 5
To: 4
To: 3
To: 0 BOOM
Всего стоимость маршрута: 100
игра лабиринт
подскажите пожалуйста, каким образом можно найти кратчайший путь в лабиринте, при прохождении можно использовать какое-то количество бомб данное в начале. не могу придумать какой либо приличный алгоритм.
Также хотелось бы находить путь максимальный по количеству очков. т.е. например в начале дается 1000 очков, за каждый ход вычитается 10 очков, за каждую использованную бомбу вычитается 50. как пройти лабиринт, чтоб получить как можно больше очков.
Также хотелось бы находить путь максимальный по количеству очков. т.е. например в начале дается 1000 очков, за каждый ход вычитается 10 очков, за каждую использованную бомбу вычитается 50. как пройти лабиринт, чтоб получить как можно больше очков.
Опишите задачу поподробнее. В любом случае это какой-то алгоритм на графах - то ли алгоритм Дейкстры, то ли алгоритмы Прима / Краскала и т.п., в зависимости от того, что вам нужно.
все приведенные алгоритмы плохо подходят т.к. в ходе поиска пути можно разрушать стены лабиринта
А в чем проблема? Просто переход из вершины к вершине, между которыми есть стена, осуществляется по ребру с отрицательным весом. А вместо алгоритма Дейкстры, для которого отрицательный вес ребер запрещен, можно взять Беллмана - Форда, к примеру.
слишком много ребер получается и как ты учтешь в графе исчерпание запаса бомб?
Цитата: LM(AL/M)
как ты учтешь в графе исчерпание запаса бомб?
Например, так: я ищу кратчайшие пути от точки, где находится объект в лабиринте, до всех граничных точек карты, при этом я сохраняю число очков, набранных на этом пути, и количество ходов до выхода. Зная начальные условия (число очко, количество бомб, вес одного хода и вес одной бомбы), всегда можно ответить, был ли исчерпан лимит. Согласен, многовато операций получится, но тут по ситуации надо смотреть. А какие еще варианты предлагаете?
Откуда вообще отрицательные ребра? Нет никаких отрицательных ребер.
Стандартный лабиринт - клечатое поле, где некоторые клетки заняты стенами. Отдельно список ребер хранить глупо, нужен просто двумерный массив стен.
Переход в соседнюю клетку весит 1, переход в занятую клетку весит 5. Дважды наступать в одну и ту же клетку не требуется, так что отмечать в лабиринте взорванные стены не нужно.
Если бы все переходы были одного веса, проще всего было бы использовать обход в ширину.
Наличие переходов веса 5 означает, что нужно делать дейкстру. Если нужно чтобы быстрее работало - дейкстра с кучей (heap).
Все просто :)
P.S Исчерпание запаса бомб несколько усложняет дело, сейчас подумаю и напишу что-нибудь.
Стандартный лабиринт - клечатое поле, где некоторые клетки заняты стенами. Отдельно список ребер хранить глупо, нужен просто двумерный массив стен.
Переход в соседнюю клетку весит 1, переход в занятую клетку весит 5. Дважды наступать в одну и ту же клетку не требуется, так что отмечать в лабиринте взорванные стены не нужно.
Если бы все переходы были одного веса, проще всего было бы использовать обход в ширину.
Наличие переходов веса 5 означает, что нужно делать дейкстру. Если нужно чтобы быстрее работало - дейкстра с кучей (heap).
Все просто :)
P.S Исчерпание запаса бомб несколько усложняет дело, сейчас подумаю и напишу что-нибудь.
Цитата: P*t*
Откуда вообще отрицательные ребра? Нет никаких отрицательных ребер.
Упс... Я пошел учиться внимательно читать условие. :) Мне показалось, что за каждый ход прибавляется 10, а за каждую бомбу вычитается 50. Да, если так, то действительно все гораздо проще.
не ... тут что-то мутное написано... одно и то же кол-во бомб можно разными способами расставить на карте преобразуя таким образом исходный граф во много новых графов, на каждом из которых можно искать оптимальный по какому-то критерию путь. Поэтому я говорю что вариант с отрицательными весами не позволяет учитывать запас бомб.
насчет своих вариантов... нету времени раздумывать над этим, но может пройдет полный перебор с отсечением по рекорду. Т.е. для каждой пройденной клетки и каждого кол-ва бомб с которым мы в нее приходим запоминать мин. кол-во ходов и дальше отскекать пути которые приводят в ту же клетку с меньшим запасом бомб или большим кол-вом ходов -- примерно так
насчет своих вариантов... нету времени раздумывать над этим, но может пройдет полный перебор с отсечением по рекорду. Т.е. для каждой пройденной клетки и каждого кол-ва бомб с которым мы в нее приходим запоминать мин. кол-во ходов и дальше отскекать пути которые приводят в ту же клетку с меньшим запасом бомб или большим кол-вом ходов -- примерно так
LM(AL/M),
1) вариант с отрицательными весами только что отпал;
2) вы предлагаете расставлять некоторое фиксированное количество бомб, а я обдумывал вариант, когда я изначально предполагаю, что количество бомб не лимитировано, а после прохождения каждого пути проверяю, не превысило ли количество использованных бомб первоначально заданное количество.
Я ведь могу формально образовать граф следующим образом: если между вершинами нет стены, их соединяет ребро весом 10, в противном случае - ребро весом 50.
1) вариант с отрицательными весами только что отпал;
2) вы предлагаете расставлять некоторое фиксированное количество бомб, а я обдумывал вариант, когда я изначально предполагаю, что количество бомб не лимитировано, а после прохождения каждого пути проверяю, не превысило ли количество использованных бомб первоначально заданное количество.
Я ведь могу формально образовать граф следующим образом: если между вершинами нет стены, их соединяет ребро весом 10, в противном случае - ребро весом 50.
Итак, я подумал.
С огранниченным запасом бомб получается совсем по другому. Берем 3-мерный массив a[x,y,p], где x и y - координата клетки в лабиринте, p - количество использованных бомб. В каждой ячейке будет храниться число, сколько нужно потратить, чтоб в это состояние попасть.
Массив заполняется обходом в ширину, запущенным в цикле по P. При переходе к каждому следующему значению P, для предыдущих P все уже будет посчитано. В a[x,y,p] можно перейти либо из a[x+/-1,y+-1,p] cо стоимостью 1, либо из a[x+/-1,y+/-1,p-1] со стоимостью 5. Нужно написать подробнее?
Если оптимизация пути не требуется, то можно побить исходный лабиринт на компоненты связности и дальше рассматривать уже состоящий из них граф.
С огранниченным запасом бомб получается совсем по другому. Берем 3-мерный массив a[x,y,p], где x и y - координата клетки в лабиринте, p - количество использованных бомб. В каждой ячейке будет храниться число, сколько нужно потратить, чтоб в это состояние попасть.
Массив заполняется обходом в ширину, запущенным в цикле по P. При переходе к каждому следующему значению P, для предыдущих P все уже будет посчитано. В a[x,y,p] можно перейти либо из a[x+/-1,y+-1,p] cо стоимостью 1, либо из a[x+/-1,y+/-1,p-1] со стоимостью 5. Нужно написать подробнее?
Если оптимизация пути не требуется, то можно побить исходный лабиринт на компоненты связности и дальше рассматривать уже состоящий из них граф.
можно поподробнее.
сейчас у меня написан обычный поиск в ширину, т.е. я просто обхожу стены.
по вашему алгоритму получится, что в конце для каждой клетки лабиринта я буду знать какое минимальное количество бомб мне понадобится чтобы туда добраться?
на компоненты связности побить не получится. или я что-то неправильно поняла?
граф может быть и связным. но например у меня есть 3 бомбы и взорвав 3 стены я могу дойти до финиша за 10 шагов, а обходя стены только за 30.
сейчас у меня написан обычный поиск в ширину, т.е. я просто обхожу стены.
по вашему алгоритму получится, что в конце для каждой клетки лабиринта я буду знать какое минимальное количество бомб мне понадобится чтобы туда добраться?
на компоненты связности побить не получится. или я что-то неправильно поняла?
граф может быть и связным. но например у меня есть 3 бомбы и взорвав 3 стены я могу дойти до финиша за 10 шагов, а обходя стены только за 30.
Цитата: rusan
по вашему алгоритму получится, что в конце для каждой клетки лабиринта я буду знать какое минимальное количество бомб мне понадобится чтобы туда добраться?
Нет, для каждой клетки и для каждого количества использованных бомб вы будете знать стоимость пути до этой точки.
То есть в a[10,10,2] будет ответ (суммарная стоимость пути) для точки 10 10, получающийся при использовании ровно 2-х бомб. Нужно будет еще взять минимум по количеству бомб - min(a[10,10,0], a[10,10,1], a[10,10,2] ...)
Цитата: rusan
на компоненты связности побить не получится. или я что-то неправильно поняла?
граф может быть и связным. но например у меня есть 3 бомбы и взорвав 3 стены я могу дойти до финиша за 10 шагов, а обходя стены только за 30.
Я имел в виду, что если оптимальность пути не требуется, то внутри компоненты связности можно передвигаться "бесплатно". Тогда можно взять граф, где вершины - компоненты связности, а веса ребер - количество стен, которые нужно взорвать для перехода от одной компоненты к другой. По такому графу можно будет идти алгоритмом Декстра. Этот способ более сложен в реализации, не стоит пытаться в данном случае его использовать.
хорошо, это поняла. но в этом случае получится стоимость пути, если задавать веса для прохода стенки. а как быть если мне просто нужно найти кратчайший путь с использованием данного количества бомб. но никаких весов нет.
просто я хочу сделать два варианта прохождения игры, один на минимальность пути, а другой на максимум по очкам.
спасибо за ответы. завтра подумаю, сегодня уже совсем мозг не варит!
просто я хочу сделать два варианта прохождения игры, один на минимальность пути, а другой на максимум по очкам.
спасибо за ответы. завтра подумаю, сегодня уже совсем мозг не варит!
Вес для прохода стенки можно сделать единичным (как для обычного прохода). Тогда в каждой ячейке массива будет как раз длина пути в соответствующую точку с соответствующим числом прохождений стенок.
Чтобы восстановить сам путь, нужно двигаться по нашему трехмерному массиву в обратном направлении (от конечной точки пути) так, чтоб на каждом шаге длина пути до рассматриваемой точки становилась на 1 меньше. То есть для каждой клетки определяется, откуда в нее пришли.
Чтобы восстановить сам путь, нужно двигаться по нашему трехмерному массиву в обратном направлении (от конечной точки пути) так, чтоб на каждом шаге длина пути до рассматриваемой точки становилась на 1 меньше. То есть для каждой клетки определяется, откуда в нее пришли.
Рекурсия рулит:)
Достаточно просто переделать для нахождения кратчайшего пути.
Ну и да тут много недочётов, накидал на коленке, так что сори за какашкокод.
В выше приведённом коде в качестве примера этот лабиринт(иЗвиНиТЕ зА НеРоВНый ПочЕРк) :
[ATTACH=CONFIG]5069[/ATTACH]
Достаточно просто переделать для нахождения кратчайшего пути.
Ну и да тут много недочётов, накидал на коленке, так что сори за какашкокод.
Код:
#include <iostream>
#include <set>
#include <vector>
using namespace std;
#define bomb_cost 50
#define step_cost 10
#define max_bombs 5
typedef pair<int,bool> step;
typedef vector<step> steps;
class labirint
{
public:
labirint()
{
peaks.clear();
access.clear();
}
void setpeakcount(unsigned int peakcount)
{
peaks.clear();
access.clear();
steps a;
a.clear();
for(unsigned int x=0;x<peakcount;x+=1)
{
peaks.push_back(x);
access.push_back(a);
}
}
void addaccess(int from,int to, bool bomb=false)
{
if(from<peaks.size() && to<peaks.size())
{
access.at(from).push_back(step(to,bomb));
}
}
steps find(int from,int to)
{
currtrace.clear();
mintrace.clear();
if(from<peaks.size() && to<peaks.size())
{
bool * blah=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
blah[x]=false;
blah[from]=true;
recurse(from,to,max_bombs,blah);
delete[] blah;
}
return mintrace;
}
static int lengthoftrace(steps &trace)
{
int ret=0;
for(int x=0;x<trace.size();x+=1)
ret+=(trace.at(x).second?bomb_cost:step_cost);
return ret;
}
private:
void recurse(int peaknumb,int peakto,int havebombs,bool * visiteds)
{
if(havebombs<0)
return;
if(peaknumb==peakto)
{
//add to min's array
if((lengthoftrace(mintrace)>=lengthoftrace(currtrace)) || lengthoftrace(mintrace)==0)
mintrace=currtrace;
return;
}
if(lengthoftrace(mintrace)<lengthoftrace(currtrace) && lengthoftrace(mintrace)!=0)
return;
bool * visited=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
visited[x]=visiteds[x];
visited[peaknumb]=true;
//recurs for subs
for(int x=0;x<access.at(peaknumb).size();x+=1)
{
if(!visited[access.at(peaknumb).at(x).first])
{
currtrace.push_back(access.at(peaknumb).at(x));
recurse(access.at(peaknumb).at(x).first,peakto,havebombs-access.at(peaknumb).at(x).second,visited);
currtrace.pop_back();
}
}
delete [] visited;
}
vector<int> peaks;
vector<step> currtrace;
vector<step> mintrace;
vector<steps> access;
};
int main()
{
//Ввод графа
labirint zz;
zz.setpeakcount(40);
/* for(int x=0;x<25;x+=1)
{
if(x-5>=0)
qWarning(" zz.addaccess(%d,%d);",x,x-5);
if(x%5!=0)
qWarning(" zz.addaccess(%d,%d);",x,x-1);
if(x%5!=4)
qWarning(" zz.addaccess(%d,%d);",x,x+1);
if(x+5<25)
qWarning(" zz.addaccess(%d,%d);",x,x+5);
}*/
zz.addaccess(0,1);
zz.addaccess(0,5);
zz.addaccess(1,0);
zz.addaccess(1,2);
zz.addaccess(1,6,true);
zz.addaccess(2,1);
zz.addaccess(2,3);
zz.addaccess(2,7,true);
zz.addaccess(3,2);
zz.addaccess(3,4);
zz.addaccess(3,8,true);
zz.addaccess(4,3);
zz.addaccess(4,9);
zz.addaccess(5,0);
zz.addaccess(5,6,true);
zz.addaccess(5,10);
zz.addaccess(6,1,true);
zz.addaccess(6,5,true);
zz.addaccess(6,7);
zz.addaccess(6,11);
zz.addaccess(7,2,true);
zz.addaccess(7,6);
zz.addaccess(7,8);
zz.addaccess(7,12);
zz.addaccess(8,3,true);
zz.addaccess(8,7);
zz.addaccess(8,9);
zz.addaccess(8,13);
zz.addaccess(9,4);
zz.addaccess(9,8);
zz.addaccess(9,14);
zz.addaccess(10,5);
zz.addaccess(10,11,true);
zz.addaccess(10,15);
zz.addaccess(11,6);
zz.addaccess(11,10,true);
zz.addaccess(11,12);
zz.addaccess(11,16,true);
zz.addaccess(12,7);
zz.addaccess(12,11);
zz.addaccess(12,13);
zz.addaccess(12,17,true);
zz.addaccess(13,8);
zz.addaccess(13,12);
zz.addaccess(13,14);
zz.addaccess(13,18,true);
zz.addaccess(14,9);
zz.addaccess(14,13);
zz.addaccess(14,19,true);
zz.addaccess(15,10);
zz.addaccess(15,16);
zz.addaccess(15,20,true);
zz.addaccess(16,11,true);
zz.addaccess(16,15);
zz.addaccess(16,17);
zz.addaccess(16,21,true);
zz.addaccess(17,12,true);
zz.addaccess(17,16);
zz.addaccess(17,18);
zz.addaccess(17,22,true);
zz.addaccess(18,13,true);
zz.addaccess(18,17);
zz.addaccess(18,19);
zz.addaccess(18,23,true);
zz.addaccess(19,14,true);
zz.addaccess(19,18);
zz.addaccess(19,24);
zz.addaccess(20,15,true);
zz.addaccess(20,21);
zz.addaccess(21,16,true);
zz.addaccess(21,20);
zz.addaccess(21,22);
zz.addaccess(22,17,true);
zz.addaccess(22,21);
zz.addaccess(22,23);
zz.addaccess(23,18,true);
zz.addaccess(23,22);
zz.addaccess(23,24);
zz.addaccess(24,19);
zz.addaccess(24,23);
//Расчёт и вывод результатов
steps res=zz.find(20,4);
cout<<"От "<<20<<" до "<<4<<"\n";
for(int x=0;x<res.size();x+=1)
{
cout<<"To: "<<res.at(x).first;
if(res.at(x).second)
cout<<" BOOM";
cout<<"\n";
}
cout<<"Всего стоимость маршрута: "<<labirint::lengthoftrace(res)<<"\n";
res=zz.find(11,20);
cout<<"От "<<11<<" до "<<20<<"\n";
for(int x=0;x<res.size();x+=1)
{
cout<<"To: "<<res.at(x).first;
if(res.at(x).second)
cout<<" BOOM";
cout<<"\n";
}
cout<<"Всего стоимость маршрута: "<<labirint::lengthoftrace(res)<<"\n";
return 0;
}
#include <set>
#include <vector>
using namespace std;
#define bomb_cost 50
#define step_cost 10
#define max_bombs 5
typedef pair<int,bool> step;
typedef vector<step> steps;
class labirint
{
public:
labirint()
{
peaks.clear();
access.clear();
}
void setpeakcount(unsigned int peakcount)
{
peaks.clear();
access.clear();
steps a;
a.clear();
for(unsigned int x=0;x<peakcount;x+=1)
{
peaks.push_back(x);
access.push_back(a);
}
}
void addaccess(int from,int to, bool bomb=false)
{
if(from<peaks.size() && to<peaks.size())
{
access.at(from).push_back(step(to,bomb));
}
}
steps find(int from,int to)
{
currtrace.clear();
mintrace.clear();
if(from<peaks.size() && to<peaks.size())
{
bool * blah=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
blah[x]=false;
blah[from]=true;
recurse(from,to,max_bombs,blah);
delete[] blah;
}
return mintrace;
}
static int lengthoftrace(steps &trace)
{
int ret=0;
for(int x=0;x<trace.size();x+=1)
ret+=(trace.at(x).second?bomb_cost:step_cost);
return ret;
}
private:
void recurse(int peaknumb,int peakto,int havebombs,bool * visiteds)
{
if(havebombs<0)
return;
if(peaknumb==peakto)
{
//add to min's array
if((lengthoftrace(mintrace)>=lengthoftrace(currtrace)) || lengthoftrace(mintrace)==0)
mintrace=currtrace;
return;
}
if(lengthoftrace(mintrace)<lengthoftrace(currtrace) && lengthoftrace(mintrace)!=0)
return;
bool * visited=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
visited[x]=visiteds[x];
visited[peaknumb]=true;
//recurs for subs
for(int x=0;x<access.at(peaknumb).size();x+=1)
{
if(!visited[access.at(peaknumb).at(x).first])
{
currtrace.push_back(access.at(peaknumb).at(x));
recurse(access.at(peaknumb).at(x).first,peakto,havebombs-access.at(peaknumb).at(x).second,visited);
currtrace.pop_back();
}
}
delete [] visited;
}
vector<int> peaks;
vector<step> currtrace;
vector<step> mintrace;
vector<steps> access;
};
int main()
{
//Ввод графа
labirint zz;
zz.setpeakcount(40);
/* for(int x=0;x<25;x+=1)
{
if(x-5>=0)
qWarning(" zz.addaccess(%d,%d);",x,x-5);
if(x%5!=0)
qWarning(" zz.addaccess(%d,%d);",x,x-1);
if(x%5!=4)
qWarning(" zz.addaccess(%d,%d);",x,x+1);
if(x+5<25)
qWarning(" zz.addaccess(%d,%d);",x,x+5);
}*/
zz.addaccess(0,1);
zz.addaccess(0,5);
zz.addaccess(1,0);
zz.addaccess(1,2);
zz.addaccess(1,6,true);
zz.addaccess(2,1);
zz.addaccess(2,3);
zz.addaccess(2,7,true);
zz.addaccess(3,2);
zz.addaccess(3,4);
zz.addaccess(3,8,true);
zz.addaccess(4,3);
zz.addaccess(4,9);
zz.addaccess(5,0);
zz.addaccess(5,6,true);
zz.addaccess(5,10);
zz.addaccess(6,1,true);
zz.addaccess(6,5,true);
zz.addaccess(6,7);
zz.addaccess(6,11);
zz.addaccess(7,2,true);
zz.addaccess(7,6);
zz.addaccess(7,8);
zz.addaccess(7,12);
zz.addaccess(8,3,true);
zz.addaccess(8,7);
zz.addaccess(8,9);
zz.addaccess(8,13);
zz.addaccess(9,4);
zz.addaccess(9,8);
zz.addaccess(9,14);
zz.addaccess(10,5);
zz.addaccess(10,11,true);
zz.addaccess(10,15);
zz.addaccess(11,6);
zz.addaccess(11,10,true);
zz.addaccess(11,12);
zz.addaccess(11,16,true);
zz.addaccess(12,7);
zz.addaccess(12,11);
zz.addaccess(12,13);
zz.addaccess(12,17,true);
zz.addaccess(13,8);
zz.addaccess(13,12);
zz.addaccess(13,14);
zz.addaccess(13,18,true);
zz.addaccess(14,9);
zz.addaccess(14,13);
zz.addaccess(14,19,true);
zz.addaccess(15,10);
zz.addaccess(15,16);
zz.addaccess(15,20,true);
zz.addaccess(16,11,true);
zz.addaccess(16,15);
zz.addaccess(16,17);
zz.addaccess(16,21,true);
zz.addaccess(17,12,true);
zz.addaccess(17,16);
zz.addaccess(17,18);
zz.addaccess(17,22,true);
zz.addaccess(18,13,true);
zz.addaccess(18,17);
zz.addaccess(18,19);
zz.addaccess(18,23,true);
zz.addaccess(19,14,true);
zz.addaccess(19,18);
zz.addaccess(19,24);
zz.addaccess(20,15,true);
zz.addaccess(20,21);
zz.addaccess(21,16,true);
zz.addaccess(21,20);
zz.addaccess(21,22);
zz.addaccess(22,17,true);
zz.addaccess(22,21);
zz.addaccess(22,23);
zz.addaccess(23,18,true);
zz.addaccess(23,22);
zz.addaccess(23,24);
zz.addaccess(24,19);
zz.addaccess(24,23);
//Расчёт и вывод результатов
steps res=zz.find(20,4);
cout<<"От "<<20<<" до "<<4<<"\n";
for(int x=0;x<res.size();x+=1)
{
cout<<"To: "<<res.at(x).first;
if(res.at(x).second)
cout<<" BOOM";
cout<<"\n";
}
cout<<"Всего стоимость маршрута: "<<labirint::lengthoftrace(res)<<"\n";
res=zz.find(11,20);
cout<<"От "<<11<<" до "<<20<<"\n";
for(int x=0;x<res.size();x+=1)
{
cout<<"To: "<<res.at(x).first;
if(res.at(x).second)
cout<<" BOOM";
cout<<"\n";
}
cout<<"Всего стоимость маршрута: "<<labirint::lengthoftrace(res)<<"\n";
return 0;
}
В выше приведённом коде в качестве примера этот лабиринт(иЗвиНиТЕ зА НеРоВНый ПочЕРк) :
[ATTACH=CONFIG]5069[/ATTACH]
Цитата: arrjj
Рекурсия рулит:)
Достаточно просто переделать для нахождения кратчайшего пути.
Ну и да тут много недочётов, накидал на коленке, так что сори за какашкокод.
Достаточно просто переделать для нахождения кратчайшего пути.
Ну и да тут много недочётов, накидал на коленке, так что сори за какашкокод.
Я могу ошибаться, но мне кажется, что ваш код не будет работать на таком примере на пути из А в Б при наличии ровно одной бомбы:
[ATTACH=CONFIG]5070[/ATTACH]
Спасибо за код, но вникать и переписывать с плюсов на perl как-то совсем не хочется. Лучше уж я сама додумаюсь, может быть когда-нибудь свершится чудо и до меня дойдет как надо делать.
Что-то у меня ничего не выходит.
Делаю так: сначала заполняю массив расстояний для p=0. т.е. обычный поиск в ширину, т.е. если натыкаюсь на стенку то просто иду дальше, с этим проблем нет.
потом в цикле заполняю для всех значений p от 1 до количества бомб, которое у меня есть.
в этом случае я просматривая соседей смотрю стенка это или нет. если сосед это проход, то $dist[$tmp_x][$tmp_y][$p] = $dist[x][y][$p] + 1; а если сосед это стенка, то $dist[$tmp_x][$tmp_y][$p] = $dist[x][y][$p - 1] + 1. Но получается полная белиберда.
Что же всё-таки неправильно? Голова уже кругом идет!
Что-то у меня ничего не выходит.
Делаю так: сначала заполняю массив расстояний для p=0. т.е. обычный поиск в ширину, т.е. если натыкаюсь на стенку то просто иду дальше, с этим проблем нет.
потом в цикле заполняю для всех значений p от 1 до количества бомб, которое у меня есть.
в этом случае я просматривая соседей смотрю стенка это или нет. если сосед это проход, то $dist[$tmp_x][$tmp_y][$p] = $dist[x][y][$p] + 1; а если сосед это стенка, то $dist[$tmp_x][$tmp_y][$p] = $dist[x][y][$p - 1] + 1. Но получается полная белиберда.
Что же всё-таки неправильно? Голова уже кругом идет!
P*t*,работает:
Нумерация:
Код:
#include <iostream>
#include <set>
#include <vector>
#include <QString>
using namespace std;
#define bomb_cost 50
#define step_cost 10
#define max_bombs 1
typedef pair<int,bool> step;
typedef vector<step> steps;
class labirint
{
public:
labirint()
{
peaks.clear();
access.clear();
}
void setpeakcount(unsigned int peakcount)
{
peaks.clear();
access.clear();
steps a;
a.clear();
for(unsigned int x=0;x<peakcount;x+=1)
{
peaks.push_back(x);
access.push_back(a);
}
}
void addaccess(int from,int to, bool bomb=false)
{
if(from<peaks.size() && to<peaks.size())
{
access.at(from).push_back(step(to,bomb));
}
}
steps find(int from,int to)
{
currtrace.clear();
mintrace.clear();
if(from<peaks.size() && to<peaks.size())
{
bool * blah=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
blah[x]=false;
blah[from]=true;
recurse(from,to,max_bombs,blah);
delete[] blah;
}
return mintrace;
}
static int lengthoftrace(steps &trace)
{
int ret=0;
for(int x=0;x<trace.size();x+=1)
ret+=(trace.at(x).second?bomb_cost:step_cost);
return ret;
}
private:
void recurse(int peaknumb,int peakto,int havebombs,bool * visiteds)
{
if(havebombs<0)
return;
if(peaknumb==peakto)
{
//add to min's array
if((lengthoftrace(mintrace)>=lengthoftrace(currtrace)) || lengthoftrace(mintrace)==0)
mintrace=currtrace;
return;
}
if(lengthoftrace(mintrace)<lengthoftrace(currtrace) && lengthoftrace(mintrace)!=0)
return;
bool * visited=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
visited[x]=visiteds[x];
visited[peaknumb]=true;
//recurs for subs
for(int x=0;x<access.at(peaknumb).size();x+=1)
{
if(!visited[access.at(peaknumb).at(x).first])
{
currtrace.push_back(access.at(peaknumb).at(x));
recurse(access.at(peaknumb).at(x).first,peakto,havebombs-access.at(peaknumb).at(x).second,visited);
currtrace.pop_back();
}
}
delete [] visited;
}
vector<int> peaks;
vector<step> currtrace;
vector<step> mintrace;
vector<steps> access;
};
int main()
{
//Ввод графа
labirint zz;
zz.setpeakcount(40);
/* for(int x=0;x<9;x+=1)
{
if(x-3>=0)
qWarning(" zz.addaccess(%d,%d);",x,x-3);
if(x%3!=0)
qWarning(" zz.addaccess(%d,%d);",x,x-1);
if(x%3!=2)
qWarning(" zz.addaccess(%d,%d);",x,x+1);
if(x+3<9)
qWarning(" zz.addaccess(%d,%d);",x,x+3);
}*/
zz.addaccess(0,1,true);
zz.addaccess(0,3,true);
zz.addaccess(1,0,true);
zz.addaccess(1,2);
zz.addaccess(1,4);
zz.addaccess(2,1);
zz.addaccess(2,5);
zz.addaccess(3,0,true);
zz.addaccess(3,4);
zz.addaccess(3,6,true);
zz.addaccess(4,1);
zz.addaccess(4,3);
zz.addaccess(4,5);
zz.addaccess(4,7,true);
zz.addaccess(5,2);
zz.addaccess(5,4);
zz.addaccess(5,8);
zz.addaccess(6,3,true);
zz.addaccess(6,7);
zz.addaccess(7,4,true);
zz.addaccess(7,6);
zz.addaccess(7,8);
zz.addaccess(8,5);
zz.addaccess(8,7);
//Расчёт и вывод результатов
steps res=zz.find(6,0);
cout<<"От "<<6<<" до "<<0<<"\n";
for(int x=0;x<res.size();x+=1)
{
cout<<"To: "<<res.at(x).first;
if(res.at(x).second)
cout<<" BOOM";
cout<<"\n";
}
cout<<"Всего стоимость маршрута: "<<labirint::lengthoftrace(res)<<"\n";
return 0;
}
#include <set>
#include <vector>
#include <QString>
using namespace std;
#define bomb_cost 50
#define step_cost 10
#define max_bombs 1
typedef pair<int,bool> step;
typedef vector<step> steps;
class labirint
{
public:
labirint()
{
peaks.clear();
access.clear();
}
void setpeakcount(unsigned int peakcount)
{
peaks.clear();
access.clear();
steps a;
a.clear();
for(unsigned int x=0;x<peakcount;x+=1)
{
peaks.push_back(x);
access.push_back(a);
}
}
void addaccess(int from,int to, bool bomb=false)
{
if(from<peaks.size() && to<peaks.size())
{
access.at(from).push_back(step(to,bomb));
}
}
steps find(int from,int to)
{
currtrace.clear();
mintrace.clear();
if(from<peaks.size() && to<peaks.size())
{
bool * blah=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
blah[x]=false;
blah[from]=true;
recurse(from,to,max_bombs,blah);
delete[] blah;
}
return mintrace;
}
static int lengthoftrace(steps &trace)
{
int ret=0;
for(int x=0;x<trace.size();x+=1)
ret+=(trace.at(x).second?bomb_cost:step_cost);
return ret;
}
private:
void recurse(int peaknumb,int peakto,int havebombs,bool * visiteds)
{
if(havebombs<0)
return;
if(peaknumb==peakto)
{
//add to min's array
if((lengthoftrace(mintrace)>=lengthoftrace(currtrace)) || lengthoftrace(mintrace)==0)
mintrace=currtrace;
return;
}
if(lengthoftrace(mintrace)<lengthoftrace(currtrace) && lengthoftrace(mintrace)!=0)
return;
bool * visited=new bool[peaks.size()];
for(int x=0;x<peaks.size();x+=1)
visited[x]=visiteds[x];
visited[peaknumb]=true;
//recurs for subs
for(int x=0;x<access.at(peaknumb).size();x+=1)
{
if(!visited[access.at(peaknumb).at(x).first])
{
currtrace.push_back(access.at(peaknumb).at(x));
recurse(access.at(peaknumb).at(x).first,peakto,havebombs-access.at(peaknumb).at(x).second,visited);
currtrace.pop_back();
}
}
delete [] visited;
}
vector<int> peaks;
vector<step> currtrace;
vector<step> mintrace;
vector<steps> access;
};
int main()
{
//Ввод графа
labirint zz;
zz.setpeakcount(40);
/* for(int x=0;x<9;x+=1)
{
if(x-3>=0)
qWarning(" zz.addaccess(%d,%d);",x,x-3);
if(x%3!=0)
qWarning(" zz.addaccess(%d,%d);",x,x-1);
if(x%3!=2)
qWarning(" zz.addaccess(%d,%d);",x,x+1);
if(x+3<9)
qWarning(" zz.addaccess(%d,%d);",x,x+3);
}*/
zz.addaccess(0,1,true);
zz.addaccess(0,3,true);
zz.addaccess(1,0,true);
zz.addaccess(1,2);
zz.addaccess(1,4);
zz.addaccess(2,1);
zz.addaccess(2,5);
zz.addaccess(3,0,true);
zz.addaccess(3,4);
zz.addaccess(3,6,true);
zz.addaccess(4,1);
zz.addaccess(4,3);
zz.addaccess(4,5);
zz.addaccess(4,7,true);
zz.addaccess(5,2);
zz.addaccess(5,4);
zz.addaccess(5,8);
zz.addaccess(6,3,true);
zz.addaccess(6,7);
zz.addaccess(7,4,true);
zz.addaccess(7,6);
zz.addaccess(7,8);
zz.addaccess(8,5);
zz.addaccess(8,7);
//Расчёт и вывод результатов
steps res=zz.find(6,0);
cout<<"От "<<6<<" до "<<0<<"\n";
for(int x=0;x<res.size();x+=1)
{
cout<<"To: "<<res.at(x).first;
if(res.at(x).second)
cout<<" BOOM";
cout<<"\n";
}
cout<<"Всего стоимость маршрута: "<<labirint::lengthoftrace(res)<<"\n";
return 0;
}
Код:
Нумерация:
Код:
0|1 2
-
3 4 5
--
6 7 8
-
3 4 5
--
6 7 8
arrjj, можно вопрос. таким способом задания лабиринта как вы себе представляете лабиринт 100 на 100 например.
Просто у меня лабиринт с толстыми стенками и я в файле его задаю, пробел это проход, # это стенка, s начальная точка, f - конечная. таким образом пользователь легко может сам создать свой лабиринт и потом его проходить.
А как в вашем случае можно это реализовать?
Просто у меня лабиринт с толстыми стенками и я в файле его задаю, пробел это проход, # это стенка, s начальная точка, f - конечная. таким образом пользователь легко может сам создать свой лабиринт и потом его проходить.
А как в вашем случае можно это реализовать?
1)Я не заботился о пользователях, я лишь привёл вам алгоритм(один из возможных)
2)Ща напишу лоадер файлов вашего формата с толстыми стенками.
2)Ща напишу лоадер файлов вашего формата с толстыми стенками.
зачем же реализовывать!!! я это так просто спросила. а как рекурсия по времени работает?
вы не могли бы мне на пальцах объяснить как алгоритм работает. может мне тоже имеет смысл переделать на рекурсию. У меня сейчас просто через очередь сделано.
вы не могли бы мне на пальцах объяснить как алгоритм работает. может мне тоже имеет смысл переделать на рекурсию. У меня сейчас просто через очередь сделано.
На тему хранения лабиринта с тонкими стенками - можно так же в текстовом виде, как и с толстыми стенками, но вместо # использовать символы | (стенка слева от клетки), _ (снизу) и L (и слева и снизу). Правая и верхняя стенки тогда будут задаваться в соседних клетках.
2arrjj
Сейчас еще раз на код посмотрю. Чем-то он мне не нравится.
А рекурсию я бы не стал использовать т.к на больших лабиринтах может стек переполниться.
2arrjj
Сейчас еще раз на код посмотрю. Чем-то он мне не нравится.
А рекурсию я бы не стал использовать т.к на больших лабиринтах может стек переполниться.
мне кажется что правильное решение очень близко и я как обычно просто его не вижу.
Сейчас проблема в том, что я как только посчитала расстояние для клетки, больше ее не рассматриваю, а в одну и ту же клетку можно попасть различными путями, без использования бомб это не имело значения. А сейчас получилось, что смена порядка рассматривания соседей влияет на результат, чего конечно быть не должно.
Сейчас проблема в том, что я как только посчитала расстояние для клетки, больше ее не рассматриваю, а в одну и ту же клетку можно попасть различными путями, без использования бомб это не имело значения. А сейчас получилось, что смена порядка рассматривания соседей влияет на результат, чего конечно быть не должно.
P*t*, мне тоже не нравится, грюж на коленке накалякал:) На небольших (<9*20) ещё норм а больше - фиг, тормозит :)
Надо сюда както оптимизацию+алгоритм дейкстры приспособить. Без оптимизации маршрута начального графа ничего стоящего не получится:)
Надо сюда както оптимизацию+алгоритм дейкстры приспособить. Без оптимизации маршрута начального графа ничего стоящего не получится:)
arrjj, а зачем Дейкстру? граф же не взвешенный. на мой взгляд для лабиринта самое простое и быстрое это волновой.
По вашим меркам что значит тормозит? сколько примерно работает?
По вашим меркам что значит тормозит? сколько примерно работает?
Взвешеный так: просто шаг (ребро) - один вес, шаг через стену (или в Вашем случае в стену) (ребро) - другой вес.
При размерах меньше 180 (поле там 9x20) вершин отрабатывает почти моментально. 10х20 секунд 25ть ну и т.д. в геометрической прогрессии. Тут почти полный перебор рекурсивно.
При размерах меньше 180 (поле там 9x20) вершин отрабатывает почти моментально. 10х20 секунд 25ть ну и т.д. в геометрической прогрессии. Тут почти полный перебор рекурсивно.
ОГО!!! даже и подумать не могла, что настолько долго. у меня сейчас 15x15, работает меньше секунды, если графику не считать конечно =)
это рекурсия так тупит? в топку тогда её!!!
это рекурсия так тупит? в топку тогда её!!!
Цитата:
ОГО!!! даже и подумать не могла, что настолько долго. у меня сейчас 15x15, работает меньше секунды, если графику не считать конечно =)
это рекурсия так тупит? в топку тогда её!!!
это рекурсия так тупит? в топку тогда её!!!
Не думаю что нужно гнать бочку на рекурсию. Она может и замедляет вашу программу, но это ничто по сравнению с ростом кол-ва вариантов достижения вершины при увеличении размерности ваших графов.
Рекурсия опасна своей глубиной, т.к. это может вызвать stack overflow.
Долго думал, как понятнее объяснить предложенный мной алгоритм и решил, что лучше всего написать псевдокод:
Код:
int ans[sizeX,sizeY,maxp] // 3-й параметр - количество использованных бомб. значение - длина пути.
fill(ans, -1) // -1 - начальное значение
ans[startX,startY,0]=0 // путь до начальной точки имеет стоимость 0
queue.add(startX,startY) // структура с клетками, которые ожидают обработки
for p=0 to maxp // цикл по количеству бомб
while queue.hasNext()
x,y = queue.min() // достаем клетку с минимальным значением стоимости
//пути (a[x,y,p]) т.к значение в ней уже не может измениться.
// Для queue хорошо использовать структуру данных heap.
if wall[x+1,y]
if ans[x+1,y,p+1]=-1 or ans[x+1,y,p+1] > ans[x,y,p]+5
ans[x+1,y,p+1] = ans[x,y,p]+5 // взрываем стену
queue2.add(x+1,y) // добавляем в очередь для следующей итерации по p
else
if ans[x+1,y,p]=-1 or ans[x+1,y,p] > ans[x,y,p]+1
ans[x+1,y,p] = ans[x,y,p]+1 // без взрыва
queue.add(x+1,y) // добавляем в очередь для текущей итерации
if wall[x-1,y] ...
if wall[x,y+1] ... // аналогично
if wall[x,y-1] ...
queue=queue2 // обновляем очередь перед следующей итерацией
result = min(a[finishX, finishY, *])
fill(ans, -1) // -1 - начальное значение
ans[startX,startY,0]=0 // путь до начальной точки имеет стоимость 0
queue.add(startX,startY) // структура с клетками, которые ожидают обработки
for p=0 to maxp // цикл по количеству бомб
while queue.hasNext()
x,y = queue.min() // достаем клетку с минимальным значением стоимости
//пути (a[x,y,p]) т.к значение в ней уже не может измениться.
// Для queue хорошо использовать структуру данных heap.
if wall[x+1,y]
if ans[x+1,y,p+1]=-1 or ans[x+1,y,p+1] > ans[x,y,p]+5
ans[x+1,y,p+1] = ans[x,y,p]+5 // взрываем стену
queue2.add(x+1,y) // добавляем в очередь для следующей итерации по p
else
if ans[x+1,y,p]=-1 or ans[x+1,y,p] > ans[x,y,p]+1
ans[x+1,y,p] = ans[x,y,p]+1 // без взрыва
queue.add(x+1,y) // добавляем в очередь для текущей итерации
if wall[x-1,y] ...
if wall[x,y+1] ... // аналогично
if wall[x,y-1] ...
queue=queue2 // обновляем очередь перед следующей итерацией
result = min(a[finishX, finishY, *])
Цитата: arrjj
P*t*, интересно, интересно... И надо к каждому минимальному маршруту до точки привязывать карту посещённых вершин, иначе зациклится.
Неа, не зациклится. По причине наличия вот такого условия:
Код:
if ans[x+1,y,p]=-1 or ans[x+1,y,p] > ans[x,y,p]+1
P*t*, огромное спасибо!!! поняла в чем моя ошибка.
при вытаскивании из очереди я просто беру следующий элемент, а надо сначала найти в очереди элемент с минимальным расстоянием и взять его.
только вот вопрос как это сделать, в перле нет никаких структур для очереди, это просто массив, в него я попарно закидываю координаты x и y. точки. Т.е. получается что мне нужно каждый раз сортировать элементы очереди по возрастанию расстояния и брать первый, так?
нужно только как-то закидывать в очередь массивом x и y, а не поэлементно. тогда проблема решена.
тогда бы получилась страшная формула, что-то типа:
@queue = @queue[sort { $dist[$a[0]][$a[1]][$p] <=> $dist[$b[0]][$b[1]][$p] } 0..$size * $size - 1];
при вытаскивании из очереди я просто беру следующий элемент, а надо сначала найти в очереди элемент с минимальным расстоянием и взять его.
только вот вопрос как это сделать, в перле нет никаких структур для очереди, это просто массив, в него я попарно закидываю координаты x и y. точки. Т.е. получается что мне нужно каждый раз сортировать элементы очереди по возрастанию расстояния и брать первый, так?
нужно только как-то закидывать в очередь массивом x и y, а не поэлементно. тогда проблема решена.
тогда бы получилась страшная формула, что-то типа:
@queue = @queue[sort { $dist[$a[0]][$a[1]][$p] <=> $dist[$b[0]][$b[1]][$p] } 0..$size * $size - 1];
Сортировать точно не надо.
Простейший способ - каждый раз пробегаться по всему массиву и находить минимальный элемент. Даже это быстрее, чем каждый раз сортировать.
Продвинутый способ - использовать структуру данных Куча. Не знаю, есть ли в перле стандартная реализация для нее. Во всяком случае это вещь, которую нужно уметь писать самостоятельно. При некотором опыте пишется за 10 минут.
Простейший способ - каждый раз пробегаться по всему массиву и находить минимальный элемент. Даже это быстрее, чем каждый раз сортировать.
Продвинутый способ - использовать структуру данных Куча. Не знаю, есть ли в перле стандартная реализация для нее. Во всяком случае это вещь, которую нужно уметь писать самостоятельно. При некотором опыте пишется за 10 минут.
Поискала в ppm, нашла пакет heap. переписала прогу на работу с кучей.
Вроде всё работает правильно на разных лабиринтах и с разным количеством бомб.
P*t* , Еще раз спасибо огромное!!!!!
Теперь можно наводить красоту в графике и заняться управлением.
Кстати по поводу времени работы. лабиринт 15x15 при количестве бомб < 11 работает меньше секунды, до 30 бомб работает до 2 секунд. если учесть что много бомб делать не интересно. то получается время счета 1 секунда. даже не заметно на фоне sleep(0.5) и т.д. в отрисовке.
Вроде всё работает правильно на разных лабиринтах и с разным количеством бомб.
P*t* , Еще раз спасибо огромное!!!!!
Теперь можно наводить красоту в графике и заняться управлением.
Кстати по поводу времени работы. лабиринт 15x15 при количестве бомб < 11 работает меньше секунды, до 30 бомб работает до 2 секунд. если учесть что много бомб делать не интересно. то получается время счета 1 секунда. даже не заметно на фоне sleep(0.5) и т.д. в отрисовке.
Видимо всё-таки поторопилась. Придумала лабиринт на котором работает неправильно.
Сам лабиринт:
[ATTACH=CONFIG]5072[/ATTACH]
И как прошел:
[ATTACH=CONFIG]5071[/ATTACH]
Получается что герой пробил 9 стенок. но при этом бомб у него было только 5.
Вот что получается в массивах расстояний:
[ATTACH]5074[/ATTACH]
Действительно лабиринт можно пройти с 5 бомбами за такую же стоимость. Но почему-то получается несколько маршрутов, причем некоторые из них неверные.
Сам лабиринт:
[ATTACH=CONFIG]5072[/ATTACH]
И как прошел:
[ATTACH=CONFIG]5071[/ATTACH]
Получается что герой пробил 9 стенок. но при этом бомб у него было только 5.
Вот что получается в массивах расстояний:
[ATTACH]5074[/ATTACH]
Действительно лабиринт можно пройти с 5 бомбами за такую же стоимость. Но почему-то получается несколько маршрутов, причем некоторые из них неверные.
Покажи уж тогда код.
Ту его часть, которая соответствует приведенному мной куску + восстановление пути.
Я, впрочем, перл не знаю, но посмотреть попробую.
На всякий случай - Во время поиска оптимального пути редактировать массив стен при взрыве бомбы не надо! Поскольку оптимальный путь никогда не проходит через одну клетку дважды, не нужно затирать стены за собой - это помешает при поиске других вариантов.
Ту его часть, которая соответствует приведенному мной куску + восстановление пути.
Я, впрочем, перл не знаю, но посмотреть попробую.
На всякий случай - Во время поиска оптимального пути редактировать массив стен при взрыве бомбы не надо! Поскольку оптимальный путь никогда не проходит через одну клетку дважды, не нужно затирать стены за собой - это помешает при поиске других вариантов.
считаю расстояния:
дальше ищу при каком p расстояние наименьшее:
и восстанавливаю путь по этому слою:
в восстановлении пути не обращай внимания на всякие функции, это просто отрисовка. Восстанавливаю так: просто смотрю соседа у которого расстояния на 1 меньше и шагаю в него.
Код:
my @dx = (1, -1, 0, 0);
my @dy = (0, 0, -1, 1);
# ищем путь от финиша к старту, чтоб потом не пришлось переворачивать найденный путь
my @hero;
my $heap = Heap::Simple->new(elements => "Any");
my $heap_next = Heap::Simple->new(elements => "Any");
for my $p(0..$kol_bomb)
{
$dist[$finish[0]][$finish[1]][$p] = 0;
$heap->key_insert($dist[$finish[0]][$finish[1]][$p], \@finish); #закинули в кучу
#заполняем массив растояний
while ($heap->count > 0)
{
@hero = @{$heap->extract_top}; #вытащили голову
last if ($hero[0] == $start[0] and $hero[1] == $start[1]); #закончили если дошли до старта
for my $i(0..3) #цикл по соседям
{
my @tmp = ($hero[0] + $dx[$i], $hero[1] + $dy[$i]); #взяли соседа
next if ($tmp[0] < 0 or $tmp[1] < 0 or $tmp[0] > $size - 1 or $tmp[1] > $size - 1);
if ($arr[$tmp[0]][$tmp[1]] == 0) #если сосед стенка
{
if ($dist[$tmp[0]][$tmp[1]][$p + 1] > $dist[$hero[0]][$hero[1]][$p] + 1)
{
$dist[$tmp[0]][$tmp[1]][$p + 1] = $dist[$hero[0]][$hero[1]][$p] + 1;
$heap_next->key_insert($dist[$tmp[0]][$tmp[1]][$p + 1], \@tmp);
}
}
else
{
if ($dist[$tmp[0]][$tmp[1]][$p] > $dist[$hero[0]][$hero[1]][$p] + 1)
{
$dist[$tmp[0]][$tmp[1]][$p] = $dist[$hero[0]][$hero[1]][$p] + 1;
$heap->key_insert($dist[$tmp[0]][$tmp[1]][$p], \@tmp);
}
}
}
}
$heap->key_absorb($heap_next); #перекинули кучу heap_next в heap
}
my @dy = (0, 0, -1, 1);
# ищем путь от финиша к старту, чтоб потом не пришлось переворачивать найденный путь
my @hero;
my $heap = Heap::Simple->new(elements => "Any");
my $heap_next = Heap::Simple->new(elements => "Any");
for my $p(0..$kol_bomb)
{
$dist[$finish[0]][$finish[1]][$p] = 0;
$heap->key_insert($dist[$finish[0]][$finish[1]][$p], \@finish); #закинули в кучу
#заполняем массив растояний
while ($heap->count > 0)
{
@hero = @{$heap->extract_top}; #вытащили голову
last if ($hero[0] == $start[0] and $hero[1] == $start[1]); #закончили если дошли до старта
for my $i(0..3) #цикл по соседям
{
my @tmp = ($hero[0] + $dx[$i], $hero[1] + $dy[$i]); #взяли соседа
next if ($tmp[0] < 0 or $tmp[1] < 0 or $tmp[0] > $size - 1 or $tmp[1] > $size - 1);
if ($arr[$tmp[0]][$tmp[1]] == 0) #если сосед стенка
{
if ($dist[$tmp[0]][$tmp[1]][$p + 1] > $dist[$hero[0]][$hero[1]][$p] + 1)
{
$dist[$tmp[0]][$tmp[1]][$p + 1] = $dist[$hero[0]][$hero[1]][$p] + 1;
$heap_next->key_insert($dist[$tmp[0]][$tmp[1]][$p + 1], \@tmp);
}
}
else
{
if ($dist[$tmp[0]][$tmp[1]][$p] > $dist[$hero[0]][$hero[1]][$p] + 1)
{
$dist[$tmp[0]][$tmp[1]][$p] = $dist[$hero[0]][$hero[1]][$p] + 1;
$heap->key_insert($dist[$tmp[0]][$tmp[1]][$p], \@tmp);
}
}
}
}
$heap->key_absorb($heap_next); #перекинули кучу heap_next в heap
}
дальше ищу при каком p расстояние наименьшее:
Код:
my $min = 0;
for my $p (0..$kol_bomb)
{
if ($dist[$start[0]][$start[1]][$p] < $dist[$start[0]][$start[1]][$min])
{
$min = $p;
}
}
for my $p (0..$kol_bomb)
{
if ($dist[$start[0]][$start[1]][$p] < $dist[$start[0]][$start[1]][$min])
{
$min = $p;
}
}
и восстанавливаю путь по этому слою:
Код:
while ($hero[0] != $finish[0] or $hero[1] != $finish[1])
{
for my $i(0..3)
{
my @tmp = ($hero[0] + $dx[$i], $hero[1] + $dy[$i]);
if ($dist[$tmp[0]][$tmp[1]][$min] == $dist[$hero[0]][$hero[1]][$min] - 1)
{
if ($arr[$tmp[0]][$tmp[1]] == 0)
{
buuum(@tmp);
clear(@tmp);
}
@hero = @tmp;
draw_hero(0, 0, @hero);
clear(@hero);
last;
}
}
}
{
for my $i(0..3)
{
my @tmp = ($hero[0] + $dx[$i], $hero[1] + $dy[$i]);
if ($dist[$tmp[0]][$tmp[1]][$min] == $dist[$hero[0]][$hero[1]][$min] - 1)
{
if ($arr[$tmp[0]][$tmp[1]] == 0)
{
buuum(@tmp);
clear(@tmp);
}
@hero = @tmp;
draw_hero(0, 0, @hero);
clear(@hero);
last;
}
}
}
в восстановлении пути не обращай внимания на всякие функции, это просто отрисовка. Восстанавливаю так: просто смотрю соседа у которого расстояния на 1 меньше и шагаю в него.
0) Надо полагать dist предварительно заполняется чем-то очень большим?
1)
Последние две строчки лучше вынести за пределы цикла.
Иначе получается, что игрок может стоя в начальной клетке впустую использовать несколько бомб и только потом куда-то идти.
2)
дальше ищу при каком p расстояние наименьшее:
и восстанавливаю путь по этому слою:
1)
Код:
for my $p(0..$kol_bomb)
{
$dist[$finish[0]][$finish[1]][$p] = 0;
$heap->key_insert($dist[$finish[0]][$finish[1]][$p], \@finish); #закинули в кучу
{
$dist[$finish[0]][$finish[1]][$p] = 0;
$heap->key_insert($dist[$finish[0]][$finish[1]][$p], \@finish); #закинули в кучу
Последние две строчки лучше вынести за пределы цикла.
Иначе получается, что игрок может стоя в начальной клетке впустую использовать несколько бомб и только потом куда-то идти.
2)
Цитата:
дальше ищу при каком p расстояние наименьшее:
Здесь претензий нет ;)
3)
Цитата:
и восстанавливаю путь по этому слою:
А вот здесь совсем неправильно.
Код:
while ($hero[0] != $finish[0] or $hero[1] != $finish[1])
{
# <<<<< Сюда вставить кусок:
my $current_dist = $dist[$hero[0]][$hero[1]][$min];
if ($arr[$hero[0]][$hero[1]] == 0)
{ # мы сейчас в стенке, значит мы ее взорвали
buuum(@hero);
clear(@hero);
$min = $min - 1; # до этого мы шли по другому слою
}
# -------------
for my $i(0..3)
{
my @tmp = ($hero[0] + $dx[$i], $hero[1] + $dy[$i]);
if ($dist[$tmp[0]][$tmp[1]][$min] == current_dist - 1)
{
# if ($arr[$tmp[0]][$tmp[1]] == 0)
# {
# buuum(@tmp);
# clear(@tmp);
# }
@hero = @tmp;
draw_hero(0, 0, @hero);
clear(@hero);
last;
}
}
}
{
# <<<<< Сюда вставить кусок:
my $current_dist = $dist[$hero[0]][$hero[1]][$min];
if ($arr[$hero[0]][$hero[1]] == 0)
{ # мы сейчас в стенке, значит мы ее взорвали
buuum(@hero);
clear(@hero);
$min = $min - 1; # до этого мы шли по другому слою
}
# -------------
for my $i(0..3)
{
my @tmp = ($hero[0] + $dx[$i], $hero[1] + $dy[$i]);
if ($dist[$tmp[0]][$tmp[1]][$min] == current_dist - 1)
{
# if ($arr[$tmp[0]][$tmp[1]] == 0)
# {
# buuum(@tmp);
# clear(@tmp);
# }
@hero = @tmp;
draw_hero(0, 0, @hero);
clear(@hero);
last;
}
}
}
да, конечно dist заполняю размером лабиринта, т.к. больше быть точно не может. таким образом избавляюсь от одной проверки.
по поводу:
[CODE="Perl"]
$dist[$finish[0]][$finish[1]][$p] = 0;
$heap->key_insert($dist[$finish[0]][$finish[1]][$p], \@finish);
[/CODE]
сделала в цикле, чтоб расстояние от финиша до финиша было всегда 0. если вынести из цикла, то оно будет расти с ростом p. а это ведь неправильно.
По повод восстановления пути, я видимо уже совсем отупела, додуматься самой мозгов не хватает.
Теперь всё работает правильно, спасибо тебе! Не знаю, чтоб я без тебя делала=)
по поводу:
[CODE="Perl"]
$dist[$finish[0]][$finish[1]][$p] = 0;
$heap->key_insert($dist[$finish[0]][$finish[1]][$p], \@finish);
[/CODE]
сделала в цикле, чтоб расстояние от финиша до финиша было всегда 0. если вынести из цикла, то оно будет расти с ростом p. а это ведь неправильно.
По повод восстановления пути, я видимо уже совсем отупела, додуматься самой мозгов не хватает.
Теперь всё работает правильно, спасибо тебе! Не знаю, чтоб я без тебя делала=)
dist может быть больше размера лабиринта - если бомб нет, а стены сделаны в виде змейки.
сделала в цикле, чтоб расстояние от финиша до финиша было всегда 0. если вынести из цикла, то оно будет расти с ростом p. а это ведь неправильно.
Цитата: rusan
сделала в цикле, чтоб расстояние от финиша до финиша было всегда 0. если вынести из цикла, то оно будет расти с ростом p. а это ведь неправильно.
Почему же неправильно? В массиве должны отображаться оптимальные пути, а добраться от начальной точки до начальной и при этом потратить сколько-то бомб - явно не оптимальный способ. ;)
Если эти две строчки в цикле, то оптимальный ответ всегда будет в $dist[$finish[0]][$finish[1]][$kol_bomb] (в последнем слое).
Если строчки вне цикла, то от использования лишних бомб результат может ухудшиться. Именно поэтому там поиск минимума по P.