Panda3D
|
00001 // Filename: findApproxLevelEntry.cxx 00002 // Created by: drose (13Mar02) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "findApproxLevelEntry.h" 00016 #include "nodePathCollection.h" 00017 #include "pandaNode.h" 00018 #include "indent.h" 00019 00020 TypeHandle FindApproxLevelEntry::_type_handle; 00021 00022 //////////////////////////////////////////////////////////////////// 00023 // Function: FindApproxLevelEntry::output 00024 // Access: Public 00025 // Description: Formats the entry for meaningful output. For 00026 // debugging only. 00027 //////////////////////////////////////////////////////////////////// 00028 void FindApproxLevelEntry:: 00029 output(ostream &out) const { 00030 out << "(" << _node_path << "):"; 00031 if (is_solution(0)) { 00032 out << " solution!"; 00033 } else { 00034 out << "("; 00035 _approx_path.output_component(out, _i); 00036 out << ")," << _i; 00037 } 00038 } 00039 00040 //////////////////////////////////////////////////////////////////// 00041 // Function: FindApproxLevelEntry::write_level 00042 // Access: Public 00043 // Description: Writes the entire level (a linked list of entries 00044 // beginning at this entry). For debugging only. 00045 //////////////////////////////////////////////////////////////////// 00046 void FindApproxLevelEntry:: 00047 write_level(ostream &out, int indent_level) const { 00048 for (const FindApproxLevelEntry *entry = this; 00049 entry != (const FindApproxLevelEntry *)NULL; 00050 entry = entry->_next) { 00051 indent(out, indent_level); 00052 out << *entry << "\n"; 00053 } 00054 } 00055 00056 //////////////////////////////////////////////////////////////////// 00057 // Function: FindApproxLevelEntry::consider_node 00058 // Access: Public 00059 // Description: Considers the node represented by the entry for 00060 // matching the find path. If a solution is found, it 00061 // is added to result; if the children of this node 00062 // should be considered, the appropriate entries are 00063 // added to next_level. 00064 // 00065 // The return value is true if result now contains 00066 // max_matches solutions, or false if we should keep 00067 // looking. 00068 //////////////////////////////////////////////////////////////////// 00069 bool FindApproxLevelEntry:: 00070 consider_node(NodePathCollection &result, FindApproxLevelEntry *&next_level, 00071 int max_matches, int increment) const { 00072 if (is_solution(increment)) { 00073 // If the entry represents a solution, save it and we're done with 00074 // the entry. 00075 result.add_path(_node_path.get_node_path()); 00076 if (max_matches > 0 && result.get_num_paths() >= max_matches) { 00077 return true; 00078 } 00079 00080 return false; 00081 } 00082 00083 // If the entry is not itself a solution, consider its children. 00084 00085 if (_approx_path.is_component_match_many(_i + increment)) { 00086 // Match any number, zero or more, levels of nodes. This is the 00087 // tricky case that requires this whole nutty breadth-first thing. 00088 00089 // This means we must reconsider our own entry with the next path 00090 // entry, before we consider the next entry--this supports 00091 // matching zero levels of nodes. 00092 00093 // We used to make a temporary copy of our own record, and then 00094 // increment _i on that copy, but we can't do that nowadays 00095 // because the WorkingNodePath object stores a pointer to each 00096 // previous generation, which means we can't use any temporary 00097 // FindApproxLevelEntry objects. Instead, we pass around the 00098 // increment parameter, which increments _i on the fly. 00099 00100 if (consider_node(result, next_level, max_matches, increment + 1)) { 00101 return true; 00102 } 00103 } 00104 00105 PandaNode *this_node = _node_path.node(); 00106 nassertr(this_node != (PandaNode *)NULL, false); 00107 00108 bool stashed_only = next_is_stashed(increment); 00109 00110 if (!stashed_only) { 00111 // Check the normal list of children. 00112 PandaNode::Children children = this_node->get_children(); 00113 int num_children = children.get_num_children(); 00114 for (int i = 0; i < num_children; i++) { 00115 PandaNode *child_node = children.get_child(i); 00116 00117 consider_next_step(child_node, next_level, increment); 00118 } 00119 } 00120 00121 if (_approx_path.return_stashed() || stashed_only) { 00122 // Also check the stashed list. 00123 int num_stashed = this_node->get_num_stashed(); 00124 for (int i = 0; i < num_stashed; i++) { 00125 PandaNode *stashed_node = this_node->get_stashed(i); 00126 00127 consider_next_step(stashed_node, next_level, increment); 00128 } 00129 } 00130 00131 return false; 00132 } 00133 00134 //////////////////////////////////////////////////////////////////// 00135 // Function: FindApproxLevelEntry::consider_next_step 00136 // Access: Public 00137 // Description: Compares the indicated child node (which is assumed 00138 // to be a child of _node_path) with the next component 00139 // of the path. If it matches, generates whatever 00140 // additional entries are appropriate and stores them in 00141 // next_level. 00142 //////////////////////////////////////////////////////////////////// 00143 void FindApproxLevelEntry:: 00144 consider_next_step(PandaNode *child_node, FindApproxLevelEntry *&next_level, 00145 int increment) const { 00146 nassertv(child_node != _node_path.node()); 00147 00148 if (!_approx_path.return_hidden() && child_node->is_overall_hidden()) { 00149 // If the approx path does not allow us to return hidden nodes, 00150 // and this node has indeed been completely hidden, then stop 00151 // here. 00152 return; 00153 } 00154 00155 nassertv(_i + increment < _approx_path.get_num_components()); 00156 00157 if (_approx_path.is_component_match_many(_i + increment)) { 00158 // Match any number, zero or more, levels of nodes. This is the 00159 // tricky case that requires this whole nutty breadth-first thing. 00160 00161 // And now we just add the next entry without incrementing its 00162 // path entry. 00163 00164 next_level = new FindApproxLevelEntry 00165 (*this, child_node, _i + increment, next_level); 00166 00167 } else { 00168 if (_approx_path.matches_component(_i + increment, child_node)) { 00169 // That matched, and it consumes one path entry. 00170 next_level = new FindApproxLevelEntry 00171 (*this, child_node, _i + increment + 1, next_level); 00172 } 00173 } 00174 }