交互式CAI課件中的分段路徑規劃

蘇維龍

（遼寧石油化工大學計算機與通信工程學院，遼寧撫順113001）

交互式CAI課件中的分段路徑規劃

蘇維龍

（遼寧石油化工大學計算機與通信工程學院，遼寧撫順113001）

在交互式CAI課件中，通過程序響應用戶的輸入，演示變化過程，可以達到更好的教學效果。在設計一個關于《微機原理》課程的交互式CAI課件時，涉及到了一個實時路徑規劃問題。針對路徑規劃中實時性的要求，通過在路徑的不同階段采用不同的規劃方法，達到了降低計算復雜度的目的，滿足了實時性的要求。

路徑規劃j實時jCAIj3D模型

在設計一個關于《微機原理》課程的交互式CAI課件時，涉及到了一個路徑規劃問題。在實現兩個部件之間的數據流動時，課件試圖演示數字的移動過程。由于課件是交互性的，學生在使用課件時，可能輸入任何合法的操作和指令。因此，把數字的全部移動路徑事先存儲是不合理的。這樣，需要根據操作者輸入的操作或指令，實時地規劃數字的移動路徑［1_2］。

路徑規劃有多種方法，各有所長［3_5］。根據所面臨問題的具體情況，在路徑的不同階段，采用不同的方法。這樣，在每個階段只保留了相關的因素，簡化掉了很多與當前階段無關的因素。在相對復雜的階段，用相對復雜的方法和計算過程保證路徑的質量。在相對簡單的階段，用簡化的方法和計算過程降低計算的復雜度［6］。

數字移動時，首先經過寄存器出口、起點支線，從寄存器來到干線（總線），在干線上行進一段距離，進入終點支線，最后到達另一個寄存器部件。根據路徑的特點，決定采用分段方式，各段采用不同的方法。場景是通過3DS Max建立的3D模型，使用VC代碼響應用戶的輸入，演示數值的變化過程。寄存器、ALU、地址加法器、支線上控制門的坐標，已經通過其他手段獲知。為了描述方便，下文中把水平方向稱為東西南北，垂直方向稱為上下。

1　路徑各階段的規劃

如圖1所示。箭頭A所指向的是離開寄存器AL的第一個數字，這個數字0以及其后的數字011 0100，首先移到圖中箭頭B所指的寄存器出口。由于寄存器在讀出數據時，寄存器中仍然保持原有數據。這些表示原有數據的數字是固定不動的，相當于是障礙物，移動數字要避開它們。同時，移動數字不能走出寄存器的范圍，寄存器四周相當于是墻壁。

圖1　寄存器內部路徑

采用人工勢場法形成路徑。其中有3個力影響數字的移動：目標點“寄存器出口”的牽引力F0UT、障礙物數字的斥力F0B和墻壁的斥力FWALL。

到達寄存器出口之后，數字將沿著支線移動，經過輸出控制門，前往干線（總線）。如圖2所示。

圖2　寄存器出口路徑

在輸出支線上，起點的坐標B已知，支線上控制門的坐標C已知。根據這兩個坐標可以確定一個方向向量：

根據V0UT的方向，設置合適的測試間隔，決定兩個測試點。比如，在圖2中，方向向量V0UT指向第4象限，就在南和東兩個方向設置兩個測試點。從兩個測試點各向下發出一條射線，通過D3DXIntersect（）函數，獲知測試點與下方物體的距離。3D模型中，支線和干線是在同一個水平高度上的。如果測試點下方不是支線，測得的距離就會有不同。圖中南方向的測試點在支線上，而東方向的測試點不在支線上。因此，當前的前進方向確定為“向南”。

明確了第一個測試點之后，把它做為移動數字的目標點。采用人工勢場法，讓這個目標點對移動數字產生引力。由于支線是平行于Y軸或者X軸的，目標點的引力會引著移動數字沿著支線移動，在沒有拐角時不會偏出支線，所以就把支線兩側的墻壁簡化掉，可以減少計算量。

當第一個移動數字在支線上移動時，后序的移動數字可以踩著前一個移動數字的腳印前進，不必另行規劃路徑。這就需要一個鏈表記載第一個移動數字的腳印。當后序的移動數字都踩過某個腳印之后，這個腳印就可以從鏈表中刪除了。

移動數字到達測試點之后，沿著當前方向，繼續尋找下一步的測試點。這個過程很像“摸石頭過河”。如圖3所示。在前進方向的前、左、右3個方向上進行測試。在到達拐角之前，測試結果都是“前測試點在支線上，左、右測試點不在支線上”，前測試點就是“下一塊石頭”，就是新的目標點，對移動數字產生引力。

圖3　直線上的路徑

如圖4所示，當前進到向左轉向的拐角時，前測試點F和右測試點R將不在支線上，左測試點L在支線上。這時，把前進方向由“向南”改為“向東”。向右轉向的拐角有類似的情況，把前進方向由“向南”改為“向西”。

當前進到支線與干線的交匯點時，交匯點類似一個三岔路口或十字路口。前、左、右3個測試點中，至少有兩個會在干線或支線上。如圖5所示，左測試點L和右測試點R在干線上。

圖4　拐角的路徑

圖5　支線與干線的交匯點

下面要進行干線上的路徑規劃，使移動數字沿著干線到達“終點支線與干線的交匯點”。由于到目前為此，這個坐標還是未知的，所以，現在要先確定它。

確定“終點支線與干線的交匯點”的坐標，方法與“起點支線與干線的交匯點”的確定過程是一樣的。從移動數字的終點開始，沿著支線反向推測，就可以找到它。這個過程中，不涉及移動數字的動態顯示，只找交匯點坐標。

