Am Samstag, 28. Februar 2009 20:42:00 schrieb Dennis Schridde: > I played a bit with implementing a better memory pool for effects and this > is what came out. Benefits: * Unlimited number of effects possible. * Faster Not (yet) benchmarked, but logic dictates that iterating over MAX_EFFECTS is slower than iterating over just the number of active effects.
> Sadly it seems to have a bug though. (Segfault) > I reliably can reproduce it by cheating an archangle and just letting it > fire. Sadly does WZ neither output a crash dump, nor is GDB able to capture > a backtrace, and it does not crash in Valgrind... > Maybe someone finds an issue by review. Bug was actually in the debug printf. Fixed thanks to a backtrace I got from Gerard. Update attached. --DevU
diff --git a/src/effects.c b/src/effects.c
index 49183f7..5c5e2ab 100644
--- a/src/effects.c
+++ b/src/effects.c
@@ -71,8 +71,6 @@
#include "game.h"
-#define MAX_EFFECTS 2500
-
#define GRAVITON_GRAVITY ((float)-800)
#define EFFECT_X_FLIP 0x1
#define EFFECT_Y_FLIP 0x2
@@ -165,19 +163,38 @@
#define MAX_SHOCKWAVE_SIZE 500
+#define EFFECT_CHUNKS_SIZE 10000
+
+typedef struct _EffectChunk EffectChunk;
+
+struct _EffectChunk {
+ EFFECT effects[EFFECT_CHUNKS_SIZE];
+ EffectChunk *next;
+};
+
+struct {
+ EffectChunk *first, *last;
+} chunkList = {
+ NULL, NULL
+};
+
/* Our list of all game world effects */
-static EFFECT asEffectsList[MAX_EFFECTS];
-static EFFECT_STATUS effectStatus[MAX_EFFECTS];
+// static size_t numEffects = 10000;
+// static EFFECT *effects = NULL;
+struct {
+ size_t num;
+ EFFECT *first, *last;
+} activeList = {
+ 0, NULL, NULL
+}, inactiveList = {
+ 0, NULL, NULL
+};
+
/* Tick counts for updates on a particular interval */
static UDWORD lastUpdateDroids[EFFECT_DROID_DIVISION];
static UDWORD lastUpdateStructures[EFFECT_STRUCTURE_DIVISION];
-static UDWORD freeEffect; /* Current next slot to use - cyclic */
-static UDWORD numEffects;
-static UDWORD activeEffects;
-static UDWORD missCount;
-static UDWORD skipped,skippedEffects,letThrough;
static UDWORD auxVar; // dirty filthy hack - don't look for what this does.... //FIXME
static UDWORD auxVarSec; // dirty filthy hack - don't look for what this does.... //FIXME
static UDWORD specifiedSize;
@@ -233,6 +250,131 @@ static void effectDroidUpdates(void);
static UDWORD effectGetNumFrames(EFFECT *psEffect);
+static void initEffectPool(EFFECT *first, EFFECT *last)
+{
+ for (EFFECT *it = first; it < last; it++)
+ {
+ // We do not need a double-linked-list for inactiveeffects, since we always pick from the front:
+ it->prev = NULL;
+ it->next = it+1;
+ }
+
+ last->prev = NULL;
+ last->next = NULL;
+}
+
+
+static EFFECT *Effect_malloc(void)
+{
+ printf("** Allocating effect No. %zd\n", activeList.num);
+
+ EFFECT *instance = inactiveList.first;
+
+ inactiveList.first = instance->next; // Remove from inactiveList (singly linked)
+ instance->next = NULL; // We are the last in activeList now
+
+ /* Append to activeList */
+ instance->prev = activeList.last;
+
+ if (instance->prev == NULL) {
+ activeList.first = instance; // activeList was empty, so fill it
+ }
+ else {
+ activeList.last->next = instance;
+ }
+
+ activeList.last = instance;
+
+ /* Adjust counts */
+ activeList.num++;
+ inactiveList.num--;
+
+ /* Ensure the next search will have something to feed its hunger with */
+ if (inactiveList.first == NULL)
+ {
+ printf("** Requiring more than %zd effects\n", activeList.num);
+
+ EffectChunk *chunk = malloc(sizeof(EffectChunk));
+ chunk->next = NULL;
+
+ chunkList.last->next = chunk;
+
+ inactiveList.num = EFFECT_CHUNKS_SIZE;
+ inactiveList.first = &chunk->effects[0];
+ inactiveList.last = &chunk->effects[EFFECT_CHUNKS_SIZE-1];
+
+ initEffectPool(inactiveList.first, inactiveList.last);
+ }
+
+ return instance;
+}
+
+
+static void Effect_free(void *self)
+{
+ printf("** Freeing an effect %zd\n", inactiveList.num);
+
+ EFFECT *instance = self;
+
+ /* Remove from activeList and fixup endings if necessary */
+ if (instance->prev != NULL) {
+ instance->prev->next = instance->next;
+ }
+ else {
+ activeList.first = instance->next; // We were the first in activeList
+ }
+ if (instance->next != NULL) {
+ instance->next->prev = instance->prev;
+ }
+ else {
+ activeList.last = instance->prev; // We were the last in activeList
+ }
+
+ /* Append to inactiveList */
+ instance->prev = NULL; // Singly linked
+ instance->next = NULL; // Last element
+
+ // inactiveList is never empty (guaranteed in mallocImpl)
+ inactiveList.last->next = instance;
+ inactiveList.last = instance;
+
+ /* Adjust counts */
+ inactiveList.num++;
+ activeList.num--;
+}
+
+
+void initEffectsSystem(void)
+{
+ EffectChunk *chunk;
+ for (chunk = chunkList.first; chunk != NULL;)
+ {
+ EffectChunk *chunkNext = chunk->next;
+ free(chunk);
+ chunk = chunkNext;
+ }
+
+ chunk = malloc(sizeof(EffectChunk));
+ chunk->next = NULL;
+
+ chunkList.first = chunk;
+ chunkList.last = chunk;
+
+ // activeList is empty at start
+ activeList.num = 0;
+ activeList.first = NULL;
+ activeList.last = NULL;
+
+ // inactiveList contains all elements
+ inactiveList.num = EFFECT_CHUNKS_SIZE;
+ inactiveList.first = &chunk->effects[0];
+ inactiveList.last = &chunk->effects[EFFECT_CHUNKS_SIZE-1];
+
+ // Initialise free-effects pool
+ initEffectPool(inactiveList.first, inactiveList.last);
+}
+
+
static void positionEffect(const EFFECT *psEffect)
{
int rx, rz;
@@ -272,76 +414,8 @@ static void killEffect(EFFECT *e)
psTile->tileInfoBits &= ~BITS_ON_FIRE; // clear fire bit
}
}
- effectStatus[e-asEffectsList] = ES_INACTIVE;
- e->control = (UBYTE) 0;
-}
-
-static BOOL essentialEffect(EFFECT_GROUP group, EFFECT_TYPE type)
-{
- switch(group)
- {
- case EFFECT_FIRE:
- case EFFECT_WAYPOINT:
- case EFFECT_DESTRUCTION:
- case EFFECT_SAT_LASER:
- case EFFECT_STRUCTURE:
- return(true);
- break;
- case EFFECT_EXPLOSION:
- if(type == EXPLOSION_TYPE_LAND_LIGHT)
- {
- return(true);
- }
- default:
- return(false);
- }
-}
-
-static BOOL utterlyReject( EFFECT_GROUP group )
-{
- switch(group)
- {
- case EFFECT_BLOOD:
- case EFFECT_DUST_BALL:
- case EFFECT_CONSTRUCTION:
- return(true);
- default:
- return(false);
- }
-}
-
-/** Simply sets the free pointer to the start - actually this isn't necessary
- as it will work just fine anyway. This WOULD be necessary were we to change
- the system so that it seeks FREE slots rather than the oldest one. This is because
- different effects last for different times and the oldest effect may have
- just got going (if it was a long effect).
-*/
-void initEffectsSystem( void )
-{
- UDWORD i;
- EFFECT *psEffect;
-
- /* Set position to first */
- freeEffect = 0;
-
- /* None are active */
- numEffects = 0;
-
- activeEffects = 0;
- missCount=0;
-
- skipped = letThrough = 0;
-
- for(i=0; i<MAX_EFFECTS; i++)
- {
- /* Get a pointer - just cos our macro requires it, speeds not an issue here */
- psEffect = &asEffectsList[i];
- /* Clear all the control bits */
- psEffect->control = (UBYTE)0;
- /* All effects are initially inactive */
- effectStatus[i] = ES_INACTIVE;
- }
+ Effect_free(e);
}
void effectSetLandLightSpec(LAND_LIGHT_SPEC spec)
@@ -392,96 +466,21 @@ void addMultiEffect(const Vector3i *basePos, Vector3i *scatter, EFFECT_GROUP gro
}
}
-UDWORD getNumActiveEffects( void )
-{
- return(activeEffects);
-}
-
-UDWORD getMissCount( void )
-{
- return(missCount);
-}
-
-UDWORD getNumSkippedEffects(void)
-{
- return(skippedEffects);
-}
-
-UDWORD getNumEvenEffects(void)
-{
- return(letThrough);
-}
-
void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool specified, iIMDShape *imd, bool lit)
{
- static unsigned int aeCalls = 0;
- UDWORD essentialCount;
- UDWORD i;
- EFFECT *psEffect = NULL;
-
- aeCalls++;
+ EFFECT *psEffect = NULL;
if(gamePaused())
{
return;
}
- /* Quick optimsation to reject every second non-essential effect if it's off grid */
- if(clipXY(pos->x, pos->z) == false)
- {
- /* If effect is essentail - then let it through */
- if(!essentialEffect(group,type) )
- {
- bool bSmoke = false;
-
- /* Some we can get rid of right away */
- if ( utterlyReject( group ) )
- {
- skipped++;
- return;
- }
- /* Smoke gets culled more than most off grid effects */
- if(group == EFFECT_SMOKE)
- {
- bSmoke = true;
- }
+ psEffect = Effect_malloc();
- /* Others intermittently (50/50 for most and 25/100 for smoke */
- if(bSmoke ? (aeCalls & 0x03) : (aeCalls & 0x01) )
- {
- /* Do one */
- skipped++;
- return;
- }
- letThrough++;
- }
- }
+ printf("*** Type: %d, Group: %d\n", type, group);
-
- for (i = freeEffect, essentialCount = 0; (asEffectsList[i].control & EFFECT_ESSENTIAL)
- && essentialCount < MAX_EFFECTS; i++)
- {
- /* Check for wrap around */
- if (i >= (MAX_EFFECTS-1))
- {
- /* Go back to the first one */
- i = 0;
- }
- essentialCount++;
- missCount++;
- }
-
- /* Check the list isn't just full of essential effects */
- if (essentialCount >= MAX_EFFECTS)
- {
- /* All of the effects are essential!?!? */
- return;
- }
-
- freeEffect = i;
-
- psEffect = &asEffectsList[freeEffect];
+ psEffect->control = 0;
/* Store away it's position - into FRACTS */
psEffect->position.x = pos->x;
@@ -499,7 +498,6 @@ void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool s
{
psEffect->frameNumber = lit;
}
-
else
{
/* Starts off on frame zero */
@@ -562,9 +560,6 @@ void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool s
break;
}
- /* Make the effect active */
- effectStatus[freeEffect] = ES_ACTIVE;
-
/* As of yet, it hasn't bounced (or whatever)... */
if(type!=EXPLOSION_TYPE_LAND_LIGHT)
{
@@ -572,43 +567,28 @@ void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool s
}
ASSERT(psEffect->imd != NULL || group == EFFECT_DESTRUCTION || group == EFFECT_FIRE || group == EFFECT_SAT_LASER, "null effect imd");
-
- /* No more slots available? */
- if(freeEffect++ >= (MAX_EFFECTS-1))
- {
- /* Go back to the first one */
- freeEffect = 0;
- }
}
/* Calls all the update functions for each different currently active effect */
void processEffects(void)
{
- unsigned int i;
-
- /* Establish how long the last game frame took */
- missCount = 0;
-
- /* Reset counter */
- numEffects = 0;
-
+ printf("STARTING FRAME: %d\n", frameGetFrameNumber());
/* Traverse the list */
- for (i = 0; i < MAX_EFFECTS; i++)
+ for (EFFECT *it = activeList.first; it != NULL;)
{
- /* Don't bother unless it's active */
- if(effectStatus[i] == ES_ACTIVE)
+ EFFECT *itNext = it->next; // If updateEffect deletes something, we would be screwed...
+
+ updateEffect(it);
+
+ /* Is it on the grid */
+ if (clipXY(it->position.x, it->position.z))
{
- updateEffect(&asEffectsList[i]);
- /* One more is active */
- numEffects++;
- /* Is it on the grid */
- if (clipXY(asEffectsList[i].position.x, asEffectsList[i].position.z))
- {
- /* Add it to the bucket */
- bucketAddTypeToList(RENDER_EFFECT,&asEffectsList[i]);
- }
+ /* Add it to the bucket */
+ bucketAddTypeToList(RENDER_EFFECT, it);
}
+
+ it = itNext;
}
/* Add any droid effects */
@@ -616,15 +596,14 @@ void processEffects(void)
/* Add any structure effects */
effectStructureUpdates();
-
- activeEffects = numEffects;
- skippedEffects = skipped;
}
/* The general update function for all effects - calls a specific one for each */
static void updateEffect(EFFECT *psEffect)
{
+ printf("S: %p E: %p G: %d T: %d NOW: %d LAST: %d DEL: %d FRAME: %d NFRA: %d\n", activeList.first, psEffect, psEffect->group, psEffect->type, gameTime, psEffect->lastFrame, psEffect->frameDelay, psEffect->frameNumber, psEffect->imd ? effectGetNumFrames(psEffect) : -1);
+
/* What type of effect are we dealing with? */
switch(psEffect->group)
{
@@ -2552,8 +2531,6 @@ static const char FXData_file_identifier[] = "FXData";
/** This will save out the effects data */
bool writeFXData(const char* fileName)
{
- unsigned int count, i;
-
if (!tagOpenWrite(FXData_tag_definition, fileName))
{
ASSERT(false, "writeFXData: error while opening file (%s)", fileName);
@@ -2562,45 +2539,30 @@ bool writeFXData(const char* fileName)
tagWriteString(0x01, FXData_file_identifier);
- // Count all the active EFFECTs
- for (i = 0, count = 0; i < MAX_EFFECTS; ++i)
- {
- if(effectStatus[i] == ES_ACTIVE)
- {
- ++count;
- }
- }
-
// Enter effects group and dump all EFFECTs
- tagWriteEnter(0x02, count);
- for (i = 0; i < MAX_EFFECTS; ++i)
- {
- const EFFECT* curEffect = &asEffectsList[i];
-
- // Don't save inactive effects
- if (effectStatus[i] != ES_ACTIVE)
- continue;
-
- tagWrite(0x01, curEffect->control);
- tagWrite(0x02, curEffect->group);
- tagWrite(0x03, curEffect->type);
- tagWrite(0x04, curEffect->frameNumber);
- tagWrite(0x05, curEffect->size);
- tagWrite(0x06, curEffect->baseScale);
- tagWrite(0x07, curEffect->specific);
-
- tagWritefv (0x08, 3, &curEffect->position.x);
- tagWritefv (0x09, 3, &curEffect->velocity.x);
- tagWrites32v (0x0A, 3, &curEffect->rotation.x);
- tagWrites32v (0x0B, 3, &curEffect->spin.x);
-
- tagWrite(0x0C, curEffect->birthTime);
- tagWrite(0x0D, curEffect->lastFrame);
- tagWrite(0x0E, curEffect->frameDelay);
- tagWrite(0x0F, curEffect->lifeSpan);
- tagWrite(0x10, curEffect->radius);
-
- tagWriteString(0x11, resGetNamefromData("IMD", curEffect->imd));
+ tagWriteEnter(0x02, activeList.num);
+ for (EFFECT *it = activeList.first; it != NULL; it = it->next)
+ {
+ tagWrite(0x01, it->control);
+ tagWrite(0x02, it->group);
+ tagWrite(0x03, it->type);
+ tagWrite(0x04, it->frameNumber);
+ tagWrite(0x05, it->size);
+ tagWrite(0x06, it->baseScale);
+ tagWrite(0x07, it->specific);
+
+ tagWritefv (0x08, 3, &it->position.x);
+ tagWritefv (0x09, 3, &it->velocity.x);
+ tagWrites32v (0x0A, 3, &it->rotation.x);
+ tagWrites32v (0x0B, 3, &it->spin.x);
+
+ tagWrite(0x0C, it->birthTime);
+ tagWrite(0x0D, it->lastFrame);
+ tagWrite(0x0E, it->frameDelay);
+ tagWrite(0x0F, it->lifeSpan);
+ tagWrite(0x10, it->radius);
+
+ tagWriteString(0x11, resGetNamefromData("IMD", it->imd));
// Move on to reading the next effect group
tagWriteNext();
@@ -2642,11 +2604,9 @@ bool readFXData(const char* fileName)
count = tagReadEnter(0x02);
for(i = 0; i < count; ++i)
{
- EFFECT* curEffect = &asEffectsList[i];
+ EFFECT* curEffect = Effect_malloc();
char imd_name[PATH_MAX];
- ASSERT(i < MAX_EFFECTS, "readFXData: more effects in this file than our array can contain");
-
curEffect->control = tagRead(0x01);
curEffect->group = tagRead(0x02);
curEffect->type = tagRead(0x03);
@@ -2676,17 +2636,12 @@ bool readFXData(const char* fileName)
curEffect->imd = NULL;
}
- effectStatus[i] = ES_ACTIVE;
-
// Move on to reading the next effect group
tagReadNext();
}
// Leave the effects group again...
tagReadLeave(0x02);
- /* Ensure free effects kept up to date */
- freeEffect = i;
-
// Close the file
tagClose();
diff --git a/src/effects.h b/src/effects.h
index b0ddb6e..e678775 100644
--- a/src/effects.h
+++ b/src/effects.h
@@ -113,14 +113,6 @@ typedef enum
} EFFECT_TYPE;
-/* Is the slot currently being used and is it active? */
-typedef enum
-{
- ES_INACTIVE,
- ES_ACTIVE
-} EFFECT_STATUS;
-
-
typedef enum
{
LL_MIDDLE,
@@ -149,6 +141,7 @@ struct _effect_def
uint16_t lifeSpan; // what is it's life expectancy?
uint16_t radius; // Used for area effects
iIMDShape *imd; // pointer to the imd the effect uses.
+ EFFECT *prev, *next; // Previous and next element in linked list
};
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Warzone-dev mailing list [email protected] https://mail.gna.org/listinfo/warzone-dev
