Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (529)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2] 3
  ignore  |  Print  
  Java collections good for gaming?  (Read 16153 times)
0 Members and 1 Guest are viewing this topic.
Offline Markus_Persson

JGO Wizard


Medals: 14
Projects: 19


Mojang Specifications


« Reply #30 - Posted 2006-10-09 16:04:55 »

Horrible on so many levels, but its fast Grin
1  
2  
3  
public class Bag{
/** code **/
}


Holy macarony, that's awesome. Grin

Play Minecraft!
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #31 - Posted 2006-10-09 16:05:10 »

Mem usage difference?

I would guess that it'll be the same. It's basically doing what an ArrayList/Vector does, but not caring about ordering.

It's funny that there isn't something like this in java.util already. There's lots of times you just want a collection of things without caring about order or set qualities.

Give me a wee while and I'll knock up a version that implements java.util.Collection.
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #32 - Posted 2006-10-09 18:50:53 »

And there it is.
Untested though, who wants to make some unit tests? The behaviour should be identical to an ArrayList apart from the ordering, so it'd be pretty easy to test by performing some operations on a Bag and an ArrayList, dumping their contents to a arrays, sorting the arrays and testing if they are identical.

edit: Broken version removed
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline oNyx

JGO Coder


Medals: 1


pixels! :x


« Reply #33 - Posted 2006-10-10 09:38:19 »

Why removefoo() instead of remove()? And there is some remove() some way down, which is sorta odd...

And over in clear()... calling Arrays.fill() looks nice n all, but it does more than necessary. From 0 to <size would be enough (everything after that is null anyways... see remove()).

indexOf() condition should be array[i].equals(o) instead of ==. Also... its important to do it this way around, because null.equals(something) wouldnt be nice Smiley

contains() can be written as return indexOf(o) >= 0; or return indexOf(o) != -1; (Either way there shouldnt be that == comparison loop.)

edit: oops... array[i] can be null aswell... so there has to be some check and seperate loops.

弾幕 ☆ @mahonnaiseblog
Offline Markus_Persson

JGO Wizard


Medals: 14
Projects: 19


Mojang Specifications


« Reply #34 - Posted 2006-10-10 11:10:54 »

indexOf() condition should be array[i].equals(o) instead of ==. Also... its important to do it this way around, because null.equals(something) wouldnt be nice Smiley

== is a lot faster than. equals, and works with null. So if that's the behavior you want (very common in games), there's no reason to change it. =)

Play Minecraft!
Offline oNyx

JGO Coder


Medals: 1


pixels! :x


« Reply #35 - Posted 2006-10-10 11:23:59 »

indexOf() condition should be array[i].equals(o) instead of ==. Also... its important to do it this way around, because null.equals(something) wouldnt be nice Smiley

== is a lot faster than. equals, and works with null. So if that's the behavior you want (very common in games), there's no reason to change it. =)

Well, yea, but its different stuff. Maybe other methods should be used for that... containsReference() and indexOfReference() perhaps?

Unexpected behaviour leads to weird bugs n glitches Wink

弾幕 ☆ @mahonnaiseblog
Offline Markus_Persson

JGO Wizard


Medals: 14
Projects: 19


Mojang Specifications


« Reply #36 - Posted 2006-10-10 12:42:20 »

Well, yes, it's already Strange Stuff, as it's not quite a List, and not quite a Set. (and definitely not a Map) :-)

Play Minecraft!
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #37 - Posted 2006-10-10 13:10:19 »

Wah! looks like I should have checked through it more thoroughly. Cleaned-up version forthcoming.
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #38 - Posted 2006-10-10 14:19:24 »

There you are then:

removefoo embarrassment removed Roll Eyes
clear() only clears what it needs to
indexOf() object equality test is now as specified by the Collection interface
Constructors suggested by the Collection interface added
ensureCapacity() method added.

Unexpected behaviour leads to weird bugs n glitches Wink
As someone who was bitten by this little humdinger, I could not agree more.

edit: Keep on scrollin' pardner, a less buggy version can be found below.
Offline CommanderKeith
« Reply #39 - Posted 2006-10-10 14:50:33 »

Wow, that is really neat  Cheesy.  far out, well done.

May I use the version you have been working on bleb?  I can't find a link.

'Bag' is a really funny name for this by the way - very suitable. 
List, Map, Set all have some kind of level of respect, but a 'Bag' like a plastic bag is a peice of crap, its just useful for chucking stuff in.  Cool

Thanks,
Keith

PS: does that version support generics?

