From 7fe30185df21617cf44100f89db462cd4501050e Mon Sep 17 00:00:00 2001 From: fusion32 Date: Sun, 18 May 2025 18:54:23 -0300 Subject: implement `matrix` and move containers into their own directory --- reference/game.c | 174 --------------------------------------- reference/types.hh | 34 -------- src/containers/matrix.hh | 132 +++++++++++++++++++++++++++++ src/containers/priority_queue.hh | 94 +++++++++++++++++++++ src/containers/vector.hh | 123 +++++++++++++++++++++++++++ src/priority_queue.hh | 94 --------------------- src/vector.hh | 123 --------------------------- 7 files changed, 349 insertions(+), 425 deletions(-) create mode 100644 src/containers/matrix.hh create mode 100644 src/containers/priority_queue.hh create mode 100644 src/containers/vector.hh delete mode 100644 src/priority_queue.hh delete mode 100644 src/vector.hh diff --git a/reference/game.c b/reference/game.c index 59bc8a5..a005445 100644 --- a/reference/game.c +++ b/reference/game.c @@ -16459,63 +16459,6 @@ void _GLOBAL__I_InstanceAttributeNames(void) return; } -// DWARF original prototype: void matrix3d(matrix3d * this, int xmin, int xmax, int ymin, -// int ymax, int zmin, int zmax, TSector * init) - -void __thiscall -matrix3d::matrix3d - (matrix3d *this,int xmin,int xmax,int ymin,int ymax,int zmin,int zmax, - TSector *init) - -{ - int iVar1; - TSector **ppTVar2; - int iVar3; - int i; - int iVar4; - - this->xmin = xmin; - this->ymin = ymin; - this->zmin = zmin; - iVar4 = (xmax - xmin) + 1; - this->dx = iVar4; - iVar3 = (ymax - ymin) + 1; - this->dy = iVar3; - iVar1 = (zmax - zmin) + 1; - this->dz = iVar1; - if (((iVar4 < 1) || (iVar3 < 1)) || (iVar1 < 1)) { - error("matrix3d: Ungueltige Feldgroesse %d..%d, %d..%d, %d..%d.\n",xmin,xmax,ymin,ymax,zmin, - zmax); - iVar4 = this->dx; - if (iVar4 < 1) { - this->dx = 1; - iVar4 = 1; - } - iVar3 = this->dy; - if (iVar3 < 1) { - this->dy = 1; - iVar3 = 1; - } - iVar1 = this->dz; - if (iVar1 < 1) { - this->dz = 1; - iVar1 = 1; - } - } - ppTVar2 = (TSector **)operator_new__(iVar4 * iVar3 * iVar1 * 4); - iVar4 = 0; - this->entry = ppTVar2; - if (0 < this->dy * this->dx * this->dz) { - do { - this->entry[iVar4] = init; - iVar4 = iVar4 + 1; - } while (iVar4 < this->dy * this->dx * this->dz); - } - return; -} - - - void __static_initialization_and_destruction_0(int __initialize_p,int __priority) { @@ -28294,43 +28237,6 @@ void _GLOBAL__I__Z7GetName6Object(void) return; } - - -// DWARF original prototype: void matrix(matrix * this, int xmin, int xmax, int ymin, int ymax) - -void __thiscall matrix::matrix(matrix *this,int xmin,int xmax,int ymin,int ymax) - -{ - int iVar1; - int *piVar2; - int iVar3; - - iVar3 = (xmax - xmin) + 1; - this->xmin = xmin; - iVar1 = (ymax - ymin) + 1; - this->ymin = ymin; - this->dx = iVar3; - this->dy = iVar1; - if ((iVar3 < 1) || (iVar1 < 1)) { - error("matrix: Ungueltige Feldgroesse %d..%d, %d..%d.\n",xmin,xmax,ymin,ymax); - iVar3 = this->dx; - if (iVar3 < 1) { - this->dx = 1; - iVar3 = 1; - } - iVar1 = this->dy; - if (iVar1 < 1) { - this->dy = 1; - iVar1 = 1; - } - } - piVar2 = (int *)operator_new__(iVar3 * iVar1 * 4); - this->entry = piVar2; - return; -} - - - void RandomShuffle(int *Buffer,int Size) { @@ -56434,40 +56340,6 @@ void __thiscall TCreature::AttackStimulus(TCreature *this,ulong param_1) return; } -// DWARF original prototype: void matrix(matrix * this, int xmin, int xmax, int -// ymin, int ymax, ulong init) - -void __thiscall matrix<>::matrix(matrix<> *this,int xmin,int xmax,int ymin,int ymax,ulong init) - -{ - int iVar1; - ulong *puVar2; - int i; - int iVar3; - - iVar3 = (xmax - xmin) + 1; - iVar1 = (ymax - ymin) + 1; - this->dy = iVar1; - this->xmin = xmin; - this->ymin = ymin; - this->dx = iVar3; - if ((iVar3 < 1) || (iVar1 < 1)) { - error("matrix: Ungueltige Feldgroesse %d..%d, %d..%d.\n",xmin,xmax,ymin,ymax); - this->dx = 1; - this->dy = 1; - } - puVar2 = (ulong *)operator_new__(this->dy * this->dx * 4); - iVar1 = 0; - this->entry = puVar2; - if (0 < this->dy * this->dx) { - do { - this->entry[iVar1] = init; - iVar1 = iVar1 + 1; - } while (iVar1 < this->dy * this->dx); - } - return; -} - void __static_initialization_and_destruction_0(int __initialize_p,int __priority) { @@ -73694,52 +73566,6 @@ void _GLOBAL__I__ZN9TShortwayC2EP9TCreatureii(void) return; } - - -// DWARF original prototype: void matrix(matrix * this, int xmin, int xmax, int -// ymin, int ymax) - -void __thiscall matrix<>::matrix(matrix<> *this,int xmin,int xmax,int ymin,int ymax) - -{ - int iVar1; - TShortwayPoint *pTVar2; - TShortwayPoint *pTVar3; - int iVar4; - - iVar4 = (xmax - xmin) + 1; - iVar1 = (ymax - ymin) + 1; - this->xmin = xmin; - this->ymin = ymin; - this->dx = iVar4; - this->dy = iVar1; - if ((iVar4 < 1) || (iVar1 < 1)) { - error("matrix: Ungueltige Feldgroesse %d..%d, %d..%d.\n",xmin,xmax,ymin,ymax); - iVar4 = this->dx; - if (iVar4 < 1) { - this->dx = 1; - iVar4 = 1; - } - iVar1 = this->dy; - if (iVar1 < 1) { - this->dy = 1; - iVar1 = 1; - } - } - iVar4 = iVar4 * iVar1; - pTVar2 = (TShortwayPoint *)operator_new__(iVar4 * 0x1c); - pTVar3 = pTVar2; - while (iVar4 = iVar4 + -1, iVar4 != -1) { - pTVar3->Waylength = -1; - pTVar3->Heuristic = -1; - pTVar3->Predecessor = (TShortwayPoint *)0x0; - pTVar3->NextToExpand = (TShortwayPoint *)0x0; - pTVar3 = pTVar3 + 1; - } - this->entry = pTVar2; - return; -} - void __static_initialization_and_destruction_0(int __initialize_p,int __priority) { diff --git a/reference/types.hh b/reference/types.hh index 82d001b..d79cf0c 100644 --- a/reference/types.hh +++ b/reference/types.hh @@ -515,14 +515,6 @@ struct THouse { int Help; }; -struct matrix { // Original name: matrix - int xmin; - int ymin; - int dx; - int dy; - ulong *entry; -}; - struct TWaitinglistEntry { struct TWaitinglistEntry *Next; char Name[30]; @@ -698,14 +690,6 @@ struct TShortwayPoint { struct TShortwayPoint *NextToExpand; }; -struct matrix { - int xmin; - int ymin; - int dx; - int dy; - struct TShortwayPoint *entry; -}; - struct TCronEntry { struct Object Obj; ulong RoundNr; @@ -766,16 +750,6 @@ struct TCondition { int Number; }; -struct matrix3d { - int xmin; - int ymin; - int zmin; - int dx; - int dy; - int dz; - struct TSector **entry; -}; - struct TSector { struct Object MapCon[32][32]; ulong TimeStamp; @@ -798,14 +772,6 @@ struct THelpDepot { int DepotNr; }; -struct matrix { - int xmin; - int ymin; - int dx; - int dy; - int *entry; -}; - struct listIterator_> { // Original name: listIterator > struct listnode_> *actNode; }; diff --git a/src/containers/matrix.hh b/src/containers/matrix.hh new file mode 100644 index 0000000..bf255ff --- /dev/null +++ b/src/containers/matrix.hh @@ -0,0 +1,132 @@ +#ifndef TIBIA_MATRIX_HH_ +#define TIBIA_MATRIX_HH_ 1 + +typedef +struct matrix{ + // REGULAR FUNCTIONS + // ========================================================================= + matrix(int xmin, int xmax, int ymin, int ymax){ + int dx = (xmax - xmin) + 1; + int dy = (ymax - ymin) + 1; + + if(dx < 1 || dy < 1){ + error("matrix: Ungueltige Feldgroesse %d..%d, %d..%d.\n", xmin, xmax, ymin, ymax); + + if(dx < 1){ + dx = 1; + } + + if(dy < 1){ + dy = 1; + } + } + + this->xmin = xmin; + this->ymin = ymin; + this->dx = dx; + this->dy = dy; + this->entry = new T[dx * dy]; + } + + matrix(int xmin, int xmax, int ymin, int ymax, T init) : matrix(xmin, xmax, ymin, ymax) { + int count = this->dx * this->dy; + for(int i = 0; i < count; i += 1){ + this->entry[i] = init; + } + } + + // TODO(fusion): Probably missing some inlined destructor? + + T *at(int x, int y){ + int xoffset = x - this->xmin; + int yoffset = y - this->ymin; + if(xoffset < 0 || xoffset >= this->dx || yoffset < 0 || yoffset >= this->dy){ + error("matrix::operator(): Ungueltiger Index %d/%d.\n", x, y); + return &this->entry[0]; + }else{ + // TODO(fusion): Are we really storing this in row major order? + return &this->entry[yoffset * this->dx + xoffset]; + } + } + + // DATA + // ========================================================================= + int xmin; + int ymin; + int dx; + int dy; + T *entry; +}; + +typedef +struct matrix3d{ + // REGULAR FUNCTIONS + // ========================================================================= + matrix3d(int xmin, int xmax, int ymin, int ymax, int zmin, int zmax){ + int dx = (xmax - xmin) + 1; + int dy = (ymax - ymin) + 1; + int dz = (zmax - zmin) + 1; + + if(dx < 1 || dy < 1 || dz < 1){ + error("matrix3d: Ungueltige Feldgroesse %d..%d, %d..%d, %d..%d.\n", + xmin, xmax, ymin, ymax, zmin, zmax); + + if(dx < 1){ + dx = 1; + } + + if(dy < 1){ + dy = 1; + } + + if(dz < 1){ + dz = 1; + } + } + + this->xmin = xmin; + this->ymin = ymin; + this->dx = dx; + this->dy = dy; + this->entry = new T[dx * dy]; + } + + matrix3d(int xmin, int xmax, int ymin, int ymax, int zmin, int zmax, T init) + : matrix(xmin, xmax, ymin, ymax, zmin, zmax) { + int count = this->dx * this->dy * this->dz; + for(int i = 0; i < count; i += 1){ + this->entry[i] = init; + } + } + + // TODO(fusion): Probably missing some inlined destructor? + + T *at(int x, int y, int z){ + int xoffset = x - this->xmin; + int yoffset = y - this->ymin; + int zoffset = z - this->zmin; + if(xoffset < 0 || xoffset >= this->dx + || yoffset < 0 || yoffset >= this->dy + || zoffset < 0 || zoffset >= this->dz){ + error("matrix3d::operator(): Ungueltiger Index %d/%d/%d.\n", x, y, z); + return &this->entry[0]; + }else{ + // TODO(fusion): Same as `matrix::at` on the XY plane. + return &this->entry[zoffset * this->dx * this->dy + + yoffset * this->dx + + xoffset]; + } + } + + // DATA + // ========================================================================= + int xmin; + int ymin; + int zmin; + int dx; + int dy; + int dz; + T *entry; +}; + +#endif //TIBIA_MATRIX_HH_ diff --git a/src/containers/priority_queue.hh b/src/containers/priority_queue.hh new file mode 100644 index 0000000..b48353e --- /dev/null +++ b/src/containers/priority_queue.hh @@ -0,0 +1,94 @@ +#ifndef TIBIA_PRIORITY_QUEUE_HH_ +#define TIBIA_PRIORITY_QUEUE_HH_ 1 + +#include "main.hh" +#include "vector.hh" + +template +struct priority_queue_entry{ + K Key; + T Data; +}; + +template +struct priority_queue{ + // REGULAR FUNCTIONS + // ========================================================================= + priority_queue(int capacity, int increment){ + Entry = new vector>(1, capacity, increment); + Entries = 0; + } + + // TODO(fusion): Probably missing some inlined destructor? + + void insert(K Key, T *Data){ + this->Entries += 1; + int CurrentIndex = this->Entries; + *this->Entry->at(CurrentIndex) = {Key, *Data}; + while(CurrentIndex > 1){ + int ParentIndex = CurrentIndex / 2; + priority_queue_entry *Current = this->Entry->at(CurrentIndex); + priority_queue_entry *Parent = this->Entry->at(ParentIndex); + if(Parent->Key <= Current->Key) + break; + std::swap(*Current, *Parent); + CurrentIndex = ParentIndex; + } + } + + void deleteMin(void){ + if(this->Entries < 1){ + error("priority_queue::deleteMin: Warteschlange ist leer.\n"); + return; + } + + if(this->Entries > 1){ + int CurrentIndex = 1; + int LastIndex = this->Entries; + std::swap(*this->Entry->at(CurrentIndex), + *this->Entry->at(LastIndex)); + + // TODO(fusion): This may be an oversight but the decompiled version + // checks in the loop below would INCLUDE `LastIndex`, which I assume + // is a bug? The first and last elements were just swapped and what + // was the first element in the queue is now at the end and should be + // considered "removed". + while(1){ + int SmallestIndex = CurrentIndex * 2; + if(SmallestIndex >= LastIndex){ + break; + } + + priority_queue_entry *Smallest = this->Entry->at(SmallestIndex); + if((SmallestIndex + 1) < LastIndex){ + priority_queue_entry *Other = this->Entry->at(SmallestIndex + 1); + if(Other->Key < Smallest->Key){ + Smallest = Other; + SmallestIndex += 1; + } + } + + priority_queue_entry *Current = this->Entry->at(CurrentIndex); + if(Current->Key <= Smallest->Key){ + break; + } + + std::swap(*Current, *Smallest); + CurrentIndex = SmallestIndex; + } + } + + this->Entries -= 1; + } + + // DATA + // ========================================================================= + vector> *Entry; + int Entries; +}; + +// TODO(fusion): We only use this structure two global queues: +// priority_queue ToDoQueue(5000, 1000); +// priority_queue AttackWaveQueue(100, 100); + +#endif //TIBIA_PRIORITY_QUEUE_HH_ diff --git a/src/containers/vector.hh b/src/containers/vector.hh new file mode 100644 index 0000000..044ffe1 --- /dev/null +++ b/src/containers/vector.hh @@ -0,0 +1,123 @@ +#ifndef TIBIA_VECTOR_HH_ +#define TIBIA_VECTOR_HH_ 1 + +#include "main.hh" + +// NOTE(fusion): What the actual fuck. This is an ever growing dynamic array +// with each access through `operator()` growing it to make sure the requested +// index is valid, even for negative indices. +template +struct vector{ + // REGULAR FUNCTIONS + // ========================================================================= + vector(int min, int max, int block){ + int space = (max - min) + 1; + if(space < 1){ + error("vector: Ungueltige Feldgroesse %d bis %d.\n", min, max); + space = 1; + } + + if(block < 0){ + error("vector: Ungueltige Blockgroesse %d.\n", block); + block = 0; + } + + this->min = min; + this->max = max; + this->start = min; + this->space = space; + this->block = block; + this->initialized = false; + this->entry = new T[this->space]; + } + + vector(int min, int max, int block, T init) : vector(min, max, block) { + this->initialized = true; + this->init = init; + for(int i = 0; i < this->space; i += 1){ + this->entry[i] = init; + } + } + + // TODO(fusion): Probably missing some inlined destructor? + + T *at(int index){ + // TODO(fusion): This is probably not the best way to achieve this. + + while(index < this->start){ + int increment = this->block; + if(increment == 0){ + increment = this->space; + } + + T *entry = new T[this->space + increment]; + for(int i = this->min; i <= this->max; i += 1){ + int old_index = i - this->start; + int new_index = old_index + increment; + + // TODO(fusion): Do we actually need to swap elements here? I'm + // assuming some non-trivial structures that would invoke their + // destructors when `this->entry` gets deleted just below. + std::swap(entry[new_index], this->entry[old_index]); + } + + if(this->entry != NULL){ + delete[] this->entry; + } + this->entry = entry; + this->start -= increment; + this->space += increment; + } + + while(index >= (this->start + this->space)){ + int increment = this->block; + if(increment == 0){ + increment = this->space; + } + + T *entry = new[this->space + increment]; + for(int i = this->min; i <= this->max; i += 1){ + int old_index = i - this->start; + int new_index = old_index; + + // TODO(fusion): Same as above. + std::swap(entry[new_index], this->entry[old_index]); + } + + if(this->entry != NULL){ + delete[] this->entry; + } + this->entry = entry; + this->space += increment; + } + + while(index < this->min){ + this->min -= 1; + if(this->initialized){ + this->entry[this->min - this->start] = this->init; + } + } + + while(index > this->max){ + this->max += 1; + if(this->initialized){ + this->entry[this->max - this->start] = this->init; + } + } + + return &this->entry[index - this->start]; + } + + // DATA + // ========================================================================= + int min; + int max; + int start; + int space; + int block; + bool initialized; + T init; + T *entry; +}; + +#endif //TIBIA_VECTOR_HH_ diff --git a/src/priority_queue.hh b/src/priority_queue.hh deleted file mode 100644 index b48353e..0000000 --- a/src/priority_queue.hh +++ /dev/null @@ -1,94 +0,0 @@ -#ifndef TIBIA_PRIORITY_QUEUE_HH_ -#define TIBIA_PRIORITY_QUEUE_HH_ 1 - -#include "main.hh" -#include "vector.hh" - -template -struct priority_queue_entry{ - K Key; - T Data; -}; - -template -struct priority_queue{ - // REGULAR FUNCTIONS - // ========================================================================= - priority_queue(int capacity, int increment){ - Entry = new vector>(1, capacity, increment); - Entries = 0; - } - - // TODO(fusion): Probably missing some inlined destructor? - - void insert(K Key, T *Data){ - this->Entries += 1; - int CurrentIndex = this->Entries; - *this->Entry->at(CurrentIndex) = {Key, *Data}; - while(CurrentIndex > 1){ - int ParentIndex = CurrentIndex / 2; - priority_queue_entry *Current = this->Entry->at(CurrentIndex); - priority_queue_entry *Parent = this->Entry->at(ParentIndex); - if(Parent->Key <= Current->Key) - break; - std::swap(*Current, *Parent); - CurrentIndex = ParentIndex; - } - } - - void deleteMin(void){ - if(this->Entries < 1){ - error("priority_queue::deleteMin: Warteschlange ist leer.\n"); - return; - } - - if(this->Entries > 1){ - int CurrentIndex = 1; - int LastIndex = this->Entries; - std::swap(*this->Entry->at(CurrentIndex), - *this->Entry->at(LastIndex)); - - // TODO(fusion): This may be an oversight but the decompiled version - // checks in the loop below would INCLUDE `LastIndex`, which I assume - // is a bug? The first and last elements were just swapped and what - // was the first element in the queue is now at the end and should be - // considered "removed". - while(1){ - int SmallestIndex = CurrentIndex * 2; - if(SmallestIndex >= LastIndex){ - break; - } - - priority_queue_entry *Smallest = this->Entry->at(SmallestIndex); - if((SmallestIndex + 1) < LastIndex){ - priority_queue_entry *Other = this->Entry->at(SmallestIndex + 1); - if(Other->Key < Smallest->Key){ - Smallest = Other; - SmallestIndex += 1; - } - } - - priority_queue_entry *Current = this->Entry->at(CurrentIndex); - if(Current->Key <= Smallest->Key){ - break; - } - - std::swap(*Current, *Smallest); - CurrentIndex = SmallestIndex; - } - } - - this->Entries -= 1; - } - - // DATA - // ========================================================================= - vector> *Entry; - int Entries; -}; - -// TODO(fusion): We only use this structure two global queues: -// priority_queue ToDoQueue(5000, 1000); -// priority_queue AttackWaveQueue(100, 100); - -#endif //TIBIA_PRIORITY_QUEUE_HH_ diff --git a/src/vector.hh b/src/vector.hh deleted file mode 100644 index 044ffe1..0000000 --- a/src/vector.hh +++ /dev/null @@ -1,123 +0,0 @@ -#ifndef TIBIA_VECTOR_HH_ -#define TIBIA_VECTOR_HH_ 1 - -#include "main.hh" - -// NOTE(fusion): What the actual fuck. This is an ever growing dynamic array -// with each access through `operator()` growing it to make sure the requested -// index is valid, even for negative indices. -template -struct vector{ - // REGULAR FUNCTIONS - // ========================================================================= - vector(int min, int max, int block){ - int space = (max - min) + 1; - if(space < 1){ - error("vector: Ungueltige Feldgroesse %d bis %d.\n", min, max); - space = 1; - } - - if(block < 0){ - error("vector: Ungueltige Blockgroesse %d.\n", block); - block = 0; - } - - this->min = min; - this->max = max; - this->start = min; - this->space = space; - this->block = block; - this->initialized = false; - this->entry = new T[this->space]; - } - - vector(int min, int max, int block, T init) : vector(min, max, block) { - this->initialized = true; - this->init = init; - for(int i = 0; i < this->space; i += 1){ - this->entry[i] = init; - } - } - - // TODO(fusion): Probably missing some inlined destructor? - - T *at(int index){ - // TODO(fusion): This is probably not the best way to achieve this. - - while(index < this->start){ - int increment = this->block; - if(increment == 0){ - increment = this->space; - } - - T *entry = new T[this->space + increment]; - for(int i = this->min; i <= this->max; i += 1){ - int old_index = i - this->start; - int new_index = old_index + increment; - - // TODO(fusion): Do we actually need to swap elements here? I'm - // assuming some non-trivial structures that would invoke their - // destructors when `this->entry` gets deleted just below. - std::swap(entry[new_index], this->entry[old_index]); - } - - if(this->entry != NULL){ - delete[] this->entry; - } - this->entry = entry; - this->start -= increment; - this->space += increment; - } - - while(index >= (this->start + this->space)){ - int increment = this->block; - if(increment == 0){ - increment = this->space; - } - - T *entry = new[this->space + increment]; - for(int i = this->min; i <= this->max; i += 1){ - int old_index = i - this->start; - int new_index = old_index; - - // TODO(fusion): Same as above. - std::swap(entry[new_index], this->entry[old_index]); - } - - if(this->entry != NULL){ - delete[] this->entry; - } - this->entry = entry; - this->space += increment; - } - - while(index < this->min){ - this->min -= 1; - if(this->initialized){ - this->entry[this->min - this->start] = this->init; - } - } - - while(index > this->max){ - this->max += 1; - if(this->initialized){ - this->entry[this->max - this->start] = this->init; - } - } - - return &this->entry[index - this->start]; - } - - // DATA - // ========================================================================= - int min; - int max; - int start; - int space; - int block; - bool initialized; - T init; - T *entry; -}; - -#endif //TIBIA_VECTOR_HH_ -- cgit v1.2.3