Discussion:
fir's inventions/solutions (old)
(too old to reply)
fir
2017-04-02 11:15:56 UTC
Permalink
Raw Message
(sorry for long post i specially write it long for sorta like educational purposes )

i recently mentioned that i will say a few words on it)
i mainly think on two ones, one is allocator needed for
cases when one need dynamically create/destroy instances
that has finite time of living and are creatted/destroyed
in mass amount

(this is not totally 'my' solutions, i just found it for myslelf and use it and find it very pleasant, but suspect some more clever people may use it too)

it goes like this


int AddCharacter(int x,int y, char* name )
{


static int it = 0;

character[it].enabled = 1 ;


// character[it].x = x ;
// character[it].y = y ;

// character[it].name = name ;


int it_used = it;

for(int n=0; n<character_max; n++)
{
it++;

if(it>=character_max)
it-=character_max;

if(!character[it].enabled)
return it_used;
}

ERROR_("Out OF Space in character[]");
}

here 'character' is a name of game character that may get born/summoned and destroyed/killed but it may be other name for each case, in roguelike i use it yet for item[] and fluid[] (where fluid is for example fire and smoke elements also created and destroyed in random ammounts)

it works this way, that it just marks if given array
record is enabled or disabled - so deletions are extremally quick, it is just " character[i].enabled = 0 " and i used
it this way though probably i will wrap it in function

void RemoveCharacter(int it)
{
character[it].enabled = 0 ;
}

this is just more friendly for zontrol+f searching which sometimes may be usefull it also could allow put some
logging lines there if need

allocating is also very quick, it just increases stacklike pointer up until it finds free record,
at start it will also will find free records immediately
but later after this iterator 'wrap up' ('wrap out'?)
when also a lot of records would be taken it could need to skip more in forward until founds free (but this imo
should be in fact rare case, co in fact this allocation is also very fast imo) im happy becouse it is very elegant imo

i use it this shape almost 15 years now and it is sufficient though it also could be extended, especially i see two points

1) in the case of array overflow i just throw an error end exit (this is good for me becous i just like to get proper size experimentally, game in typical run just produces usually some peak amount of instances and it just it is ok to found what size it will suffice)

on the other hand, hovever game users could try to 'hack'
a game scenertios and try to make for example as much more bullets as they can (and as my game has like that say today 'sandbox' nature (i mean being like partially open simulation/ virtual vorld ) i would like to expect that and be ready for
going out of typical peaks - so instead of simple error
i culd reconsider of just calling reallocks up

this bring hovewer two small side problems

i) i would need to turn fully static array into pointer
to heap block, which as far as i remember (from my own test)
is in fact slower (and those items here are basic ram my program works on) - i mean in fact i expect it will be
slower (i expect something in the range of 20% slower (that would need more test i got no time to do ),
i can probably live with that hovever, as i recently dont
much care, but i mention it to show both advantages and downsides

(btw, if i would decided that the code would probably look like

character_max*= 2;

character = (Character*) realloc(character, character_max*sizeof(Character));

something like that)

ii) there is in fact problem of realocking it down, if some user hackers will hack to flod whole game with a lot of objects (summoned monsters, created items, summoned fire flames on large areas etc), they could also obtain a peak that maybe could reach physical limits od given desktop ..

windows itself can handle that making virtual ram and slowing
all down (which is somewhat good, so maybe this is good way, hovewer it could probably return error form reallock at some moment, but if is i would probably feel ok just showing error and closing app here - though maybe more civilised behaviour would be to me to return back to code and code it thios way "wizard sees that his summoning spells dont work for some reason" (the reason would be reallock fail until other part of coded do nor destroy some records) - this is far more gentle hovever needs a bit more work, but it is normal work, so no special reason to sidestep it)

