1、插件或者TileMap工具生成地图json文件
2、astar寻路算法
3、将json文件与寻路算法结合，获得路径坐标，并转化为游戏内的实际坐标
// astar算法 模仿blake老师的写法，用来熟悉算法
var map_maze = []; // 场景节点顺序保存数组
var open_table = []; // 开启列表
var close_table = []; // 关闭列表
var path_stack = []; // 保存路径
var is_found = 0; // 是否找到路径 1 true 0 false
var open_node_count = 0; // 开启列表元素个数
var close_node_count = 0; // 关闭列表元素个数
var top = -1; // path_stack从后往前变量指针
var map_height = 0; //地图高度
var map_width = 0; // 地图宽度
var BARRIER = 1; // 阻挡标记
function swap(idx1, idx2) {
var tmp = open_table[idx1];
open_table[idx1] = open_table[idx2];
open_table[idx2] = tmp;
}
function adjust_heap(nIndex){
var curr = nIndex;
var child = curr * 2 - 1; // 得到左孩子idx( 下标从0开始，所有做孩子是curr*2+1 )
var parent = Math.floor((curr - 1) / 2); // 得到双亲idx
if(nIndex < 0 || nIndex >= open_node_count){
return;
}
// 往下调整( 要比较左右孩子和cuur parent )
while(child < open_node_count){
if(child + 1 < open_node_count &&
open_table[child].s_g + open_table[child].s_h > open_table[child + 1].s_g + open_table[child + 1].s_h){
++child; // 判断左右孩子大小
}
if (open_table[curr].s_g + open_table[curr].s_h <= open_table[child].s_g + open_table[child].s_h) {
break;
}else{
swap(child, curr); // 交换节点
curr = child;// 再判断当前孩子节点
child = curr * 2 + 1; // 再判断左孩子
}
}
if (curr != nIndex) {
return;
}
// 往上调整( 只需要比较cuur child和parent )
while (curr != 0) {
if (open_table[curr].s_g + open_table[curr].s_h >= open_table[parent].s_g + open_table[parent].s_h) {
break;
} else {
swap(curr, parent);
curr = parent;
parent = Math.floor((curr - 1) / 2);
}
}
}
function insert_to_opentable(x, y, curr_node, end_node, w){ // w损耗
var i;
if (map_maze[x * map_width + y].s_style != BARRIER){ // 不是障碍物
if (!map_maze[x * map_width + y].s_is_in_closetable){ // 不在闭表中
if (map_maze[x * map_width + y].s_is_in_opentable){ // 在open表中
// 需要判断是否是一条更优化的路径
// 检查如果用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些,
// 如果新的G值更低, 那就把它的 "父方格" 改为目前选中的方格 C,
// 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的).
// 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做.
if (map_maze[x * map_width + y].s_g > curr_node.s_g + w){ //如果更优化
map_maze[x * map_width + y].s_g = curr_node.s_g + w;
map_maze[x * map_width + y].s_parent = curr_node;
for (i = 0; i < open_node_count; ++i) {
if (open_table[i].s_x == map_maze[x * map_width + y].s_x && open_table[i].s_y == map_maze[x * map_width + y].s_y) {
break;
}
}
adjust_heap(i); // 下面调整点
}
}else{// 不在open中
map_maze[x * map_width + y].s_g = curr_node.s_g + w;
map_maze[x * map_width + y].s_h = Math.abs(end_node.s_x - x) + Math.abs(end_node.s_y - y);
map_maze[x * map_width + y].s_parent = curr_node;
map_maze[x * map_width + y].s_is_in_opentable = 1;
open_table[open_node_count++] = (map_maze[x * map_width + y]);
}
}
}
}
// 邻居处理
function get_neighbors(curr_node, end_node) {
var x = curr_node.s_x;
var y = curr_node.s_y;
// 下面对于8个邻居进行处理！
// 直线损耗10 斜线损耗14
if ((x + 1) >= 0 && (x + 1) < map_height && y >= 0 && y < map_width) {
insert_to_opentable(x + 1, y, curr_node, end_node, 10);
}
if ((x - 1) >= 0 && (x - 1) < map_height && y >= 0 && y < map_width) {
insert_to_opentable(x - 1, y, curr_node, end_node, 10);
}
if (x >= 0 && x < map_height && (y + 1) >= 0 && (y + 1) < map_width) {
insert_to_opentable(x, y + 1, curr_node, end_node, 10);
}
if (x >= 0 && x < map_height && (y - 1) >= 0 && (y - 1) < map_width) {
insert_to_opentable(x, y - 1, curr_node, end_node, 10);
}
if ((x + 1) >= 0 && (x + 1) < map_height && (y + 1) >= 0 && (y + 1) < map_width) {
insert_to_opentable(x + 1, y + 1, curr_node, end_node, 10 + 4);
}
if ((x + 1) >= 0 && (x + 1) < map_height && (y - 1) >= 0 && (y - 1) < map_width) {
insert_to_opentable(x + 1, y - 1, curr_node, end_node, 10 + 4);
}
if ((x - 1) >= 0 && (x - 1) < map_height && (y + 1) >= 0 && (y + 1) < map_width) {
insert_to_opentable(x - 1, y + 1, curr_node, end_node, 10 + 4);
}
if ((x - 1) >= 0 && (x - 1) < map_height && (y - 1) >= 0 && (y - 1) < map_width) {
insert_to_opentable(x - 1, y - 1, curr_node, end_node, 10 + 4);
}
}
// 0. 初始化01地图
// 1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表.
// 2. 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A.
// 3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格
// 4. 从 "开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块),检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑) 的方格. 如果这些方格还不在 "开启列表" 里的话, 将它们加入 "开启列表", 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的 "父方格" 为 C.
// 5. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些, 如果新的G值更低, 那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做.
// 就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表". 再继续找出它周围可以到达的方块, 如此循环下去...
// 那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经被找到.
// 最后以终点为起点通过 "父方块" 可以依次索引到最初的 "起始方块", 这样就得到了路径
// 0.(此处是否可优化下map_maze的初始化，不必每次都清空push一次？？？)
function astar_init(map){
open_table = [];
close_table = [];
path_stack = [];
map_maze = [];
map_height = map.height;
map_width = map.width;
is_found = 0;
open_node_count = 0;
close_node_count = 0;
top = -1;
for (var i = 0; i < map.length; i++){
for(var j = 0; j < map.width; j++){
var node = {};
// F = G + H 其中，F 是从起点经过该点到终点的总路程，G 为起点到该点的“已走路程”，H 为该点到终点的“预计路程”。
node.s_g = 0; // g值
node.s_h = 0;
node.s_is_in_closetable = 0;
node.s_is_in_opentable = 0;
node.s_style = map.data[i * map.width + j]; // 数据类型 0 1
node.s_x = i;
node.s_y = j;
node.s_parent = null;
map_maze.push(node);
path_stack.push(null);
open_table.push(null);
close_table.push(null);
}
}
}
// 1. A*核心代码
function astar_search(map, src_x, src_y, dst_x, dst_y){
var path = [];
if(src_x == dst_x && src_y == dst_y){
console.log("起点==终点！");
return path;
}
// 初始化map
astar_init(map);
//1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表.
var start_node = map_maze[src_y * map.width + src_x];
var end_node = map_maze[dst_y * map.width + dst_x];
var curr_node = null;
open_table[open_node_count++] = start_node;
start_node.s_is_in_opentable = 1; // 加入open表
start_node.s_g = 0;
// 曼哈顿距离
start_node.s_h = Math.abs(end_node.s_x - start_node.s_x) + Math.abs(end_node.s_y - start_node.s_y);
start_node.s_parent = null;
is_found = 0;
while(1){
curr_node = open_table[0]; // open表的第一个点一定是f值最小的点(通过堆排序得到的)
open_table[0] = open_table[--open_node_count]; // 最后一个点放到第一个点，然后进行堆调整
adjust_heap(0); // 调整堆
close_table[close_node_count++] = curr_node; // 当前点加入close表
curr_node.s_is_in_closetable = 1; // 已经在close表中了
if (curr_node.s_x == end_node.s_x && curr_node.s_y == end_node.s_y) // 终点在close中，结束
{
is_found = 1;
break;
}
get_neighbors(curr_node, end_node); // 对邻居的处理
if (open_node_count == 0) // 没有路径到达
{
is_found = 0;
break;
}
}
if(is_found){
curr_node = end_node;
while(curr_node){
path_stack[++top] = curr_node;
curr_node = curr_node.s_parent;
}
while (top >= 0) // 下面是输出路径看看~
{
console.log(path_stack[top].s_y, path_stack[top].s_x);
path.push(cc.v2(path_stack[top].s_y, path_stack[top].s_x));
top--;
}
}else{
console.log("么有找到路径");
}
return path;
}
module.exports = {
search: astar_search,
};
// nav_map.js 将路径转换为游戏内的坐标
var astar = require("astar");
cc.Class({
extends: cc.Component,
properties: {
// foo: {
// default: null, // The default value will be used only when the component attaching
// to a node for the first time
// url: cc.Texture2D, // optional, default is typeof default
// serializable: true, // optional, default is true
// visible: true, // optional, default is true
// displayName: 'Foo', // optional
// readonly: false, // optional, default is false
// },
// ...
is_debug: true,
},
onLoad: function(){
var newNode = new cc.Node();
this.new_draw_node = newNode.addComponent(cc.Graphics);
this.node.addChild(newNode);
this.new_draw_node.lineWidth = 2;
this.color1 = new cc.Color(0, 255, 0, 255);
this.color2 = new cc.Color(0, 0, 255, 255);
},
map_degbu_draw: function() {
var x_line = this.map.item_size * 0.5;
var ypos = this.map.item_size * 0.5;
this.new_draw_node.clear();
for (var i = 0; i < this.map.height; i++) {
var xpos = x_line;
for (var j = 0; j < this.map.width; j++) {
if (this.map.data[i * this.map.width + j] === 0) {
this.new_draw_node.strokeColor = this.color1;
this.new_draw_node.moveTo(xpos, ypos);
this.new_draw_node.lineTo(xpos + 1, ypos + 1);
this.new_draw_node.stroke();
} else {
this.new_draw_node.strokeColor = this.color2;
this.new_draw_node.moveTo(xpos, ypos);
this.new_draw_node.lineTo(xpos + 1, ypos + 1);
this.new_draw_node.stroke();
}
xpos += this.map.item_size;
}
ypos += this.map.item_size;
}
},
start: function(){
this.map = require("game_map_" + this.node.name);
if (this.is_debug) {
this.map_degbu_draw();
}
},
astar_search: function(src_w, dst_W){
var src = this.node.convertToNodeSpaceAR(src_w);
var dst = this.node.convertToNodeSpaceAR(dst_w);
var src_mx = Math.floor((src.x) / this.map.item_size);
var src_my = Math.floor((src.y) / this.map.item_size);
var dst_mx = Math.floor((dst.x) / this.map.item_size);
var dst_my = Math.floor((dst.y) / this.map.item_size);
var path = astar.search(this.map, src_mx, src_my, dst_mx, dst_my);
var world_offset = this.node.convertToWorldSpaceAR(cc.v2(this.map.item_size * 0.5, this.map.item_size * 0.5));
var path_pos = [];
for(var i = 0; i < path.length; i++){
var x = path[i].x * this.map.item_size;
var y = path[i].y * this.map.item_size;
var pos = cc.v2(world_offset.x + x, world_offset.y + y);
path_pos.push(pos);
}
return path_pos;
}
});
// nav_agent.js 寻路的实际应用
var nav_map = require("nav_map");
var State = {
Idle: 0,
Walk: 1,
};
cc.Class({
extends: cc.Component,
properties: {
// foo: {
// default: null, // The default value will be used only when the component attaching
// to a node for the first time
// url: cc.Texture2D, // optional, default is typeof default
// serializable: true, // optional, default is true
// visible: true, // optional, default is true
// displayName: 'Foo', // optional
// readonly: false, // optional, default is false
// },
// ...
speed: 100,
game_map: {
type: nav_map,
default: null,
}
},
// use this for initialization
onLoad: function() {
this.state = State.Idle;
this.walk_total = 0.0;
this.walk_time = 0;
},
nav_to_map: function(dst_wpos) {
var src_wpos = this.node.convertToWorldSpaceAR(cc.v2(0, 0));
this.road_set = this.game_map.astar_search(src_wpos, dst_wpos);
console.log(this.road_set);
if (!this.road_set || this.road_set.length <= 1) {
this.state = State.Idle;
return;
}
this.walk_next = 1;
this._walk_to_next();
},
stop_nav: function() {
this.state = State.Idle;
},
_walk_to_next: function() {
if (!this.road_set || this.walk_next >= this.road_set.length) {
this.state = State.Idle;
return;
}
var src = this.node.getPosition();
var dst = this.node.parent.convertToNodeSpaceAR(this.road_set[this.walk_next]);
var dir = dst.sub(src); // 朝向
var len = dir.mag();
this.vx = (dir.x / len) * this.speed;
this.vy = (dir.y / len) * this.speed;
this.walk_total = len / this.speed;
this.walk_time = 0;
this.state = State.Walk;
},
_walk_update: function(dt) {
if (this.state != State.Walk) {
return;
}
this.walk_time += dt;
if (this.walk_time > this.walk_total) {
dt -= (this.walk_time - this.walk_total);
}
var sx = this.vx * dt;
var sy = this.vy * dt;
this.node.x += sx;
this.node.y += sy;
if (this.walk_time > this.walk_total) {
this.walk_next++;
this._walk_to_next();
}
},
update: function(dt) {
if (this.state == State.Walk) {
this._walk_update(dt);
}
},
});
// enemy_AI.js 简单的怪物AI
var nav_agent = require("nav_agent");
cc.Class({
extends: cc.Component,
properties: {
// foo: {
// default: null, // The default value will be used only when the component attaching
// to a node for the first time
// url: cc.Texture2D, // optional, default is typeof default
// serializable: true, // optional, default is true
// visible: true, // optional, default is true
// displayName: 'Foo', // optional
// readonly: false, // optional, default is false
// },
// ...
think_f_time: 0.25,
search_R: 150, // 发现玩家追击上去
attack_R: 30, // 攻击玩家。
player_agent: {
type: nav_agent,
default: null,
}
},
// use this for initialization
onLoad: function() {
this.think_time = 0.0;
this.agent = this.getComponent("nav_agent");
},
_do_think_AI: function() {
var target_pos = this.player_agent.node.getPosition();
var now_pos = this.node.getPosition();
var dir = target_pos.sub(now_pos);
var len = dir.mag();
if (len > this.search_R) { // 停止下来
this.agent.stop_nav();
return;
}
if (len < this.attack_R) {
this.agent.stop_nav();
return;
}
target_pos = this.player_agent.node.convertToWorldSpaceAR(cc.v2(0, 0));
this.agent.nav_to_map(target_pos);
},
// called every frame, uncomment this function to activate update callback
update: function(dt) {
this.think_time += dt;
if (this.think_time >= this.think_f_time) { // 决策来做思考
this.think_time = 0.0;
this._do_think_AI();
}
},
网友评论