163 lines
3.8 KiB
C++
163 lines
3.8 KiB
C++
/*
|
||
* © Copyright 2014 – Urheberrechtshinweis
|
||
* Alle Rechte vorbehalten / All Rights Reserved
|
||
*
|
||
* Programmcode ist urheberrechtlich geschuetzt.
|
||
* Das Urheberrecht liegt, soweit nicht ausdruecklich anders gekennzeichnet, bei Frank Ebner.
|
||
* Keine Verwendung ohne explizite Genehmigung.
|
||
* (vgl. § 106 ff UrhG / § 97 UrhG)
|
||
*/
|
||
|
||
#ifndef NAVMESHWALKRANDOM_H
|
||
#define NAVMESHWALKRANDOM_H
|
||
|
||
|
||
#include "../NavMesh.h"
|
||
#include "../NavMeshLocation.h"
|
||
#include "../../geo/Heading.h"
|
||
|
||
#include "NavMeshSub.h"
|
||
#include "NavMeshWalkParams.h"
|
||
#include "NavMeshWalkEval.h"
|
||
|
||
namespace NM {
|
||
|
||
/**
|
||
* pick a truely random destination within the reachable area
|
||
* weight this area (evaluators)
|
||
* repeat this several times to find a robus destination
|
||
*/
|
||
template <typename Tria> class NavMeshWalkRandom {
|
||
|
||
private:
|
||
|
||
const NavMesh<Tria>& mesh;
|
||
|
||
std::vector<NavMeshWalkEval<Tria>*> evals;
|
||
|
||
public:
|
||
|
||
struct ResultEntry {
|
||
NavMeshLocation<Tria> location;
|
||
Heading heading;
|
||
double probability;
|
||
ResultEntry() : heading(0) {;}
|
||
};
|
||
|
||
struct ResultList : std::vector<ResultEntry> {};
|
||
|
||
public:
|
||
|
||
/** ctor */
|
||
NavMeshWalkRandom(const NavMesh<Tria>& mesh) : mesh(mesh) {
|
||
|
||
}
|
||
|
||
/** add a new evaluator to the walker */
|
||
void addEvaluator(NavMeshWalkEval<Tria>* eval) {
|
||
this->evals.push_back(eval);
|
||
}
|
||
|
||
ResultEntry getOne(const NavMeshWalkParams<Tria>& params) const {
|
||
|
||
// sanity checks
|
||
params.check();
|
||
|
||
ResultEntry res;
|
||
res.probability = 0;
|
||
|
||
// to-be-walked distance;
|
||
const float toBeWalkedDist = params.getToBeWalkedDistance();
|
||
const float toBeWalkedDistSafe = 1.0 + toBeWalkedDist * 1.1;
|
||
|
||
// construct reachable region
|
||
const NavMeshSub<Tria> reachable(params.start, toBeWalkedDistSafe);
|
||
|
||
NavMeshRandom<Tria> rnd = reachable.getRandom();
|
||
NavMeshPotentialWalk<Tria> pwalk(params);
|
||
|
||
// improve quality (the higher, the better)
|
||
for (int i = 0; i < 50; ++i) {
|
||
|
||
PERF_REGION(1, "NavMeshWalkRandom::SampleLoop");
|
||
|
||
// draw a random destination
|
||
// is this destination within the reachable area? (triangles might be larger!)
|
||
pwalk.end = rnd.draw();
|
||
if (pwalk.end.pos.getDistance(params.start.pos) > toBeWalkedDistSafe) {
|
||
--i; continue;
|
||
}
|
||
|
||
// calculate the probability for this destination
|
||
const double p = eval(pwalk);
|
||
|
||
// better?
|
||
if (p > res.probability) {
|
||
res.location = pwalk.end;
|
||
res.probability = p;
|
||
}
|
||
|
||
}
|
||
|
||
// destination is known. update the heading
|
||
res.heading = Heading(params.start.pos.xy(), res.location.pos.xy());
|
||
return res;
|
||
|
||
}
|
||
|
||
ResultList getMany(const NavMeshWalkParams<Tria>& params) const {
|
||
|
||
// sanity checks
|
||
params.check();
|
||
|
||
ResultList res;
|
||
|
||
// to-be-walked distance;
|
||
const float toBeWalkedDist = params.getToBeWalkedDistance();
|
||
const float toBeWalkedDistSafe = 1.0 + toBeWalkedDist * 1.1;
|
||
|
||
// construct reachable region
|
||
const NavMeshSub<Tria> reachable(params.start, toBeWalkedDistSafe);
|
||
|
||
NavMeshRandom<Tria> rnd = reachable.getRandom();
|
||
NavMeshPotentialWalk<Tria> pwalk(params);
|
||
|
||
// improve quality (the higher, the better)
|
||
for (int i = 0; i < 50; ++i) {
|
||
|
||
PERF_REGION(1, "NavMeshWalkRandom::SampleLoop");
|
||
|
||
pwalk.end = rnd.drawWithin(params.start.pos, toBeWalkedDistSafe);
|
||
|
||
// calculate the probability for this destination
|
||
const double p = eval(pwalk);
|
||
|
||
ResultEntry re;
|
||
re.heading = Heading(params.start.pos.xy(), pwalk.end.pos.xy());
|
||
re.location = pwalk.end;
|
||
re.probability = p;
|
||
res.push_back(re);
|
||
|
||
}
|
||
|
||
return res;
|
||
|
||
}
|
||
|
||
double eval(const NM::NavMeshPotentialWalk<Tria>& pwalk) const {
|
||
PERF_REGION(2, "NavMeshWalkRandom::EvalLoop");
|
||
double p = 1.0;
|
||
for (const NavMeshWalkEval<Tria>* eval : evals) {
|
||
const double p1 = eval->getProbability(pwalk);
|
||
p *= p1;
|
||
}
|
||
return p;
|
||
}
|
||
|
||
|
||
};
|
||
|
||
}
|
||
|
||
#endif // NAVMESHWALKRANDOM_H
|