I propose a method
Node {
public Spatial getDescendant(String name);
}
As jME encourages one to use unique names for Spatials, it just makes sense to provide a method to make use of the useful consequence of this convention. No problem if the scene happens to not have unique names-- it would just return the first node found (JavaDoc will specify whether that is depth-first or depth-last). If there is no such descendant, return null.
I'm coding one up for my TestDotScene example right now, but the usefulness is pretty general: If I want to manipulate the controller for the Spatial named "x", I really don't care where it is in the scene graph:
[s]Controller c = rootNode.getDescendant("x");[/s]
CORRECTION:
Controller c = rootNode.getDescendant("x").getController(0);
You can see exactly what I intend at the bottom of jmetest.ogerxml.TestDotScene.simpleInitGame(). Only difference there is, I have to pass the ancestor Node, since I am not implementing a Node instance method as I propose.
Hi!
blaine said:
JavaDoc will specify whether that is depth-first or depth-last
If you need to implement the breadth-first search or the depth-first search to add your new method, it would be fine to make it as general as possible and to separate your method and the BFS/DFS so that someone else can use these searches for other operations. I wrote some very general classes to handle these searches, I might have to add them into JME when my feature is ready and it would be stupid to have two non trivial pieces of code that perform a very similar operation.
To be consistent with the getChild() methods, shouldn't it be named Node.getController(String name);?
And wouldn't a descendant rather mean a subclass of Node?
There are already the Methods:
Spatial getChild(int i)
Spatial getChild(String name)
List<Spatial> getChildren()
Controller getController(int i)
int getControllerCount()
ArrayList<Controller> getControllers()
blaine said:
...
I'm coding one up for my TestDotScene example right now, but the usefulness is pretty general: If I want to manipulate the controller for the Spatial named "x", I really don't care where it is in the scene graph:
Controller c = rootNode.getDescendant("x");
I don't understand you. Is this what you want?
Node n = rootNode.getDescendant("x");
Controller c = n.getController();
gouessej said:
Hi!
blaine said:
JavaDoc will specify whether that is depth-first or depth-last
If you need to implement the breadth-first search or the depth-first search to add your new method, it would be fine to make it as general as possible and to separate your method and the BFS/DFS so that someone else can use these searches for other operations. I wrote some very general classes to handle these searches, I might have to add them into JME when my feature is ready and it would be stupid to have two non trivial pieces of code that perform a very similar operation.
WRT the BFS/DFS decision, no problem there. I just add a boolean bfs param, with a convenience wrapper with it defauting to one of the two (since in 9/10 cases the user won't care). I actually planned on doing this, but didn't want to obscure the primary purpose in this discussion.
WRT generalizing farther, I've been coding these spatial recursions for years, and I find that due to practicalities of Java, this get-Spatial part is the only piece that is needed over and over. If you could pass an anonymous (non-instance) method in Java, as you can in most programming languages, it would make sense to code a recursive
visitor method, but the requirement to pass an instance of an implementation makes for some hideous code to accomplish the same thing with Java. Could well be that you have some generalization idea that hasn't occurred to me. If so, post an example and I'll be happy to learn.
Haladria said:
blaine said:
...
I'm coding one up for my TestDotScene example right now, but the usefulness is pretty general: If I want to manipulate the controller for the Spatial named "x", I really don't care where it is in the scene graph:
Controller c = rootNode.getDescendant("x");
I don't understand you. Is this what you want?
Node n = rootNode.getDescendant("x");
Controller c = n.getController();
Sorry. Didn't type what was in my brain. I'll correct my original entry below.
Core-Dump said:
To be consistent with the getChild() methods, shouldn't it be named Node.getController(String name);?
And wouldn't a descendant rather mean a subclass of Node?
There are already the Methods:
Spatial getChild(int i)
Spatial getChild(String name)
List<Spatial> getChildren()
Controller getController(int i)
int getControllerCount()
ArrayList<Controller> getControllers()
Sorry CD. I didn't type what I meant. Please see revised first post in this topic.
Core-Dump said:
...
And wouldn't a descendant rather mean a subclass of Node?
There are already the Methods:
Spatial getChild(int i)
Spatial getChild(String name)
List<Spatial> getChildren()
...
The meaning of
descendant is an exact extension of the parent/child Spatial metaphor that all of us understand. None of us confuse
child with subclass.
Just as one's granddaughter is not their child, neither is a Spatial 2 levels down from X, a child of X.
Just as a granddaughter may be a parent, so may my getDescendant Spatial be a Node.
But isn't it the same as Node.getChild(String name)?
It also searches recursively for the first spatial with the given name.
If so, then I revise this Topic to just be a proposal to correct the JavaDocs for getChild(String). I am being pulled away from computer and can't try now.
… You know, I had a vague recollection that I had tested and found that out about a year ago, but I checked the Javadoc three times before I submitted this Topic, and it clearly says "child" with no indication of recursion, nesting, grandchildren, descendant, etc., and is in no way differentiated in this respect from the peer getChild(int) method which is not recursive.
Verified. Thanks for pointing this out, Core-Dump.
I think Spatial.getChild() should be deprecated, deferring to Spatial.getDescendant() (which would do the exact same thing), because
- The name getChild() is misleading, because it says that it will return a child when it actually returns a descendant.
- It is bad to introduce recursion in an API without making that very clear. I, and probably most, have been under the impression that if my this Node does not have a child named "x", then getChild"x" would quickly return null. Example: I want to check if rootNode contains "Ninja". I do not expect that getChild() will recurse through my entire graph, including TerrainPages if rootNode does not contain a Ninja child.
It would be good to have a Node.getChild(String) which does just that, but I'd be afraid of changing behavior in such a drastic way (i.e. to make it return a child instead of a descendant).
Here is my BFS & DFS source code:
private static abstract class Visitor{
/**
* Cell that is visited at first
*/
private Cell firstVisitedCell;
/**
* Cell that is currently visited
*/
private Cell currentlyVisitedCell;
/**
* abstract data type used to store the sons of the current cell
*/
private List<Cell> cellsList;
/**
* Each cell that has been seen has to be marked to avoid an infinite loop
* (by visiting the same cell more than once)
*/
private List<Cell> markedCellsList;
/**
* Prepare the visit of the whole network by beginning with the root cell
* @param network: visited network
*/
private Visitor(Network network){
this(network.children!=null?(Cell)network.children.get(0):null);
}
/**
* Prepare the visit of the whole network by beginning with the provided cell
* @param firstVisitedCell: cell that is visited at first
*/
private Visitor(Cell firstVisitedCell){
this.firstVisitedCell=firstVisitedCell;
this.currentlyVisitedCell=null;
this.cellsList=new ArrayList<Cell>();
this.markedCellsList=new ArrayList<Cell>();
}
/**
* Starts the visit (not thread-safe)
*/
final boolean visit(){
return(visit(this.firstVisitedCell));
}
/**
*
* @param firstVisitedCell
* @return true if the network has been fully visited, otherwise false
*/
final boolean visit(Cell firstVisitedCell){
clearInternalStorage();
this.firstVisitedCell=firstVisitedCell;
if(firstVisitedCell!=null)
{markedCellsList.add(firstVisitedCell);
cellsList.add(firstVisitedCell);
}
boolean hasToContinue=true;
Portal portal;
Cell son;
while(!cellsList.isEmpty())
{//Get the next element (pop operation)
currentlyVisitedCell=cellsList.remove(getNextCellIndex());
//This is the main treatment
if(hasToContinue=performTaskOnCurrentlyVisitedCell())
for(int i=0;i<currentlyVisitedCell.getPortalCount();i++)
{portal=currentlyVisitedCell.getPortalAt(i);
son=portal.getCellAt(0).equals(currentlyVisitedCell)?portal.getCellAt(1):portal.getCellAt(0);
if(!markedCellsList.contains(son))
{//Mark the cell to avoid traveling it more than once
markedCellsList.add(son);
if(hasToPush(son,portal))
{//Add a new cell to travel (push operation)
cellsList.add(son);
}
}
}
else
break;
}
return(hasToContinue);
}
protected void clearInternalStorage(){
this.currentlyVisitedCell=null;
this.cellsList.clear();
this.markedCellsList.clear();
}
protected abstract int getNextCellIndex();
/**
* Allows to perform a task on the currently visited cell.
* Each cell is visited at most once per visit.
* @return true if the visit has to go on, otherwise the visit is stopped
*/
protected abstract boolean performTaskOnCurrentlyVisitedCell();
/**
* Allows to perform a test on the currently visited son of the visited cell.
* @return true if this son has to be pushed
*/
protected boolean hasToPush(Cell son,Portal portal){
return(true);
}
protected final Cell getCurrentlyVisitedCell(){
return(currentlyVisitedCell);
}
protected final List<Cell> getCellsList(){
return(Collections.unmodifiableList(cellsList));
}
protected final List<Cell> getMarkedCellsList(){
return(Collections.unmodifiableList(markedCellsList));
}
}
private static abstract class BreadthFirstSearchVisitor extends Visitor{
private BreadthFirstSearchVisitor(Network network){
super(network.children!=null?(Cell)network.children.get(0):null);
}
private BreadthFirstSearchVisitor(Cell firstVisitedCell){
super(firstVisitedCell);
}
/**
* The internal list is used as a FIFO
*/
@Override
protected final int getNextCellIndex(){
return(0);
}
}
The DFS has only a getNextCellIndex method that returns the last index. I have put some abstract methods to insert some operations during the search to allow lots of specializations. My main aim was to avoid rewriting the BFS several times or copy/paste the same code. The whole source code is here:
https://tuer.svn.sourceforge.net/svnroot/tuer/tuer/jme/Network.java
The abstract methods here might get useless until you want to treat very complex cases. I think that my source code can be simplified as JME 2 uses only trees where the source code above supports graphs. Finally, it would be fine only to have something that keeps the same idea, a very general visitor.
blaine said:
Verified. Thanks for pointing this out, Core-Dump.
I think Spatial.getChild() should be deprecated, deferring to Spatial.getDescendant() (which would do the exact same thing), because
- The name getChild() is misleading, because it says that it will return a child when it actually returns a descendant.
- It is bad to introduce recursion in an API without making that very clear. I, and probably most, have been under the impression that if my this Node does not have a child named "x", then getChild"x" would quickly return null. Example: I want to check if rootNode contains "Ninja". I do not expect that getChild() will recurse through my entire graph, including TerrainPages if rootNode does not contain a Ninja child.
It would be good to have a Node.getChild(String) which does just that, but I'd be afraid of changing behavior in such a drastic way (i.e. to make it return a child instead of a descendant).
Sometimes you can use the word child not only for the next generation och children but all generations below you.
gouessej said:
Here is my BFS & DFS source code:
...
I have classes like that too, but that is extremely heavy-weight for the very common case where you want to do something to a single spatial. For this situation, I shouldn't have to implement, instantiate, or subclass anything. My getDescendant() method is 12 lines, and that is with extra tests for nulls and such.
But, I have Spatial.getChild(String) now anyways.
Haladria said:
blaine said:
Verified. Thanks for pointing this out, Core-Dump.
...
Sometimes you can use the word child not only for the next generation och children but all generations below you.
Good point. In domains where precision has an important impact, such as science and programming, care should be taken to clarify ambiguities like that. Having two peer methods getChild(int) and getChild(String) which implement conflicting connotational definitions is extremely ambiguous.
blaine said:
Haladria said:
blaine said:
Verified. Thanks for pointing this out, Core-Dump.
...
Sometimes you can use the word child not only for the next generation och children but all generations below you.
Good point. In domains where precision has an important impact, such as science and programming, care should be taken to clarify ambiguities like that. Having two peer methods getChild(int) and getChild(String) which implement conflicting connotational definitions is extremely ambiguous.
Yes, it should definitely be mentioned in the javadoc.