最后，在起點支線與干線的交匯點，與終點與干線的交匯點之間，建立起一條路徑。

干線是一個U型的內部總線，采用極坐標系的人式勢場法建立路徑。在U型內部總線的內側，任選一點作為極坐標系的原點，U型內部總線的開口方向為坐標軸方向。如圖6所示。假設圖中A點是起點支線與干線的交匯點，D點是終點支線與干線的交匯點。極坐標中A點的角度α小于D點的角度β，干線上的路徑就是從角度小的位置向角度大的位置前進。沿著干線向下找測試點，直到拐角B點，轉向左找測試點，直到拐角C點，最后找到D點。

圖6　干線上的路徑

為了防止誤入支線，要事先確定B點和C點的極坐標。當測試點的角度小于B點的角度時，只向南移動。測試點的角度大于B點的角度之后，改為向西移動。當測試點的角度大于C點之后，改為向北移動。

如果起點在左側，終點在右側，干線上的路徑就是從角度大的位置向角度小的位置前進。方法類似。

到達D點之后，開始在終點支線上的移動。在終點支線上的路徑規劃與起點支線方法相同。

進入終點寄存器后，寄存器中沒有靜態數字，沒有障礙物，移動數字在終點坐標處的引力作用下，直奔終點，完成全部移動過程。最后幾個數字會受前面數字的影響。比如，移動數字為8個，前5個數字到達目的地之后，后3個數字需要避開它們。前5個數字相當于后3個數字的障礙物，處理方法與起點寄存器類似。

2　移植到其他3D模型時的問題

2.1對于控制門位置的要求

由于移動數字在起點支線的初始方向要參照控制門的位置來確定，所以，在建立3D模型時，對控制門的位置有一定的要求。如果起點與控制門之間沒有拐點或者只有一個拐點，移動數字的初始方向的確定是沒有問題的。

如圖7所示，B處是不能安排控制門的。如果把A處的出口控制門安排在B處，同樣可以實現對“循環移位器”出口的控制。但是，在確定移動數字離開“循環移位器”的初始方向時，要根據“循環移位器”的出口坐標E和出口控制門的坐標B的連線來決定。這樣就把初始方向算錯了。這種出錯情況的一個特征是E與B之間有兩次相同方向的拐角。

圖7　控制門的位置

由于入口控制門要參與終點支線與干線交匯點的確定過程，所以，入口控制門的位置C也有類似的要求。

圖中C處的入口控制門是可以安排在D處的。雖然D處與入口坐標F之間有兩個拐角，但這兩個拐角是不同方向的，所以不影響從入口逆推終點交匯點時的初始方向。在出口控制門也有類似的情況。總之，出口坐標與出口控制門之間不出現連續的同向拐角，入口坐標與入口控制門之間不出現連續的同向拐角，就可以正確確定移動數字的初始方向。

2.2測試點間隔的設定

在決定下一個局部目標點時，要以一個相同的間隔分別向前進方向的前、左、右3個方向設定測試點（比如圖4中的F、L、R 3個測試點）。測試點的間隔有一個合適的范圍，超出范圍會導致錯誤的測試結果。間隔不能太小，要大于3D模型中支線或干線的寬度。間隔太小會在支線與干線并沒有交匯時，也出現測試點多于一個的情況。間隔也不能太大，不能讓測試點落在另一條支線或干線上。

3　結束語

本文介紹了一個實現《微機原理》CAI課件時面臨的實時路徑規劃問題的解決過程。通過分段規劃的方法，減少了計算的復雜度，滿足了實時性的要求。實現的課件效果良好。同時，只要修改少量的參數，課件就可以適用于其它的一些類似的3D模型。如果3D模型差異較大，可能需要修改少量代碼。

［1］單建華.基于行為的實時路徑規劃［J］.控制工程，2009，16（3）：367_370.

［2］莊慧忠，李晗，陸震宇.動態不確定環境下移動機器人的在線實時路徑規劃［J］.計算機應用與軟件，2011，28（2）：172_ 175，194.

［3］李天成，孫樹棟，高揚.基于扇形柵格地圖的移動機器人全局路徑規劃［J］.機器人，2010，32（4）：547_552.

［4］張彪，曹其新，王雯珊.使用三維柵格地圖的移動機器人路徑規劃［J］.西安交通大學學報，2013，47（10）：57_61.

［5］馮翔，馬美怡，施尹，等.基于社會群體搜索算法的機器人路徑規劃［J］.計算機研究與發展，2013，50（12）：2543_2553.

［6］吳乙萬，黃智.基于動態虛擬障礙物的智能車輛局部路徑規劃方法［J］.湖南大學學報：自然科學版，2013，40（1）：33_37.

Segmented Path Plannlng of lnteractlVe CAI courseWare

SU Wei_1ong
（School of Computer and Communication Engineering，Liaoning University of Petroleum&Chemical Technology，Fushun 113001，China）

In an interactive CAI courseware，a better teaching effect is achieved by responding user's input using program and demonstrating the process of change.A rea1_time path p1anning prob1em is invo1ved when an interactive CAI courseware is designed for the course of″microcomputer princip1e″.Through adopting different path p1anning methods in different stages according to rea1_time requirement of path p1anning，the comp1exity of computation is reduced，whi1e rea1_time requirement is satisfied.

path p1anningjrea1 timejCAIj3D mode1

TN709

A

1674_6236（2016）10_0058_03

2015_05_28稿件編號：201505248

蘇維龍（1965—），男，遼寧新民人，講師。研究方向：計算機輔助教學。