- yet one case is hovever, if hacky user will generate a big peak and resize this pools there is not exactly clear how mechanic to use to resize it down, (and wonder if i need to,
becouse windows could page this ram but construction of this aloocker makes it will be all still touched round around, so it seems it would be better to resize it odwn) I could just use normal time measure and get it down after say 2 minutes
or maybe i just should measure the occupation and resize it
down say twice if occupatiion reaches (<10%) (the last seems
mkost simple, i would need count/monitor the reall occupation
though (which is ismple i just increase counter++ in add() and decrease in remove())

[in fact i could also think a bit whats the conclusion of it]
[the conclusion would be probably to do all, reallock upsize, gentle fallback, yet this down resize mechanics]

this also borders to the second point

2) there would be nice to optimise working of this as
some algorithm needs to scan thru (scan thru) whole
container (esp there is a couple of them, especially
find (like find_character_at(x,y) etc) but also some like just draw_characters() etc).. there maybe could show some elements of square algorithm (container of characters where some of them searches in container of itmes etc) and it would be
possibly good to got this loops small - this could be adressed
immo (and probably is more important to me than point (1)


i would need a bit of consideration how to do that, one way
would be just to use this reallock based downsizing mechanic
(with appropriate 're-collecing' it is memcoping higher locatedrecords to down locations) (and this way it looks that more aggresive downsizing seem more profileble, contradictory the previous attempt when lazy downsizing seem better from other point of view

but im also not sure if i sould not want to try some mechanism
on a static version (which could be some other mechanism maybe simpler.. it could be probably something based on the fact that if i would count the real occupation (say 5000), and current iterator in allocators is say 7000, i may be sure thet i got at least 2000 free records behind - this fact could be used probably to introduce some other pointer character_top
(character_top < character_max) and generate some additional 'wind backs' in a try to not get character_top to much high
(and use this character_top in scanning algorithms)

there is obviously a trouble if little additional cost of winding back in those allocations will be less (and how less) then gain/cost of introducing/not introducing this character_top pointer, but i personally think that it should
be 'profitable')

if so there probably just some line like could be added

if(it > current_occupation*3) it=0; //wind back

(maybe even less than 3 would be better, i dont know)

will try it probably
fir
2017-04-02 12:19:26 UTC
Permalink
Raw Message
Post by fir
if so there probably just some line like could be added
if(it > current_occupation*3) it=0; //wind back
(maybe even less than 3 would be better, i dont know)
will try it probably
if so that would look like this

const int character_max = 10000;

Character character[character_max];

int character_top = 0;

int character_real_occupation = 0;


int AddCharacter(int x,int y, char* name )
{

character_real_occupation++;

static int it = 0;

character[it].enabled = 1 ;

character[it].x = x ;
character[it].y = y ;

character[it].name = name ;


int it_used = it;

for(int n=0; n<character_max; n++)
{
it++;


if(it>character_real_occupation*1.5) //wind back
it = 0;

if(it>=character_max)
it-=character_max;

if(!character[it].enabled)
{
if(character_top < it) character_top = it;

return it_used;
}
}

ERROR_("Out OF Space in character[]");
}

void RemoveCharacter(int it)
{
if(!character[it].enabled) ERROR_("tryin to remove non existing character");

character[it].enabled = 0 ;
character_real_occupation--;

}

that should keep top somewhat lower than full array size
(here top should be keeped at 1.5*peek_occupation)
but there is a problem that when some higher peak will be reached thet top will stay at this level..

this is still some problem
1) i could improve it a bit maybe by checking if the record removed is the top one, (and if so scan down
and lock the new top at the higher momentary top record)
- that should work well if all records will have
short living time, but if it is some mixed approcha then
such topliner could stay long at higher top blocking it)

2) one could do this recollecting (on condition like "character_real_occupation*10 < character_top") but
i) reccolecting is in fact very slow operation (not sure if worth it)
ii) there is a trouble when call it - in fact many of those adds and frees, could be called form those scanning loopps (im not sure as to this hovewer)

for(int i=0; i<character_top; i++)
{
if(...) add_character(); //?
if(...) remove_character(n);//?
}

