   My function is too slow
  I'm making with SDL a turn-based RPG that plays on a rectangular tile map. So far I've been doing fairly well, but I've run into a slight problem. It's NPC movement, or, more specificaly, NPC detection of player/other NPCs. Here is the function:void npcaction(){    int x,y,i,j,a,b,c,d;    float ix;    srand(unsigned(SDL_GetTicks()));    for(y=0;y<mapsize;y++)    {   for(x=0;x<mapsize;x++)   {   if((map[x][y].critter!=0)&&(map[x][y].critter!=&player))   {   for(i=0;i<8;i++) map[x][y].critter->ai.alert=0;   a=x-map[x][y].critter->effective.sight;   b=x+map[x][y].critter->effective.sight;   c=y-map[x][y].critter->effective.sight;   d=y+map[x][y].critter->effective.sight;   if(a<0) a=0;   if(b>=mapsize) b=mapsize-1;   if(c<0) c=0;   if(d>=mapsize) d=mapsize-1;   for(i=a;i<=b;i++)   {  for(j=c;j<=d;j++)  {if((distance(x,y,i,j)<=map[x][y].critter->effective.sight)&&((x!=i)||(y!=j))){   ix=i-x;   if(ix==0) ix=0.000001;   switch(map[x][y].critter->facing)   {   case 0:   { if((j<=y)&&(map[j].critter!=0)) {    if(((j-y)/ix>=-0.41)&&((j-y)/ix<0)) map[x][y].critter->ai.alert[6]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>=-2.41)) map[x][y].critter->ai.alert[7]++;    if((j-y)/ix<-2.41) map[x][y].critter->ai.alert[0]++;    if(((j-y)/ix<=0.41)&&((j-y)/ix>0)) map[x][y].critter->ai.alert[2]++;    if(((j-y)/ix>0.41)&&((j-y)/ix<=2.41)) map[x][y].critter->ai.alert[1]++;    if((j-y)/ix>2.41) map[x][y].critter->ai.alert[0]++;    if((j-y)/ix==0)    {  if(i<x) map[x][y].critter->ai.alert[6]++;  else map[x][y].critter->ai.alert[2]++;    } } break;   }   case 1:   { if((i-x>=j-y)&&(map[j].critter!=0)) {    if(((j-y)/ix>=-2.41)&&((j-y)/ix<-1)) map[x][y].critter->ai.alert[7]++;    if(((j-y)/ix<-2.41)||((j-y)/ix>2.41)) map[x][y].critter->ai.alert[0]++;    if(((j-y)/ix>=0.41)&&((j-y)/ix<2.41)) map[x][y].critter->ai.alert[1]++;    if(((j-y)/ix<0.41)&&((j-y)/ix>=-0.41)) map[x][y].critter->ai.alert[2]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>-1)) map[x][y].critter->ai.alert[0]++;    if((j-y)/ix==-1)    {  if(i<x) map[x][y].critter->ai.alert[7]++;  else map[x][y].critter->ai.alert[3]++;    } } break;   }   case 2:   { if((i>=x)&&(map[j].critter!=0)) {    if((j-y)/ix>=2.41) map[x][y].critter->ai.alert[0]++;    if(((j-y)/ix<2.41)&&((j-y)/ix>=0.41)) map[x][y].critter->ai.alert[1]++;    if(((j-y)/ix<0.41)&&((j-y)/ix>=-0.41)) map[x][y].critter->ai.alert[2]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>=-2.41)) map[x][y].critter->ai.alert[3]++;    if((j-y)/ix<-2.41) map[x][y].critter->ai.alert[4]++; } break;   }   case 3:   { if((i-x>=y-j)&&(map[j].critter!=0)) {    if(((j-y)/ix>=0.41)&&((j-y)/ix<1)) map[x][y].critter->ai.alert[1]++;    if(((j-y)/ix<0.41)&&((j-y)/ix>=-0.41)) map[x][y].critter->ai.alert[2]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>=-2.41)) map[x][y].critter->ai.alert[3]++;    if(((j-y)/ix<-2.41)||((j-y)/ix>=2.41)) map[x][y].critter->ai.alert[4]++;    if(((j-y)/ix<2.41)&&((j-y)/ix>1)) map[x][y].critter->ai.alert[5]++;    if((j-y)/ix==1)    {  if(i<x) map[x][y].critter->ai.alert[5]++;  else map[x][y].critter->ai.alert[1]++;    } } break;   }   case 4:   { if((j<=y)&&(map[j].critter!=0)) {    if(((j-y)/ix>=-0.41)&&((j-y)/ix<0)) map[x][y].critter->ai.alert[2]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>=-2.41)) map[x][y].critter->ai.alert[3]++;    if(((j-y)/ix<-2.41)||((j-y)/ix>=2.41)) map[x][y].critter->ai.alert[4]++;    if(((j-y)/ix<2.41)&&((j-y)/ix>=0.41)) map[x][y].critter->ai.alert[5]++;    if(((j-y)/ix<0.41)&&((j-y)/ix>0)) map[x][y].critter->ai.alert[6]++;    if((j-y)/ix==0)    {  if(i<x) map[x][y].critter->ai.alert[6]++;  else map[x][y].critter->ai.alert[2]++;    } } break;   }   case 5:   { if((i-x<=j-y)&&(map[j].critter!=0)) {    if(((j-y)/ix>=-2.41)&&((j-y)/ix<-1)) map[x][y].critter->ai.alert[3]++;    if(((j-y)/ix<-2.41)||((j-y)/ix>2.41)) map[x][y].critter->ai.alert[4]++;    if(((j-y)/ix>=0.41)&&((j-y)/ix<2.41)) map[x][y].critter->ai.alert[5]++;    if(((j-y)/ix<0.41)&&((j-y)/ix>=-0.41)) map[x][y].critter->ai.alert[6]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>-1)) map[x][y].critter->ai.alert[7]++;    if((j-y)/ix==-1)    {  if(i<x) map[x][y].critter->ai.alert[7]++;  else map[x][y].critter->ai.alert[3]++;    } } break;   }   case 6:   { if((i<=x)&&(map[j].critter!=0)) {    if((j-y)/ix>=2.41) map[x][y].critter->ai.alert[4]++;    if(((j-y)/ix<2.41)&&((j-y)/ix>=0.41)) map[x][y].critter->ai.alert[5]++;    if(((j-y)/ix<0.41)&&((j-y)/ix>=-0.41)) map[x][y].critter->ai.alert[6]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>=-2.41)) map[x][y].critter->ai.alert[7]++;    if((j-y)/ix<-2.41) map[x][y].critter->ai.alert[0]++; } break;   }   case 7:   { if((i-x<=y-j)&&(map[j].critter!=0)) {    if(((j-y)/ix>=0.41)&&((j-y)/ix<1)) map[x][y].critter->ai.alert[5]++;    if(((j-y)/ix<0.41)&&((j-y)/ix>=-0.41)) map[x][y].critter->ai.alert[6]++;    if(((j-y)/ix<-0.41)&&((j-y)/ix>=-2.41)) map[x][y].critter->ai.alert[7]++;    if(((j-y)/ix<-2.41)||((j-y)/ix>=2.41)) map[x][y].critter->ai.alert[0]++;    if(((j-y)/ix<2.41)&&((j-y)/ix>1)) map[x][y].critter->ai.alert[1]++;    if((j-y)/ix==1)    {  if(i<x) map[x][y].critter->ai.alert[5]++;  else map[x][y].critter->ai.alert[1]++;    } } break;   }   default: break;   }}  }   }   j=0;   for(i=1;i<8;i++)   { if((map[x][y].critter->ai.alert==map[x][y].critter->ai.alert[j])&&(rand()%2==0)) j=i; if(map[x][y].critter->ai.alert>map[x][y].critter->ai.alert[j]) j=i;   }   if((map[x][y].critter->ai.alert[j]>0)&&(map[x][y].critter->moved==0))   { j+=4; if(j>7) j-=8; map[x][y].critter->facing=j; map[x][y].critter->moved=1; move(map[x][y].critter,1);   }   }   }    }    for(y=0;y<mapsize;y++)    {   for(x=0;x<mapsize;x++)   {   if(map[x][y].critter!=0) map[x][y].critter->moved=0;   }    }}With some toying around I've come to conclusion that the bottleneck is the part (well, it's a big part) where the critter checks surrounding tiles for other critters. With 1 critter per 100 tiles it's a lagfest, but it works fine with 1 critter per 1000 tiles.The largest number of critters that allow smooth gameplay is 3 per 1000 tiles. The map size is 409*409, or 167281 tiles, and I'm running this on a Pentium 4 @ 2GHz with 256Mb RAM.While ~502 critters on a map is more than enough for me, I am concerned with how will my game behave on lower-end systems, especialy since it's only about 40% done and may get even more resource-hungry down the road.Oh, I almost forgot - the sight range of the critters I'm testing this with (rabbits) is set to 15 because I figure that will be the average sight range of all creatures.So, my question is: is there a better way to do detection of other creatures on the map? I'd really like to avoid reducing the map size because my goal is to have a simple ecosystem simulation in my game (ie creatures feed, reproduce and die) and that wouldn't work very well on a small map.   
  It isn't necessary to iterate over the entire map. You can iterate over the critters instead if you make sure both that the critters know where they are and that the map knows which critters are in a given area.Also, you have alot of duplicate code you could condense.   ;  Also, if the range of sight of your critters is 15, you could choose to divide your map into 8 by 8 sections, and have each section hold a list of critters in that section. This way, you wouldn't need to check 31*31-1 map locations for each critter, but only 9 sections.   ;  So, I should organise my critters into a dynamicaly linked list? I was thinking about that before but for some reason thought that it wasn't worth it because it takes a long time to go through a 500+ long list. But now that you've mentioned it, it occured to me that I chould check list length against number of tiles that have to be checked visualy ((sight*2)^2) and use whichever is faster in that particular instance. And I'd cut down on searching for critters all over the map.Thanks for suggestions :D*edit* Wow, that's also a nice idea! I would've never thought of making a map of the map.   ;Quote:I was thinking about that before but for some reason thought that it wasn't worth it because it takes a long time to go through a 500+ long listI'm not suggesting to go through the critter list for each critter, but to go to the 9 map sections around each critter and get a list of critters from the sections which is much much shorter than 500. So time complexity is O(n), where n is number of critters (500). Your time complexity is O(m*r*r), where m is number of tiles (167281) and r is range of sight (15).   ;  So, I would have a separate linked list for every 8*8 section of the map, and then check the part the section that the critter is in as well as the neighbouring sections? Now that looks fast. I feel stupid for not thinking of it myself :(   ;  Just glancing through the code there, I notice a loop with around 4/5 nested loops! Is there anyways that you can get rid of some of them? I am pretty sure that you will notice a speed increase if you do.   ;  You calculate (j-y)/ix quite a few times in the switch. Try to store the value maybe?   ;  Wiggin's solution should get rid of most of those nested loops. I smell a huge speed increase.And I feel like such a noob because now it seems so obvious.   ;Quote:So, I would have a separate linked list for every 8*8 section of the map, and then check the part the section that the critter is in as well as the neighbouring sections?Yup. It's a fairly standard method for this sort of thing. The O(n) complexity can't be improved upon because, well, all the critters are presumably active all the time.   