• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Enerjak

LITTLE help returning nodes recursively....

5 posts in this topic

OK, i recently decided to practice some tree building techniques before taking on data structures in school (im doing java 2 in the fall so i have time) But i want to at least know the basics...Anyways, my problem is this:

I'm trying to get the number of nodes per node by ID. you know, here's what I have

[CODE]
public Node getChildren(int id)
{
Node retNode = new Node();
if(First != null)
{
retNode = First;
First = retNode;
}
else
{
retNode = last;
last = retNode;

}
getChildren(id);
return retNode;
}
[/CODE]

now if i remove the recursive call to getChildren(id) it works but it returns the same node as many times as there are children in the node
so i have this:

[CODE]
Node root = new Node("Root");
Node child = root.addChildToBack("Eggman");
Node Child2 = root.addChildToBack("Sonic");
Node child3 = root.addChildToFront("Tails");
Node child4 = child.addChildToBack("Snively");
Node child5 = Child2.addChildToBack("Sally");

String message = "Root node has: " + root.getChildrenCount() + "\n" +
"Child Node has: " + child.getChildrenCount() + "\n" +
"Child Node 2 has: " + Child2.getChildrenCount() + "\n" +
"Child Node 3 has: " + child3.getChildrenCount() + "\n";

JOptionPane.showMessageDialog(null, message);

for(int x = 0; x < root.getChildrenCount(); x++)
{
Node c = root.getChildren(x);
JOptionPane.showMessageDialog(null, " " + c.getName());
}
[/CODE]

now, as u can see it'll get tails 3 times since that's how many children the root has. any advice?
0

Share this post


Link to post
Share on other sites
Maybe you should try to comment and explain your code a little, because frankly, I have no idea what you are even trying to do there.

You have two places where you say a=b, b=a which seems pointless as the second line would be like saying b=b.

Your function is taking a parameter id and completely ignores it, so what is the point in calling it three times with a different parameter that doesn't do anything?

You have a recursive call and completely ignore the return value. On top of that, you call it on the same node itself.

Your recursion has no apparent condition to ever abort. How does it ever return instead of just going on until you run out of memory?
0

Share this post


Link to post
Share on other sites
Well, as i said, I'm not really familiar with recursion that well, Basically I want to get all nodes based on the ID of the node like how many children it has. I want to do this recursivly but not sure how to do an abort clause for it, as i tried this:

[CODE]
public Node getChildren(int id)
{
counter = id;
if(counter > 0)
{
if(this != null)
{
return this;
}
else
{
return null;
}
}
return null;
}
[/CODE]

I suppose i could just use a vector to add nodes and get them that way, but i want to get them based on how many there are so i can print everything about them.
like root.getChildre(0).getName(), blah blah. if you need anymore please let me know what else i can give
0

Share this post


Link to post
Share on other sites
1. How should the addressing of the node(s) of interest work? The "id" parameter is compared to what kind of member? From the snippets given so far it seems me that the "id" is just an index into the first level of the tree, i.e. into the list of children of the root node. So no deeper addressing is possible. Is this intention?

2. It seems me wise to differ between a routine getChildrenRecursively and countChildrenRecursively, although the latter one can actually be implemented using the result of the former one.

3. The skeleton implementation of counting may look as follows. Due to the lack of other information, the implementation makes the assumption that addressing the node of interest is done only at the level of a given node.

[code]
public class Node {

// returning the total count of children
//
public int countChildrenRecursively() {
int result = 0;
for( Node currentChild : myChildren ) {
result = result + currentChild.countChildrenRecursively() + 1;
}
return result;
}

// returning the count of children starting with the one addressed by index
//
public int countChildrenRecursively(int index) {
int result = 0;
if( index>=0 && index<myChildren.size() ) {
result = mychildren.at(index).countChildrenRecursively() + 1;
}
return result;
}

}
[/code]

As you can see, the recursion terminates automatically at nodes that have no children, because the summation loop will not be entered in such cases.

4. Having a routine that returns a collection of nodes ... well, may be meaningful or may be not. Notice that such a routine does a flattening on a sub-tree. In principle it would be sufficient to return the addressed nodes itself, because all the other nodes of interest are naturally linked to it. E.g.

[code]
public class Node {

public Node getChild(int index) { ... }

}
[/code]

If you actually want to flatten the sub-tree, then recursion is actually your friend. However, it means that you have a [i]collection[/i] of nodes to return. Moreover, you obviously have to deal with a single collection for all children. The easiest way would be by providing the collection as parameter. E.g.

[code]
public class Node {

public void collectChildrenRecursively(List<Node> collector) {
if( collector == null ) {
throw new NullPointerException();
}
for( Node currentChild : myChildren ) {
currentChild.collectChildrenRecursively( collector );
collector.add( currentChild );
}
}

}
[/code]

The above solution adds the current child behind the children of the current child, and hence does a [url="http://en.wikipedia.org/wiki/Depth-first_search"]deep-first[/url] traversal.


/* all code above is untested */ Edited by haegarr
0

Share this post


Link to post
Share on other sites
thanks i'll keep looking, your advice helped me a lot and i may even do it that way but i'll keep looking.
0

Share this post


Link to post
Share on other sites
From what I can tell, and it has been a while dealing with Java, but your for loop where you use getChildrenCount() should be in your getChildren statement. I'll give a shot at offering some pseudo-code mixed with the Java you have:

[code]
public Node getChildren(Node parentNode)
{
// You wanted to print the names
JOptionPane.showMessageDialog(null, " " + parentNode.getName());

// Then get the child nodes
// For each child node...
for(int x = 0; x < parentNode.getChildrenCount(); x++)
{
// Here's the recursion. This only gets called when getChildrenCount() is greater than 0, thus it does end at some point.
// This passes the child node at index "x" as the new parent node
getChildren(parentNode.getChildren(x));
}
}[/code]

Then replace your whole for loop in the main part of your program with a call to getChildren(root).
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0