Alternative to nesting for-loops

[RemmyDZ]

Hello all,

I am writing a program, and right now there's one function which makes use of nesting (a for-loop inside a for-loop in this case).
Now, I noticed that this particular function takes alot of CPU usage.
If I do not execute the function, my CPU usage (on a dual-core) is around 5% average.
If I do execute the function, the CPU usage on average is 25-30%, a big difference.
Now I tried to write an alternative to the structure, but for some reason, it doesn't work, my whole program freezes.
I was wondering if you guys could help me with this.

This is the original code:

void DrawMap()
{
	for(int i=0; i<mapSizeX; i++)
	{
		for(int j=0; j<mapSizeY; j++)
		{
			if(map[i][j] == 0)
				DrawObject();
		}
	}
}

And this is the alternative I tried, but it does not work, as stated above:

void DrawMap()
{
	int i = 0;
	int j = 0;
	bool done = false;
	while(!done)
	{
		if(map[i][j] == 0)
			DrawObject();
		else
		{
			if(i<mapSizeX)
				i++;
			else if(i == mapSizeX)
			{
				i = 0;
				if(j<mapSizeY)
					j++;
				else if(j == mapSizeY)
					done = true;
			}
		}
	}
}

Thanks in advance!


Greetings,
RemmyDZ :)

[codewalker]

Nested loop is the only way you can properly access an double dimension array, for more dimensions there will be more nested loops

[RemmyDZ]

Thanks for the quick reply!

So you're basically saying that there is no other way I can do this?

[codewalker]

It will hard, inefficient. If your mapSizeX is 10 then you will have to manually write 10 for loops for mapSizeY. OR some tricky code in single loop.

In second case the loop is going to run mapSizeY X mapSizeX times anyway. So there is no point in not using nested loops

[ValliusDax]

Have you experimented with the modulo operator (%)?

Without full code it's difficult for me to give you perfect code... but something like this:

void DrawMap()
{
	for(int i=0; i<mapSizeX+mapSizeY; i++)
	{
		if(map[i/mapSizeX][j%mapSizeY] == 0)
			DrawObject();
        }
}

That being said, this won't speed things up at all. It's more likely that the calls to DrawObject are slowing things down... try a trivial replacement for DrawObject (like increment an int) and see if that is what's hogging the CPU (for loops shouldn't cause that much use unless they're huge).

[RemmyDZ]

Thanks for the replies!

In the meantime, I tried something else.
I only ran DrawMap once, and made it store the coordinates of the objects into an array with x and y integers.
This way, I can avoid the nesting, but it seems that ValliusDax is right, because right now, my CPU usage on average is 15-20%, so it has dropped a bit, but not as much as I want it to.
Unfortunately, I am using a library, and the DrawObject function is the only way to draw.

[cire]

What does DrawObject do? What it does can't be dependent on what's stored in the map at whatever position you happen to be checking, as neither the map nor the coordinates you're using are passed to the function. Is there a reason it may need to be called more than once in your DrawMap function?

It seems to me DrawMap might be written:

void DrawMap()
{
   bool objectDrawn = false ;

    for(int i=0; i<mapSizeX && !objectDrawn; i++)
    {
        for(int j=0; j<mapSizeY && !objectDrawn; j++)
        {
            if(map[i][j] == 0)
            {
                DrawObject();
                objectDrawn = true ;
            }
        }
    }
}

which, depending on the contents of map, could cut down considerably the number of times you're calling DrawObject.

[RemmyDZ]

The problem is, the map refreshes every 1/60 of a second, but you made me think now.
Maybe I could only make the object draw once, since DrawObject only draws the background bitmap, and there's no need to refresh that, since it's not affected by anything.
I am going to try that right now, thanks alot for the tip! :)

I'll post the results as soon as possible!

[RemmyDZ]

I'm glad I can say that this problem is now solved!

Here's what I did:
In my previous system, I had the map devided into pieces of 16*16.
Now, everytime that piece was a '0' in the map file, I made the program draw a piece of background (DrawObject) with the size of 16*16 pixels.
Of course, most of my level consisted of background, so the program had to draw alot, and since the screen refreshes every 1/60 of a second, it took alot of CPU usage.
Now, I tried to get rid of the nested loops, as I said before, but it only took away like 5% CPU usage.
Now, I replaced the tiny pieces of background by one big background, and on top of that I made the program draw the other objects (like player, enemies, and so on).
Thanks to Cire, I thought of that method, so thank you Cire, and thank all of you, for helping me out, and for the very quick replies, I appreciate it alot!

Thanks all!


Greetings,
RemmyDZ :)