EDIT: oops, now I see it as an attachment.  Many thanks  Smiley.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online kappa
« League of Dukes »

JGO Kernel


Medals: 74
Projects: 15


★★★★★


« Reply #40 - Posted 2006-10-10 15:02:19 »

bleb that new version is even nicer, it can now completely replace ArrayList, Bag looks to becoming the ultimate gaming collection Smiley

btw not sure about this but couldn't you change

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
public boolean removeAll( Collection<?> c )
{
      boolean changed = false;

      Iterator<?> iter = c.iterator();
      while( iter.hasNext() )
      {
         changed |= remove( iter.hasNext() );
      }

      return changed;
}


to

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
public boolean removeAll(Collection<?> c) 
{
     
   boolean changed = false;      

   for (int i = 0; i < c.size(); i++) {
      changed |= remove(c.get(i));
   }

   return changed;
}


if it is correct it would avoid creating an iterator which might be faster.
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #41 - Posted 2006-10-10 15:11:36 »

It might be faster in some cases, but not in others. Some collections are very good at random access, such as ArrayList, and some are not so good, such as LinkedList.
Using the iterator means that c's implementation gets to decide what is the most efficient way to access its members, which is a good thing.

edit: I missed the obvious answer: Collection does not have a get( int index ) method.
Offline zingbat

Senior Member




Java games rock!


« Reply #42 - Posted 2006-10-10 21:06:17 »

What a suprise. So ArrayList is far from being as fast as people dreamed of.

I found an interesting book chapter about OO code performance optimization here:
http://gee.cs.oswego.edu/dl/oosdw3/ch25.html

Initialy come from this article:
http://www.cs.cmu.edu/~jch/java/speed.html

"Give me a wee while and I'll knock up a version that implements java.util.Collection"

Why not creating a collection wraper on Bag instead of making it implement the Collection interface?

I have eard that using interfaces will make method calls a bit slower, but i have also eard the javac -O will make this irrelevant.

PS: Also if the Bag class is made final it may become a tad faster.
Offline cylab

JGO Ninja


Medals: 38



« Reply #43 - Posted 2006-10-10 21:22:48 »

bleb that new version is even nicer, it can now completely replace ArrayList, Bag looks to becoming the ultimate gaming collection Smiley

btw not sure about this but couldn't you change

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
public boolean removeAll( Collection<?> c )
{
      boolean changed = false;

      Iterator<?> iter = c.iterator();
      while( iter.hasNext() )
      {
         changed |= remove( iter.next() );
      }

      return changed;
}


to

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
public boolean removeAll(Collection<?> c) 
{
     
   boolean changed = false;      

   for (int i = 0; i < c.size(); i++) {
      changed |= remove(c.get(i));
   }

   return changed;
}


if it is correct it would avoid creating an iterator which might be faster.

I think the best of both worlds would be:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
public boolean removeAll(Collection<?> c) 
{
     
   boolean changed = false;      
   Iterator<?> iter = c.iterator();
   int l= c.size();

   for (int i = 0; i < l; i++)
   {
      changed |= remove( iter.next() );
   }

   return changed;
}


that would at least avoid the hasNext checks...

Mathias - I Know What [you] Did Last Summer!
Offline fletchergames

Senior Member





« Reply #44 - Posted 2006-10-10 22:32:32 »

Bag is buggy.  When I plugged it into an existing game instead of the ArrayLists I was using, it stopped working.  All I used it for was the following: add elements to the Bag, iterate over the elements in the Bag, and sometimes remove an element using the iterator.  I verified that it was after I removed the an element that the game started crashing, but I don't see what the problem is.  I did not create a minimal test case where this occurs, so I don't know if you'll be able to reproduce the bug.

The clear method should be changed to check for the condition where the Bag is empty.  Otherwise, calling the clear method on an empty Bag causes an IllegalArgumentException in the Arrays call.

What good's the indexOf method?  There's no get method to use the index.  I think it's best that it doesn't have a get method because this forces the person using the Bag class to use an Iterator.  Using an Iterator preserves the conception that the Bag is a bag of unordered elements, not an array.

I did write one additional method: getRandomElement().  I believe this is a useful method that preserves the Bag concept, unlike a general get method.

