Zefrieg made the suggestion that I use a graph with an associative container such as the std::map as an alternative to the dynamic 2D array. I'm obliged to say that I am quite impressed with the well thought out response Zefrieg presented. Thanks again Zefrieg. The major concern was the memory requirements needed for a "portal jump" within a world. The 2D array would unnecessarily be expanded to include the new world position. This can more efficiently be accomplished using a graph to construct the "mental map" and an std::map container to access individual nodes within the graph. You should have a look at my prior entry to see Zefrieg's rationalization.
I fashioned a generic undirected graph class and have posted the source for it and a demonstration of how to use it. Feel free to use and modify it or tell me what I did wrong. Just don't cry to me if your puter esplodes. [smile]
// ==============================================================================// ------------------------------------------------------------------------------// SOURCE NAME : UGraph.h // AUTHOR : Neil Kemp// DESCRIPTION : This module declares and defines a generic class to define and// : manipulate undirected graphs.// ------------------------------------------------------------------------------// ==============================================================================#include #ifndef ___U_GRAPH_H___#define ___U_GRAPH_H___template class UGraph{private: template struct UGraph_Node_s { T Data; std::vector<unsigned int> Adjacency_List; }; std::vector > ___Node_List; void (*___Traversal_Callback_Function_Pointer)(const T &Data); std::vector<bool> ___Traversal_Nodes_Visited_List; std::vector<bool> ___Adjacent_Nodes_Visited_List; void ___Add_Node_To_List(const T &Data); bool ___Delete_Node_From_List(unsigned int Index); bool ___Retrieve_Node_Data(unsigned int Index, T &Data_Out) const; void ___DFS(unsigned int Node_Index); void ___BFS(unsigned int Node_Index, bool Traverse_Adjacents);public: UGraph(void); unsigned int Add_Node(const T &Data); bool Add_Edge(unsigned int Node_Index_A, unsigned int Node_Index_B); bool Delete_Node(unsigned int Index); bool Delete_Edge(unsigned int Node_Index_A, unsigned int Node_Index_B); bool Get_Node_Data(unsigned int Node_Index, T &Data_Out) const; bool Get_Node_Data(unsigned int Node_Index, T &Data_Out, std::vector<unsigned int> &Adjacency_List) const; bool Get_Node_Adjacency_List(unsigned int Node_Index, std::vector<unsigned int> &Adjacency_List) const; unsigned int Get_Node_Count(void) const; void Depth_First_Search(void(*Function_Pointer)(const T &Data)); void Breadth_First_Search(void(*Function_Pointer)(const T &Data)); bool Save_To_File(FILE* File_Pointer) const; bool Load_From_File(FILE* File_Pointer);};// PRI M FUNCTION : ___Add_Node_To_List()// PARAMETERS : p0(IN) const &T - Node data of type T// RETURN VALUE : void// DESCRIPTION : Add a node to the private vector list of UGraph_Node_s // : with initialized data of type T// ------------------------------------------------------------------------------template void UGraph::___Add_Node_To_List(const T &Data){ // Create the node UGraph_Node_s Temp_Node; Temp_Node.Data = Data; // Add the node to the list ___Node_List.push_back(Temp_Node);}// End ___Add_Node_To_List()// ------------------------------------------------------------------------------// PRI M FUNCTION : ___Delete_Node_From_List()// PARAMETERS : p0(IN) unsigned int - Node index// RETURN VALUE : bool// DESCRIPTION : Delete a node from the private vector list of nodes at // : the index parameter location. Shift all adjacency indices// : which are > to the index deleted.// ------------------------------------------------------------------------------template bool UGraph::___Delete_Node_From_List(unsigned int Index){ // Check bounds of index if(Index >= ___Node_List.size()) return false; // Remove every edge referenced in the node's adjacency list size_t Adjacency_List_Size = ___Node_List[Index].Adjacency_List.size(); for(size_t i=0; i { Delete_Edge(Index, ___Node_List[Index].Adjacency_List); // Decrement the loop variable to compensate for deleted item i--; // Decrement the adjacency list size Adjacency_List_Size --; } // Get a node iterator std::vector >::iterator I = ___Node_List.begin() + Index; // Erase Node ___Node_List.erase(I); // Shift all adjacency lists for every node size_t NList_Size = ___Node_List.size(); for(size_t i=0; i { size_t AList_Size = ___Node_List.Adjacency_List.size(); for(size_t j=0; j { // Decrement the adjacency list indices if greater than deleted index if(___Node_List.Adjacency_List[j] > Index) ___Node_List.Adjacency_List[j]--; } } return true;}// End ___Add_Node_To_List()// ------------------------------------------------------------------------------// PRI M FUNCTION : ___Retrieve_Node_Data()// PARAMETERS : p0(IN) unsigned int - Node index// : p1(OUT) &T - The data reference to be returned// RETURN VALUE : bool// DESCRIPTION : Return the node data located in the node specified by the// : index parameter using an ouput parameter reference.// ------------------------------------------------------------------------------template bool UGraph::___Retrieve_Node_Data(unsigned int Index, T &Data_Out) const{ // Check bounds of index if(Index >= ___Node_List.size()) return false; // Set the data parameter to the specified data Data_Out = ___Node_List[Index].Data; return true;}// End ___Retrieve_Node_Data()// ------------------------------------------------------------------------------// PRI M FUNCTION : ___DFS()// PARAMETERS : p0(IN) unsigned int - Node index// RETURN VALUE : void// DESCRIPTION : A recursive Depth-First-Search function calls the private// : Traversal Callback Function for every node visited in the// : graph.// ------------------------------------------------------------------------------template void UGraph::___DFS(unsigned int Node_Index){ // Mark node as visited ___Traversal_Nodes_Visited_List[Node_Index] = true; // Call the traversal callback function ___Traversal_Callback_Function_Pointer(___Node_List[Node_Index].Data); // Recursive call for every unvisited adjacent node size_t Adjacency_List_Size = ___Node_List[Node_Index].Adjacency_List.size(); for(size_t i=0; i { // DFS for every unvisited adjacent node if(___Traversal_Nodes_Visited_List[ ___Node_List[Node_Index].Adjacency_List] == false) ___DFS(___Node_List[Node_Index].Adjacency_List); }}// End ___DFS()// ------------------------------------------------------------------------------// PRI M FUNCTION : ___BFS()// PARAMETERS : p0(IN) unsigned int - Node index// : p1(IN) bool - Traverse adjacent nodes or not// RETURN VALUE : void// DESCRIPTION : A recursive Breadth-First-Search function calls the private// : Traversal Callback Function for every node visited in the// : graph.// ------------------------------------------------------------------------------template void UGraph::___BFS(unsigned int Node_Index, bool Traverse_Adjacents){ // If the node is unvisited if( ___Traversal_Nodes_Visited_List[Node_Index] == false) { // Call the traversal callback function ___Traversal_Callback_Function_Pointer(___Node_List[Node_Index].Data); // Mark node as visited ___Traversal_Nodes_Visited_List[Node_Index] = true; } // Traverse adjacent nodes if(Traverse_Adjacents) { // Set the adjacent nodes have been visited ___Adjacent_Nodes_Visited_List[Node_Index] = true; // Recursive call for adjacent nodes size_t Adjacency_List_Size = ___Node_List[Node_Index].Adjacency_List.size(); for(size_t i=0; i { // DFS for every unvisited adjacent node - // the BFS call IS NOT allowed to traverse adjacent nodes if(___Traversal_Nodes_Visited_List[___Node_List[Node_Index].Adjacency_List] == false) ___BFS(___Node_List[Node_Index].Adjacency_List, false); } // Recursive call for adjacent nodes for(size_t i=0; i { // DFS for every unvisited adjacent node - // the BFS call IS allowed to traverse adjacent nodes if(___Adjacent_Nodes_Visited_List[___Node_List[Node_Index].Adjacency_List] == false) ___BFS(___Node_List[Node_Index].Adjacency_List, true); } } }// End ___BFS()// ------------------------------------------------------------------------------// PUB M FUNCTION : UGraph() CONSTRUCTOR// PARAMETERS : void// RETURN VALUE : void// DESCRIPTION : The default constructor// ------------------------------------------------------------------------------template UGraph::UGraph(void){ }// End UGraph() CONSTRUCTOR// ------------------------------------------------------------------------------// PUB M FUNCTION : Add_Node()// PARAMETERS : p0(IN) const &T - Data to initialize node with// RETURN VALUE : unsigned int - The index of the node just added// DESCRIPTION : Add a node to the graph and return the index where it can// : be accessed.// ------------------------------------------------------------------------------template unsigned int UGraph::Add_Node(const T &Data){ // Add the node ___Add_Node_To_List(Data); // Return the new node index return (unsigned int)___Node_List.size() - 1; }// End Add_Node()// ------------------------------------------------------------------------------// PUB M FUNCTION : Add_Edge()// PARAMETERS : p0(IN) unsigned int - Node index A// : p1(IN) unsigned int - Node index B// RETURN VALUE : bool// DESCRIPTION : Add an edge between two nodes located at the specified // : indices.// ------------------------------------------------------------------------------template bool UGraph::Add_Edge(unsigned int Node_Index_A, unsigned int Node_Index_B){ // Check bounds of indices if(Node_Index_A >= ___Node_List.size()) return false; if(Node_Index_B >= ___Node_List.size()) return false; // Add undirected edge between both nodes by registering // each in both nodes adjacency lists ___Node_List[Node_Index_A].Adjacency_List.push_back(Node_Index_B); ___Node_List[Node_Index_B].Adjacency_List.push_back(Node_Index_A); return true;}// End Add_Edge()// ------------------------------------------------------------------------------// PUB M FUNCTION : Delete_Node()// PARAMETERS : p0(IN) unsigned int - Node index// RETURN VALUE : bool// DESCRIPTION : Delete a node from the graph// ------------------------------------------------------------------------------template bool UGraph::Delete_Node(unsigned int Index){ // Delete the node from the list return ___Delete_Node_From_List(Index);}// End Delete_Node()// ------------------------------------------------------------------------------// PUB M FUNCTION : Delete_Edge()// PARAMETERS : p0(IN) unsigned int - Node index A// : p1(IN) unsigned int - Node index B// RETURN VALUE : bool// DESCRIPTION : Delete an edge that connects two nodes specified with the// : parameter indices.// ------------------------------------------------------------------------------template bool UGraph::Delete_Edge(unsigned int Node_Index_A, unsigned int Node_Index_B){ // Check bounds of indices if(Node_Index_A >= ___Node_List.size()) return false; if(Node_Index_B >= ___Node_List.size()) return false; // Update the adjacency lists of the two nodes // Remove references to node[index_b] in node[index_a] size_t List_Size = ___Node_List[Node_Index_A].Adjacency_List.size(); for(size_t i=0; i { // Check for references to node[index_b] in node[index_a] if(___Node_List[Node_Index_A].Adjacency_List == Node_Index_B) { // Delete reference std::vector<unsigned int>::iterator I = ___Node_List[Node_Index_A].Adjacency_List.begin() + i; ___Node_List[Node_Index_A].Adjacency_List.erase(I); // Decrement the loop variable to compensate for deleted item i--; // Decrement the list size List_Size --; } } // Remove references to node[index_a] in node[index_b] List_Size = ___Node_List[Node_Index_B].Adjacency_List.size(); for(size_t i=0; i { // Check for references to node[index_b] in node[index_a] if(___Node_List[Node_Index_B].Adjacency_List == Node_Index_A) { // Delete reference std::vector<unsigned int>::iterator I = ___Node_List[Node_Index_B].Adjacency_List.begin() + i; ___Node_List[Node_Index_B].Adjacency_List.erase(I); // Decrement the loop variable to compensate for deleted item i--; // Decrement the list size List_Size --; } } return true;}// End Delete_Edge()// ------------------------------------------------------------------------------// PUB M FUNCTION : Get_Node_Data() OVERLOADED A// PARAMETERS : p0(IN) unsigned int - Node index// : p1(OUT) &T - The returned data// RETURN VALUE : bool// DESCRIPTION : Return the node data from the node specified at the index// : parameter// ------------------------------------------------------------------------------template bool UGraph::Get_Node_Data(unsigned int Node_Index, T &Data_Out) const{ // Check bounds of index if(Node_Index >= ___Node_List.size()) return false; // Set output parameter data Data_Out = ___Node_List[Node_Index].Data; return true;}// End Get_Node_Data() OVERLOADED A// ------------------------------------------------------------------------------// PUB M FUNCTION : Get_Node_Data() OVERLOADED B// PARAMETERS : p0(IN) unsigned int - Node index// : p1(OUT) &T - The returned data// : p2(OUT) &std::vector - Returned list of // : adjacent node indices// RETURN VALUE : bool// DESCRIPTION : Return the node data and the list of adjacent node indices// : from the node specified at the index parameter.// ------------------------------------------------------------------------------template bool UGraph::Get_Node_Data(unsigned int Node_Index, T &Data_Out, std::vector<unsigned int> &Adjacency_List) const{ // Check bounds of index if(Node_Index >= ___Node_List.size()) return false; // Set output parameter data Data_Out = ___Node_List[Node_Index].Data; // Set output parameter adjacency list Adjacency_List = ___Node_List[Node_Index].Adjacency_List; return true;}// End Get_Node_Data() OVERLOADED B// ------------------------------------------------------------------------------// PUB M FUNCTION : Get_Node_Adjacency_List()// PARAMETERS : p0(IN) unsigned int - Node index// : p1(OUT) &std::vector - Returned list of // : adjacent node indices// RETURN VALUE : bool// DESCRIPTION : Return the list of adjacent node indices from the node // : specified at the index parameter.// ------------------------------------------------------------------------------template bool UGraph::Get_Node_Adjacency_List(unsigned int Node_Index, std::vector<unsigned int> &Adjacency_List) const{ // Check bounds of index if(Node_Index >= ___Node_List.size()) return false; // Set output parameter adjacency list Adjacency_List = ___Node_List[Node_Index].Adjacency_List; return true;} // End Get_Node_Adjacency_List()// ------------------------------------------------------------------------------// PUB M FUNCTION : Get_Node_Count()// PARAMETERS : void// RETURN VALUE : unsigned int// DESCRIPTION : Return the number of nodes in the graph// ------------------------------------------------------------------------------template unsigned int UGraph::Get_Node_Count(void) const{ return ___Node_List.size();}// End Get_Node_Adjacency_List()// ------------------------------------------------------------------------------// PUB M FUNCTION : Depth_First_Search()// PARAMETERS : p0(IN) void(*)(const T &Data) - The callback function// RETURN VALUE : void// DESCRIPTION : Seach the graph using a depth first search. The callback// : function is called for every node visited and is passed the// : node data as a parameter.// ------------------------------------------------------------------------------template void UGraph::Depth_First_Search(void(*Function_Pointer)(const T &Data)){ // Check for graph nodes if(!___Node_List.size()) return; // Clear and resize the nodes visited list ___Traversal_Nodes_Visited_List.resize(___Node_List.size()); ___Traversal_Nodes_Visited_List.assign(___Node_List.size(), false); // Set the callback function pointer ___Traversal_Callback_Function_Pointer = Function_Pointer; // Traverse the nodes ___DFS(0); // Dump the visited list data ___Traversal_Nodes_Visited_List.clear();}// End Depth_First_Search()// ------------------------------------------------------------------------------// PUB M FUNCTION : Breadth_First_Search()// PARAMETERS : p0(IN) void(*)(const T &Data) - The callback function// RETURN VALUE : void// DESCRIPTION : Seach the graph using a breadth first search. The callback// : function is called for every node visited and is passed the// : node data as a parameter.// ------------------------------------------------------------------------------template void UGraph::Breadth_First_Search(void(*Function_Pointer)(const T &Data)){ // Check for graph nodes if(!___Node_List.size()) return; // Clear and resize the nodes visited list ___Traversal_Nodes_Visited_List.resize(___Node_List.size()); ___Traversal_Nodes_Visited_List.assign(___Node_List.size(), false); // Clear and resize the adjacent visited list ___Adjacent_Nodes_Visited_List.resize(___Node_List.size()); ___Adjacent_Nodes_Visited_List.assign(___Node_List.size(), false); // Set the callback function pointer ___Traversal_Callback_Function_Pointer = Function_Pointer; // Traverse the nodes ___BFS(0, true); // Dump the visited lists data ___Traversal_Nodes_Visited_List.clear(); ___Adjacent_Nodes_Visited_List.clear();}// End Breadth_First_Search()// ------------------------------------------------------------------------------// PUB M FUNCTION : Save_To_File()// PARAMETERS : p0(IN) FILE* - A file pointer already initialized to write // : binary data and set to the proper location // : of the file where the graph is the be // : written.// RETURN VALUE : bool// DESCRIPTION : Save the graph to a file using a file pointer parameter// : which is initialized to write binary.// ------------------------------------------------------------------------------template bool UGraph::Save_To_File(FILE* File_Pointer) const{ // Check file pointer if(!File_Pointer) return false; // Graph is saved in the following format // unsigned int - Number of nodes // For each node // T - The data for the node // unsigned int - Number of adjacent indices // For each adjacent index // unsigned int - Adjacent index unsigned int Node_Count; unsigned int Adjacency_Count; // Ouput number of graph nodes Node_Count = (unsigned int)___Node_List.size(); fwrite(&Node_Count, 1, sizeof(unsigned int), File_Pointer); // For every node for(unsigned int i=0; i { // Ouput the graph node data fwrite(&___Node_List.Data, 1, sizeof(T), File_Pointer); // Output the number of adjacent graph nodes Adjacency_Count = (unsigned int)___Node_List.Adjacency_List.size(); fwrite(&Adjacency_Count, 1, sizeof(unsigned int), File_Pointer); // For every adjacent index for(unsigned int j=0; j { // Ouput the graph adjacent indices fwrite(&___Node_List.Adjacency_List[j], 1, sizeof(unsigned int), File_Pointer); } } return true;}// End Save_To_File()// ------------------------------------------------------------------------------// PUB M FUNCTION : Load_From_File()// PARAMETERS : p0(IN) FILE* - A file pointer already initialized to read // : binary data and set to the proper location // : of the file where the graph is the be // : read from.// RETURN VALUE : bool// DESCRIPTION : Load the graph from a file using a file pointer parameter// : which is initialized to read binary.// ------------------------------------------------------------------------------template bool UGraph::Load_From_File(FILE* File_Pointer){ // Check file pointer if(!File_Pointer) return false; // Clear the node list ___Node_List.clear(); // Graph loaded in the following format // unsigned int - Number of nodes // For each node // T - The data for the node // unsigned int - Number of adjacent indices // For each adjacent index // unsigned int - Adjacent index unsigned int Node_Count; unsigned int Adjacency_Count; // Read number of graph nodes fread(&Node_Count, 1, sizeof(unsigned int), File_Pointer); // Resize the node list to the size needed ___Node_List.resize(Node_Count); // For every node for(unsigned int i=0; i { // Read in the graph node data fread(&___Node_List.Data, 1, sizeof(T), File_Pointer); // Read in the number of adjacent graph nodes fread(&Adjacency_Count, 1, sizeof(unsigned int), File_Pointer); // Resize node's adjacency list ___Node_List.Adjacency_List.resize(Adjacency_Count); // For every adjacent index for(unsigned int j=0; j { // Ouput the graph adjacent indices fread(&___Node_List.Adjacency_List[j], 1, sizeof(unsigned int), File_Pointer); } } return true;}// End Load_From_File()// ------------------------------------------------------------------------------#endif
// Save the graph from a temp filevoid Save_Graph(const UGraph<char> &Test_Graph){ FILE* File_Pointer = fopen("Test_Graph.ug", "wb"); if(!File_Pointer) return; Test_Graph.Save_To_File(File_Pointer); fclose(File_Pointer);}// Load the graph from a temp filevoid Load_Graph(UGraph<char> &Test_Graph){ FILE* File_Pointer = fopen("Test_Graph.ug", "rb"); if(!File_Pointer) return; Test_Graph.Load_From_File(File_Pointer); fclose(File_Pointer);}// The graph search callback function void Callback_Print(const char &Data){ std::cout << Data << " ";}// Test the graph interfaceint main(void){ UGraph<char> Test_Graph; // Create this graph // v // /|\ // u w x // / \ // q t // / \ // r s // Add the nodes Test_Graph.Add_Node('v'); Test_Graph.Add_Node('u'); Test_Graph.Add_Node('w'); Test_Graph.Add_Node('x'); Test_Graph.Add_Node('q'); Test_Graph.Add_Node('t'); Test_Graph.Add_Node('r'); Test_Graph.Add_Node('s'); // Add the edges Test_Graph.Add_Edge(0, 1); Test_Graph.Add_Edge(0, 2); Test_Graph.Add_Edge(0, 3); Test_Graph.Add_Edge(1, 4); Test_Graph.Add_Edge(1, 5); Test_Graph.Add_Edge(4, 6); Test_Graph.Add_Edge(4, 7); // Save the graph to file Save_Graph(Test_Graph); // BF Seach the graph to print it from 'v' Test_Graph.Breadth_First_Search(Callback_Print); std::cout << std::endl; // DF Seach the graph to print it from 'v' Test_Graph.Depth_First_Search(Callback_Print); // Delete the root node Test_Graph.Delete_Node(0); // u w x // / \ // q t // / \ // r s std::cout << std::endl; // BF Seach the graph to print it from 'u' Test_Graph.Breadth_First_Search(Callback_Print); // Add edges to reconnect 'w' and 'x' Test_Graph.Add_Edge(0, 1); Test_Graph.Add_Edge(3, 2); // u // /|\ // q t w // /|\ // r s x std::cout << std::endl; // BF Seach the graph to print it from 'u' Test_Graph.Breadth_First_Search(Callback_Print); // Load the graph from file Load_Graph(Test_Graph); // v // /|\ // u w x // / \ // q t // / \ // r s std::cout << std::endl; // BF Seach the graph to print it from 'v' Test_Graph.Breadth_First_Search(Callback_Print); std::cout << "\n" << std::endl; return 0;}
SLAM...
Simultaneous Localization And Mapping or SLAM is the mechanism I am presently trying to develop for the troll agent. Thanks to Timkin for that clarification. If you google for more information you'll find many pages discussing its use in modern robotics exploring the real world.
Wikipedia: Simultaneous localization and mapping
Trollish Animations...
I've been using Milkshape to build the troll animations. I own Max, which would turn out smoother animations, but can't seem to give up the simplicity of the Milkshape controls. Recently I've created a sit-down animation so the troll can have a rest and meditate. I've also been fine-tuning the walk animation which looks very nice when scaled to actual time. Next I'll be working on the pick-up/put-down sequence. Eventually the troll will communicate its needs to you and other trolls using a form of sign language. A system of blended animations will be developed once the language is defined.