Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (121)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Working with a custom General Tree... advice needed.  (Read 726 times)
0 Members and 1 Guest are viewing this topic.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Posted 2006-04-18 03:55:56 »

I have a game that uses an AI to find the fastest route from one Wikipedia page to another by cycling through links. This StorageTree does all of the logic, for the most part, and works except for one problem. Wikipedia is immense, and so recursive page loading effectively does not end until the goal is found or the timeout is reached. I'm fine with that, it's all neccessary, of course, but there is one problem:

Currently as elements are added to my tree they are added in preorder - from the leftmost childnode to the parent nodes and finally to the right nodes. The problem is that I want to add pages on a levelorder basis so that I check every link on a site before moving on to sites further away from the original root. Basically I want to add items in the order of their depths in the tree, rather than the usual recursive way to do things.

I've thought of a few ways to do this, but this obviously needs to be efficient so it can juggle the most pages at once, and the ways I was thinking of involve a lot of wasted memory. Anyone have any ideas?

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
/**
 * The StorageTree is used by WikiRipper to save all possible moves
 * in an efficient and easily accessible manner. It is a basic general
 * tree with an array of nodes to each leaf. These nodes represent each
 * article, and their next nodes are all articles they are linked to. Upon
 * creation, the StorageTree constructs itself using timeout, start, and end
 * provided by the WikiRipper.
 * @author Eli Delventhal
 *
 */


import java.util.LinkedList;
import java.util.TreeSet;
import java.util.Iterator;

public class StorageTree implements java.io.Serializable
{
   private static final long serialVersionUID = 1L;
   private Node root;
   private int timeout;
   private long startTime;
   private String goal;
   private TreeSet added; //any article added already is put into this list
   private Node found; //if this node is not null then a goal has been found
   
   public StorageTree(int to, String start, String end)
   {
      //The start time is used to test when to stop loading
      startTime = new java.util.Date().getTime();
      added = new TreeSet();
      timeout = to; goal = end;
      root = new Node(start);
      addNode(root);
      clear();
   }
   
   /**
    * addNode is a recursive method to add this node to the tree, and then
    * it calls itself for each of the node's links.
    * @param n   The node to add
    */

   private void addNode(Node n)
   {
      //Halt in case of a timeout
      if (new java.util.Date().getTime() - startTime >= timeout*1000)
         return;
      //Halt in case the goal has been found
      if (n.data.equalsIgnoreCase(goal))
      {
         found = n;
         return;
      }
      //Halt if the goal has already been found
      if (found != null)
         return;
     
      //Get the links out and remove any that are already in the tree
      LinkedList l = getLinks(n.data);
      for (Iterator i = l.iterator(); i.hasNext();)
      {
         Object o = i.next();
         if (added != null)
         {
            if (added.contains(o))
               i.remove();
            else
               added.add(o);
         }
      }
      //Create an array to represent all links from this Node
      n.next = new Node[l.size()];
     
      //Cycle through every link and call addNode for each of
      //those Nodes, and also set their parent to this Node
      int index = 0;
      for (Iterator i = l.iterator(); i.hasNext(); index++)
      {
         n.next[index] = new Node((String)i.next());
         n.next[index].parent = n;
         addNode(n.next[index]);
      }
   }
   
   /**
    * Called after the search is over or the goal has been found,
    * clearing out all variables used.
    */

   private void clear()
   {
      added = null; //added is no longer needed, so clear it
      //Although this seems crazy, if a goal was found then there is
      //no reason to preserve any other parts of the tree.
      if (found != null)
         root = null;
      goal = null; //We don't need to know the goal anymore
      startTime = timeout = 0; //Clear startTime and timeout, uneeded
   }
   
   /**
    * Pull all the links out of an article and return them as a LinkedList.
    * @param article   The article on Wikipedia to load
    * @return   Every link found within that article
    */

   private LinkedList getLinks(String article)
   {
      LinkedList choices = new LinkedList();
      String page = ConnectionManager.loadPage(article);
      String search = "<a href=\"/wiki/";
      for (int i = 0; i < page.length() - search.length(); i++)
      {
         try
         {
            if (page.substring(i,i+search.length()).equals(search))
               choices.add(page.substring(i+search.length(),page.indexOf('\"
',i+search.length())));
         }
         catch (Exception e) {}
      }
      return choices;
   }
   
   /**
    * Returns the absolute best choice to make, but returns null if there
    * was never any goal found with the provided timeout.
    * @param location   The location to get the best choice from.
    * @return   The article of the best choice.
    */
   public String getBestChoice(String location)
   {
      if (found == null)
         return null;
      Node search = found;
      while (search.parent != null)
      {
         if (search.parent.data.equalsIgnoreCase(location))
            return search.data;
         search = search.parent;
      }
      return null;
   }
   
   /**
    * Mostly for debug reasons, this method prints the path, from the
    * found Node upwards, of the best choice.
    */
   public void printBestChoice()
   {
      if (found == null)
      {
         System.out.println("Wasn'
t found... will instead print tree.");
         printTree();
         return;
      }
      Node search = found;
      while (search.parent != null)
      {
         System.out.print(search.data + "
");
         search = search.parent;
      }
      System.out.println();
   }
   
   /**
    * Prints out the entire tree in preorder.
    */
   private void printTree()
   {
      printNode(root);
   }
   
   private void printNode(Node n)
   {
      if (n == null)
         return;
      System.out.print(n.data + "
: ");
      if (n.next == null)
         return;
      for (int i = 0; i < n.next.length; i++)
         printNode(n.next[i]);
      System.out.println();
   }
   
   private class Node
   {
      public Node[] next;
      public String data;
      public Node parent; //parent is neccessary to find the fastest path
     
      public Node(String d)
      {
         data = d;
      }
   }
}

See my work:
OTC Software
Offline Mr_Light

Senior Duke


Medals: 1


shiny.


« Reply #1 - Posted 2006-04-18 07:21:14 »

you could just hold a collection branches and iliterate once over it for every level calling foo() where foo puts more branches in the collection or removes itself (and offcourse gets the leafs)

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #2 - Posted 2006-04-18 08:18:26 »

Yeah, I was thinking that, but do you think it will get absurd or use up too much RAM? I was thinking also maybe create a Queue of String[]'s and have it enqueue every level and then dequeue them all, and don't move to a new row until the Queue is empty, but, again, the possibility of memory waste arises...

See my work:
OTC Software
Pages: [1]
  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.

theagentd (18 views)
2014-10-25 15:46:29

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (45 views)
2014-10-16 15:22:06

Norakomi (34 views)
2014-10-16 15:20:20

lcass (39 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (68 views)
2014-10-14 00:35:47

TehJavaDev (60 views)
2014-10-14 00:32:37

BurntPizza (74 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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!