I attached my version of Bag, which is basically the same as the previous except for the bug fix and the additional method.  I also sorted the methods alphabetically and put the inner class and the variables at the bottom (since they're private anyways).

Seeing this Bag class suggests to me that we could write our own public domain classes that anyone on the Java Games Forum could modify.  This would result in some nice open source code.  When mixing the Bag class with my own code, I stored it in the jgf.util package.  The "jgf" package could be the standard package for code from the Java Games Forum if we ever started writing public domain classes with any frequency.
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #45 - Posted 2006-10-11 03:20:12 »

Quote
Bag is buggy

As I said, untested Roll Eyes Quick someone! Keep the community data-structure effort going and write some unit tests!

As to the indexOf() method, I agree that it should be made private, else users may be tempted to save the index for use at a later time when it may be wrong. With the getRandomElement method, may I suggest that you also add a version that takes a Random object as an argument, so repeatable behaviour can be had if desired?
Online Riven
« League of Dukes »

JGO Overlord


Medals: 741
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #46 - Posted 2006-10-11 11:15:34 »

This:
1  
2  
3  
4  
5  
6  
7  
8  
9  
public E remove( int index )
{
   E o = array[ index ];
   array[ index ] = array[ size ];
   array[ size ] = null;
   size--;

   return o;
}


Should be:
1  
2  
3  
4  
5  
6  
7  
8  
9  
public E remove( int index )
{
   size--;
   E o = array[ index ];
   array[ index ] = array[ size ];
   array[ size ] = null;

   return o;
}


as 'size' is the amount of objects in the bag, so array[size] is either array.length (ArrayIndexOutOfBounds) or null (the one after the last object)


Disclaimer: I didn't run/test anything.

oNyx version didn't have this bug BTW.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline pepijnve

Junior Member




Java games rock!


« Reply #47 - Posted 2006-10-11 14:09:58 »

Here's a version with all the previously mentioned fixes and a test class.
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #48 - Posted 2006-10-11 15:09:44 »

This is going well isn't it? Smiley

Find attached yet another version that:

Fixes the attribution, so mad props go to oNyx as they should
Added a get( index ) method, so random access is possible
Added a warning in the javadocs of indexOf(), to the effect that indices can change at any time.

I had half a mind to make all the methods that expose access to the underlying array (indexOf(), get( index ), remove( index ) ) private, as they widen the scope for user error, but I think pragmatism wins out here - random access is too useful.
Anyone who is already straying from the cradle of java.util can presumably handle the risk.
Offline pepijnve

Junior Member




Java games rock!


« Reply #49 - Posted 2006-10-11 15:42:34 »

Personally I would leave the random access stuff out. I can't say I see the point with this kind of data structure:
  • get(int): not sure what this would give you besides slightly faster iteration (since you don't have to create an iterator).
  • remove(int): you need to call indexOf to find the correct index, so this is as fast/slow as remove(Object)
  • indexOf(): only seems useful for the above two methods. contains(Object) already provides the only other usage I come up with.
Offline oNyx

JGO Coder


Medals: 1


pixels! :x


« Reply #50 - Posted 2006-10-11 15:47:03 »

Nice nice Smiley

But I dont like indexOf in its current state, because branching around in the loop is slower than doing it only once (with two loops). So... like:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
public int indexOf(Object o){
   if(o!=null){
      for(int i=0;i<size;i++){
         if(o.equals(array[i]){
            return i;
         }
      }
   }else{
      for(int i=0;i<size;i++){
         if(array[i]==null){
            return i;
         }
      }
   }
   return -1;
}


And get(int) and remove(int) are fine... see my example loops (main method of the very first Bag class).

弾幕 ☆ @mahonnaiseblog
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #51 - Posted 2006-10-11 16:19:51 »

Nice nice Smiley

But I dont like indexOf in its current state, because branching around in the loop is slower than doing it only once (with two loops). So... like:

Fair enough, change made.

As to get( index ) and remove( index ), they are needed for random access, as in fletchergames' getRandomElement() method.
I'm coming round to thinking that indexOf() can only cause harm though. The user can only safely use the returned index immediately to remove an element, so they may as well have used remove( Object ).

I'll privatise it for now, can anyone think of a use case where it's needed?
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #52 - Posted 2006-10-11 18:27:30 »

Seeing the discussion with much interest.

What about opening a sourceforge project for collecting all the jgf's community code ?

I could copy the few classes that I have in OpenMali (https://www.openmali.org/) and we could include additionally this Bag class and RIven's precomputed sin/cos and so on..

Of course it's just a beginning..there would be regular releases for big games and 4k games could just grab the latest source of any file they'd need. And of course, credits are due to anyone who contributed, in date order..

So what'd you think ?

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #53 - Posted 2006-10-11 18:32:38 »

Hmm... seems like Orangy Tang already had the same idea, see : http://www.java-gaming.org/forums/index.php?topic=15060.0

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline CommanderKeith
« Reply #54 - Posted 2006-10-12 06:02:01 »

I'll privatise it for now, can anyone think of a use case where it's needed?

Let's not make it private since as you said, there's no point protecting me from my own stupidity when I use Bag & do a remove() during a loop that does get().

Also I assume most of us still use
for(inti=0;i<list.size();i++){
 list.get(i).doStuff();
}
so making Bag to have the same get(int) method would be ideal.

I often do remove() during a loop of get()'s.  For example:
for(int i=0;i<list.size();i++){
 if (list.get(i).isDead()){
  remove(i);
 }
}

Short of using an iterator, I suppose for a Bag we could now loop thru from the back & it'd be doing the same thing as looping forward thru an ArrayList.  So for a Bag it'd be:
for(int i=list.size() - 1; i >= 0; i--){
 if (list.get(i).isDead()){
  remove(i);
 }
}



Offline oNyx

JGO Coder


Medals: 1


pixels! :x


« Reply #55 - Posted 2006-10-12 07:01:47 »

And there you shot yourself in the foot... Smiley

The first remove should be like remove(i--), because the last one gets this slot after the remove and it needs to be checked, too. Same goes for ArrayList, but its the next one which gets this slot and not the last one.

In reverse order its ok, because it doesnt matter what happens with the already checked elements.

弾幕 ☆ @mahonnaiseblog
Offline CommanderKeith
« Reply #56 - Posted 2006-10-12 07:47:54 »

That's the point I was trying to get across - the forward-loop that we'd normally do in an ArrayList won't work for Bag, but a backwards loop is OK. 

[I wonder if we should change Bag so that the forward-loop works fine like it does with  ArrayList.  So when we remove(i) it takes one from the front and puts it at i.  index Zero will still be the 'first' in the list, but it could be stored in the back of the array.  That way the forward loop-thru would work but the backwards one wouldn't. 

This might save some re-factoring when converting between ArrayList & Bag...? ]

On second thought, I don't think that'd work...there goes my foot   Tongue

Offline oNyx

JGO Coder


Medals: 1


pixels! :x


« Reply #57 - Posted 2006-10-12 08:25:50 »

That forward loop would be equally wrong with an ArrayList (as I said).

But its a minor (unsually not visible) glitch. If there are 2 "dead" ones the first one will be removed and the next one during the next iteration. If there are 4, 2 will be removed and 1 during the next iteration and the remaining one in the iteration after that. So... its not a horrible mistake to make. Maybe its even benefitical, because the (slow) shifting will be spread across several frames.

edit: With Bag its of course just silly, because there is no heavy remove penality.

弾幕 ☆ @mahonnaiseblog
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #58 - Posted 2006-10-12 10:29:18 »

I'll privatise it for now, can anyone think of a use case where it's needed?

Let's not make it private since as you said, there's no point protecting me from my own stupidity when I use Bag & do a remove() during a loop that does get().

You misunderstand. get( index ) and remove( index ) are still public, but indexOf( Object ) is not. I can't think of a case where it is needed (remove( indexOf( o ) ) can be replaced by remove( o ), and get( indexOf( o ) )... well, there are easier ways... Roll Eyes ). Exposing indexOf() will, AFAICS, just encourage people to save the indexes for later use, when they may very well be erroneous.

I don't really understand this animosity towards using Iterators. Is it really a bottleneck?
Offline pepijnve

Junior Member




Java games rock!


« Reply #59 - Posted 2006-10-12 11:27:01 »

I don't really understand this animosity towards using Iterators. Is it really a bottleneck?
I was wondering the same thing. Loops like the ones above seem pretty error prone. Removing items from a collection while iterating over it seems a lot more natural to me using an Iterator. I use the for(Smiley statement in my code all the time and it's never been a cause of performance problems so far...
Pages: 1 [2] 3
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (31 views)
2014-07-18 06:55:21

Zero Volt (27 views)
2014-07-17 23:47:54

danieldean (23 views)
2014-07-17 23:41:23

MustardPeter (24 views)
2014-07-16 23:30:00

Cero (39 views)
2014-07-16 00:42:17

Riven (41 views)
2014-07-14 18:02:53

OpenGLShaders (28 views)
2014-07-14 16:23:47

Riven (28 views)
2014-07-14 11:51:35

quew8 (25 views)
2014-07-13 13:57:52

SHC (61 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!