हम कक्षा को ग्राफ बूस्ट के तहत मुखौटा करते हैं। भाग 1: इंटरफ़ेस को स्पर्श न करें

प्रस्तावना: बूस्ट कॉन्सेप्ट्स
भाग 2: अवधारणा समर्थन के कार्यान्वयन को पूरा करना

हमारे खेल के लिए पथ खोज एल्गोरिथ्म को फिर से बनाने में कुछ समय लगा। अतीत पूरी तरह से स्व-निर्मित था - पक्ष का एक कदम, और सब कुछ खराब है ... मैं इसे एक अच्छे स्रोत से तैयार करना चाहता था। यह तब था जब मुझे याद आया कि रेखांकन के साथ काम करने के लिए बूस्ट की कार्यक्षमता है। दुर्भाग्य से, दृष्टिकोण "एक फ़ंक्शन ढूंढें, कॉल करें - और यह सभी काम करता है" नहीं हुआ। पुस्तकालय में जोर उपयोग की अधिकतम लचीलेपन पर है, जो सादगी को नकारात्मक रूप से प्रभावित करता है। इसी समय, घातक कुछ भी नहीं - सब कुछ खरोंच से करने से बेहतर है (और फिर इसे ठीक करना)। अन्य पुस्तकालयों से संपर्क करने की कोई इच्छा नहीं थी, जबकि परियोजना में बढ़ावा लंबे समय से इस्तेमाल किया जा रहा है ...

दिया गया है - निम्नलिखित (इस लेख के लिए महत्वपूर्ण) इंटरफ़ेस के साथ एक खेल मैदान का एक वर्ग

class GameField { public: GameField(); bool canPass(int x, int y) const; int getWidth() const; int getHeight() const; }; 

क्षेत्र वर्ग कोशिकाओं का एक नियमित ग्रिड है। आप सीधे और तिरछे दोनों पड़ोसी कोशिकाओं में जा सकते हैं। GameField :: canPass विधि आपको यह जांचने की अनुमति देती है कि क्या किसी दिए गए सेल में प्रवेश करना संभव है (यानी यह मौजूद है और इसमें कोई बाधा नहीं है)

पहला कदम बढ़ावा की अवधारणाओं से परिचित होना था - मैंने उनके बारे में पिछले लेख में लिखा था। इसके बिना, रेखांकन के लिए सभी पुस्तकालय आवश्यकताओं को यादृच्छिक रूप से पूरा करना होगा, हमेशा के लिए पढ़ें। मैं खुद को नहीं दोहराऊंगा, मैं केवल पिछले लेख के एक छोटे से जोड़ पर ध्यान केंद्रित करूंगा। यह अवधारणा को सत्यापित करने के लिए निम्नलिखित तरीका प्रदान करता है।

 BOOST_CONCEPT_ASSERT((SomeFuncAppropriate<SomeClass>)); 

मैंने यह भी शिकायत की कि आंख के दोहरे ब्रेक से चोट लगी। यह पता चला है कि वे न केवल मुझे काटते हैं, और बढ़ावा अधिक परिचित विकल्प प्रदान करता है

 boost::function_requires<SomeFuncAppropriate<SomeClass> >(); 

यह रिकॉर्डिंग का यह रूप है जिसे मैं भविष्य में उपयोग करूंगा।

So. एक स्रोत वर्ग है जिसे स्वीकार करने के लिए बढ़ावा देने के लिए एक ग्राफ के रूप में प्रच्छन्न होना चाहिए। उसी समय, मैं प्लेइंग फ़ील्ड (गेमफिल्ड) की कक्षा को बदलना नहीं चाहता - यहाँ मैं इसका सरलीकृत संस्करण देता हूँ, वास्तव में क्लास का इंटरफ़ेस पहले से ही बड़ा है, लेकिन कार्य की गैर-प्रत्यक्ष कार्यक्षमता के लिए इसे बदलना व्यावहारिक नहीं है। रास्ता खोजने के लिए, हम ए * एल्गोरिथ्म (आसार) का उपयोग करेंगे। प्रलेखन का कहना है कि बढ़ावा :: astar_search फ़ंक्शन को ग्राफ़ को दो अवधारणाओं के अनुरूप करने की आवश्यकता है: वर्टेक्स सूची ग्राफ़ और घटना ग्राफ़ ।

• VertexListGraph ग्राफ के सभी कोने के कुशल ट्रैवर्सल की संभावना का सुझाव देता है। ऐसा करने के लिए, आपको कोने की संख्या और उनकी गणना निर्धारित करने का एक साधन प्रदान करना होगा।
• IncidenceGraph में ऊपर से आने वाले सभी किनारों पर पुनरावृति करने के लिए एक इंटरफ़ेस होना चाहिए। इसके अलावा, इस प्रकार के रेखांकन के लिए, किसी दिए गए किनारे के लिए शुरुआती और समाप्ति कोने प्राप्त करना संभव होना चाहिए।

