Optimization help?

Game Mechanics
#1

Greetings.

So I have been profiling my code, and I have smoothed out almost all of the rough edged. I have this one though that kinda baffles me.

I have a function that returns a series of points when drawing a line. Kind of like an itinerary of points. It is used for several things. I use it to calculate a projectile’s path, and I also use it to calculate line of sight. Lots of stuff.

Problem is it sucks. I am guessing a large part of the suckiness is the allocating of new points in the loop as the path grows.

Can some nice person on here help me optimize it, or give me ideas on how I could optimize it myself?


public static void calc_line(ArrayList<RPGUtil.point> xitinerary,RPGUtil.point source, RPGUtil.point dest, int max_size)
    {
        RPGUtil.point lp;

        xitinerary.clear();
        int x2 = dest.x;
        int y2 = dest.y;
        int x = source.x;
        int y = source.y;

        int dx = Math.abs(x2 - x), sx = x < x2 ? 1 : -1;
        int dy = Math.abs(y2 - y), sy = y < y2 ? 1 : -1;
        int err = (dx>dy ? dx : -dy)/2;

          while (!(x == x2 && y == y2))
          {
            lp = new RPGUtil.point(x,y);
            xitinerary.add(lp);
            if ( (max_size !=0 ) && (xitinerary.size() >= max_size) )
            {
                xitinerary.clear();
                break;
            }
            int e2 = err;
            if (e2 > -dx)
            {
                err -= dy;
                x += sx;
            }
            if (e2 < dy)
            {
                err += dx;
                y += sy;
            }
          }
    }
#2

You could always save a bit of time (Sacrificing Memory) by using what is called an object pool.

Basically, when you call xitinerary.clear(), you’d add all of them to some sort of collect or array (With a maximum size). Whenever you need an object of that type, you would call ObjectType.getInstance(Type1 val1, Type2 val2, …) whatever you’d need to set the values. It would either pull an object off your collection or instantiate a new one.

#3

Nothing particularly stands out in that function there that should be any kind of a performance problem, unless you are calling it 10000x per frame, or making lines that are 1,000,000 points long. It’s basically about as fast looking as it could be, without resorting to passing in parallel arrays of int[] x/y (which is legit and will stop you needing to allocate points). So I’d do that and if it still ain’t fast enough, reconsider how it’s being called in the first place.

Cas :slight_smile:

#4

It isn’t very efficient any more (since Java 1.5).

#5

I stand corrected!

It was the first thing that came to mind. And I’m not surprised that it in’it that good (More a statement of, I’m not surprised to hear that my knowledge is incorrect, than me saying I purposefully gave bad advice. xD)

#6

UprightPath, it is still a good advice when programming on Android, the DVM sucks :’(

#7

It’s still efficient in the case of objects that are relatively expensive to construct or in the case of objects that are produced and discarded in their thousands per frame, though.

Cas :slight_smile:

#8

Which is what I tend to program in when I’m doing anything game related. It’s the only reason I purchased the phone I have. xD

And I thought so, but I wasn’t sure. I would guess that the number of times this operation is actually used per frame would end up mattering?

#9

I guess maybe I just went into optimization overdrive? I had a horrid issue with screen painting last night, and after fixing it, this was the method that floated to the top of the execution time.

This is the most expensive thing that happens once per turn for the hero, and once per turn for any NPC/spawn that is attempting to move somewhere. During my last profile test, this function was called 81 times in the 5 or so moves I made.

The hero uses this function like a radar and going completely around himself to see what he can see and stop when he can’t. It works like a wind shield wiper blade.

The monsters simply do it to see if they can see the nearest prey for possible attack persons.

#10

Try taking the ArrayList out of the parameter and make it a return value. It could be the fact that your existing ArrayList is in a older generation than your newly created points. The way many non-Android garbage collectors work means it’s more expensive to store things in old objects than it is to create a new temporary storage object to hold more temporary objects.

A better solution is to not use ArrayList. Create an object with an [icode]void add(int x, int y)[/icode], [icode]getX(int index)[/icode], and [icode]getY(int index)[/icode] method. And store the x,y coordinates interleaved in the same array ([icode]{x0, y0, x1, y1, …, xn, yn}[/icode]), not in parallel arrays. This will guarantee that all the point data gets grouped together and there is no memory management problem stemming from how a point is used or how long it lives.

You can also use a profiler for a block of code inside a method by specifying a range of line numbers to time. Then you can pinpoint which lines inside a method take longest to execute once you know which method takes the most time. Besides that, you should not start a class name with a lowercase letter. (But obviously that would not alter the performance.)

#11

That could be interpreted in all sorts of wrong ways by those with just not quite enough knowledge. It is not more expensive to use old objects, at all, per se. It is very slightly more expensive to garbage collect them with some collectors, though.

Cas :slight_smile:

#12

Good point, but not really the problem behind that usage. It occurred to me that the OP is probably attempting unnecessary optimization. The method would have to be called a lot more for it to be a problem for either object creation trouble or inner loop performance. I’ll still clarify to avoid confusion. If this method created thousands of Objects, it would add up, but it probably does not unless the two points are far away.

…

Generational garbage collectors divide objects into groups based on the assumption that newer objects are likely to be temporary and older objects are likely to stick around even longer. Garbage collecting in the young generation uses an algorithm that scales with the number of live references and, for the old generation, uses an algorithm that depends on the number of total objects created.

So keeping temporary objects entirely in the young generation means that it’s cheap to create lots of temporary objects. It’s okay for a young object to reference an object in any generation, but an old generation object that even temporarily references younger generation objects is bad. It means that the thousands of objects you create in the young generation suddenly have to be scanned using the old gen algorithm instead of the young gen one.

…

Has anyone done testing on object pooling compared to generating immutable objects with G1? I haven’t tried anything with huge numbers of objects in that version.