Jump to content
  • Advertisement
Sign in to follow this  
EdBoon

terribly slow function needs more efficient structure

This topic is 2750 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a program that i ran in a profiler and 50% of the entire code is in one function. It is really slowing down the program and thought maybe there is a much better way to code this. The program is in XNA but its really more of standard code question so I put it in general game programming. I am running collision detection using spacial hashing and this update function is from updating the grid.


public void Update()
{
int bucketListCount;
int count = occupiedBucket.Count();

for (int i = 0; i < count; i++)
{
bucketListCount = bucketList[occupiedBucket.ElementAt(i)].Count();
for (int j = 0; j < bucketListCount; j++)
{
for (int k = j + 1; k < bucketListCount; k++)
{
bucketList[occupiedBucket.ElementAt(i)].ElementAt(j).handleCollide(bucketList[occupiedBucket.ElementAt(i)].ElementAt(k));
}
}
}
}

There are a lot of uses of elementAt(), would that cause the slowdown to happen? the function it calls inside of itself (handlecollide) isnt spending any time in it so it is all just in the for statements. There has to be a better way to code this. Bucketlist count is usually around 3 or 4 and count is around 200-300.

thanks guys,

[Edited by - EdBoon on November 29, 2010 9:02:32 PM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by no such user
What are the exact types of the variables here?


oh yea sorry, the objects in the list that it is counting and elementsat() are from a class i created holding the enemy information such as position health bitmap etc..

also i guess i could explain a little bit what the for loops are doing>>

the bucketlist is an array of lists that represent buckets in the grid which when an object gets placed into a bucket or sector of the grid, an indicator gets placed inside of occupiedBucket, so that i dont have to cycle through the entire bucketlist and find if there is an object inside of the particular bucket. if an item is across a bucket divider, it gets placed into two buckets (or 4 if at a cross). each bucket of enemies and projectiles checks everyone else in the list at least once and does the collision function with them.

the more i try to explain i see im going in circles

variables:
occupiedBucket: a list of integers
bucketList: an array of lists which contain gameEntities (enemies, projectiles, turrets, etc..)
handlecollide: not too important because the profiler says hardly any time is spent inside of this function, but 50% is spent inside of the update function.


please let me know what is unclear because im sure theres more :) thanks again

Share this post


Link to post
Share on other sites
Quote:
Original post by no such user
What are the exact types of the variables here?


oh yea sorry, the objects in the list that it is counting and elementsat() are from a class i created holding the enemy information such as position health bitmap etc..

also i guess i could explain a little bit what the for loops are doing>>

the bucketlist is an array of lists that represent buckets in the grid which when an object gets placed into a bucket or sector of the grid, an indicator gets placed inside of occupiedBucket, so that i dont have to cycle through the entire bucketlist and find if there is an object inside of the particular bucket. if an item is across a bucket divider, it gets placed into two buckets (or 4 if at a cross). each bucket of enemies and projectiles checks everyone else in the list at least once and does the collision function with them.

the more i try to explain i see im going in circles

variables:
occupiedBucket: a list of integers
bucketList: an array of lists which contain gameEntities (enemies, projectiles, turrets, etc..)
handlecollide: not too important because the profiler says hardly any time is spent inside of this function, but 50% is spent inside of the update function.


please let me know what is unclear because im sure theres more :) thanks again


**double post my fault

Share this post


Link to post
Share on other sites
Are the buckets linked lists or vectors/arrays? ElementAt will be very expensive for linked lists. ElementAt(200) will have to go through 200 nodes before it gets the element you're interested in.

Share this post


Link to post
Share on other sites
Quote:
Original post by Thrump
Are the buckets linked lists or vectors/arrays? ElementAt will be very expensive for linked lists. ElementAt(200) will have to go through 200 nodes before it gets the element you're interested in.


i do not believe they are linkedlist, they seem to function the same as array lists but is type safe. (I am using c# by the way)

i declare them like this:


public static int min = 0;
public static int max = Game1.map.levelHeight;
public static int cellSize = 64;
public static int width = (max-min)/cellSize;
public static int numberOfBuckets = width*width;
public List<GameEntity>[] bucketList = new List<GameEntity>[numberOfBuckets];
public List<int> occupiedBucket = new List<int>();
Vector2 normal;



public Grid()
{
for (int i = 0; i < numberOfBuckets; i++)
{
bucketList = new List<GameEntity>();
}
}


So I'm pretty sure they aren't searching through the entire list each location but i may be wrong.

originally I had them as foreach in the Update section but I read that for loops are much more efficient, although I didn't see much of a change in performance numbers. Actually a couple days ago it was much more code and have gotten it down to the couple of for loops, but still not much improvement on efficiency. any ideas?
thanks again.

Share this post


Link to post
Share on other sites
The proper way to iterate through a linked list is to do something like

while(currentElement = list->nextelement())
{
// do something with currentElement
}

Otherwise, each time you address an element by index number, the program iterates through the list element by element until it gets to the requested element, which takes more and more time every time the index increases.

Share this post


Link to post
Share on other sites
List<T> is represented by arrays in .Net, not linked lists.

List<T> has a [] operator. Use it instead of ElementAt.

ElementAt is a LINQ extension method and uses the IEnumerable interface. The IEnumerable interface is not meant for random access and is guaranteed to be slower than indexing the List<T> directly using operator[].



That said, your loop can be written like this:


public void Update()
{
foreach (var bucket in occupiedBucket.Select(x => bucketList[x]))
{
int bucketListCount = bucket.Count();
for (int j = 0; j < bucketListCount - 1; j++)
for (int k = j + 1; k < bucketListCount; k++)
bucket[j].handleCollide(bucket[k]);
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
List<T> is represented by arrays in .Net, not linked lists.

List<T> has a [] operator. Use it instead of ElementAt.

ElementAt is a LINQ extension method and uses the IEnumerable interface. The IEnumerable interface is not meant for random access and is guaranteed to be slower than indexing the List<T> directly using operator[].


thanks a lot, i removed the elementAt in there and just indexing, and it improved by about 2%, but from 50% to 48% not much difference :(

any other simple mistakes you can see??

Share this post


Link to post
Share on other sites
The HandleCollide function must be pretty expensive then, if the enumeration wasn't the primary cause.

Alternatively, instead of checking everything inside each occupied bucket against each other, you could use Sweep and prune instead of (or in conjunction with) buckets.

[Edited by - Nypyren on November 29, 2010 10:47:09 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!