इसके अलावा, ग्राफ़ अवधारणाओं को कई विशेष प्रकार की परिभाषा की आवश्यकता होती है, जिसके आधार पर बढ़ावा हमारी कक्षा में हेरफेर करने में सक्षम होगा। आइए हम उन पर अधिक विस्तार से ध्यान दें।

vertex_descriptor वर्टेक्स के प्रकार को परिभाषित करता है। GameField वर्ग में, एक शीर्ष दो सेल निर्देशांक द्वारा परिभाषित किया गया है। पहला विचार एक संरचना या मूल्यों की एक जोड़ी (std :: pair) का उपयोग करके इस परिभाषा को दोहराना है। हालाँकि, vertex_descriptor , ग्राफ के प्रकार के आधार पर, विभिन्न अवधारणाओं को संतुष्ट करना चाहिए, अर्थात्, ऑपरेटरों, निर्माणकर्ताओं, आदि को लागू किया जाना चाहिए। यह नहीं कहना कि यह बहुत कठिन है, लेकिन यह सोचना और समझना आसान है कि शीर्ष के दो निर्देशांक हमारे खेल के मैदान के कार्यान्वयन की एक विशेषता है। अपने आप से, ग्राफ का प्रतिनिधित्व इससे (हमारे मामले में) लाभ नहीं करता है। इसलिए यह तय किया गया था कि ग्राफ मॉडल में, कोने बस (0, 0) -> 0, (0, 1) -> 1, और इतने पर होंगे। यह आपको मानक प्रकार को शीर्ष प्रकार के रूप में उपयोग करने की अनुमति देगा, जो पहले से ही सभी आवश्यक कार्यक्षमता का समर्थन करता है। बेशक, आपको दो कार्यों को लागू करना होगा - ग्राफ़ के निर्देशांक में शीर्ष सूचकांक का अनुवाद करना

 std::pair<int, int> getCoordinates(const Vertex position, const GameField& graph) { return std::make_pair(position % graph.getWidth(), position / graph.getWidth()); } 

और वापस

 Vertex getVertex(int x, int y, const GameField& graph) { return x + y * graph.getWidth(); } 

वर्टेक्स टाइप कहां से आया, इसके बारे में नीचे बताया जाएगा।

edge_descriptor - धार का प्रकार। एक किनारे दो कोने हैं, और इसे नीचे लिखें: std :: pair <vertex_descriptor, vertex_descriptor>

Direct_category - विशेष टैग प्रकारों में से एक से मेल खाना चाहिए (संक्षेप में, ये डेटा और विधियों के बिना संरचनाएं हैं), जो यह निर्धारित करेगा कि ग्राफ़ निर्देशित है या नहीं। हमारे मामले में, ऐसा नहीं है, इसलिए हम मूल्य वृद्धि का उपयोग करेंगे: अप्रत्यक्ष_टैग

edge_parallel_category एक अन्य टैग प्रकार जो यह निर्धारित करता है कि हमारे ग्राफ में समानांतर किनारों की अनुमति है (जब एक से अधिक धार दो कोने के बीच मौजूद हो सकते हैं)। मान्य नहीं है - उपयोग को बढ़ावा दें :: disallow_parallel_edge_tag

traversal_category एक टैग भी। ग्राफ ट्रैवर्सल विधियों को परिभाषित करता है। यहां सब कुछ थोड़ा और जटिल है। VertexListGraph के लिए, यह बढ़ावा देना चाहिए :: vertex_list_graph_tag, और IncidenceGraph के लिए, क्रमशः, बढ़ावा देने के लिए :: घटना_ग्राफ_टैग। यह एक नया टैग प्रकार बनाकर हल किया गया है जो दोनों बाईपास विकल्पों को विरासत में मिला है।

 struct game_field_traversal_catetory: public boost::vertex_list_graph_tag, public boost::incidence_graph_tag { }; 

vertex_iterator ट्रेसिंग वर्टिकल के लिए एक पुनरावृत्त । हम लेख के अगले भाग में इसके कार्यान्वयन पर विचार करेंगे।

out_edge_iterator शीर्ष से आने वाले किनारों को पार करने के लिए एक पुनरावृत्ति , भविष्य में भी लागू किया जाएगा।

degree_size_type टाइप जिसमें वर्टेक्स की डिग्री (आउटगोइंग किनारों की संख्या) व्यक्त की जाती है। पूर्णांक।

vertices_size_type वह प्रकार जिसमें ग्राफ कोने की संख्या व्यक्त की जाती है। पूर्णांक के रूप में भी लें।

