c++ and some other alnguages has some containers but
afair they not have the one that is really needed - container that
reduces square complexity when you write a program thet uses
colisions in space (and i realized that today)

say you got milion obiects in space (2d or 3d or more)
seachiung for potential collisions by counting distances kills
the cpu to death - but if you would have a good container
you just could search in R vicinity..

so the quest is - such container need to be done

(i once was writing some code based on sorting, right now i dont quite remember the results, it worked as far as i remember but the additional
complexity (mess) it added to my code i was not happy with.. but the
way of adding wel known container with clean interface could help

niedziela, 16 lipca 2023 o 17:35:30 UTC+2 fir napisał(a):
> c++ and some other alnguages has some containers but
> afair they not have the one that is really needed - container that
> reduces square complexity when you write a program thet uses
> colisions in space (and i realized that today)
>
> say you got milion obiects in space (2d or 3d or more)
> seachiung for potential collisions by counting distances kills
> the cpu to death - but if you would have a good container
> you just could search in R vicinity..
>
> so the quest is - such container need to be done
>
> (i once was writing some code based on sorting, right now i dont quite remember the results, it worked as far as i remember but the additional
> complexity (mess) it added to my code i was not happy with.. but the
> way of adding wel known container with clean interface could help

if that group would be serious (and users not so old and tired i guess) some
could state some kind of contest here to write such container and compare results

as i recently was writing about c dictionaty and i guess this might be the way i probbaly would need to test it (back tehn i alsoyested soem code based on sorting coordinates, though for soem reason i got not mych pleasant memory on thsi as it maked code more rigid and i didnt seen teh results cleen

wtorek, 8 sierpnia 2023 o 00:56:12 UTC+2 fir napisał(a):
> as i recently was writing about c dictionaty and i guess this might be the way i probbaly would need to test it (back tehn i alsoyested soem code based on sorting coordinates, though for soem reason i got not mych pleasant memory on thsi as it maked code more rigid and i didnt seen teh results cleen

ok i wrote this, hopwewer all this containers i written recently are not tested forbugs etc

seem to work

// space directory

struct Spaced_Entry { int id; };
struct Spaced_KeyEntry { Spaced_Entry* tab; int tablen; };
Spaced_KeyEntry* spaced = NULL; int spaced_keys = 0;

int spaced_cells_x = 10; int spaced_cells_y = 10; //+ 2 for outerspace (10x10 inner, 12x12 all)
float spaced_low_x = -10000; float spaced_high_x = 10000;
float spaced_low_y = -10000; float spaced_high_y = 10000;
int spaced_initialised = 0;

void InitialiseSpaceDirectory(float cells_x, float low_x, float high_x, float cells_y, float low_y,float high_y)
{ if(spaced_initialised) return; spaced_initialised = 1;
spaced_cells_x = cells_x; spaced_low_x = low_x; spaced_high_x = high_x;
spaced_cells_y = cells_y; spaced_low_y = low_y; spaced_high_y = high_y;
spaced_keys = (spaced_cells_x+2)*(spaced_cells_y+2);
spaced = (Spaced_KeyEntry*) realloc(spaced, spaced_keys*sizeof(Spaced_KeyEntry) );
for(int k=0; k<spaced_keys;k++) spaced[k] = {NULL, 0};
}

int AssignKeyForSpacePoint(float x, float y)
{ int nx = (x-spaced_low_x)/(spaced_high_x-spaced_low_x)*spaced_cells_x; if(nx<0) nx = -1; if(nx>=spaced_cells_x) nx = spaced_cells_x; /
int ny = (y-spaced_low_y)/(spaced_high_y-spaced_low_y)*spaced_cells_y; if(ny<0) ny = -1; if(ny>=spaced_cells_y) ny = spaced_cells_y;
int key = (1+nx) + (spaced_cells_x+2)*(1+ny); return key;
}

int key_y(int key){ return key/(spaced_cells_x+2);}
int key_x(int key){ return key - key_y(key)*(spaced_cells_x+2);}

void SpaceDirectory_AddPoint( float x, float y, int id)
{ int key = AssignKeyForSpacePoint( x, y);
spaced[key].tab = (Spaced_Entry*) realloc(spaced[key].tab, ++spaced[key].tablen * sizeof(Spaced_Entry));
spaced[key].tab[spaced[key].tablen-1] = {id};
}

void PrintOutSpaceDirectory()
{ for(int key=0; key<spaced_keys; key++)
{
printf("\n space directory for key %d (%d, %d) : ",key, key_y(key), key_x(key));
for(int i=0; i<spaced[key].tablen; i++) printf("id %d ",spaced[key].tab[i].id);
}
}

//////////// agents
struct Agent {int enabled; float x,y,r;}; Agent* agent = NULL; int agent_size = 0; int agent_last_reallockd = 0;
void UpsizeAgentArray() { if(++agent_size > agent_last_reallockd) agent = (Agent*) realloc(agent, (agent_last_reallockd = 2*agent_size+100)*sizeof(Agent) );}
void AddAgent(float x,float y, float r) { UpsizeAgentArray(); agent[agent_size-1] = {1,x,y,r};}
void AddAgents(int n) { for(int i=0; i<n;i++) AddAgent(rand2(-100,50),rand2(-100,70),10);}

//////// test
void TestSpaceDirectory()
{ InitialiseSpaceDirectory(5,-100,100,5,-100,100); AddAgents(100);
for(int i=0; i<agent_size; i++) SpaceDirectory_AddPoint(agent[i].x, agent[i].y, i );
PrintOutSpaceDirectory();

}

result

space directory for key 0 (0, 0) :
space directory for key 1 (0, 1) :
space directory for key 2 (0, 2) :
space directory for key 3 (0, 3) :
space directory for key 4 (0, 4) :
space directory for key 5 (0, 5) :
space directory for key 6 (0, 6) :
space directory for key 7 (1, 0) :
space directory for key 8 (1, 1) : id 2 id 9 id 18 id 27 id 30 id 54 id 84 id 85 id 89 id 94 id 97
space directory for key 9 (1, 2) : id 1 id 3 id 6 id 24 id 28 id 51
space directory for key 10 (1, 3) : id 49
space directory for key 11 (1, 4) : id 21 id 26 id 43 id 45 id 46 id 66 id 82 id 96
space directory for key 12 (1, 5) :
space directory for key 13 (1, 6) :
space directory for key 14 (2, 0) :
space directory for key 15 (2, 1) : id 7 id 25 id 50 id 60 id 63 id 69 id 72 id 91 id 93 id 99
space directory for key 16 (2, 2) : id 0 id 5 id 16 id 55 id 56 id 70 id 90
space directory for key 17 (2, 3) : id 10 id 14 id 47 id 48 id 71 id 73 id 83
space directory for key 18 (2, 4) : id 22 id 78
space directory for key 19 (2, 5) :
space directory for key 20 (2, 6) :
space directory for key 21 (3, 0) :
space directory for key 22 (3, 1) : id 4 id 8 id 23 id 44 id 58 id 74 id 75 id 81 id 92
space directory for key 23 (3, 2) : id 19 id 32 id 39 id 42 id 61
space directory for key 24 (3, 3) : id 35 id 37 id 57 id 67
space directory for key 25 (3, 4) : id 34 id 64 id 98
space directory for key 26 (3, 5) :
space directory for key 27 (3, 6) :
space directory for key 28 (4, 0) :
space directory for key 29 (4, 1) : id 11 id 12 id 31 id 33 id 41 id 62 id 80 id 87
space directory for key 30 (4, 2) : id 53 id 59 id 76
space directory for key 31 (4, 3) : id 20 id 36 id 40 id 52 id 88 id 95
space directory for key 32 (4, 4) : id 13 id 15 id 17 id 38 id 68 id 79 id 86
space directory for key 33 (4, 5) :
space directory for key 34 (4, 6) :
space directory for key 35 (5, 0) :
space directory for key 36 (5, 1) : id 29 id 77
space directory for key 37 (5, 2) :
space directory for key 38 (5, 3) : id 65
space directory for key 39 (5, 4) :
space directory for key 40 (5, 5) :
space directory for key 41 (5, 6) :
space directory for key 42 (6, 0) :
space directory for key 43 (6, 1) :
space directory for key 44 (6, 2) :
space directory for key 45 (6, 3) :
space directory for key 46 (6, 4) :
space directory for key 47 (6, 5) :
space directory for key 48 (6, 6) :

i tested the code for collisions of 1000 and 10k objects (counting mutual colisions )
and the results are

1000 collisions (raw) 2 time 35.2 ms
1000 collisions (space dir 10 10) 2 time 3.4 ms

1000 collisions (raw) 2 time 30.9 ms
1000 collisions (space dir 100 100) 2 time 0.2 ms

1000 collisions (raw) 0 time 30.9 ms
1000 collisions (space dir 200 200) 0 time 0.2 ms

10000 collisions (raw) 348 time 3151.0 ms
10000 collisions (space dir 10 10) 348 time 288.2 ms

10000 collisions (raw) 366 time 3162.9 ms
10000 collisions (space dir 100 100) 366 time 7.8 ms

10000 collisions (raw) 368 time 3156.9 ms
10000 collisions (space dir 200 200) 368 time 3.6 ms

it seem to be a great succes of this method only if i got no bug somewhere

full code below

// space directory

struct Spaced_Entry { int id; };
struct Spaced_KeyEntry { Spaced_Entry* tab; int tablen; int allocked; };
Spaced_KeyEntry* spaced = NULL; int spaced_keys = 0;

int spaced_cells_x = 10;
int spaced_cells_y = 10; //+ 2 for outerspace (10x10 inner, 12x12 all)
float spaced_low_x = -10000; float spaced_high_x = 10000;
float spaced_low_y = -10000; float spaced_high_y = 10000;
int spaced_initialised = 0;

void InitialiseSpaceDirectory(float cells_x, float low_x, float high_x, float cells_y, float low_y,float high_y)
{ // if(spaced_initialised) return; spaced_initialised = 1;
spaced_cells_x = cells_x; spaced_low_x = low_x; spaced_high_x = high_x;
spaced_cells_y = cells_y; spaced_low_y = low_y; spaced_high_y = high_y;
spaced_keys = (spaced_cells_x+2)*(spaced_cells_y+2);
spaced = (Spaced_KeyEntry*) realloc(spaced, spaced_keys*sizeof(Spaced_KeyEntry) );
for(int k=0; k<spaced_keys;k++) spaced[k] = {NULL, 0, 0};
}

int AssignKeyForSpacePoint(float x, float y)
{ int nx = (x-spaced_low_x)/(spaced_high_x-spaced_low_x)*spaced_cells_x; if(nx<0) nx = -1; if(nx>=spaced_cells_x) nx = spaced_cells_x;
int ny = (y-spaced_low_y)/(spaced_high_y-spaced_low_y)*spaced_cells_y; if(ny<0) ny = -1; if(ny>=spaced_cells_y) ny = spaced_cells_y;
int key = (1+nx) + (spaced_cells_x+2)*(1+ny); return key;
}

int key_y(int key){ return key/(spaced_cells_x+2);}
int key_x(int key){ return key - key_y(key)*(spaced_cells_x+2);}

void SpaceDirectory_AddPoint( float x, float y, int id)
{ int key = AssignKeyForSpacePoint( x, y);
if(++spaced[key].tablen>spaced[key].allocked)
spaced[key].tab = (Spaced_Entry*) realloc(spaced[key].tab, (spaced[key].allocked = spaced[key].tablen*2+30) * sizeof(Spaced_Entry));
spaced[key].tab[spaced[key].tablen-1] = {id};
}

void SpaceDirectoryEntries_Free()
{ for(int key=0; key<spaced_keys; key++)
{
for(int i=0; i<spaced[key].tablen; i++) spaced[key].tab = (Spaced_Entry*) realloc(spaced[key].tab,0);
spaced[key].tablen = 0;
spaced[key].allocked = 0;

}

}

void PrintOutSpaceDirectory()
{ for(int key=0; key<spaced_keys; key++)
{
printf("\n space directory for key %d (%d, %d) : ",key, key_y(key), key_x(key));
for(int i=0; i<spaced[key].tablen; i++) printf("id %d ",spaced[key].tab[i].id);
}
}

//////////// agents
struct Agent {int enabled; float x,y,r;}; Agent* agent = NULL; int agent_size = 0; int agent_last_reallockd = 0;
void UpsizeAgentArray() { if(++agent_size > agent_last_reallockd) agent = (Agent*) realloc(agent, (agent_last_reallockd = 2*agent_size+100)*sizeof(Agent) );}
void AddAgent(float x,float y, float r) { UpsizeAgentArray(); agent[agent_size-1] = {1,x,y,r};}
void AddAgents(int n, float low_x, float high_x, float low_y, float high_y ) { for(int i=0; i<n;i++) AddAgent(rand2(low_x,high_x),rand2(low_y,high_y),10);}
void DeleteAgents( ) { agent = (Agent*) realloc(agent, 0); agent_size = 0; agent_last_reallockd = 0; }

//////////////

inline int CheckCOllision(int i, int j)
{ if(i==j) return 0;

float dx = agent[j].x - agent[i].x;
float dy = agent[j].y - agent[i].y;
float dist = sqrt(dx*dx+dy*dy);
if(dist<agent[i].r+agent[j].r) return 1; else return 0;
}

void TestCollisionsRaw()
{

int collisions = 0;
TakeDeltaTimeNS(1);

for(int j=0; j<agent_size; j++)
{
// if(!agent[j].enabled) continue;
for(int i=0; i<agent_size; i++)
{
// if(!agent[i].enabled) continue;
if(CheckCOllision(i,j)) collisions++;

}
}
float t = TakeDeltaTimeNS(1);
printf("\n %d collisions (raw) %d time %.1f ms ", agent_size, collisions,t/1000/1000);

}

int CheckForCollisionInCell(int id, int key_x, int key_y)
{ if(key_x<0) return 0; if(key_y<0) return 0;
if(key_x >= spaced_cells_x + 2) return 0;
if(key_y >= spaced_cells_y + 2) return 0;

int collisions = 0;
int key = key_y*(spaced_cells_x+2)+key_x;

for(int i=0; i<spaced[key].tablen; i++)
if(CheckCOllision(id,spaced[key].tab[i].id)) collisions++;

return collisions;

}

int CheckForCollision_BySpaceDirectory(int id)
{ int key = AssignKeyForSpacePoint(agent[id].x, agent[id].y);
int kx = key_x(key); int ky = key_y(key);

int collisions = 0;

collisions+=CheckForCollisionInCell(id, kx-1, ky-1);
collisions+=CheckForCollisionInCell(id, kx-1, ky);
collisions+=CheckForCollisionInCell(id, kx-1, ky+1);

collisions+=CheckForCollisionInCell(id, kx+0, ky-1);
collisions+=CheckForCollisionInCell(id, kx+0, ky);
collisions+=CheckForCollisionInCell(id, kx+0, ky+1);

collisions+=CheckForCollisionInCell(id, kx+1, ky-1);
collisions+=CheckForCollisionInCell(id, kx+1, ky);
collisions+=CheckForCollisionInCell(id, kx+1, ky+1);

return collisions;

}

void TestCollisions_BySpaceDirectory()
{ TakeDeltaTimeNS(1);

int collisions =0;

for(int i=0; i<agent_size;i++)
collisions+= CheckForCollision_BySpaceDirectory(i);

float t = TakeDeltaTimeNS(1);
printf("\n %d collisions (space dir %d %d) %d time %.1f ms ", agent_size, spaced_cells_x, spaced_cells_y, collisions,t/1000/1000);

}

void AddAgentsToSpaceDirectory()
{ for(int i=0; i<agent_size; i++)
SpaceDirectory_AddPoint(agent[i].x, agent[i].y, i );

}

void TestCollisions(int N, int cells_x, int cells_y)
{ printf("\n");
AddAgents(N, -10000,10000,-10000,10000);
TestCollisionsRaw();
InitialiseSpaceDirectory(cells_x,-10000,10000,cells_y,-10000,10000); AddAgentsToSpaceDirectory();
TestCollisions_BySpaceDirectory(); SpaceDirectoryEntries_Free();
DeleteAgents();

}

//////// test
void TestSpaceDirectory()
{

TestCollisions(1000, 10, 10);
TestCollisions(1000, 100,100);
TestCollisions(1000, 200,200);

TestCollisions(10000, 10, 10);
TestCollisions(10000, 100,100);
TestCollisions(10000, 200,200);

}

On Tuesday, 8 August 2023 at 06:57:47 UTC+3, fir wrote:
> i tested the code for collisions of 1000 and 10k objects (counting mutual colisions )
> and the results are
>
>
> 1000 collisions (raw) 2 time 35.2 ms
> 1000 collisions (space dir 10 10) 2 time 3.4 ms
>
> 1000 collisions (raw) 2 time 30.9 ms
> 1000 collisions (space dir 100 100) 2 time 0.2 ms
>
> 1000 collisions (raw) 0 time 30.9 ms
> 1000 collisions (space dir 200 200) 0 time 0.2 ms
>
> 10000 collisions (raw) 348 time 3151.0 ms
> 10000 collisions (space dir 10 10) 348 time 288.2 ms
>
> 10000 collisions (raw) 366 time 3162.9 ms
> 10000 collisions (space dir 100 100) 366 time 7.8 ms
>
> 10000 collisions (raw) 368 time 3156.9 ms
> 10000 collisions (space dir 200 200) 368 time 3.6 ms
>
> it seem to be a great succes of this method only if i got no bug somewhere
>

Note that 10 x 10 point map is like chessboard (6th century, India)
and the 200 x 200 point map is from roguelike games.
There are no problems to detect collisions on chessboard or in
roguelike game.

Collision detection can be issue when it is like some space battle in
say 2M x 2M x 2M universe, between lot of entities of different shapes.
To simplify detecting that it is impossible to make so large array.

wtorek, 8 sierpnia 2023 o 10:45:39 UTC+2 Öö Tiib napisał(a):
> On Tuesday, 8 August 2023 at 06:57:47 UTC+3, fir wrote:
> > i tested the code for collisions of 1000 and 10k objects (counting mutual colisions )
> > and the results are
> >
> >
> > 1000 collisions (raw) 2 time 35.2 ms
> > 1000 collisions (space dir 10 10) 2 time 3.4 ms
> >
> > 1000 collisions (raw) 2 time 30.9 ms
> > 1000 collisions (space dir 100 100) 2 time 0.2 ms
> >
> > 1000 collisions (raw) 0 time 30.9 ms
> > 1000 collisions (space dir 200 200) 0 time 0.2 ms
> >
> > 10000 collisions (raw) 348 time 3151.0 ms
> > 10000 collisions (space dir 10 10) 348 time 288.2 ms
> >
> > 10000 collisions (raw) 366 time 3162.9 ms
> > 10000 collisions (space dir 100 100) 366 time 7.8 ms
> >
> > 10000 collisions (raw) 368 time 3156.9 ms
> > 10000 collisions (space dir 200 200) 368 time 3.6 ms
> >
> > it seem to be a great succes of this method only if i got no bug somewhere
> >
> Note that 10 x 10 point map is like chessboard (6th century, India)
> and the 200 x 200 point map is from roguelike games.
> There are no problems to detect collisions on chessboard or in
> roguelike game.
>
> Collision detection can be issue when it is like some space battle in
> say 2M x 2M x 2M universe, between lot of entities of different shapes.
> To simplify detecting that it is impossible to make so large array.

those are detections in 2d "float" space (may be also 3d ) not on a tile map..those collisions normal raw way kill cpu begining from 2000+ objects (and it is not so strightforward to write it good in c - the above is good imo)

On 08/08/2023 10:32, fir wrote:
> wtorek, 8 sierpnia 2023 o 10:45:39 UTC+2 Öö Tiib napisał(a):
>> On Tuesday, 8 August 2023 at 06:57:47 UTC+3, fir wrote:
>>> i tested the code for collisions of 1000 and 10k objects (counting mutual colisions )
>>> and the results are
>>>
>>>
>>> 1000 collisions (raw) 2 time 35.2 ms
>>> 1000 collisions (space dir 10 10) 2 time 3.4 ms
>>>
>>> 1000 collisions (raw) 2 time 30.9 ms
>>> 1000 collisions (space dir 100 100) 2 time 0.2 ms
>>>
>>> 1000 collisions (raw) 0 time 30.9 ms
>>> 1000 collisions (space dir 200 200) 0 time 0.2 ms
>>>
>>> 10000 collisions (raw) 348 time 3151.0 ms
>>> 10000 collisions (space dir 10 10) 348 time 288.2 ms
>>>
>>> 10000 collisions (raw) 366 time 3162.9 ms
>>> 10000 collisions (space dir 100 100) 366 time 7.8 ms
>>>
>>> 10000 collisions (raw) 368 time 3156.9 ms
>>> 10000 collisions (space dir 200 200) 368 time 3.6 ms
>>>
>>> it seem to be a great succes of this method only if i got no bug somewhere
>>>
>> Note that 10 x 10 point map is like chessboard (6th century, India)
>> and the 200 x 200 point map is from roguelike games.
>> There are no problems to detect collisions on chessboard or in
>> roguelike game.
>>
>> Collision detection can be issue when it is like some space battle in
>> say 2M x 2M x 2M universe, between lot of entities of different shapes.
>> To simplify detecting that it is impossible to make so large array.
>
> those are detections in 2d "float" space (may be also 3d ) not on a tile map..those collisions normal raw way kill cpu begining from 2000+ objects (and it is not so strightforward to write it good in c - the above is good imo)

Maybe you want an R-Tree?

This has nothing to do with C, comp.programming would be better

wtorek, 8 sierpnia 2023 o 12:35:47 UTC+2 Richard Harnden napisał(a):
> On 08/08/2023 10:32, fir wrote:
> > wtorek, 8 sierpnia 2023 o 10:45:39 UTC+2 Öö Tiib napisał(a):
> >> On Tuesday, 8 August 2023 at 06:57:47 UTC+3, fir wrote:
> >>> i tested the code for collisions of 1000 and 10k objects (counting mutual colisions )
> >>> and the results are
> >>>
> >>>
> >>> 1000 collisions (raw) 2 time 35.2 ms
> >>> 1000 collisions (space dir 10 10) 2 time 3.4 ms
> >>>
> >>> 1000 collisions (raw) 2 time 30.9 ms
> >>> 1000 collisions (space dir 100 100) 2 time 0.2 ms
> >>>
> >>> 1000 collisions (raw) 0 time 30.9 ms
> >>> 1000 collisions (space dir 200 200) 0 time 0.2 ms
> >>>
> >>> 10000 collisions (raw) 348 time 3151.0 ms
> >>> 10000 collisions (space dir 10 10) 348 time 288.2 ms
> >>>
> >>> 10000 collisions (raw) 366 time 3162.9 ms
> >>> 10000 collisions (space dir 100 100) 366 time 7.8 ms
> >>>
> >>> 10000 collisions (raw) 368 time 3156.9 ms
> >>> 10000 collisions (space dir 200 200) 368 time 3.6 ms
> >>>
> >>> it seem to be a great succes of this method only if i got no bug somewhere
> >>>
> >> Note that 10 x 10 point map is like chessboard (6th century, India)
> >> and the 200 x 200 point map is from roguelike games.
> >> There are no problems to detect collisions on chessboard or in
> >> roguelike game.
> >>
> >> Collision detection can be issue when it is like some space battle in
> >> say 2M x 2M x 2M universe, between lot of entities of different shapes..
> >> To simplify detecting that it is impossible to make so large array.
> >
> > those are detections in 2d "float" space (may be also 3d ) not on a tile map..those collisions normal raw way kill cpu begining from 2000+ objects (and it is not so strightforward to write it good in c - the above is good imo)
> Maybe you want an R-Tree?
>
> This has nothing to do with C, comp.programming would be better

why should i listen to a lier?