kirkd

OK, I have to play.

 

Over a decade ago I was working on a project with another developer whose job it was to implement the model for a 2D scatter plot.  The scatter plot had the ability to color-by and size-by - pick a data column and you would get a color or size gradient based on the data values. We had settled on 20 color steps and 20 size steps for the plot, and he was perplexed by how to accomplish this.  I suggested a 20x20 2D array, each element of which would hold the indices of the points corresponding to that a particular size and color, with the data range divided by 20 to get the bins for each one.  Not the most elegant solution, but seemed workable.

 

We were developing in VB 6 and he was enamored with dictionaries - everything was a dictionary.  So, he developed a dictionary that would be accessed by a two element string consisting of the bin locations.  In other words instead of the array bins(x,y), he had the dictionary bins["x,y"].  In his code, he would compute the color/size bin numerically, combine these into a string, use this to access the dictionary.  OK, whatever.

 

Put on top of this that his code computed the color and size bin locations in different locations and they might not always occur in the same order - sometimes you got "color,size" and sometimes you got "size,color."  It all depended on if the user clicked "color by" or "size by" first.  Oh, and he would use "first element 0" based calculations in one area and "first element 1" based calculations in another area. 

 

Now the kicker - the item stored in the dictionary was - wait for it - another dictionary.  This one was accessed by breaking up the original string key, doing some non-sensical conversions (not the obivous 20*y+x to get a linearlized array from the 2D array), and then access this dictionary with that new, converted key.  Which was converted to a string.

 

I inherited this code when he left.

 

I've come up with an idea for a card game which I think would be good as an in-person as well as an online game. The details of the game are quite superfluous to my question, which is...

Given a multiplayer card game, or even something like Words with Friends, what are the backend requirements? I have no experience with this sort of thing, and I'm probably way out of my league on it all, but I'm curious as to what such a game entails. Is it run on a server which players log into and all the gameplay is managed there, or is it be done on the users' machines? How about as an Android app?

-Kirk

At the risk of being either laughed or flamed off the planet...

I wrote what I hope to be a very generic A* implementation using templates. I had wrestled with tyring to do this same sort of thing using a class hierarchy, but it became very unweildy very quickly. I haven't had much experience with templates, so I thought this might be a good place to start. All that being said, below are the two clases that seem to be serving me very well right now. Any comments and constructive criticisms are welcome.