मैं और अधिक विस्तार से टैग प्रकारों पर ध्यान केंद्रित करूँगा (इसे सही तरीके से टैगिंग कहा जाता है)। मॉडल के एक या किसी अन्य विशेषता का लाभ उठाने के लिए उनका उपयोग कार्यों को अधिभारित करने के लिए किया जाता है। उदाहरण के लिए, बढ़ावा को परिभाषित करते हुए :: अप्रत्यक्ष_टैग टैग, हम लाइब्रेरी को बताते हैं कि ग्राफ़ के किनारों को निर्देशित नहीं किया गया है। नतीजतन, यह उन कार्यों का उपयोग करेगा जिन्हें आउटगोइंग और इनकमिंग किनारों की एक अलग परिभाषा की आवश्यकता नहीं है।

अब आपको खेल के मैदान के प्रकारों का मिलान करने की आवश्यकता है। पहला बाध्यकारी विकल्प अतिरिक्त परिभाषाओं को सीधे कक्षा में रखना है।

 class GameField { public: typedef int vertex_descriptor; ... 

हालाँकि, मैं गेमफिल्ड इंटरफ़ेस को अपरिवर्तित छोड़ना चाहता हूं। सौभाग्य से, बढ़ावा इस तरह के एक अवसर प्रदान करता है। सभी आवश्यक प्रकार लाइब्रेरी द्वारा ग्राफ क्लास से सीधे नहीं निकाले जाते हैं, अर्थात ऐसा नहीं है

 GameField::vertex_descriptor 

इसके बजाय, एक विशेष बढ़ावा :: graph_traits टेम्पलेट का उपयोग किया जाता है।

 boost::graph_traits<GameField>::vertex_iterator 

डिफ़ॉल्ट रूप से, यह बस पैरामीटर वर्ग से संबंधित प्रकार प्राप्त करता है, अर्थात। निम्नलिखित करता है

  template <typename Graph> struct graph_traits { typedef typename Graph::vertex_descriptor vertex_descriptor; ... 

आप GameField वर्ग के लिए अपना स्वयं का विशेषज्ञता ग्राफ_ट्रेट्स लिख सकते हैं, जो इसके साथ काम करेगा, क्योंकि यह हमारे लिए सुविधाजनक है, अर्थात्। खेल के मैदान में आवश्यक प्रकारों की खोज करने की कोशिश न करें। प्रकारों की पसंद को शब्दों में वर्णित किया गया था, अब हम अंतिम कार्यान्वयन पर विचार करेंगे। इसे बूस्ट नेमस्पेस में रखना याद रखें।

 namespace boost { template <> struct graph_traits<GameField> { typedef int vertex_descriptor; typedef std::pair <vertex_descriptor, vertex_descriptor> edge_descriptor; typedef boost::undirected_tag directed_category; typedef boost::disallow_parallel_edge_tag edge_parallel_category; typedef game_field_traversal_catetory traversal_category; typedef VertexIteratorImpl vertex_iterator; typedef OutEdgeIteratorImpl out_edge_iterator; typedef int degree_size_type; typedef int vertices_size_type; typedef void in_edge_iterator; typedef void edge_iterator; typedef void edges_size_type; }; } 

ध्यान दें कि संरचना में कई प्रकार हैं जो पहले उल्लेख नहीं किए गए थे: in_edge_iterator, edge_iterator, edge_size_type। उन्हें क्रमशः वर्टेक्लिस्टग्राफ और इंसीडियॉगग्राफ की अवधारणाओं को लागू करने की आवश्यकता नहीं है, आप उन्हें निर्दिष्ट नहीं कर सकते हैं ( शून्य करें )।

आगे के काम में, ग्राफ_ट्रिट्स में प्रकारों को संदर्भित करना उचित है (यानी, उदाहरण के लिए, यदि यह एक शीर्ष है, तो इसके बजाय vertex_descriptor का उपयोग करें), ताकि आप आवश्यक होने पर एक स्थान पर परिभाषाओं को बदल सकें। चूंकि फॉर्म बूस्ट का निर्माण :: ग्राफ_ट्रेट्स <GameField> :: vertex_descriptor लिखने और पढ़ने दोनों के लिए भारी है, हम सरल प्रकार के नाम पेश करते हैं, जिसका उपयोग हम भविष्य में करेंगे।

 typedef boost::graph_traits<GameField>::vertex_descriptor Vertex; typedef boost::graph_traits<GameField>::edge_descriptor Edge; typedef boost::graph_traits<GameField>::vertex_iterator VertexIterator; typedef boost::graph_traits<GameField>::out_edge_iterator OutEdgeIterator; typedef boost::graph_traits<GameField>::degree_size_type DegreeSizeType; typedef boost::graph_traits<GameField>::vertices_size_type VerticesSizeType; 

सभी आवश्यक प्रकार परिभाषित हैं। VertexIteratorImpl और OutEdgeIteratorImpl का उपयोग ग्राफ_ट्रिट्स <GameField> में किया गया था - हम लेख के अगले भाग में इन पुनरावृत्तियों के कार्यान्वयन पर विचार करेंगे। समर्थित अवधारणाओं के लिए आवश्यक रेखांकन कार्य भी कार्यान्वित किए जाएंगे।