Игроку необходимо пройти из точки start
в точку end
. На каждой точке, он видит одну из двух инструкций:
- Иди на следующую точку (адрес
текущий + 1
(NEXT)) - Иди на указанную точку (адрес
[start + 1.. end - 1]
(JUMP))
Как случайным образом сгенерировать пути для игрока, что бы не было зацикленности? Путь должен быть сгенерирован так, что бы игрок прошел все точки и что бы нельзя было спрогнозировать, куда будет прыжок (кроме последнего. Последний прыжок будет на последнюю область). Конечная точка должна иметь инструкцию NEXT.
Параметр генератора percent
- это отношение количества команд JUMP к количеству точек(1000). precent = 100
означает, что все точки содержат инструкцию JUMP, кроме последней точки.
Посоветуйте как можно оптимизировать алгоритм? Мой алгоритм для генерации пути в 200'000 точек очень много времени занимает. А планируемая максимальная длина 1М точек.
- Посчитать количество инструкций JUMP.
- Разместить инструкции JUMP (без указывания адреса прыжка). Тогда начала сегмента будет следующий адрес после JUMP.
- Назначить(соединить) случайным образом каждой команде JUMP адрес начала сегмента. Нельзя назначать уже с соединенным сегментом.
- Сгенерировать путь.
У меня не особо получилось сделать алгоритм эффективным ни по времени, ни по памяти. Главнее сделать алгоритм эффективным по времени. Если есть идеи для улучшения, буду благодарен. Если можно распараллелить процесс, подскажите как.
Пример кода:
// seed - для псевдослучайности
void generatePath(int start, int end, double percent, uint seed = 1)
{
QRandomGenerator randG(seed);
const int lenPath = end - start + 1;
// 1. Посчитать количество инструкций JUMP.
const int cntJump = int((lenPath - 1) * percent);
QVector<int> ggLenPath(lenPath-1);
std::generate(ggLenPath.begin(), ggLenPath.end(), [n = -1] () mutable { return ++n; });
// 2. Разместить инструкции JUMP (без указывания адреса прыжка).
// Тогда начала сегмента будет следующий адрес после JUMP.
QVector<int> jumpAddrSource(cntJump);
std::sample(ggLenPath.begin(), ggLenPath.end(), jumpAddrSource.begin(), cntJump, randG);
// 3. Назначить(соединить) случайным образом каждой команде JUMP
// адрес начала сегмента. Нельзя назначать уже с соединенным
// сегментом и на себя.
QVector<int> jumpAddrDest = jumpAddrSource;
{
int currJump = 0;
std::set<int> existsLink;
for (int i = 0; i < cntJump - 1; ++i) {
int numSector = randG.bounded(cntJump - 1 - i);
int offset = 0;
for (const auto &ex : existsLink) {
if (numSector + offset >= ex) {
++offset;
} else {
break;
}
}
existsLink.insert(numSector + offset);
jumpAddrDest[currJump] = jumpAddrSource[numSector + offset] + 1;
currJump = numSector + offset + 1;
}
jumpAddrDest[currJump] = jumpAddrSource[cntJump - 1] + 1;
}
// 4. Сгенерировать путь.
for (int i = 0; i < lenPath; ++i) { addPointNext(i); }
for (int i = 0; i < jumpAddrSource.size(); ++i) { addPointJump(jumpAddrSource[i], jumpAddrDest[i]); }
}
UDP: реализовал алгоритм @MBo на с++ (generatePathMbo). Результат:
generatePath(0, 200000, 1) = 304.713 sec // 99% времени занимает пункт 3 (наполнение jumpAddrDest)
generatePathMbo(0, 200000, 1) = 0.073 sec
Код:
#include <QCoreApplication>
#include <QDebug>
#include <QRandomGenerator>
#include <QVector>
#include <set>
const bool PRINT_GEBUG = true;
static QStringList ll;
void addPointNext(int address) {
if (PRINT_GEBUG) {
ll << QString("%1 - NEXT").arg(address, 4, 10, QLatin1Char('0'));
}
}
void addPointJump(int address, int jumpAddr) {
if (PRINT_GEBUG) {
ll[address] = QString("%1 - JUMP : %2")
.arg(address, 4, 10, QLatin1Char('0'))
.arg(jumpAddr, 4, 10, QLatin1Char('0'));
}
}
void generatePath(int start, int end, double percent, uint seed = 1); //код выше
void generatePathMbo(int start, int end, double percent, uint seed = 1)
{
QRandomGenerator randG(seed);
const int lenPath = end - start + 1;
const int cntJump = int((lenPath - 1) * percent);
QVector<int> path(lenPath - 1);
std::generate(path.begin(), path.end(), [n = 0] () mutable { return ++n; });
QVector<int> starts(cntJump + 1);
starts[0] = 0;
std::sample(path.begin(), path.end(), starts.begin() + 1, cntJump, randG);
QVector<int> ends(cntJump);
std::transform(starts.begin() + 1, starts.end(), ends.begin(), [] (int addr) { return --addr; });
if (PRINT_GEBUG) {
qDebug() << starts;
qDebug() << ends;
}
for (int i = cntJump; i >= 2; --i) {
int iFrom = randG.bounded(1, i);
if (iFrom < i - 1) {
std::swap(starts[iFrom], starts[i - 1]);
std::swap(ends[iFrom], ends[i - 1]);
}
}
for (int i = 0; i < lenPath; ++i) { addPointNext(i); }
for (int i = 0; i < ends.size(); ++i) { addPointJump(ends[i], starts[i + 1]); }
}
int main(int argc, char *argv[]) {
QCoreApplication a(argc, argv);
QElapsedTimer t;
t.start();
generatePath(0, 11, 0.4);
qDebug() << "generatePath() = " << t.restart() / 1000. << "sec";
if (PRINT_GEBUG) { for (const auto & l : ll) { qDebug() << l; } }
ll.clear();
generatePathMbo(0, 11, 0.4);
qDebug() << "generatePathMbo() = " << t.restart() / 1000. << "sec";
if (PRINT_GEBUG) { for (const auto & l : ll) { qDebug() << l; } }
ll.clear();
return a.exec();
}
Out:
generatePath() = 0 sec
"0000 - JUMP : 0004"
"0001 - JUMP : 0002"
"0002 - NEXT"
"0003 - JUMP : 0011"
"0004 - NEXT"
"0005 - NEXT"
"0006 - NEXT"
"0007 - NEXT"
"0008 - NEXT"
"0009 - NEXT"
"0010 - JUMP : 0001"
"0011 - NEXT"
QVector(0, 1, 2, 4, 11)
QVector(0, 1, 3, 10)
generatePathMbo() = 0.011 sec
"0000 - JUMP : 0002"
"0001 - JUMP : 0004"
"0002 - NEXT"
"0003 - JUMP : 0001"
"0004 - NEXT"
"0005 - NEXT"
"0006 - NEXT"
"0007 - NEXT"
"0008 - NEXT"
"0009 - NEXT"
"0010 - JUMP : 0011"
"0011 - NEXT"