Here's the GraphSearch class which does the actual search.
[source lang="cpp"]/** @author Robert Kirk DeLisle rkdelisle@gmail.com @version 0.1 @section LICENSE @section DESCRIPTION GraphSearch Template Class Provides different graph search/pathfinding algorithms. Currently: Dijkstra A* IDA* Fringe Search Usage: GraphSearch<Searchable, Heuristic> Searchable class: Any class intended to serve as a node within a graph for the search. Must implement: std::string GetUID() - retrieve a globally unique ID for the node vector< Searchable * > GetNeighbors() - get all valid neighbors of this node from the graph float G() - retrieve the G value (cost thus far) for this node void G(float value) - set the G value for this node float GetCostToExpand() - how much did it cost to expand this node from the parent Searchable * GetParentNode() - retrieve a pointer to the parent node. If null, assumed to be the start location of the search std::string GetGeneratingTransform() - what is the parsable transform that led to generation of this node from the parent a vector of these will be stored as the solution/path from Start to Goal void ReplaceNode( Searchable * ) - used to replace one node (the caller) with another (the parameter) in the search this will maintain the order of the nodes in the list and apply the correct costs if we find a shorter path to a node after first evaluating it These functions need to be defined to operate on the Searchable class: bool NodeSort( Searchable &left, Searchable &right ) - sorting algorithm used by GraphSearch to maintain search priority returns (left.F() > right.F()) bool IsGoal( Searchable * ) - is this node the goal? Heuristic Template Class: A class providing a function to calculate the appropriate heuristic for the search. Implements: float ComputeH( Searchable & ) - compute and store the heuristic for the passed node Note: for Dijkstra, ComputeH() returns 0.0*/#ifndef GRAPHSEARCH_12Oct12_RKD#define GRAPHSEARCH_12Oct12_RKD#include <vector>#include <map>#include <string>#include <algorithm>#include <iostream>template<class Searchable, class H>class GraphSearch{ private: /** The priority queue will be a vector managed by std::algorithm::make_heap(), ::push_heap() and ::pop_heap(). */ std::vector<Searchable *> vpq_open_list; /** To facilitate searching the priority queue, a std::map will be maintained in parallel. */ std::map<std::string, Searchable *> map_open_list; // /** Closed list will be a std::map to facilitate easy searching */ std::map<std::string, Searchable *> map_closed_list; /** Vector to hold the solution. Each entry correponds to the results of Searchable::GetGeneratingTransform() moving from node to node in the search space. Each transformation is a string that comes from Searchable::GetGeneratingTransform() and correcponds to a transormation applied to the object represented by the node. */ std::vector<std::string> m_Solution; bool m_SolutionFound; /** Store the transformations necessary to move from the Start node to the Goal node. Each transformation is a string that comes from Searchable::GetGeneratingTransform() and correcponds to a transormation applied to the object represented by the node. */ std::vector<std::string> StorePathToGoal(Searchable *); //capture the path to the goal once it is found //return the length of that path /** Delete dynamic objects stored in open and closed lists */ void FreeLists(); public: /** Default constructor. Initialize necessary variables. */ GraphSearch() { Init(); }; /** Initialize object variables. */ void Init() { m_SolutionFound = false; m_Solution.clear(); vpq_open_list.clear(); map_open_list.clear(); map_closed_list.clear(); }; /** The A* Search Algorithm \param *Start - Pointer to the start node as a Searchable object. \param *heu - Heuristic object to be used by the algorithm. \return true if a solution is found false if the search space is fully evaluated and no solution is found */ bool AStar(Searchable *Start, H heu); /** Retrieve the solution/path from Start to Goal */ std::vector<std::string> GetSolution() { return m_Solution; }; /** Default destructor */ ~GraphSearch() {};};template<class Searchable, class H>bool GraphSearch<Searchable, H>::AStar(Searchable *Start, H heu){ //run A* from the start node to the goal node //if a solution is found, store it in the m_Solution variable //and return "true", otherwise, return "false" Searchable *current; std::vector<Searchable *> neighbor_list; Init(); vpq_open_list.push_back(Start); std::make_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); map_open_list[ Start->GetUID() ] = Start; Start->G(0.0); while (!vpq_open_list.empty()) { std::pop_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); current = vpq_open_list.back(); if ( IsGoal(current) ) { m_SolutionFound = true; StorePathToGoal( current ); //take the Start out of the lists so that it doesn't get deleted map_open_list.erase(Start->GetUID()); map_closed_list.erase(Start->GetUID()); FreeLists(); return true; } vpq_open_list.pop_back(); map_open_list.erase( current->GetUID() ); map_closed_list[ current->GetUID() ] = current; neighbor_list = current->GetNeighbors(); for( typename std::vector<Searchable *>::iterator it=neighbor_list.begin(); it != neighbor_list.end(); it++ ) { if ( map_closed_list.find( (*it)->GetUID() ) != map_closed_list.end() ) { delete *it; continue; } if ( map_open_list.find( (*it)->GetUID() ) != map_open_list.end() ) { typename std::map<std::string, Searchable *>::iterator ol_it = map_open_list.find( (*it)->GetUID() ); if ( (*ol_it).second->G() > current->G() + (*it)->GetCostToExpand() ) { (*ol_it).second->ReplaceNode( (*it) ); (*ol_it).second->G( current->G() + (*it)->GetCostToExpand() ); (*ol_it).second->H( heu.ComputeH( (*ol_it).second )); std::make_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); } delete *it; } else { (*it)->G( current->G() + (*it)->GetCostToExpand() ); (*it)->H( heu.ComputeH( (*it) )); map_open_list[ (*it)->GetUID() ] = (*it); vpq_open_list.push_back( (*it) ); std::push_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); } } } m_SolutionFound = false; return false; //if we get here, we've exhaused the entire search space}template<class Searchable, class H>std::vector<std::string> GraphSearch<Searchable, H>::StorePathToGoal(Searchable *current){ //capture the path to the goal once it is found //return the length of that path m_Solution.clear(); if ( !m_SolutionFound ) return m_Solution; while( current->GetParentNode() != 0 ) { m_Solution.push_back( current->GetGeneratingTransform() ); current = current->GetParentNode(); }; std::reverse(m_Solution.begin(), m_Solution.end()); return m_Solution;}template<class Searchable, class H>void GraphSearch<Searchable, H>::FreeLists(){ for ( typename std::map<std::string, Searchable *>::iterator it=map_open_list.begin(); it!=map_open_list.end(); it++) delete (*it).second; map_open_list.clear(); for ( typename std::map<std::string, Searchable *>::iterator it=map_closed_list.begin(); it!=map_closed_list.end(); it++) delete (*it).second; map_closed_list.clear();}#endif[/source]


This is an example of a Heuristic Class that is used by GraphSearch. The only necessary function is ComputeH but I put in the option to pick from multiple heuristics before it is passed to GraphSearch.

