Continue reading “Lindenmayer System 分形圖形學 – 以閃電效果為例”

Voronoi Diagram 是由俄國數學家 Georgy Voronoy 所定義的空間分割圖，在許多領域都有廣泛的應用。

Continue reading “Voronoi Diagram – A Case Study of Fortune’s Algorithm”

嘗試了在 Roguelike 遊戲中會看到的隨機迷宮生成
在每次玩家進入地城時會產生出不一樣的迷宮
使遊戲的變化性提升

Continue reading “Maze Generator – 迷宮產生器”

偶然和同好聊到 A* 時
得知了一種優化方法
可以得到更高效能的運算結果
 
先來看一張沒有用這種方法優化所算出來的路徑

 
可以看出雖然原來的方法所算出來的路徑的確正確
但卻又不能算是最佳路徑
原因在於一定要經過我們所定義出可行走的點
但如果將算出來的路徑再重製一次後會不會得到更好的結果呢?
 
可視點優化(Line of sight)：
原理相當簡單，我們人在行走時如果遇到上面這種狀況
一定會以我們 “看” 到的最佳點前進
以上圖為例
我們在左下角的起點要向右上角的終點移動時
一定會直接以紅框為下一個目標點
因為我們可以 “看” 見紅框點
 
找到專案中的 AStar.cs
並新增 Function 如下

private static ArrayList LineOfSight( ArrayList path )
{
	ArrayList list = new ArrayList();
	list.Add( (Node)path[0] );

	Node startNode = (Node)path[0];
	Node nextNode;

	int checkIndex = 1;

	while( checkIndex < path.Count )
	{
		nextNode = ( (Node)path[checkIndex] );

		if( !Physics.Linecast( startNode.position, nextNode.position ) )
		{
			checkIndex++;
		}
		else
		{
			if( checkIndex == path.Count - 1 )
			{
				list.Add( (Node)path[checkIndex - 1] );
				list.Add( (Node)path[checkIndex] );
			}
			else
			{
				list.Add( (Node)path[checkIndex - 1] );
				startNode = (Node)path[checkIndex - 1];
				nextNode = (Node)path[checkIndex];
			}

			checkIndex++;
		}
	}

	return list;
}

 
接著找到原來的 CalculatePath 方法
並修改成

private static ArrayList CalculatePath(Node node)
{		
	ArrayList list = new ArrayList();
		
	while (node != null)
	{			
		list.Add( node );
		node = node.parent;			
	}
		
	list.Reverse();
	return LineOfSight( list );
}

 
這樣一來就可算出 Line of sight 優化過後的路徑

 
和沒有優化的路徑相比
是不是又更簡單明瞭
附上一張多障礙物模擬

到目前為止
A* 的基本實作都已經結束了
但我們可以做一些簡單的優化來提高 A* 的運算結果
 
在上一篇中可以發現
雖然計算出來的路徑的確是最短路徑
但在移動方向上卻只限制於上下左右四個方向
 
考慮到優化演算的結果
我們在這邊加入斜向方向判定
 
首先一樣找到 NodeManager.cs 腳本
找到 GetNeighbours 方法

//Get the current node's neighbors
public void GetNeighbours( Node node, ArrayList neighbors )
{		
	Vector3 neighborPos = node.position;
	int row = GetNodeRow( neighborPos );
	int column = GetNodeColumn( neighborPos );
		
	//Bottom
	int leftNodeRow = row - 1;
	int leftNodeColumn = column;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Top
	leftNodeRow = row + 1;
	leftNodeColumn = column;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Right
	leftNodeRow = row;
	leftNodeColumn = column + 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Left
	leftNodeRow = row;
	leftNodeColumn = column - 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);			
}

在原本的方法中
我們只有上下左右四個方向
所以在這邊將斜向方向也一併加入運算

//Get the current node's neighbors
public void GetNeighbours( Node node, ArrayList neighbors )
{		
	Vector3 neighborPos = node.position;
	int row = GetNodeRow( neighborPos );
	int column = GetNodeColumn( neighborPos );
		
	//Bottom
	int leftNodeRow = row - 1;
	int leftNodeColumn = column;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Top
	leftNodeRow = row + 1;
	leftNodeColumn = column;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Right
	leftNodeRow = row;
	leftNodeColumn = column + 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Left
	leftNodeRow = row;
	leftNodeColumn = column - 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);

	//Bottom Right
	leftNodeRow = row - 1;
	leftNodeColumn = column + 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Bottom Left
	leftNodeRow = row - 1;
	leftNodeColumn = column - 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Top Right
	leftNodeRow = row + 1;
	leftNodeColumn = column + 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Top Left
	leftNodeRow = row + 1;
	leftNodeColumn = column - 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);			
}

 
再次執行 Unity
結果如下

 
加入斜向移動後果然移動距離又更短了
最後附上多個障礙物的模擬

