游戲圍線演算法
⑴ 游戲場景管理的八叉樹演算法是怎樣的
八叉樹（octree）是三維空間劃分的數據結構之一，它用於加速空間查詢，例如在游戲中： 加速用於可見性判斷的視錐裁剪（view frustum culling）。加速射線投射（ray casting），如用作視線判斷或槍擊判定。 鄰近查詢（proximity query），如查詢玩家角色某半徑范圍內的敵方NPC。碰撞檢測的粗略階段（broad phase），找出潛在可能碰撞的物體對。總括而言，前3個應用都是加速一些形狀（frustum、ray、proximity shape如球體）的相交測試（intersection test）。這種做法是adaptive的，就是說按照一定的條件（葉節點只能有一個點）來進行分割。實際上，我們可以設置其他條件去決定是否分割一個葉節點，例如節點內的點超過10個，或是最多分割4層就不再分割等等。在分割時，我們只需檢查點是在每個軸的哪一方，就能知道該點應放置在哪個新的節點里。建立了一個四／八叉樹之後，我們可以得出一個重要特性： 如果一個形狀S與節點A的空間（正方形／立方體）不相交，那麼S與A子樹下的所有點都不相交。那麼，在相交測試中，我們可以從根節點開始，遍歷四／八叉樹的節點，如節點相交就繼續遍歷，如不相交就放棄遍歷該子樹，最後在葉節點進行形狀與點的相交測試。這樣做，一般能剔除許多點，但注意最壞的情況是所有點集中在一起，那麼就不起加速作用。因此，除了傳統的四／八叉樹實現，也可以參考一些更新的技術。
⑵ 高分求演算法：關於井字棋(三子棋)的演算法！！面談感謝！！！！
「井字棋」游戲（又叫「三子棋」），是一款十分經典的益智小游戲，想必很多玩家都有玩過。「井字棋」的棋盤很簡單，是一個3×3的格子，很像中國文字中的「井」字，所以得名「井字棋」。「井字棋」游戲的規則與「五子棋」十分類似，「五子棋」的規則是一方首先五子連成一線就勝利；「井字棋」是一方首先三子連成一線就勝利。
井字棋（英文名Tic-Tac-Toe）
井字棋的出現年代估計已不可考，西方人認為這是由古羅馬人發明的；但我們中國人認為，既然咱們都發明了圍棋、五子棋，那發明個把井字棋自然是不在話下。這些純粹是口舌之爭了，暫且不提。
想起小時候上課喜歡玩井字棋，只要一張草稿紙、一支筆、同桌兩人就可以玩了。上體育課，也可以拿著樹枝在沙坑裡玩。但一直感覺這游戲太簡單了，後來接觸了五子棋，著迷了一陣，但水平總是很差，便也不玩了。
一字棋游戲極小極大分析法
設有九個空格，由MAX，MIN二人對弈，輪到誰走棋誰就往空格上放一隻自己的棋子，誰先使自己的棋子構成「三子成一線」(同一行或列或對角線全是某人的棋子)，誰就取得了勝利。
用叉號表示MAX，用圓圈代表MIN。
比如右圖中就是MIN取勝的棋局。
為了不致於生成太大的博弈樹，假設每次僅擴展兩層。估價函數定義如下：
設棋局為P，估價函數為e(P)。
(1) 若P對任何一方來說都不是獲勝的位置，則e(P)=e(那些仍為MAX空著的完全的行、列或對角線的總數)-e(那些仍為MIN空著的完全的行、列或對角線的總數)
(2) 若P是MAX必勝的棋局，則e(P)＝+∞。
(3) 若P是B必勝的棋局，則e(P)＝-∞。
比如P如右圖示,則e(P)=6-4=2
要注意利用棋盤位置的對稱性,在生成後繼節點的位置時，下列博弈結局
都是相同的棋局(在博弈中，一宇棋的分枝系數比較小起初是由於對稱性，而後是由於棋盤上未布子的空格減少所致)。圖3.15畫出了經過兩層搜索生成的博弈樹，靜態估值記在端節點下面，倒推值記在圓圈內。
由於右圖所示位置具有最大的倒推值，它應當選取為MAX的第一步（正好是MAX的最好的優先走步）。
現在我們假設MAX走了這一步，而MIN的回步是直接在X上方的空格里放上一個圓圈(對MAX來說這是一步壞棋，他一定沒有採用好的搜索策略)。下一步，MAX又在新的格局下搜索兩層，產生如圖3.16所示的搜索圖。
現在圖中MAX有兩個可能「最好的」優先走步，假設MAX走了圖上指明的那一步。而MIN為了避免立即敗北被迫走了另一步，從而產生如下棋局：MAX再次搜索，產生如圖3.17所示的樹。
在這棵樹中某些端節點(例如其中一個標記著A)代表MIN獲勝，因此它們的估值為—∞。當這些估值被倒推回去時，可看到MAX的最好的也是唯一能使他避免立即失敗的一個走步。現在，MIN可以看出MAX必然在他的下一走步中獲勝，因此，MIN只好認輸。
按極大極小演算法編程下一字棋的演示(右圖，可以點擊操作)．．．
我們就利用Visual Basic編寫一個「井字棋」的小游戲。
【設計思路】
首先，我們要知道，「井字棋」游戲是一款典型的棋類游戲，游戲時一方式是電腦，另一方是玩家。所以，這類游戲在開始時有兩種方式：一種是玩家先走；另一種是電腦先走。這是我們要考慮的第一個問題。
其次，由於與玩家對戰的是計算機，所以我們要編寫一個過程（Chuqi），它可以使程序模擬人的思維與人下棋（其實就是「人工智慧」的體現），這個Chuqi過程也是本游戲軟體的關鍵。此外，我們還要編寫兩個過程（Lianxian和Shuying），Lianxian過程用來時刻判斷棋盤中是否有三個棋子連成一線；Shuying過程用來判斷如果有三個棋子連成一線，是哪一方連成一線的，即判斷哪一方獲勝。
以上幾個問題就是該「井字棋」游戲實現的關鍵思路。....
QQ:744192659
郵箱:[email protected]
⑶ 平碼三中三9宮演算法怎麼算
第一行2，11第二行4，1，0第三行2，7，5帶進去試試看。
分析：把空格從第一行到第三行分別標為ABCDEFGH得知一個9所以A十B＝13，E十H＝5。A+B＝13有好幾種可能可是A+c÷F=4，所以A只有在1，2，3裡面取。先取了3帶入，即A為3，B為10，那麼B－DXG＝4，所以DxG＝6。
觀察第二行與第二行算式特點兩式相減得到G－H＝DE，把各種可能帶入，否定。說明不行，那就取A＝2，B=11，則C＝2F，DXG＝7，已知E十H＝5取各種情況帶入。
(3)游戲圍線演算法擴展閱讀：
第一種是在在3×3方格盤上，是把1至8八個小木塊隨意擺放，每一空格其周圍的數字可移至空格。玩者要將小木塊按12345678的順序重新排好，以最少的移動次數拼出結果者為勝。
第二種玩法如九宮格算術游戲玩法，推動木格中8個數字排列，橫豎都有3個格，使每行、每列兩個對角線上的三數之和都等於15。在計算的同時，還必須思考怎麼把數字方塊推動到相對應的位置上，這個游戲不僅僅考驗人的數字推理能力，也同時考驗了人的思維邏輯能力。
⑷ 夢幻西遊自動尋路的尋路演算法怎麼算
A*尋路演算法 A*（A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的
節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價
中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最
好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價
函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎？肯定沒懂。接著看。
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是
。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函
數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計
算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}
⑸ 戰棋類游戲移動范圍的演算法
你看一下下面兩篇，戰棋是窮舉法尋路的較多
http://dev.gameres.com/Program/Abstract/SLGPath.htm
http://dev.gameres.com/Program/Abstract/SLGMove.htm
⑹ 圍棋如何計算目數
圍棋點目演算法有兩種：數子法和計目法
1、計目（比目）法：用簡單的文字表述，就是計算比較雙方終局時所圍的地域目數，並以目數多少來判斷勝負結果，日韓圍棋規則都採用計目法。而中國的圍棋規則則是採用數子法。
2、數子法是根據棋局終局後對局雙方的棋子在棋盤上所歸屬位點的多少來計算判斷勝負結果的。
計目法由於只計算所圍的地域目數，收完單官與否並不影響勝負結果，因而規定棋局終局不收單官。所以是否收完所有單官，是數子法和計目法在終局時的主要區別。 所謂歸本數，是指數子法的基礎勝負標准。因為標准圍棋棋盤總計有361個交叉點，所以對局雙方每方應得點數應為總點數的一半，即180.5點。多於此數者勝，少於此數者敗，等於此數者和。
(6)游戲圍線演算法擴展閱讀：
圍棋，是一種策略性兩人棋類游戲，中國古時稱「弈」，西方名稱「Go」。流行於東亞國家（中、日、韓、朝），屬琴棋書畫四藝之一。圍棋起源於中國，傳為帝堯所作，春秋戰國時期即有記載。隋唐時經朝鮮傳入日本，流傳到歐美各國。圍棋蘊含著中華文化的豐富內涵，它是中國文化與文明的體現。
圍棋使用方形格狀棋盤及黑白二色圓形棋子進行對弈，棋盤上有縱橫各19條線段將棋盤分成361個交叉點，棋子走在交叉點上，雙方交替行棋，落子後不能移動，以圍地多者為勝。因為黑方先走佔了便宜，所以人為規定黑方局終時要給白方貼子。中國古代圍棋是黑白雙方在對角星位處各擺放兩子（對角星布局），為座子制，由白方先行。現代圍棋由日本發展而來，取消了座子規則，黑先白後，使圍棋的變化更加復雜多變。圍棋也被認為是世界上最復雜的棋盤游戲。