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]

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

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

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.

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??