Advertisement Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

505 Good

About kirkd

  • Rank
    Advanced Member

Personal Information

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. Yeah, I thought of that, too.  The catch is that this is the very last piece of my application that I need to finish.  The whole thing is complete apart from the Save functionality and all done in Tkinter.  Ugh.  I hate to mix the two, but maybe for this one piece...
  2. In my application I want to let the user specify a new file name or pick an existing file which will simply be appended.    asksavefilename works to specify a new file, but it throws a warning window if an existing file is picked saying it will be overwritten.  askopenfilename lets you pick an existing file without the overwrite warning, but you can't specify a new file   Any ideas how to make either of these work or am I going to have to roll my own dialog?  If I could force asksavefilename not to throw the overwrite warning, that would be great.   -Kirk  
  3. Ah, I got it now.  The map provides the cannonical form, and the multimap returns the whole list/set.  Seems obvious now that you point it out.
  4. Hmmmm....not quite there.  This seems fine to get access to the preferred name by any synonym or the list of synonyms by any preferred name.  It doesn't address the question of getting the full list of synonyms from any single member of the list.   For example, given the synonym list [A,b,c,d,e,f], with A being the preferred name, I want to get the entire list as well as the preferred name by using any single member of that list.  syn_list['d'] would return [A,b,c,d,e,f] as well as the preferred name 'A'.  syn_list['f'] would return the same thing.
  5. I have data which consists of list of synonyms and within each list there is a preferred synonym.  For example, [A,b,c,d,e] and [Z,y,x,w,v], with the capitalized letter being the preferred name for that particular list of synonyms.  I want to be able to access all the members of the synonym list with any member of that list, and I want to be able to access the preferred name for a synonym list by any member of the list.    The things that come to mind in C++ are maps and multimaps, and in Python Dictionaries.  I don't know of a version of multimap in Python.  Even with these, though it seems clunky.   For maps/dictionaries, I could create a vector/list of each synonym list which is stored in a map/dictionary multiple times, once for each item in the synonym list.  If this were in C++ I could store the pointer to the vector of each one to save some space.  Something like:   std::vector<std::string> syn_list_a std::vector<std::string> syn_list_z std::map<std::string, std::vector<string> > syn_map std::map<std::string, std::string> > pref_map   syn_map["A"] = &syn_list_a syn_map["b"] = &syn_list_a ... syn_map["Z"] = &syn_list_z syn_map["y"] = &syn_list_z ... pref_map["A"] = "A" pref_map["b"] = "A" ... pref_map["Z"] = "B" pref_map["y"] = "B"   For Python, I could translate this to dictionaries.   But, this all seems very inelegant and clunky.  Any suggestions for a better way??
  6. kirkd

    2D Array - really that hard?

        Ah, the classic TDVC - thumb drive version control.  Love it.
  7. kirkd

    2D Array - really that hard?

      Excellent observation, but actually "inherited" in this case translates to "deleted and rewrote from scratch."  8^D   Just one more layer of fun.  When my colleague left, I was given access to his folders where he stored code - he didn't use any code management system, as if you needed to be told that.  I had to navigate by timestamps since his directory structure consisted of :   /old /older /new /newer /newest /newer_than_newer /most_newer   I'm not kidding.  <shudder>
  8. 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.  
  9. kirkd

    Game AI for card game

    That article is quite good.  Are there similar online resources that could be recommended?  Perhaps approaching a different problem - board game, other card games, etc.?  Just trying to get a good grasp of the topic.
  10. Aeramor - thanks for the tip. They have a great selection of platforms - best I've seen thus far. I might have other projects that can use this sort of thing.
  11. Cool. Thanks for the info!! More research to do...
  12. Thanks for the response. Certainly out of my league right now, but interesting to consider. Regarding the game itself, yes it would be very simple relative to any sort of MMORPG. No more complex than poker or spades, most likely. Regarding the server, is this something that could be done on the cloud? Say, Amazon EC2? I'm developing the idea right now as an actual card game, but it occurred to me that an online version or a phone app would be an interesting way to widen the audience.
  13. 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
  14. 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 @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 @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_RKD template<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;"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]
  15. kirkd

    Implementing A* - open_list

    Cornstalks, I wondered if map would work, but for the wrong reason. Thanks for the explanation. Also thanks for the example. That is in concept what I'm doing now. It is nice to have someone else come to the same conclusion and validate my approach.
  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!