How do I sort a list into 1/2 or 1/4 chunks?

[EvanBlack]

I have a big problem... linear search methods are TOO SLOW! I need help on how to make a search method that can blast through a list of like 1225 clones.

This is what I am using and FPS dead stops once I have to find stuff at the end of the list.

Code: Select all

Actor* getActorByNode(char name[30], int node)
{
    Actor* Tile;
    int i = 0;
    char buffer[30];
 
    do
    {
        sprintf(buffer, "%s.%i",name, i);
        Tile = getclone(buffer);
        ++i;
    }while(node != Tile->a_nID);
 
    return Tile;
}


node is compared an Actor Variable and if they match then it returns the variable. The problem is, it has to search through all 1,225 clones before it can match the last one. Not only that but it must do this about 35 times every second or less. So 2.57 MILLION times a minute.

I need to be able to cut that search time in like 1/2 or less. But the problem is I am not well versed in search methods. Can anyone help me out here?

[skydereign]

Well it depends on how the actors and their IDs are listed. If it is in a sortable pattern, then you can use a binary search but then chances are it'd be 1 for 1. Speaking of which, couldn't you use the node number to grab the actual clone? For example linking actors to nodes via cloneindex. That or storing in an array (by node) the cloneindex of the actor. That way you can just plug that in and not have to run through them. Also, weren't you using a max of 120ish actors?

[EvanBlack]

I solved it by using two arrays to store the tiles Actor* 's, an odd and even arrays.

With the isotiles being small and using a resolution of 800x600, I have to use a 35x35 tile array to fill the entire screen.

If I lower the resolution then I can lower the actor count. But I want to be able to use the higher resolution also.

The problem with the node number and clone index thing, I am not really sure what I would do. The clone index is static, while the nodes are dynamic, semi-random. There is a formula to know exactly which clone will have what node at any given time, but im not a mathematician and I couldn't figure out that formula. Also, the node map can be up to 4 Million Nodes.

The clones move from one side two the other two simulate a never ending map, but their nodes change based on direction. Like a 4 way treadmill.

I cut the search time in half and I no long am getting actors by x,y so I can now move function a bit more functional. Like keeping track of the objects on the tiles and destroying or moving them as necessary.

Im really going to try to limit the calls to destroy and create because anytime I can just move an object or tile to a new spot and just change the animation would be preferable.

But for now.. it works... Once I am all finished, everything working as it should, I will try to optimize my code even more and make functions and search times faster.

Right now its using up extra space in the memory it doesn't need. But they are just integer arrays, I will change them later.

I really need better sorted arrays though, I just don't know enough about them or how I could possibly do it, I even thought about a Binary Tree but it just doesn't make sense for this kind of search. The second thing I thought of was using more than 2 arrays, but I don't know the math involved to sort them. Right now I am using if(node %2 == 0) {store in even array}