im not quite sure if to spawning destroing items in such loops (affecting loop counter itself character_top
will grant errorles execution in all cases (quite possibly it may worl errorles in some kind but may bring some index order-related behaviours, but maybe secondary)

but if such add remove will be error-proff im not sure at this moment than if collecting the container under such lup operating on this container would be also as much
errorless - i suspect no as some item above 'i' in the result of collecting my jump belov 'i' and not be executed

on the other side calling this collection from third-side calling point (such point could be found, for example end of frame) brings some global structural dependency which are quite unpleasant

(so i would treat this collecting as not necessary good
idea, maybe unles proven it gives some gain)

probably there are still some other options though
fir
2017-04-02 13:08:00 UTC
Permalink
Raw Message
Post by fir
Post by fir
if so there probably just some line like could be added
if(it > current_occupation*3) it=0; //wind back
(maybe even less than 3 would be better, i dont know)
will try it probably
if so that would look like this
const int character_max = 10000;
Character character[character_max];
int character_top = 0;
int character_real_occupation = 0;
int AddCharacter(int x,int y, char* name )
{
character_real_occupation++;
static int it = 0;
character[it].enabled = 1 ;
character[it].x = x ;
character[it].y = y ;
character[it].name = name ;
int it_used = it;
for(int n=0; n<character_max; n++)
{
it++;
if(it>character_real_occupation*1.5) //wind back
it = 0;
if(it>=character_max)
it-=character_max;
if(!character[it].enabled)
{
if(character_top < it) character_top = it;
return it_used;
}
}
ERROR_("Out OF Space in character[]");
}
void RemoveCharacter(int it)
{
if(!character[it].enabled) ERROR_("tryin to remove non existing character");
character[it].enabled = 0 ;
character_real_occupation--;
}
that should keep top somewhat lower than full array size
(here top should be keeped at 1.5*peek_occupation)
but there is a problem that when some higher peak will be reached thet top will stay at this level..
this is still some problem
1) i could improve it a bit maybe by checking if the record removed is the top one, (and if so scan down
and lock the new top at the higher momentary top record)
- that should work well if all records will have
short living time,
at this case above (which my be quite usefull, as for example in my game fluid[] container (with fire, smoke etc) would be probably most large and most dynamic /short living, the coude would look maybe like
(not tested for errors (and it may have some) and a bit badly written)


int AddCharacter(int x,int y, char* name )
{

character_real_occupation++;

static int it = 0;

character[it].enabled = 1 ;

character[it].x = x ;
character[it].y = y ;

character[it].name = name ;


int it_used = it;

if(character_top < it_used + 1)
character_top = it_used + 1;

for(int n=0; n<character_max; n++)
{
it++;


if(it>character_real_occupation*2) //wind back to keep character_top low
it = 0;

if(it>=character_max)
it-=character_max;

if(!character[it].enabled)
{
return it_used;
}
}

ERROR_("Out OF Space in character[]");
}

void RemoveCharacter(int it)
{
if(!character[it].enabled) ERROR_("tryin to remove non existing character");

character[it].enabled = 0 ;
character_real_occupation--;


if(it==character_top-1)
{
character_top--;

for(;;)
{
if(character_top==0) break;

if(!character[character_top-1].enabled)
character_top--;
else
break;
}


}
}
Post by fir
but if it is some mixed approcha then
such topliner could stay long at higher top blocking it)
2) one could do this recollecting (on condition like "character_real_occupation*10 < character_top") but
i) reccolecting is in fact very slow operation (not sure if worth it)
ii) there is a trouble when call it - in fact many of those adds and frees, could be called form those scanning loopps (im not sure as to this hovewer)
for(int i=0; i<character_top; i++)
{
if(...) add_character(); //?
if(...) remove_character(n);//?
}
im not quite sure if to spawning destroing items in such loops (affecting loop counter itself character_top
will grant errorles execution in all cases (quite possibly it may worl errorles in some kind but may bring some index order-related behaviours, but maybe secondary)
but if such add remove will be error-proff im not sure at this moment than if collecting the container under such lup operating on this container would be also as much
errorless - i suspect no as some item above 'i' in the result of collecting my jump belov 'i' and not be executed
on the other side calling this collection from third-side calling point (such point could be found, for example end of frame) brings some global structural dependency which are quite unpleasant
(so i would treat this collecting as not necessary good
idea, maybe unles proven it gives some gain)
probably there are still some other options though
a***@gmail.com
2017-04-02 13:29:00 UTC
Permalink
Raw Message
fir wrote:
------
Character character[character_max];

int character_top = 0;

int character_real_occupation = 0;



int AddCharacter(int x,int y, char* name )
{


character_real_occupation++;


static int it = 0;

character[it].enabled = 1 ;



character[it].x = x ;


character[it].y = y ;



character[it].name = name ;
-----
It means tha a single character
character[it]
is >= 64+32= 96 bit object at last here...
Is it not too much?
fir
2017-04-02 13:55:15 UTC
Permalink
Raw Message
Post by a***@gmail.com
------
Character character[character_max];
int character_top = 0;
int character_real_occupation = 0;
int AddCharacter(int x,int y, char* name )
{
character_real_occupation++;
static int it = 0;
character[it].enabled = 1 ;
character[it].x = x ;
character[it].y = y ;
character[it].name = name ;
-----
It means tha a single character
character[it]
is >= 64+32= 96 bit object at last here...
Is it not too much?
dont know what you mean here,
characters are game characters and in rogualike can be a
quite big structures described by various coefficients (even few hundreds of bytes each )

ps as to this last code i tested it by casting spells and showing those counters on hud
(in fact one can run it to if want

minddetonator.htw.pl/platform19.zip

to show those hud debug press f8 once and to cast spelss
pres 'z' then hold '1' moving the mouse)

and it seem to work (at least top is less than max, it grows appropraitely) some problem is it gets down but usually only at the end when all fluid vanishes,

im not sure if this is some bug or this is becouse
usually the top blocking fluid is the one that is
created sorta last so it has nearly longest time to live)

it seem roughly work (at least top is less then max) but maybe i should yet try to work to make it drop down a bit quicker,
maybe also i should try to test this collecting code
which would should be simple sorta

for()
{
int f = find_first_free();
int l = find_last_occupied();

if(f>l) break;

mem_copy(f,l);

}

though as i said this memcopy brings maybe some doubts
fir
2017-04-02 14:50:49 UTC
Permalink
Raw Message
Post by fir
Post by a***@gmail.com
------
Character character[character_max];
int character_top = 0;
int character_real_occupation = 0;
int AddCharacter(int x,int y, char* name )
{
character_real_occupation++;
static int it = 0;
character[it].enabled = 1 ;
character[it].x = x ;
character[it].y = y ;
character[it].name = name ;
-----
It means tha a single character
character[it]
is >= 64+32= 96 bit object at last here...
Is it not too much?
dont know what you mean here,
characters are game characters and in rogualike can be a
quite big structures described by various coefficients (even few hundreds of bytes each )
ps as to this last code i tested it by casting spells and showing those counters on hud
(in fact one can run it to if want
minddetonator.htw.pl/platform19.zip
to show those hud debug press f8 once and to cast spelss
pres 'z' then hold '1' moving the mouse)
and it seem to work (at least top is less than max, it grows appropraitely) some problem is it gets down but usually only at the end when all fluid vanishes,
im not sure if this is some bug or this is becouse
usually the top blocking fluid is the one that is
created sorta last so it has nearly longest time to live)
ye thats probably the reason,
found yet that i should add one line


int AddFluid(float x,float y, char* type, int delay, int life )
{

fluid_real_occupation++;

static int it = 0;

if(it>fluid_top) it = fluid_top; //here

fluid[it].enabled = 1 ;


becouse without it even when all vanished iterator was setted in high position blocking unecesssary (unnnnecesary, unnnnecesssarrry, sorry, this first n fills like my weak heart)

this solution with _top is now a bit more slow adding and removing (and a bit more complex) but probably it is worth it.. maybe i will check some day
Post by fir
it seem roughly work (at least top is less then max) but maybe i should yet try to work to make it drop down a bit quicker,
maybe also i should try to test this collecting code
which would should be simple sorta
for()
{
int f = find_first_free();
int l = find_last_occupied();
if(f>l) break;
mem_copy(f,l);
}
though as i said this memcopy brings maybe some doubts
Loading...