C ++ 11 - prawie działa :)
Po przeczytaniu tego artykułu zebrałem odrobinę mądrości od tego faceta, który najwyraźniej pracował przez 25 lat nad mniej skomplikowanym problemem liczenia ścieżek unikania na kwadratowej sieci.
#include <cassert>
#include <ctime>
#include <sstream>
#include <vector>
#include <algorithm> // sort
using namespace std;
// theroretical max snake lenght (the code would need a few decades to process that value)
#define MAX_LENGTH ((int)(1+8*sizeof(unsigned)))
#ifndef _MSC_VER
#ifndef QT_DEBUG // using Qt IDE for g++ builds
#define NDEBUG
#endif
#endif
#ifdef NDEBUG
inline void tprintf(const char *, ...){}
#else
#define tprintf printf
#endif
void panic(const char * msg)
{
printf("PANIC: %s\n", msg);
exit(-1);
}
// ============================================================================
// fast bit reversal
// ============================================================================
unsigned bit_reverse(register unsigned x, unsigned len)
{
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16)) >> (32-len);
}
// ============================================================================
// 2D geometry (restricted to integer coordinates and right angle rotations)
// ============================================================================
// points using integer- or float-valued coordinates
template<typename T>struct tTypedPoint;
typedef int tCoord;
typedef double tFloatCoord;
typedef tTypedPoint<tCoord> tPoint;
typedef tTypedPoint<tFloatCoord> tFloatPoint;
template <typename T>
struct tTypedPoint {
T x, y;
template<typename U> tTypedPoint(const tTypedPoint<U>& from) : x((T)from.x), y((T)from.y) {} // conversion constructor
tTypedPoint() {}
tTypedPoint(T x, T y) : x(x), y(y) {}
tTypedPoint(const tTypedPoint& p) { *this = p; }
tTypedPoint operator+ (const tTypedPoint & p) const { return{ x + p.x, y + p.y }; }
tTypedPoint operator- (const tTypedPoint & p) const { return{ x - p.x, y - p.y }; }
tTypedPoint operator* (T scalar) const { return{ x * scalar, y * scalar }; }
tTypedPoint operator/ (T scalar) const { return{ x / scalar, y / scalar }; }
bool operator== (const tTypedPoint & p) const { return x == p.x && y == p.y; }
bool operator!= (const tTypedPoint & p) const { return !operator==(p); }
T dot(const tTypedPoint &p) const { return x*p.x + y * p.y; } // dot product
int cross(const tTypedPoint &p) const { return x*p.y - y * p.x; } // z component of cross product
T norm2(void) const { return dot(*this); }
// works only with direction = 1 (90° right) or -1 (90° left)
tTypedPoint rotate(int direction) const { return{ direction * y, -direction * x }; }
tTypedPoint rotate(int direction, const tTypedPoint & center) const { return (*this - center).rotate(direction) + center; }
// used to compute length of a ragdoll snake segment
unsigned manhattan_distance(const tPoint & p) const { return abs(x-p.x) + abs(y-p.y); }
};
struct tArc {
tPoint c; // circle center
tFloatPoint middle_vector; // vector splitting the arc in half
tCoord middle_vector_norm2; // precomputed for speed
tFloatCoord dp_limit;
tArc() {}
tArc(tPoint c, tPoint p, int direction) : c(c)
{
tPoint r = p - c;
tPoint end = r.rotate(direction);
middle_vector = ((tFloatPoint)(r+end)) / sqrt(2); // works only for +-90° rotations. The vector should be normalized to circle radius in the general case
middle_vector_norm2 = r.norm2();
dp_limit = ((tFloatPoint)r).dot(middle_vector);
assert (middle_vector == tPoint(0, 0) || dp_limit != 0);
}
bool contains(tFloatPoint p) // p must be a point on the circle
{
if ((p-c).dot(middle_vector) >= dp_limit)
{
return true;
}
else return false;
}
};
// returns the point of line (p1 p2) that is closest to c
// handles degenerate case p1 = p2
tPoint line_closest_point(tPoint p1, tPoint p2, tPoint c)
{
if (p1 == p2) return{ p1.x, p1.y };
tPoint p1p2 = p2 - p1;
tPoint p1c = c - p1;
tPoint disp = (p1p2 * p1c.dot(p1p2)) / p1p2.norm2();
return p1 + disp;
}
// variant of closest point computation that checks if the projection falls within the segment
bool closest_point_within(tPoint p1, tPoint p2, tPoint c, tPoint & res)
{
tPoint p1p2 = p2 - p1;
tPoint p1c = c - p1;
tCoord nk = p1c.dot(p1p2);
if (nk <= 0) return false;
tCoord n = p1p2.norm2();
if (nk >= n) return false;
res = p1 + p1p2 * (nk / n);
return true;
}
// tests intersection of line (p1 p2) with an arc
bool inter_seg_arc(tPoint p1, tPoint p2, tArc arc)
{
tPoint m = line_closest_point(p1, p2, arc.c);
tCoord r2 = arc.middle_vector_norm2;
tPoint cm = m - arc.c;
tCoord h2 = cm.norm2();
if (r2 < h2) return false; // no circle intersection
tPoint p1p2 = p2 - p1;
tCoord n2p1p2 = p1p2.norm2();
// works because by construction p is on (p1 p2)
auto in_segment = [&](const tFloatPoint & p) -> bool
{
tFloatCoord nk = p1p2.dot(p - p1);
return nk >= 0 && nk <= n2p1p2;
};
if (r2 == h2) return arc.contains(m) && in_segment(m); // tangent intersection
//if (p1 == p2) return false; // degenerate segment located inside circle
assert(p1 != p2);
tFloatPoint u = (tFloatPoint)p1p2 * sqrt((r2-h2)/n2p1p2); // displacement on (p1 p2) from m to one intersection point
tFloatPoint i1 = m + u;
if (arc.contains(i1) && in_segment(i1)) return true;
tFloatPoint i2 = m - u;
return arc.contains(i2) && in_segment(i2);
}
// ============================================================================
// compact storage of a configuration (64 bits)
// ============================================================================
struct sConfiguration {
unsigned partition;
unsigned folding;
explicit sConfiguration() {}
sConfiguration(unsigned partition, unsigned folding) : partition(partition), folding(folding) {}
// add a bend
sConfiguration bend(unsigned joint, int rotation) const
{
sConfiguration res;
unsigned joint_mask = 1 << joint;
res.partition = partition | joint_mask;
res.folding = folding;
if (rotation == -1) res.folding |= joint_mask;
return res;
}
// textual representation
string text(unsigned length) const
{
ostringstream res;
unsigned f = folding;
unsigned p = partition;
int segment_len = 1;
int direction = 1;
for (size_t i = 1; i != length; i++)
{
if (p & 1)
{
res << segment_len * direction << ',';
direction = (f & 1) ? -1 : 1;
segment_len = 1;
}
else segment_len++;
p >>= 1;
f >>= 1;
}
res << segment_len * direction;
return res.str();
}
// for final sorting
bool operator< (const sConfiguration& c) const
{
return (partition == c.partition) ? folding < c.folding : partition < c.partition;
}
};
// ============================================================================
// static snake geometry checking grid
// ============================================================================
typedef unsigned tConfId;
class tGrid {
vector<tConfId>point;
tConfId current;
size_t snake_len;
int min_x, max_x, min_y, max_y;
size_t x_size, y_size;
size_t raw_index(const tPoint& p) { bound_check(p); return (p.x - min_x) + (p.y - min_y) * x_size; }
void bound_check(const tPoint& p) const { assert(p.x >= min_x && p.x <= max_x && p.y >= min_y && p.y <= max_y); }
void set(const tPoint& p)
{
point[raw_index(p)] = current;
}
bool check(const tPoint& p)
{
if (point[raw_index(p)] == current) return false;
set(p);
return true;
}
public:
tGrid(int len) : current(-1), snake_len(len)
{
min_x = -max(len - 3, 0);
max_x = max(len - 0, 0);
min_y = -max(len - 1, 0);
max_y = max(len - 4, 0);
x_size = max_x - min_x + 1;
y_size = max_y - min_y + 1;
point.assign(x_size * y_size, current);
}
bool check(sConfiguration c)
{
current++;
tPoint d(1, 0);
tPoint p(0, 0);
set(p);
for (size_t i = 1; i != snake_len; i++)
{
p = p + d;
if (!check(p)) return false;
if (c.partition & 1) d = d.rotate((c.folding & 1) ? -1 : 1);
c.folding >>= 1;
c.partition >>= 1;
}
return check(p + d);
}
};
// ============================================================================
// snake ragdoll
// ============================================================================
class tSnakeDoll {
vector<tPoint>point; // snake geometry. Head at (0,0) pointing right
// allows to check for collision with the area swept by a rotating segment
struct rotatedSegment {
struct segment { tPoint a, b; };
tPoint org;
segment end;
tArc arc[3];
bool extra_arc; // see if third arc is needed
// empty constructor to avoid wasting time in vector initializations
rotatedSegment(){}
// copy constructor is mandatory for vectors *but* shall never be used, since we carefully pre-allocate vector memory
rotatedSegment(const rotatedSegment &){ assert(!"rotatedSegment should never have been copy-constructed"); }
// rotate a segment
rotatedSegment(tPoint pivot, int rotation, tPoint o1, tPoint o2)
{
arc[0] = tArc(pivot, o1, rotation);
arc[1] = tArc(pivot, o2, rotation);
tPoint middle;
extra_arc = closest_point_within(o1, o2, pivot, middle);
if (extra_arc) arc[2] = tArc(pivot, middle, rotation);
org = o1;
end = { o1.rotate(rotation, pivot), o2.rotate(rotation, pivot) };
}
// check if a segment intersects the area swept during rotation
bool intersects(tPoint p1, tPoint p2) const
{
auto print_arc = [&](int a) { tprintf("(%d,%d)(%d,%d) -> %d (%d,%d)[%f,%f]", p1.x, p1.y, p2.x, p2.y, a, arc[a].c.x, arc[a].c.y, arc[a].middle_vector.x, arc[a].middle_vector.y); };
if (p1 == org) return false; // pivot is the only point allowed to intersect
if (inter_seg_arc(p1, p2, arc[0]))
{
print_arc(0);
return true;
}
if (inter_seg_arc(p1, p2, arc[1]))
{
print_arc(1);
return true;
}
if (extra_arc && inter_seg_arc(p1, p2, arc[2]))
{
print_arc(2);
return true;
}
return false;
}
};
public:
sConfiguration configuration;
bool valid;
// holds results of a folding attempt
class snakeFolding {
friend class tSnakeDoll;
vector<rotatedSegment>segment; // rotated segments
unsigned joint;
int direction;
size_t i_rotate;
// pre-allocate rotated segments
void reserve(size_t length)
{
segment.clear(); // this supposedly does not release vector storage memory
segment.reserve(length);
}
// handle one segment rotation
void rotate(tPoint pivot, int rotation, tPoint o1, tPoint o2)
{
segment.emplace_back(pivot, rotation, o1, o2);
}
public:
// nothing done during construction
snakeFolding(unsigned size)
{
segment.reserve (size);
}
};
// empty default constructor to avoid wasting time in array/vector inits
tSnakeDoll() {}
// constructs ragdoll from compressed configuration
tSnakeDoll(unsigned size, unsigned generator, unsigned folding) : point(size), configuration(generator,folding)
{
tPoint direction(1, 0);
tPoint current = { 0, 0 };
size_t p = 0;
point[p++] = current;
for (size_t i = 1; i != size; i++)
{
current = current + direction;
if (generator & 1)
{
direction.rotate((folding & 1) ? -1 : 1);
point[p++] = current;
}
folding >>= 1;
generator >>= 1;
}
point[p++] = current;
point.resize(p);
}
// constructs the initial flat snake
tSnakeDoll(int size) : point(2), configuration(0,0), valid(true)
{
point[0] = { 0, 0 };
point[1] = { size, 0 };
}
// constructs a new folding with one added rotation
tSnakeDoll(const tSnakeDoll & parent, unsigned joint, int rotation, tGrid& grid)
{
// update configuration
configuration = parent.configuration.bend(joint, rotation);
// locate folding point
unsigned p_joint = joint+1;
tPoint pivot;
size_t i_rotate = 0;
for (size_t i = 1; i != parent.point.size(); i++)
{
unsigned len = parent.point[i].manhattan_distance(parent.point[i - 1]);
if (len > p_joint)
{
pivot = parent.point[i - 1] + ((parent.point[i] - parent.point[i - 1]) / len) * p_joint;
i_rotate = i;
break;
}
else p_joint -= len;
}
// rotate around joint
snakeFolding fold (parent.point.size() - i_rotate);
fold.rotate(pivot, rotation, pivot, parent.point[i_rotate]);
for (size_t i = i_rotate + 1; i != parent.point.size(); i++) fold.rotate(pivot, rotation, parent.point[i - 1], parent.point[i]);
// copy unmoved points
point.resize(parent.point.size()+1);
size_t i;
for (i = 0; i != i_rotate; i++) point[i] = parent.point[i];
// copy rotated points
for (; i != parent.point.size(); i++) point[i] = fold.segment[i - i_rotate].end.a;
point[i] = fold.segment[i - 1 - i_rotate].end.b;
// static configuration check
valid = grid.check (configuration);
// check collisions with swept arcs
if (valid && parent.valid) // ;!; parent.valid test is temporary
{
for (const rotatedSegment & s : fold.segment)
for (size_t i = 0; i != i_rotate; i++)
{
if (s.intersects(point[i+1], point[i]))
{
//printf("! %s => %s\n", parent.trace().c_str(), trace().c_str());//;!;
valid = false;
break;
}
}
}
}
// trace
string trace(void) const
{
size_t len = 0;
for (size_t i = 1; i != point.size(); i++) len += point[i - 1].manhattan_distance(point[i]);
return configuration.text(len);
}
};
// ============================================================================
// snake twisting engine
// ============================================================================
class cSnakeFolder {
int length;
unsigned num_joints;
tGrid grid;
// filter redundant configurations
bool is_unique (sConfiguration c)
{
unsigned reverse_p = bit_reverse(c.partition, num_joints);
if (reverse_p < c.partition)
{
tprintf("P cut %s\n", c.text(length).c_str());
return false;
}
else if (reverse_p == c.partition) // filter redundant foldings
{
unsigned first_joint_mask = c.partition & (-c.partition); // insulates leftmost bit
unsigned reverse_f = bit_reverse(c.folding, num_joints);
if (reverse_f & first_joint_mask) reverse_f = ~reverse_f & c.partition;
if (reverse_f > c.folding)
{
tprintf("F cut %s\n", c.text(length).c_str());
return false;
}
}
return true;
}
// recursive folding
void fold(tSnakeDoll snake, unsigned first_joint)
{
// count unique configurations
if (snake.valid && is_unique(snake.configuration)) num_configurations++;
// try to bend remaining joints
for (size_t joint = first_joint; joint != num_joints; joint++)
{
// right bend
tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint,1).text(length).c_str());
fold(tSnakeDoll(snake, joint, 1, grid), joint + 1);
// left bend, except for the first joint
if (snake.configuration.partition != 0)
{
tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint, -1).text(length).c_str());
fold(tSnakeDoll(snake, joint, -1, grid), joint + 1);
}
}
}
public:
// count of found configurations
unsigned num_configurations;
// constructor does all the work :)
cSnakeFolder(int n) : length(n), grid(n), num_configurations(0)
{
num_joints = length - 1;
// launch recursive folding
fold(tSnakeDoll(length), 0);
}
};
// ============================================================================
// here we go
// ============================================================================
int main(int argc, char * argv[])
{
#ifdef NDEBUG
if (argc != 2) panic("give me a snake length or else");
int length = atoi(argv[1]);
#else
(void)argc; (void)argv;
int length = 12;
#endif // NDEBUG
if (length <= 0 || length >= MAX_LENGTH) panic("a snake of that length is hardly foldable");
time_t start = time(NULL);
cSnakeFolder snakes(length);
time_t duration = time(NULL) - start;
printf ("Found %d configuration%c of length %d in %lds\n", snakes.num_configurations, (snakes.num_configurations == 1) ? '\0' : 's', length, duration);
return 0;
}
Budowanie pliku wykonywalnego
Kompiluj z
Używam MinGW pod Win7 z g ++ 4.8 dla kompilacji „linux”, więc przenośność nie jest gwarantowana w 100%.g++ -O3 -std=c++11
Działa również (w pewnym sensie) ze standardowym projektem MSVC2013
Niezdefiniowanie NDEBUGpozwala uzyskać ślady wykonania algorytmu i podsumowanie znalezionych konfiguracji.
Występy
z tablicami skrótów lub bez nich kompilator Microsoft działa marnie: kompilacja g ++ jest 3 razy szybsza .
Algorytm praktycznie nie wykorzystuje pamięci.
Ponieważ kontrola kolizji jest w przybliżeniu w O (n), czas obliczeń powinien być w O (nk n ), przy k nieco mniejszym niż 3.
W moim i3-2100@3,1 GHz, n = 17 zajmuje około 1:30 (około 2 milionów węże / minutę).
Nie skończyłem optymalizacji, ale nie spodziewałbym się więcej niż x3, więc w zasadzie mogę mieć nadzieję, że osiągnę n = 20 poniżej godziny lub n = 24 poniżej dnia.
Osiągnięcie pierwszego znanego nieugiętego kształtu (n = 31) zajęłoby od kilku lat do dekady, przy założeniu braku przerw w dostawie prądu.
Liczenie kształtów
N wielkość wąż N1 stawów.
Każde złącze może być lewe lub wygięte w lewo lub w prawo (3 możliwości).
Liczba możliwych składania wynosi zatem 3 N-1 .
Zderzenia nieco zmniejszą tę liczbę, więc faktyczna liczba jest bliska 2,7 N-1
Jednak wiele takich fałd prowadzi do identycznych kształtów.
dwa kształty są identyczne, jeśli istnieje obrót lub symetria, które mogą przekształcić jeden w drugi.
Zdefiniujmy segment jako dowolną prostą część złożonego korpusu.
Na przykład wąż wielkości 5 złożony na 2. stawie miałby 2 segmenty (jeden 2 jednostki długości i drugi 3 jednostki długości).
Pierwszy segment zostanie nazwany głową , a ostatni ogon .
Konwencjonalnie orientujemy głowę węży poziomo z ciałem skierowanym w prawo (jak na pierwszej figurze OP).
Daną liczbę oznaczamy za pomocą listy podpisanych długości segmentów, przy czym długości dodatnie wskazują na prawe fałdowanie, a ujemne na lewe.
Początkowa długość jest zgodna z konwencją.
Rozdzielanie segmentów i zagięć
Jeśli weźmiemy pod uwagę tylko różne sposoby podziału węża o długości N na segmenty, otrzymamy podział identyczny do składu N.
Przy użyciu tego samego algorytmu, jak przedstawiono na stronie wiki jest łatwy do wygenerowania wszystkich 2 n-1 możliwe przegrody węża.
Każda przegroda z kolei wygeneruje wszystkie możliwe zagięcia, stosując lewe lub prawe zagięcie do wszystkich swoich połączeń. Jedno takie składanie będzie nazywane konfiguracją .
Wszystkie możliwe partycje mogą być reprezentowane przez liczbę całkowitą N-1 bitów, przy czym każdy bit reprezentuje obecność połączenia. Nazwamy tę liczbę całkowitą generatorem .
Przycinanie partycji
Zauważając, że wygięcie danej przegrody od głowy w dół jest równoważne zgięciu symetrycznej przegrody od ogona w górę, możemy znaleźć wszystkie pary symetrycznych przegród i wyeliminować jedną z dwóch.
Generator symetrycznej partycji jest generatorem partycji zapisanym w odwrotnej kolejności bitów, który jest banalnie łatwy i tani do wykrycia.
To wyeliminuje prawie połowę możliwych partycji, wyjątkami są partycje z generatorami „palindromowymi”, które pozostają niezmienione przez odwrócenie bitów (na przykład 00100100).
Dbanie o poziome symetrie
Dzięki naszym konwencjom (wąż zaczyna wskazywać w prawo), pierwsze zagięcie zastosowane po prawej stronie stworzy rodzinę zagięć, które będą poziomymi symetriami od tych, które różnią się tylko pierwszym zgięciem.
Jeśli zdecydujemy, że pierwsze zakręt zawsze będzie po prawej stronie, eliminujemy wszystkie poziome symetrie za jednym razem.
Mycie palindromów
Te dwa cięcia są wydajne, ale niewystarczające, aby zająć się tymi nieznośnymi palindromami.
Najbardziej szczegółowa kontrola w ogólnym przypadku wygląda następująco:
rozważ konfigurację C z partycją palindromową.
- jeśli odwrócimy każde zagięcie w C, otrzymamy poziomą symetrię C.
- jeśli odwrócimy C (stosując zakręty od ogona do góry), otrzymamy tę samą figurę obróconą w prawo
- jeśli zarówno cofniemy, jak i odwrócimy C, otrzymamy tę samą liczbę obróconą w lewo.
Możemy sprawdzić każdą nową konfigurację z 3 innymi. Ponieważ jednak generujemy już tylko konfiguracje zaczynające się od skrętu w prawo, mamy tylko jedną możliwą symetrię do sprawdzenia:
- odwrócone C rozpocznie się od skrętu w lewo, którego z założenia nie można powielić
- z konfiguracji odwróconej i odwróconej-odwróconej tylko jedna rozpocznie się od skrętu w prawo.
To jedyna konfiguracja, którą możemy powielić.
Eliminowanie duplikatów bez przechowywania
Moje początkowe podejście polegało na przechowywaniu wszystkich konfiguracji w ogromnej tabeli mieszającej, aby wyeliminować duplikaty, sprawdzając obecność wcześniej obliczonej konfiguracji symetrycznej.
Dzięki wspomnianemu artykułowi stało się jasne, że ponieważ partycje i foldery są przechowywane jako pola bitowe, można je porównać jak każdą wartość liczbową.
Aby więc wyeliminować jednego członka pary symetrycznej, możesz po prostu porównać oba elementy i systematycznie zachować najmniejszy (lub największy, jak chcesz).
Zatem testowanie konfiguracji duplikacji sprowadza się do obliczenia symetrycznej partycji, a jeśli obie są identyczne, zwijanie. W ogóle nie jest potrzebna pamięć.
Kolejność generacji
Oczywiste jest, że kontrola kolizji będzie najbardziej czasochłonną częścią, więc zmniejszenie tych obliczeń jest znaczną oszczędnością czasu.
Możliwym rozwiązaniem jest posiadanie „węża ragdoll”, który rozpocznie się w płaskiej konfiguracji i będzie stopniowo wyginany, aby uniknąć ponownego obliczenia całej geometrii węża dla każdej możliwej konfiguracji.
Wybierając kolejność testowania konfiguracji, aby maksymalnie przechowywać ragdoll dla każdej łącznej liczby połączeń, możemy ograniczyć liczbę instancji do N-1.
Używam rekurencyjnego skanu sake od ogona w dół, dodając pojedynczy staw na każdym poziomie. Zatem nowa instancja ragdoll jest zbudowana na konfiguracji nadrzędnej, z jednym dodatkowym zgięciem.
Oznacza to, że zakręty są stosowane w kolejności sekwencyjnej, co wydaje się wystarczające, aby uniknąć kolizji we wszystkich przypadkach.
Po wykryciu kolizji zgięcia, które prowadzą do wykroczenia, są stosowane we wszystkich możliwych rozkazach, aż do znalezienia prawidłowego złożenia lub wyczerpania wszystkich kombinacji.
Kontrola statyczna
Zanim nawet pomyślałem o ruchomych częściach, bardziej efektywne było przetestowanie statycznego ostatecznego kształtu węża pod kątem skrzyżowań.
Odbywa się to poprzez narysowanie węża na siatce. Każdy możliwy punkt jest wykreślany od głowy w dół. Jeśli istnieje skrzyżowanie, co najmniej para punktów spadnie na to samo miejsce. Wymaga to dokładnie N wykresów dla dowolnej konfiguracji węża, dla stałego czasu O (N).
Główną zaletą tego podejścia jest to, że sam test statyczny po prostu wybierze prawidłowe sam unikające się ścieżki na kwadratowej sieci, co pozwala przetestować cały algorytm przez hamowanie dynamicznego wykrywania kolizji i upewnienie się, że znajdziemy prawidłową liczbę takich ścieżek.
Kontrola dynamiczna
Kiedy wąż składa się wokół jednego stawu, każdy obrócony segment zamiata obszar, którego kształt nie jest trywialny.
Oczywiście można sprawdzić kolizje, testując indywidualnie włączenie we wszystkich takich obszarach. Globalna kontrola byłaby bardziej wydajna, ale biorąc pod uwagę złożoność obszarów, o której nie mogę myśleć (oprócz użycia GPU do narysowania wszystkich obszarów i przeprowadzenia globalnej kontroli trafień).
Ponieważ test statyczny zajmuje się początkową i końcową pozycją każdego segmentu, musimy tylko sprawdzić przecięcia z łukami przeciągniętymi przez każdy obracający się segment.
Po interesującej dyskusji z trichoplaxem i odrobiną JavaScript, aby uzyskać orientację , wymyśliłem tę metodę:
Spróbuj zadzwonić w kilku słowach, jeśli zadzwonisz
- C środek obrotu,
- S obrotowy segment o dowolnej długości i kierunku, który nie zawiera C ,
- L linia przedłużająca S
- H linia prostopadła do L przechodząca przez C ,
- I przecięcie L i H ,
(źródło: free.fr )
Dla każdego segmentu, który nie zawiera I , obszar przemiatania jest ograniczony przez 2 łuki (i 2 segmenty, które zostały już zajęte przez kontrolę statyczną).
Jeśli ja wchodzi w segmencie łuk zmieciony przez Muszę być również brane pod uwagę.
Oznacza to, że możemy sprawdzić każdy nieruchliwy segment w stosunku do każdego segmentu obrotowego za pomocą 2 lub 3 odcinków z łukiem
Użyłem geometrii wektorowej, aby całkowicie uniknąć funkcji trygonometrycznych.
Operacje wektorowe dają zwarty i (względnie) czytelny kod.
Przecięcie segmentu do łuku wymaga wektora zmiennoprzecinkowego, ale logika powinna być odporna na błędy zaokrąglania.
Znalazłem to eleganckie i wydajne rozwiązanie w niejasnym wpisie na forum. Zastanawiam się, dlaczego nie jest szerzej rozpowszechniany.
Czy to działa?
Hamowanie dynamicznego wykrywania kolizji powoduje powstanie prawidłowej liczby unikających ścieżek do n = 19, więc jestem pewien, że globalny układ działa.
Dynamiczne wykrywanie kolizji daje spójne wyniki, chociaż brakuje kontroli zgięć w innej kolejności (na razie).
W rezultacie program zlicza węże, które można zgiąć od głowy w dół (tj. Ze stawami złożonymi w kolejności rosnącej od głowy).
