游戏服务端NPC寻路
2019-03-16 本文已影响2人
大华夏
在制作MMO类型游戏时，角色的寻路可以放在客户端进行(基本上现在的游戏引擎都有寻路支持)，这个时候服务端只需要做些寻路校验即可。可对于NPC来说，如果放到客户端是乎就不太合理了，单人副本或许还勉强可行，对于多人联机副本来说，就不好弄了，这个时候就需要服务端来对NPC做寻路处理。
如何设计NPC寻路
假设NPC要从A点到B点，如果都是直接走直线(两点距离)也就无所谓寻路了，而在游戏场景中会有很多地方设置了障碍物，那么遇到有障碍物的地方就得绕路走，最终才到达终点。把所以经过的点串起来这就是一个路径了。
那么我们在设计算法时就得有个依据，有个规则：每走一步我们都认为走的这点到终点的直线距离最短的这个点(不能是障碍物点)就是我们要走的点，不需要考虑这点与终点之间是否有障碍物。
image.png
如图，按照这个规则从A到B，中途会经过a，b，c点。b点是个很重要点，按我们的原则来说走到a点时，肯定下一步就是要走到b点，因为此时b点距离B点的直线距离最近。而走到b之后，会发现此时没法往前走(前面都是障碍物)了。所以在设计算法时，这个时候就得往回退一步，回到a点，再找下一步(此时要把b排除在外，否则就死寻死路了)，往后直到走到B点。
代码实现
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* NPC寻路封装
* @author chester
*
*/
public class WayFinding {
//有效路径
private LinkedList<int[]> path = new LinkedList<>();
//当前要检测的点
private List<int[]> checks = new ArrayList<>();
//起点
private int[] start;
//终点
private int[] end;
//是否寻路结束
private boolean finish = false;
private static final Boolean flag = new Boolean(true);
//存放所以已经检测过的点
private Map<int[], Boolean> checked = new HashMap<>();
//
private Map<String, List<String>> removePaths = new HashMap<>();
public WayFinding(int[] start,int[] end) {
this.start = start;
this.end = end;
this.path.add(this.start);
}
/**
* 添加检测的坐标
* 如果此坐标已经被检测过，则不能添加
* @param x
* @param y
*/
private void addCheck(int x,int y) {
boolean add = true;
for (int[] checkedOne : checked.keySet()) {
if(checkedOne[0] == x && checkedOne[1] == y) {
add = false;
break;
}
}
if(!add) {
return;
}
int[] point = new int[] {x,y};
checked.put(point, flag);
checks.add(point);
if(point[0] == end[0] && point[1] == end[1]) {
finish = true;
}
}
/**
* 增加检测点
* @param map
*/
public void addChecks(int[][] map) {
int[] point = path.getLast();
int x = point[0]; //x
int y = point[1]; //y
addCheck(x-1, y-1, map);
addCheck(x-1, y, map);
addCheck(x-1, y+1, map);
addCheck(x, y-1, map);
// addCheck(x, y, map);
addCheck(x, y+1, map);
addCheck(x+1, y-1, map);
addCheck(x+1, y, map);
addCheck(x+1, y+1, map);
}
/**
* 添加可检测的坐标
* @param x
* @param y
* @param map
*/
private void addCheck(int x,int y,int[][] map) {
if(x<0 || y<0) {
return;
}
// map.length
if(x >= map.length || y>= map[0].length) {
return;
}
if(map[x][y] == 1) {//有障碍物，不能通过
return;
}
for (int[] point : path) {
if(x == point[0] && y==point[1]) {
return;
}
}
int[] last = path.getLast();
String fromKey = String.format("[%d,%d]", last[0],last[1]);
String toKey = String.format("[%d,%d]", x,y);
List<String> removePaths = getRemovePath(fromKey);
if(removePaths!=null) {
for (String val : removePaths) {
if(val.equals(toKey)) {
return;
}
}
}
addCheck(x,y);
}
/**
* 计算曼哈顿距离
* @param point1
* @param point2
* @return
*/
public static int manhattanDistance(int[] point1,int[] point2) {
return Math.abs(point1[0]-point2[0]) + Math.abs(point1[1]-point2[1]);
}
/**
* 欧几里得距离
* @param point1
* @param point2
* @return
*/
public static int euclideanDistance(int[] point1,int[] point2) {
int x = point1[0]-point2[0];
int y = point1[1]-point2[1];
return x*x + y*y;
}
/**
* 返回寻路路径
* @param map 地图 是一个二维数组(int[x][y]), 坐标值为1时表示有障碍物不能通过
* @return
*/
public LinkedList<int[]> finding(int[][] map) {
boolean findNext = true;
while (!finish) {
if(findNext) {
addChecks(map);//增加检测点
}
findNext = finding0(map);
}
if(removePaths.size()>0) {
//缩减路径
curtailPath();
}
return path;
}
/**
* 精简路径
*/
private void curtailPath(int[][] map) {
int index1 = -1;
int index2 = -1;
for(int i=path.size()-1; i>0;i--) {
int[] point1 = path.get(i);
for(int j=0;j<i-1;j++) {
int[] point2 = path.get(j);
if(neighbor(point1, point2)) {
index1 = i;
index2 = j;
break;
}
}
if(index1!=-1) {
break;
}
}
if(index1!=-1) {
int count = index1-index2-1;
System.out.println("缩减：" +count);
while(count>0) {
path.remove(index2+1);
count--;
}
}
List<int[]> removes = new ArrayList<>();
//再次精简
for(int i=0;i<path.size()-2;i++) {
int[] point1 = path.get(i);
int[] point2 = path.get(i+2);
int[] point = path.get(i+1);
if(neighbor(point1, point2)) {
removes.add(point);
i++;
continue;
}
if(point1[0] == point2[0] && Math.abs(point1[1]-point2[1]) == 2) {
int x = point1[0];
int y = point1[1]>point2[1] ? point2[1]+1 : point1[1]+1;
if(point[0] !=x || point[1]!=y) {
if(map[x][y] !=1) {
path.set(i+1, new int[] {x,y});
}
}
}else if(point1[1] == point2[1] && Math.abs(point1[0]-point2[0]) == 2) {
int x = point1[0]>point2[0] ? point2[0]+1 : point1[0]+1;
int y = point1[1];
if(point[0] !=x || point[1]!=y) {
if(map[x][y] !=1) {
path.set(i+1, new int[] {x,y});
}
}
}
}
if(removes.size()>0) {//移除不需要的节点
path.removeAll(removes);
}
}
private boolean neighbor(int[] point1,int[]point2) {
int x1 = point1[0];
int y1 = point1[1];
int x2 = point2[0];
int y2 = point2[1];
if(x1-1 == x2 && (y1-1==y2 || y1 == y2 || y1+1 == y2)) {
return true;
}
if(x1 == x2 && (y1-1 == y2 || y1+1 == y2)) {
return true;
}
if(x1+1 == x2 && (y1-1 == y2 || y1 == y2 || y1+1 == y2)) {
return true;
}
return false;
}
/**
* 寻找下个点
* @param map
* @return 未寻到下个点返回false
*/
private boolean finding0(int[][] map) {
//保存最小曼哈顿点
int minManhanttan = 0;
int[] minPoint = null;
for (int[] point : checks) {
int manhattan = manhattanDistance(point, end);
// int manhattan = euclideanDistance(point, end);
System.out.println("Distance: " + manhattan);
if(minPoint == null) {
minPoint = point;
minManhanttan = manhattan;
}else {
if(minManhanttan>manhattan) {
minManhanttan = manhattan;
minPoint = point;
}
}
}
if (minPoint == null || checks.size() == 0) {//此时说明已无路可走，只能往回走了
backOne(map);
return false;
}
path.add(minPoint);
checks.clear();
System.out.println(String.format("findingPath: (%d,%d)", minPoint[0],minPoint[1]));
return true;
}
private int[] removeFromChecked(int x,int y) {
int[] remove = null;
for (int[] point : checked.keySet()) {
if(point[0] == x && point[1] == y) {
remove = point;
break;
}
}
if(remove!=null) {
checked.remove(remove);
}
return remove;
}
/**
* 添加退后一步后需要检测的坐标
* @param xx
* @param yy
* @param last
* @param map
*/
private void backOneAddCheck(int xx,int yy,int[] last,int[][] map) {
if(last == null || (xx != last[0] || yy!=last[1])) {//被移除的坐标不能再次添加，否则就死循环了
int[] add = removeFromChecked(xx, yy);
if(add==null) {
add = new int[] {xx,yy};
}
addCheck(xx, yy, map);
}
}
private List<String> getRemovePath(String fromKey){
if(!removePaths.containsKey(fromKey)) {
return null;
}
return removePaths.get(fromKey);
}
private void addRemovePath(String fromKey,String toKey) {
if(!removePaths.containsKey(fromKey)) {
removePaths.put(fromKey, new ArrayList<>());
}
removePaths.get(fromKey).add(toKey);
}
/**
* 往回退一个步
* 此时需要从路径中移除除最后一个坐标，移除后，把与新的最后一个坐标相邻的坐标(被移除的坐标除外)添加到路径检测中
* @param map
*/
private void backOne(int[][] map) {
int[] point = null;
int[] last = null;
last = path.removeLast(); //删除最后一个节点
point = path.getLast();
String fromKey = String.format("[%d,%d]", point[0],point[1]);
String toKey = String.format("[%d,%d]", last[0],last[1]);
addRemovePath(fromKey, toKey);
int x = point[0]; //x
int y = point[1]; //y
backOneAddCheck(x-1, y-1,last, map);
backOneAddCheck(x-1, y,last, map);
backOneAddCheck(x-1, y+1,last, map);
backOneAddCheck(x, y-1,last, map);
backOneAddCheck(x, y+1,last, map);
backOneAddCheck(x+1, y-1,last, map);
backOneAddCheck(x+1, y,last, map);
backOneAddCheck(x+1, y+1,last, map);
}
}
测试
import java.util.LinkedList;
/**
* 地图信息
*
* @author chester
*
*/
public class MapAtlas {
// 地图
public static final int[][] map = new int[][] {
//{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 0
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 1
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 2
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 3
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 4
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 5
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 6
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 7
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, }, // 8
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 9
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 10
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, }, // 11
{ 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, }, // 12
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, // 13
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, // 14
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, // 15
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, // 16
};
public static void main(String[] args) {
WayFinding wayFinding = new WayFinding(new int[] { 3, 3 }, new int[] { 14, 22 });
LinkedList<int[]> path = wayFinding.finding(map);
System.out.println("经过的点:");
for (int[] point : path) {
System.out.println(String.format("point(%d,%d)", point[0],point[1]));
}
}
}
结果输出：
经过的点:
point(3,3)
point(4,4)
point(5,5)
point(6,6)
point(7,7)
point(8,8)
point(9,9)
point(10,10)
point(11,9)
point(11,8)
point(11,7)
point(12,6)
point(13,7)
point(14,8)
point(14,9)
point(14,10)
point(14,11)
point(14,12)
point(14,13)
point(14,14)
point(14,15)
point(14,16)
point(14,17)
point(14,18)
point(14,19)
point(14,20)
point(14,21)
point(14,22)
总结
从寻找出来的路径来看，虽然不是最优路径，但不影响使用了。通常来说NPC的移动是有范围的，而在所移动范围的障碍物呢实际上是非常有限的，当角色移动到NPC的范围内，NPC的移动加上角色的移动，在视觉感官上显得也就自然了。
