本文以Python作為服務器, Unity作為客戶端引擎, 主要討論的是服務端實現尋路并由客戶端表現架構下的程序設計思路.
1. 整體思路
首先, 我們討論尋路算法的比較和選擇: A-star一般來說有更好的性能, 因為它是從起點到終點路徑上的點與起點之間的最短路徑計算, 而Dijkstra算法則是起點到圖結構中所有點的最短路徑計算, 有一些浪費了.
服務端尋路架構下, 服務端的作用在于定時根據游戲中玩家的位置變化, 進行新路線計算并把結果用point list的形式發(fā)送給客戶端.
客戶端的職責, 則是要把point list實際轉化為畫面上怪物單位的連續(xù)移動.
2. 討論尋路算法
尋路算法, 指的是找出Start點到End點之間的一條最短路徑. 這條最短路徑通過的是地圖上的可通行區(qū)域, 即應當繞開堵塞區(qū)域(block area).
我們主要考慮兩個常見的最短路徑算法:
A-star(A* search algorithm)
Dijkstra算法
我們可以從時間開銷方面去比較這倆算法:
以常見的二叉堆(又名Priority Queue)實現為例, Dijkstra算法的時間開銷為O(ElgV), E是邊的數目, V是結點的數目, 算法最耗時的操作是從Q中提出V次的最小key值結點(extractMin), 和對所有E條邊進行的decreaseKey操作.
值得注意的是: 迪杰斯特拉算法能夠找出從S(Source)點到所有其他圖結構中結點的最短路徑.
Astar算法, 如果也是用二叉堆實現的話, 時間開銷也是O(ElgV), 因為其最耗時操作也是Q中進行V次的extractMin操作, 以及對所有E條邊進行的decreaseKey操作. 但是, 這里所說的都是算法的最壞情況, 也就是說找出來的最短路徑需要遍歷整個地圖的最壞情況.
由于Astar算法是一個貪心算法(F = G+H中的H數值是用曼哈頓距離估算的, 并不是一個精確可靠的值), 因此雖然Dijkstra和Astar在二叉堆實現情況下都是O(ElgV), 大多數情況下Astar算法的時間開銷只會明顯少于Dijkstra, 我個人粗略估計至少是少一個數量級, 也就是說不到1/10, 特別是地圖越大這個比例會越小.
用更直白的話來說, 迪杰斯特拉算法是找出S點到所有圖中點的最短路徑, A-star只找出S到E和S到路徑上其他點的最短路徑, 明顯A-star要完成的任務更少. 由于游戲中我們大多數情況下只需要S到E點的最短路徑, 因此A-star是更加省時節(jié)約開銷的算法.
3. A-star with heap的實現
# encoding:utf-8
import time
from heapq import heappush, heappop
"""
path finding module: A* path finding算法, 用heap實現版本
quick guide:
start = Node(None, 20, 20)
end = Node(None, 50, 30)
print find_path(start, end) # return path list
It reads a map in the beginning of this script. Currently layout_medium.txt is chosen.
To download map(layout_medium.txt):
https://share.weiyun.com/5mtyHYi
"""
_2dmap = []
map_border = ()
g_close_list = {}
class Node:
def __init__(self, father, x, y, end=None):
if x < 0 or x >= map_border[0] or y < 0 or y >= map_border[1]:
raise Exception("node position can't beyond the border!")
self.father = father
self.x = x
self.y = y
if father != None:
G2father = calc_G(father, self)
if not G2father:
raise Exception("father is not valid!")
self.G = G2father + father.G
self.H = calc_H(self, end)
self.F = self.G + self.H # 初始化的時候計算出F
else: # it has no father, thus it is the start point
self.G = 0
self.H = 0
self.F = 0
def reset_father(self, father, new_G):
if father != None:
self.G = new_G
self.F = self.G + self.H
self.father = father
def calc_G(node1, node2): # 該點
dx = abs(node1.x - node2.x)
dy = abs(node1.y - node2.y)
if dx == 1 and dy == 0:
return 10 # same row
if dx == 0 and dy == 1:
return 10 # same col
if dx == 1 and dy == 1:
return 14 # cross
else:
return 0
def calc_H(cur, end): # 估算該點到終點距離(忽略墻等阻擋物), 采用Manhattan distance
return 10*(abs(end.x - cur.x) + abs(end.y - cur.y))
def addAdjacentIntoOpen_new(heap, open_list, close_list, node, end):
# 將該節(jié)點從開放列表移到關閉列表當中。
open_list.pop((node.x, node.y)) # key 為(x, y)形式的坐標tuple
close_list[(node.x, node.y)] = node
_adjacent = []
# 地圖的layout的邊界需要用0進行標記, 否則會進入except
try:
#_adjacent.append(Node(node, node.x - 1, node.y - 1, end)) # 這個時候就初始化了F值
_adjacent.append(Node(node, node.x, node.y - 1, end))
#_adjacent.append(Node(node, node.x + 1, node.y - 1, end))
_adjacent.append(Node(node, node.x + 1, node.y, end))
#_adjacent.append(Node(node, node.x + 1, node.y + 1, end))
_adjacent.append(Node(node, node.x, node.y + 1, end))
#_adjacent.append(Node(node, node.x - 1, node.y + 1, end))
_adjacent.append(Node(node, node.x - 1, node.y, end))
except Exception, e:
print e
print "***_adjacent append error!", (node.x, node.y)
pass
for a in _adjacent:
if (a.x, a.y) == (end.x, end.y):
new_G = calc_G(a, node) + node.G
end.reset_father(node, new_G)
# print "End point reached!"
return True
if (a.x, a.y) in close_list: # 墻體等部分也在close_list中, 因此不會被認為是可以考慮的結點
continue
if (a.x, a.y) not in open_list:
open_list[(a.x, a.y)] = a
heappush(heap, (a.F, a))
else: # those nodes in open_list
exist_node = open_list[(a.x, a.y)]
new_G = calc_G(a, node) + node.G
if new_G < exist_node.G:
exist_node.reset_father(node, new_G)
# how to update the value in heap? we can push this node into it, and try to clean the heap top later
# 因此, heap取出最小值的時候會檢查是否已經在close_list中
heappush(heap, (exist_node.F, exist_node))
return False
def find_the_path_new(start, end):
"""need to use end node to extract result"""
open_list = {}
close_list = dict(g_close_list)
if (start.x, start.y) in g_close_list.keys():
print "start in block area"
return end
if (end.x, end.y) in g_close_list.keys():
print "end in block area"
return end
open_list[(start.x, start.y)] = start
heap = []
the_node = start
try:
while not addAdjacentIntoOpen_new(heap, open_list, close_list, the_node, end): # only return True when destination reached
F, the_node = heappop(heap)
while (the_node.x, the_node.y) in close_list.keys(): # the_node是已經走過了的點的話, 丟棄了再抽出一個新的the_node,
# 出現這個代碼的原因是addAdjacentIntoOpen_new最后一個else語句中為了實現decreaseKey的操作, 直接塞入了新的結點, 而沒有刪除老的結點
# 這個操作一旦發(fā)生, 我們的Q中會出現重復的結點. 因此這里必須檢查一下是否新取出的heapTop結點是已經在close_list中的走過的結點
F, the_node = heappop(heap)
except Exception, e:
print e
pass
return end
def find_path(start, end):
"""return a path list of points from start to end"""
serialized_list = []
print 'Debug: start: ', (start.x, start.y), ' end: ', (end.x, end.y)
end = find_the_path_new(start, end)
if end.father:
serialize_path(end.father, serialized_list)
serialized_list.reverse()
return serialized_list # 反向, 從而變?yōu)槠瘘c到終點的路徑
else:
return None
# =======================================================================
def print_map():
print ' Y',
for i in xrange(len(_2dmap)):
print i,
print
print ' X'
row = 0
for l in _2dmap:
print '%3d' % row, ' ',
row = row + 1
for i in l:
print i,
print
def mark_path(node):
if node.father == None: # start point
return
_2dmap[node.x][node.y] = '#'
mark_path(node.father)
def serialize_path(node, serialized_list):
"""extract result to a path list containing all the points orderly"""
if node.father == None:
return
serialized_list.append((node.x, node.y))
serialize_path(node.father, serialized_list)
def read_map(filepath):
global map_border
f = open(filepath, 'r')
line = f.readline()
t, origin_pos = line.split("=") # str type
line = f.readline()
t, height = line.split("=")
line = f.readline()
t, width = line.split("=")
line = f.readline()
t, accuracy = line.split("=")
for line in f:
# line = f.readline()
line = line[1:-3].replace(',', '')
l = list(line)
_2dmap.append(l)
map_border = (len(_2dmap), len(_2dmap[0]))
row_index = 0
for row in _2dmap:
col_index = 0
for n in row:
if n == '0': # 0 for block, not reachable
block_node = Node(None, col_index, row_index) # 要非常注意x=col_index, y=row_index
g_close_list[(block_node.x, block_node.y)] = block_node
col_index = col_index + 1
row_index = row_index + 1
def transform_path_list(path_list):
if path_list:
print "crude path:", path_list
return [(p[0]-30.0, 0, 30.0-p[1]) for p in path_list]
else:
return []
read_map('layout_medium.txt') # read map in the beginning
if __name__ == '__main__':
print "original map:"
print_map()
start = Node(None, 8, 19)
end = Node(None, 52, 40)
timePoint1 = time.time()
res = find_path(start, end) # core
print res
print 'time cost: ', time.time() - timePoint1
# extra: mark and print path
if res:
mark_path(end.father)
print_map()
4. 地圖信息的導出和使用
首先, 是地圖信息的導出和使用. 這部分的代碼我是參考的https://blog.csdn.net/fansongy/article/details/51699058這篇文章所給出的一個腳本, 只是根據我的地圖size去修改其的輸入參數.
按下Export按鈕后的樣子
using UnityEngine;
using System.Collections;
using System.Text;
using UnityEditor;
// 將NavMesh轉化為bitmap平面地圖的類
public class NavExport : MonoBehaviour
{
#region Public Attributes
public Vector3 leftUpStart = Vector3.zero;
public float accuracy = 1;
public int height = 30;
public int wide = 30;
#endregion
#region Unity Messages
void OnGUI()
{
if (GUILayout.Button("Export"))
{
exportPoint(leftUpStart, height, wide, accuracy);
}
}
#endregion
#region Public Methods
public void Exp()
{
exportPoint(leftUpStart, wide, height, accuracy);
}
public void exportPoint(Vector3 startPos, int x, int y, float accuracy)
{
StringBuilder str = new StringBuilder();
int[,] list = new int[x, y];
str.Append("startpos=").Append(startPos).Append("\r\n");
str.Append("height=").Append(y).Append("\r\nwide=").Append(x).Append("\r\naccuracy=").Append(accuracy).Append("\r\n");
for (int i = 0; i < y; ++i) // row, 即y值
{
str.Append("{");
for (int j = 0; j < x; ++j) // col, x value
{
int res = list[j, i];
UnityEngine.AI.NavMeshHit hit;
for (int k = -10; k < 30; ++k)
{ // startPos = (-30, 0, 30). x:(-30 ~ 30), y(30, -30)
if (UnityEngine.AI.NavMesh.SamplePosition(startPos + new Vector3(j * accuracy, k, -i * accuracy), out hit, 0.2f, UnityEngine.AI.NavMesh.AllAreas))
{
res = 1;
break;
}
}
Debug.DrawRay(startPos + new Vector3(j * accuracy, 0, -i * accuracy), Vector3.up, res == 1 ? Color.green : Color.red, 100f);
str.Append(res).Append(",");
}
str.Append("},\n");
}
Debug.Log(str.ToString());
System.IO.File.WriteAllText(@"layout.txt", str.ToString(), Encoding.UTF8);
Debug.Log("file written!");
}
#endregion
}
[CustomEditor(typeof(NavExport))]
public class NavExportHelper : Editor
{
public override void OnInspectorGUI()
{
base.OnInspectorGUI();
if (GUILayout.Button("Export"))
{
var exp = target as NavExport;
exp.Exp();
}
}
}
導出時候的參數
5. 服務端
尋路是一項比較消耗CPU時間的任務, 因此我們要限制其的頻率. 具體來說, 我們進行一次新尋路的條件判斷, 主要抓住的是時間和位置. 如果時間間隔不夠大(比如未到0.5sec), 就不尋路; 如果玩家沒有移動, 那么怪物單位也沒有必要再次進行尋路計算, 用之前的路線即可.
if self.nav_timer >= NAVIGATION_INTERVAL and (abs(self.lastPlayerPosition[0]-player.position[0])> 0.5 or abs(self.lastPlayerPosition[2]-player.position[2])>0.5):
self.lastPlayerPosition = player.position
self.navigate(self.position, player.position)
self.navigate函數的實現如下
def navigate(self, start, end):
start = HeapAstar.Node(None, int(round((start[0] + 30.0))), int(round((30.0-start[2]))))
end = HeapAstar.Node(None, int(round((end[0] + 30.0))), int(round((30.0-end[2]))))
self.path_list = HeapAstar.transform_path_list(HeapAstar.find_path(start, end))
這里一個細節(jié)點, 是尋路算法對輸入輸出坐標的轉換. 首先, NavExport.cs腳本所生成的layout.txt的x, y值(分別對應列數, 行數)都是大于0的正整數, 而我們Unity中的坐標往往是以(0, 0, 0)為中心的實數, 很多點的坐標還是負的, 比如(-1.6, 3, -10.52), 因此我們需要坐標的變換, 實現"實轉整, 負轉正".
假設輸入給NavExport.cs腳本的參數是
startpos=(-30.0, 0.0, 30.0)
height=60
wide=60
accuracy=1,
那么, 對坐標轉換處理的代碼如下:
# 輸入坐標的轉換
start = HeapAstar.Node(None, int(round((start[0] + 30.0))), int(round((30.0-start[2]))))
end = HeapAstar.Node(None, int(round((end[0] + 30.0))), int(round((30.0-end[2]))))
# 輸出坐標的轉換
def transform_path_list(path_list):
if path_list:
print "crude path:", path_list
return [(p[0]-30.0, 0, 30.0-p[1]) for p in path_list]
else:
return []
6. 客戶端的實現
客戶端的收包與nav_path更新
JArray navArray = (JArray)x.Value ["nav_path"];
客戶端的路徑應用
using UnityEngine;
using System.Collections;
using Newtonsoft.Json.Linq;
public class EnemyMovement : MonoBehaviour
{
Transform player; // remember it is of type Transform!!!
public UnityEngine.AI.NavMeshAgent nav;
public JArray nav_path;
float moveSpeed = 2.0f;
public float minDistance = 4f;
public Vector3 lastTarget;
EnemyHealth enemyHealth;
PlayerHealth playerHealth;
float timer = 0f;
float lastTimePoint = 0f;
Rigidbody enemyRigidbody;
void Awake() {
player = GameObject.FindGameObjectWithTag("Player").transform; // init
nav = GetComponent<UnityEngine.AI.NavMeshAgent>();
nav.enabled = false; // 默認不要打開, 否則會引發(fā)和服務端尋路的沖突
enemyHealth = GetComponent<EnemyHealth> ();
playerHealth = GameObject.FindGameObjectWithTag ("Player").GetComponent<PlayerHealth> ();
lastTimePoint = Time.realtimeSinceStartup;
enemyRigidbody = GetComponent<Rigidbody>();
}
void FixedUpdate() {
timer = Time.realtimeSinceStartup - lastTimePoint;
if (enemyHealth.currentHealth > 0 && !playerHealth.isDead) { // if both are alive
// 服務端和本地共同尋路
// 遠距離使用服務端尋路
lastTimePoint = Time.realtimeSinceStartup;
if (Vector3.Distance (transform.position, player.position) > minDistance && nav_path != null && nav_path.Count > 0) {
nav.enabled = false;
JToken elem = nav_path [0];
JArray posArray = (JArray)elem;
Vector3 target = new Vector3 ((float)posArray [0], (float)posArray [1], (float)posArray [2]);
// Debug.Log ("target, " + target.ToString("F4") + "; position, " + transform.position.ToString("F4") );
// Debug.Log ("Distance, " + Vector3.Distance (transform.position, target));
if (Vector3.Distance (transform.position, target) <= 0.9f) { // 認為已經到達點了, 更新target
Debug.Log ("point touched, " + transform.position.ToString("F4") );
// Debug.Log ("before, " + nav_path.Count);
nav_path.Remove (elem);
// Debug.Log ("after, " + nav_path.Count);
if (nav_path.Count > 0) {
elem = nav_path [0];
target = new Vector3 ((float)posArray [0], (float)posArray [1], (float)posArray [2]);
}
}
// 向著無論舊的還是新的target行進
Debug.DrawLine(transform.position, target, Color.yellow, 8f, false);
transform.LookAt (target); //敵人面向追蹤目標
transform.eulerAngles = new Vector3 (0.0f, transform.eulerAngles.y, 0.0f); //設置敵人的Rotation屬性，確保敵人只在y軸旋轉
float deltaTime = Time.deltaTime;
Debug.Log("forward, " + transform.forward.ToString("F4") + " speed, " + moveSpeed.ToString("F4") + " timer" + timer.ToString("F4") );
Vector3 movement = transform.forward * moveSpeed * timer;
timer = 0.0f;
Debug.Log ("movement, " + movement.ToString("F4") );
Debug.Log("++++result:" + (transform.position+movement).ToString("F4"));
transform.position = movement + transform.position;
//enemyRigidbody.MovePosition(transform.position+movement); //敵人以moveSpeed的速度向點位靠近
Debug.Log("++++position:" + transform.position.ToString("F4"));
} else { // 近距離使用客戶端尋路
nav.enabled = true;
nav.SetDestination (player.position);
}
} else { // stop navigation if dead
nav.enabled = false;
}
}
void Update() {
}
}
如此, 我們就可以實現服務端計算尋路路線, 客戶端進行表現的架構設計了. 我們可以利用Debug.DrawLine函數來畫出行走的路線(只在UnityEditor的Scene View中展現, 實際Build出來的游戲畫面中是看不到的).
// 輸入參數依次是: line的起點, 終點, 顏色, 持續(xù)存在時間, false這個固定就這么寫.
Debug.DrawLine(transform.position, target, Color.yellow, 8f, false);
最后客戶端行走的效果