[source lang="cpp"]/** @author Robert Kirk DeLisle rkdelisle@gmail.com @version 0.1 @section LICENSE @section DESCRIPTION Heuristic Template Class example For use with GraphSearch Template Class Provides a heuristic for the 2x2x2 Rubik's Cube Usage: GraphSearch<Searchable> Searchable class: Any class intended to serve as a node within a graph for the search and for which a heuristic is calculated. Must implement: ComputeH( Searchable & ) - returns a heuristic estimate of distance to the goal from the passed Searchable node*/#include <map>#include <fstream>#include <string>#include <sstream>#include <iostream>#ifndef CUBE2HEURISTIC_2012OCT09_RKD#define CUBE2HEURISTIC_2012OCT09_RKDtemplate<class Searchable>class Cube2Heuristic{ public: /** For this example, two possible heuristics are available: DIJKSTRA returns 0.0 as Dijkstra search uses no heuristic UPDOWNFACE returns the max of the number of turn necessary to properly position (NOT orient) the top corners or the bottom corners. */ enum Heuristics { DIJKSTRA, UPDOWNFACE }; /** Compute the heuristic value \param *node - Pointer to the node of interest. \return the computed value */ float ComputeH(Searchable *node); /** For this example, I have set up the ability to pre-select which heuristic you want to use. \param h - Value from the Cube2Heuristic::Heuristics enumeration */ void SetHeuristic( Heuristics h ) { m_SelectedHeuristic = h; }; /** Default constructor. Initialize any heuristics and set a default one to be used. */ Cube2Heuristic() { InitUpDownFace(); m_SelectedHeuristic = UPDOWNFACE; }; /** Default destructor. */ ~Cube2Heuristic() {}; private: /** Holds the pre-computed heuristic. \param .first - A UID for the 2x2x2 Cube \param .second - The maximum of the number of turns to properly position (NOT orient) the upper corners or the lower corners. */ std::map<unsigned int, int> UpDownFaceHeuristic; /** Initialize the heuristic */ void InitUpDownFace(); /** Retrieve the precomputed UPDONWFACEHEURISTIC - used by ComputeH() \param *node - pointer to the node/2x2x2 cube of interest */ float GetUpDownFaceHeuristic(Searchable *node); Heuristics m_SelectedHeuristic;};template<class Searchable>float Cube2Heuristic<Searchable>::GetUpDownFaceHeuristic(Searchable *node){ return std::max( UpDownFaceHeuristic[node->GetTopID()], UpDownFaceHeuristic[node->GetBottomID()] );};template<class Searchable>float Cube2Heuristic<Searchable>::ComputeH(Searchable *node){ switch ( m_SelectedHeuristic ) { case DIJKSTRA: return 0.0; case UPDOWNFACE: return GetUpDownFaceHeuristic(node); default: return 0.0; }}template<class Searchable>void Cube2Heuristic<Searchable>::InitUpDownFace(){ std::fstream HFile; std::string incomingLine; int pos, moves; unsigned int ID; HFile.open("UpDownFace.heu", std::ios::in); while ( !HFile.eof() ) { std::getline(HFile, incomingLine); pos = incomingLine.find(","); std::istringstream( incomingLine.substr(0,pos) ) >> ID; std::istringstream( incomingLine.substr(pos+1) ) >> moves; UpDownFaceHeuristic[ID] = moves; } HFile.close();};#endif[/source]

I'm implementing an A* algorithm (mostly for fun and conceptual learning), and the open_list needs to do two things.  1)  act as a priority queue for the purpose of searching closest nodes first, and 2) I need to determine if a node is already in the open_list before adding it.  (2) is the case when I ask for neighbors of the current node and don't want to inadvertantly add a node twice to the list.

(1) is easily done (in C++) with std::priority_queue, but I cannot efficiently search a PQ for a pre-existing node.
(2) is easily done with a std::map, but I cannot use it as a priority queue

The only answer I see for this right now is to have two parallel structures that I make sure I keep consistent.  Any other option that I'm overlooking??

At the risk of starting a religious war...

I'm in the design process and currently looking at pathfinding. I'm happy to use A* as my graph search alogorithm, and I like the idea of making this pathfinder as reusable as possible since we don't have anything at this point requiring less than a massive rewrite.

My first instinct is to use class structures and inheritance. Specifically, my search algorithm (A* in this case) would accept an AStarSearchable class, which would implement the appropriate ExpandNode function and have some friend functions to take care of other details such as DistnaceFromStart, HeuristicToCoal, DistanceToGoal (DistnaceFromStart + HeuristicToGoal). In the extreme, I cold make a SearchAlgorithm base class and then have different algorithms derived from that.

On the other hand, if I use templates and make my A* algorithm a template class with the expectation that the supplied parameter type implements the functions I mentioned, I see another way to get at the same result.

Which would you choose, and why?