一般而言，程式設計師在撰寫程式時，常會需要使用或維護別人所寫的程式碼，此時就會遇到理解程式碼的問題。雖然程式設計師閱讀相關的設計文件可以幫助了解程式的運作，但有可能會遇到文件過期的問題，所以通常程式設計師會先閱讀完設計文件，然後在除錯模式下於程式中插入中斷點，藉由觀察中斷點之間變數的變化以及呼叫過的函式路徑，來理解程式運作的方式以及原理。近年來雖然已經有一些軟體視覺化工具可以透過圖形來視覺化程式內部的資料以幫助程式設計師除錯，但它們在實用上還有許多限制，使得軟體視覺化工具無法成為程式設計人員每天使用的工具之一。因此我們提出一個軟體視覺化除錯工具xDIVA[1]來幫助程式設計師進行除錯。xDIVA使用3D的圖形、顏色和動畫來視覺化除錯資訊。讓使用者以理想的視覺化隱喻（Visualization Metaphor(VM))來視覺化變數和資料結構。

xDIVA的動畫系統的呈現方式是將使用者決定的兩中斷點的狀態畫面中加上插補(interpolation)，其中VM的移動方式為計算出兩中斷點中所有VM之個別的位移量，並於在每次畫面更新時將需要移動的VM分別移動了長度為( 總位移量 / 動畫中的總畫面數 )的距離，然而這樣的動畫系統在VM移動時容易穿透其他VM，而造成觀看上的混淆。所以本論文提出一套方法減少xDIVA動畫的視覺混淆，在動畫補間產生前計算出VM移動的路徑以避免移動中與其他VM產生重疊，也就是在VM的位移中加入路徑尋找的概念。此方法提供兩種靜態路徑尋找: a. Astar演算法 、 b. VGRAPH演算法，Astar演算法計算出的結果會與原先的路徑較接近，但是產生的速度較慢， VGRAPH演算法產生路徑的方式較快但是計算結果與原先路徑的差異較大。由於採用靜態路徑尋找，VM於實際移動中還是有機會跟其他移動的VM重疊，所以本論文另外提出一個動態修正路徑的方法避免碰撞，使得使用者能從中選擇適合的演算法產生易於觀察的動畫。

Generally speaking, a programmer usually needs to use or maintain the code which is written by someone else. Before he/she is capable of modifying the code, he/she must understand the program. Several entities can help understanding a program. For example, a design document, if available, can greatly help the understanding of a program. However, a design document might be out of date or inconsistent to the code. Tracing the source code is often used as a last resort. It is common to trace a program by debugger. The programmers set break points inside the program and then execute the program in debug mode to observe the change of variable values in order to understand how does the program work.

In recent years, although there have been some software visualization tools to visualize the data structure in the program by graphic and try to help programmers debugging, but these tool have many restrictions on the practical use which make the programmer not use these visualization tool every day. Therefore, we propose a visualization debugging tool xDIVA[1] to help programmers debugging. xDIVA use 3D graphics, color and animation to visual debugging information. xDIVA allows the user choosing the desired visual metaphor (Visualization Metaphor (VM)) to visualize variables and data structures.
xDIVA animation system to generate interpolated frames between key frames, where key frames are snapshots of the 3D scene at breakpoints. The VM moving in the animation which may pass through other VM, this situation will cause the visual confusion when programmer watching the animation. To solve this problem, this paper presents a method to reduce the visual confusion xDIVA animation by giving a collision-free path to the moving VM.
We provide two static path-finding algorithm: A*(Astar) and VGRAPH for user to generate a path for VM. The path computed by A* is similar to the original way by interpolation, but it take much more time in computing; the path generated by VGRAPH is very different from the original path but It’s computing time is less than A*.The environment in DIVA is 3D, so the path generated by static path-finding algorithm still have chance to collide with dynamic object. Therefore, we propose a dynamic path-modifying algorithm to solve the problem.

[1] Y.-P. Cheng, H.-Y. Tsai, C.-S. Wang and C.-H. Hsueh. xDIVA: automatic animation between debugging break points. In Proceedings of the 5th international symposium on Software visualization, Salt Lake City, Utah, USA, pages 221–222, 2010.

[2] Guido Rößling and Bernd Freisleben. Experiences in using animations in introductory computer science lectures. In SIGCSE, Bulletin, 32(1):134-138, 2000.

[3] Jorma Sajaniemi and Marja Kuittinen. Program Animation Based on the Roles of Variables. In Proceedings of the 2003 ACM symposium on Software visualization, pages 7-ff, 2003.

[4] Lauer, T., Muller, R. and Ottmann, T. Animations for Teaching Purposes: Now and Tomorrow. Special Issue of the Journal of Universal Computer Science (J.UCS), 7(5):420-433, 2001.

[5] Stasko, J. and Kraemer, E. A methodology for building application-specific visualizations of parallel programs. In Journal of Parallel and Distributed Computing, 18(2):258-264, 1993.

[6] Stasko, J. Tango: A framework and system for algorithm animation. In SIGCHI, 21(3), Bulletin, 1990.

[7] Stasko, J. Animating algorithm with XTANGO. In SIGACT, 23(2):67-71, 1992.

[8] Moreno, A., Myller, N., Sutinen, E., and Ben-Ari, M. Visualizing Programs with Jeliot 3. In the Proceedings of the International Working Conference on Advanced Visual Interfaces, AVI’04, pages 373 -376, 2004.

[9] http://en.wikipedia.org/wiki/Tcl

[10] Dijkstra, E. W. A note on two problems in connexion with graphs. In Numerische Mathematik, 1(1):269–271, 1959.

[11] http://en.wikipedia.org/wiki/A*_search_algorithm

[12] T. Lozano-Pérez and M.A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles. In Communications of the ACM, 22(10):560-570, 1979.

[13] Y. H. Liu and S. Arimoto. Proposal of Tangent Graph and Extended Tangent Graph for Path Planning of Mobile Robots. In Proceedings of the 1991 IEEE International Conference on Robotics and Automation, volume 1, pages 312 - 317, 1991.

[14] CHIEN-WAN HUN, HUN-CHEN CHEN and MING-FUNG HWANG. On-Line Algorithm for Optimal 3D Path Planning. In Computer Applications in Engineering Education, 2010

[15] Hachour. A three dimensional collision- free-path planning. International Journal of Systems Applications, Engineering & Development, 3(4):117-126, 2009.

[16] S.J. Guy, J. Chhugani, C. Kim, N. Satish, M. Lin, D. Manocha and P. Dubey. ClearPath: highly parallel collision avoidance for multi-agent simulation. Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, New Orleans, Louisiana: ACM, pages 177–187, 2009.

[17] Cherif Foudil1, Djedi Noureddine1, Cedric Sanza and Yves Duthen. Path Finding and Collision Avoidance in Crowd Simulation. Journal of Computing and Information Technology, 17(3): 217–228, 2009