在上一篇中我們已經完成了 A* 尋路的功能了
但是缺少了障礙物判定的方法
如果有認真看每一篇教學的讀者會發現
在一開始定義 Node 時，有一個 isObstacle 參數用來判斷該 Node 是不是障礙物
在這一篇我們就是要將它實現出來
 
找到 NodeManager.cs 腳本
找到其中的 CreateNode 方法

void CreateNodes()
{
	nodes = new Node[numOfColumns, numOfRows];
		
	for (int col = 0; col < numOfColumns; col++)
	{    
		for (int row = 0; row < numOfRows; row++)
		{
			Vector3 cellPos = GetNodePosition(col, row);
			Node node = new Node(cellPos);
			nodes[col, row] = node;
		}            
	}        
}

將它改寫成

void CreateNodes()
{
	nodes = new Node[numOfColumns, numOfRows];
		
	for (int col = 0; col < numOfColumns; col++)
	{	
		for (int row = 0; row < numOfRows; row++)
		{
			Vector3 cellPos = GetNodePosition(col, row);
			Node node = new Node(cellPos);
			nodes[col, row] = node;

			//Obstacle Update
			cellPos -= new Vector3( 0, 100, 0 );
			RaycastHit hit;
			Ray ray = new Ray( cellPos, new Vector3( 0, 1, 0 ) );
				
			if( Physics.Raycast( ray , out hit, 1000 ) )
			{
				if( hit.transform.tag == "Obstacle" )
					nodes[col, row].MarkAsObstacle();
			}				
		}			
	}		
}

 
接著在場景中加入任一包含 Collider 的物件
並將其 Tag 設定為 Obstacle

 
執行 Unity
得到以下成果

終於到了最後一步
可以看到辛苦理解後的實現成果了
 
新增一個 C# 腳本命名為 TestAStar.cs

using UnityEngine;
using System.Collections;

public class TestAStar : MonoBehaviour
{
    //The start and end gameobject
    public GameObject startCube, endCube;
    
    private Transform startTransform, endTransform;

    private Node startNode;
    private Node endNode;

    public ArrayList pathArray;
    private float elapsedTime = 0.0f;

    //Interval time between pathfinding
    public float intervalTime = 1.0f;
    
    void Start ()
    {
        startTransform = startCube.transform;
        endTransform = endCube.transform;

        pathArray = new ArrayList();
        FindPath();
    }
    
    void Update ()
    {        
        elapsedTime += Time.deltaTime;
        
        if (elapsedTime >= intervalTime)
        {
            elapsedTime = 0.0f;
            FindPath();
        }        
    }
    
    void FindPath()
    {
        //Get start node with position
        startNode = new Node( NodeManager.instance.GetNodeCenter( startTransform.position ) );
        //Get end node with position
        endNode = new Node( NodeManager.instance.GetNodeCenter( endTransform.position ) );

        pathArray = AStar.FindPath(startNode, endNode);
    }

    //Display the a-star path finding line
    void OnDrawGizmos()
    {
        if (pathArray == null)
            return;

        if (pathArray.Count > 0)
        {            
            for( int cnt = 0; cnt < pathArray.Count; cnt++ )
            {                
                if( cnt <= pathArray.Count - 2 )
                    Debug.DrawLine( ( (Node)pathArray[cnt] ).position, ( (Node)pathArray[cnt + 1] ).position, Color.green);                
            }
        }
    }    
}

 
這個腳本主要是用來呼叫前面幾篇寫好的方法
直接來看怎麼使用 TestAStar.cs
 
在場景中新增一空物件取名為 AStar
並新增兩個 Cube 分別取名為 Start 以及 End 當作起始點與終點
並將兩個 Cube 分別拉近 AStar 欄位中
執行開始則會看到實作結果

 
到此 A* 演算法實作已經完成了