Best way to deal with infinite elements?

Newbie & Debugging Questions
#1

Hello,

When I use some type of element that can be infinite (games that only finish when the player dies) I always put everything inside of two Arrays. So, when the first Array has more than X elements I start to fill the second Array, when the second Array has more than X elements I clean the first Array and start to fill again.

I can save memory for not renderer a lot of stuff and only renderer the lasts. In games with automatically movement is good, because the elements will disappear with time every time I clean one of arrays, and the lasts will always renderer.

e.g: Array rectArray;
I can use this to control and renderer a lot of rectangles created automatically in the game and “clean” the old rectangles when the array is cleaned, but everytime I need to do a loop with for (i=0 ; i< array.size; i++) to verify collision and other things, so this can be bad for performance.

So, this is a good practice? Is there any other better way to deal with “infinite stuff” created in the game?

Here a small example of what I said before:


Array<Rectangle> listRec1 = new Array<Rectangle>();
Array<Rectangle> listRec2 = new Array<Rectangle>();
Rectangle playerRec = new Rectangle();

.....

render(float delta)
{
	if (currentTime - previousTime > 5) //5 seconds
	{
		if (listRec1.size <= 10)
		{
			listRec1.add(new Rectangle(anyX, anyY, anyW, anyH);
				if (listRec1.size == 9 && listRec2.size == 9)
				listRec2.clear; //clear listRec2.
		}
		else if (listRec2.size < 10)
		{
			listRec2.add(new Rectangle(anyX, anyY, anyW, anyH);
		}
		else if (listRec1.size <=10 && listRec2.size < 10)
		{
			listRec1.clear; //Clear listRec1
			listRec2.add(new Rectangle(anyX, anyY, anyW, anyH); //Add last Rec to listRec2
		}
	}			
		
	if (listRec1.size > 0)
		for (int i=0; i<listRec1.size; i++)
		{
			//code to draw all rectangle inside listRec1.
			//code to verify collision with player and Recs.
		}
		
	if (listRec2.size > 0)
			for (int i=0; i<listRec2.size; i++)
		{
			//code to draw all rectangle inside listRec2.
			//code to verify collision with player and Recs.
		}
}
#2

Any ideia?

#3

I recommend you make a rectangle the size of the screen and add (and draw) the entity whenever it collides (and is inside) with the screen.

#4

Another tactic might be a First-in-First-out (FIFO) Queue. (see Java Queue)

Use the queue how you might use your array or List, and when the size reaches some maximum (10 in your example), remove some number of elements from the queue and let it fill up again. This is assuming that the Rectangles you’re adding should be removed in the same order they where added. If some of them can persist longer than others, you can implement a PriorityQueue instead, and sort it once per update loop.

Still another alternative would be to detect that each Rectangle has become “expired”, either from a timer, or from moving outside some boundary defined by you. Then once each time through the update loop, remove the expired elements.

#5

I could be mistaken, but it sounds like a circular buffer could be useful in this circumstance. The Apache Commons Collection has a CircularFifoBuffer class, or you could roll your own.

#6

I’m implementing FIFO now, I think this is really good for what I want.

I’m trying LinkedList and Queue, which is better and why? any difference in performance? I think LinkedList has more options to use and I need to change a lot of code to implement, so I want to be sure before making changes.

#7

Queue is just an interface, LinkedQueue is one implementation of it. ArrayDeque is my personal favorite, and is probably faster for most use cases.
If you are actually concerned about speed (which you probably shouldn’t be at this point), then the only way to know it to measure.

#8

“This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.” http://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html

Interesting, this option would be the best? because all are very similar, I can use any of them that will work, but it seems that this ArrayDeque is better.

#9

GWT don’t have compatibility with ArrayDeque =/.

I’m using LinkedList right now, thanks guys, I have more performance and a lot of code cleaned.

#10

Depending on your needs as you mentioned using this for something like an endless runner I’d get rid of objects altogether if all you are tracking is one type of data (re: rectangles). Use primitive arrays and keep track of the active count and index by stride of your data. You can get more clever and store multiple types of data perhaps with an increased stride and some sort of index data which identifies the data type. This doesn’t require new object creation and also brings cache locality into play when you are working over all the data for rendering / collision detection. IE the only time you are guaranteed to have a contiguous block of data with Java is primitive arrays. It will be at least an order of magnitude faster than creating new objects and iterating over a collection of objects regardless of collection used.

Of note is that I didn’t really look into supposed logic issues in the pseudo-code you posted, but here is more or less how you’d do it without objects. It will be a lot faster! Benchmark it and report back… ;D



static final s_MAX_SIZE = 10;

static final s_STRIDE = 4;

int listRec1[] = new int[s_STRIDE * s_MAX_SIZE];
int listRec2[] = new int[s_STRIDE * s_MAX_SIZE];

int listCount1, listCount2;

Rectangle playerRec = new Rectangle();

render(float delta)
{
   if (currentTime - previousTime > 5) //5 seconds
   {
      if (listCount1 < s_MAX_SIZE)
      {
         int index = s_STRIDE * listCount1++;  // post increment only happens after mult.
         listRec1[index] = anyX;
         listRec1[index+1] = anyY;
         listRec1[index+2] = anyW;
         listRec1[index+3] = anyH;         

         if (listCount1 == s_MAX_SIZE && listCount2 == s_MAX_SIZE)
         {         
             listCount2 = 0; //clear listRec2.
         }
      }
      else if (listCount2 < s_MAX_SIZE)
      {
         int index = s_STRIDE * listCount2++;
         listRec2[index] = anyX;
         listRec2[index+1] = anyY;
         listRec2[index+2] = anyW;
         listRec2[index+3] = anyH;         
      }
      else if (listCount1 <= s_MAX_SIZE && listCount2 < s_MAX_SIZE)
      {
         listCount1 = 0;

         int index = s_STRIDE * listCount2++;
         listRec2[index] = anyX;
         listRec2[index+1] = anyY;
         listRec2[index+2] = anyW;
         listRec2[index+3] = anyH;         
      }
   }         
      
   for (int i = listCount1; --i >= 0;)
   {
      int index = i * s_STRIDE;
      int rectX = listRec1[index];
      int rectY = listRec1[index+1];
      int rectW = listRec1[index+2];
      int rectH = listRec1[index+3];

      //code to draw all rectangle inside listRec1.
      //code to verify collision with player and Recs.
   }
      
   for (int i = listCount2; --i >= 0;)
   {
      int index = i * s_STRIDE;
      int rectX = listRec2[index];
      int rectY = listRec2[index+1];
      int rectW = listRec2[index+2];
      int rectH = listRec2[index+3];

      //code to draw all rectangle inside listRec2.
      //code to verify collision with player and Recs.
   }
}