This site requires JavaScript, please enable it in your browser!
Greenfoot back
MrBradley
MrBradley wrote ...

2017/12/17

Is the order of adding and removing similar Actors at the same location deterministic?

MrBradley MrBradley

2017/12/17

#
If I have an actor placing a stack of other actor objects at the same location in the world, will this work like a stack if the objects are then picked up - in a First In Last Out order? Is the getObjectsAt() method deterministic? I would like to be able to pick up the last one put down. I have run some simple tests and this does not appear to be the case. Thanks.
danpost danpost

2017/12/17

#
How will you be picking the objects up? and what exactly do you mean by "pick up"?
MrBradley MrBradley

2017/12/18

#
Our main actors have pick/put methods that are used to remove/add other prop actors in worlds. Main actor = washer; minor actor = plate. The testing I do is: washer.putPlate(); // #1 washer.putPlate(); // #2 washer.putPlate(); // #3 washer.pickPlate(); // #2 washer.pickPlate(); // #1 washer.pickPlate(); // #3 with the results being different each time it is run. Where putPlate adds a plate actor to the world - addObject( plate, x,y ) and pickPlate removes one plate actor from the world - getOneObjectAtOffset( x, y); remove(plate); both at the current location of the washer. I am trying to demo the Stack data structure in our classroom scenario.
danpost danpost

2017/12/18

#
The 'getObjectsAt' method is not documented to be deterministic, meaning that you can currently find some order in the returned list, it may not be there in another version of greenfoot (or in a future version). That being said, it is probably best to have a Stack actor at each location where plates are being placed and have the plates added to the stack by way of the Stack object so it can track the order of plates at its location. Removing a plate will also will be done by way of the Stack object.
davmac davmac

2017/12/19

#
Is the getObjectsAt() method deterministic?
I think you mean something different to "deterministic". Its behaviour is deterministic, because if you always run the same sequence of operations you will always get the same result. However, it does not return objects in any sort of externally meaningful order (and certainly not in the order that they were placed in the world). To put it another way, you can expect getObjectsAt() to do what its documentation says it will do - no more and no less. Since it doesn't prescribe any order for the returned objects, you shouldn't rely on any order. The actual order depends on internal implementation details (which are complicated, and which are also liable to change between Greenfoot versions, as danpost also says). From the other thread:
I'm wondering what performance improvements are gained by hashing (?) the actors into the set/list vs adding them either FIFO or FILO orders. Any way to specify a different collect class at runtime?
I'm not sure I understand the question - are you asking about what Greenfoot is doing, or something that you are thinking of doing? To be clear about Greenfoot's behaviour, it uses a complex data structure which divides the world dynamically into different areas, and for each area maintains a set (actually stored as a map) of actors in that area. When an actor is moved, its map entry in each area which it overlaps must potentially be removed, and the use of a HashMap allows that to be done efficiently (without searching linearly through list). A HashMap does not maintain the ordering of entries added into it, and so the collision check methods in Greenfoot return lists of actors that are not in any specific order. There is no way to specify that a different type of map (other than a HashMap) be used for the purpose described above. It's considered an implementation detail.
MrBradley MrBradley

2017/12/19

#
By deterministic, I mean that given the same input and operations, the outputs would be the same or predictable (ie, not random), but I understand your point. I see the that order was not prescribed. It just caught me by surprise when I was demonstrating it. While thinking over the benefits of HashMaps and more generally about GF and came up with much the same reasoning for its use. I was wondering if your implementation would still perform well if one used the x,y coord as the key to the hashmap then maintained an ordered list for the objects at that location? I recall this from my Comp Sci days... Are you using a n-ary tree based hashmap? Thanks for taking the time to respond and satisfy my curiosity. :)
davmac davmac

2017/12/19

#
I was wondering if your implementation would still perform well if one used the x,y coord as the key to the hashmap then maintained an ordered list for the objects at that location?
The use of the map is for mapping an actor (in a region) to an actor segment, represented by an ActorNode. The javadoc for the ActorNode class pretty much explains it, so I'll paste that here: An ActorNode represents a piece (or whole) of an Actor within the IBSP collision checking tree. Because an actor can be split over several tree nodes, it may be represented by several ActorNodes, which are linked together in a linked list. So, the hashmap for a region is about getting the ActorNode which ties an actor to the region, it is not actually keyed by location at all. Using the x,y co-ordinate as a key to a HashMap storing lists of objects at that location would not be much use for implementing getObjectsAt(), because getObjectsAt() returns a list of all actors overlapping the specified location, not a list of objects that are exactly at the specified location.
Are you using a n-ary tree based hashmap?
The hashmap is a plain java.util.HashMap, it is implemented (as I understand) by mapping key objects somewhat arbitrarily to an integer index and using the index to look up value objects in an array. The regions I referred to area are actually stored in something like a k-d tree (k=2) which is a form of binary tree (when I implemented it I only was aware of Binary Space Partition trees which are more general, so it's not exactly the same as the k-d tree described by wikipedia). The tree is dynamic and splits are based on actor positions (if there are lots of actors in an area there should be lots of splits, and so lots of regions, with the idea being that 1 actor per region is ideal; however insertion of an actor doesn't cause a region to split smaller than the size of the actor, roughly speaking, in order to prevent pointless splits).
MrBradley MrBradley

2017/12/27

#
One Solution: To close this topic off for others who might be interested, I have taken the following approach: For an Actor you would like to impose an order on, use a serial # or ID field assigned by incrementing a static field. Change GF method call from getOneObjectAt(...) to getObjectsAt(...) Cycle through each element looking for the one with the largest (or smallest depending on removal order) ID, then use/remove that one. Thanks to both Dan and Davin for their suggestions.
You need to login to post a reply.