mbm_mlmap.d2l

转载其他网站的资料与大家分享

		var dy = _dy - miny;
		var sx = _sx - minx;
		var sy = _sy - miny;
		var newg;
		var cx = 0;
		var cy = 0;
		var node;

		var _done = false;

		//node grid array used to hold references
		var ng = new Array();
		ng.length = height+1;
		for(var i = 0; i<ng.length; i++){
			ng[i] = new Array();
			ng[i].length = width+1;
		}

		//starting and ending node's
		var enode = new oNode(dx, dy);
		var snode = new oNode(sx, sy, false, true, -1, 0, this[FORWARDHEURISTICS[_fh]](dx, dy, sx, sy)*_factor);
		snode.f = snode.h;
		ng[snode.y][snode.x] = snode;
		oq.Insert(snode);

		//pdis = new oTerminal(100, 30, 40, 40, 6, 0);

		var stime = new Date();
		while (node = oq.Remove())
		{
			//updateterminal(AreaData, node.x, node.y);

			if(node.x == enode.x && node.y == enode.y) {   //Found the destination
				_done = true;
				this.LastScore = node.f;
				if(_reduc == 99)
					return node.f;

				//BUILD PATH USING REFRENCED PARENTS
				var donebuild = false;
				ptd.push(node);
				if (ptd[ptd.length-1].parent!=-1) do {
					ptd.push(ptd[ptd.length-1].parent);
					if (ptd[ptd.length-1].parent==-1)
						donebuild=true;
				} while (!donebuild);

				if(this.PathToMap) {
					var pathbit = 0x10000 << _algo;
					//var pathbit = 0x10000 << _fh-1;
					for (var i = 0; i<ptd.length; i++) {
						AreaData[ptd[i].y][ptd[i].x] |= pathbit;
					}
				}

				//reverse the path now so we can work with it from start and reduce the points
				//TODO: Clean up and add more functionality to the reduction algo
				var vecanglelast = 0;
				var vecanglenew = 0;
				var vecdistance;
				for (var d=ptd.length-1; d>=0; d--)
				{
					if (d == ptd.length-1 && d) {		//add first point always
						fp.push(ptd[d]);
						if(!_reduc)
							vecanglelast = getAngle(fp[fp.length-1].x, fp[fp.length-1].y,
								ptd[d-1].x, ptd[d-1].y);
						else
							vecanglelast = 0;
						continue;
					}

					if (d == 0) {				//add last point always
						fp.push(ptd[d]);
						break;
					}

					if(!_reduc)
						vecanglenew = getAngle(fp[fp.length-1].x, fp[fp.length-1].y,
							   ptd[d].x, ptd[d].y);
					else vecanglenew = 0;
					vecdistance = this.euclidian(fp[fp.length-1].x, fp[fp.length-1].y,
							   ptd[d].x, ptd[d].y);

					if(vecanglenew != vecanglelast || vecdistance > _dist)
					{
						fp.push(ptd[d]);
						if(!_reduc)
							vecanglelast = getAngle(fp[fp.length-1].x, fp[fp.length-1].y,
							   ptd[d-1].x, ptd[d-1].y);
						else vecanglelast = 0;
						continue;
					}

				}
				this.Path = new Array();
				//Put the offset back in and move to path
				for (var d = 0; d<fp.length; d++)
					this.Path[d] = {x:fp[d].x + minx, y:fp[d].y + miny}

				// print("Total pathing time: " + (new Date() - stime));
				return this.Path;

			}
			else {  		// look for adjacent blocks that we attach to and add them to open
				for(var vy = -1; vy < 2; vy ++) {
					for(var vx = -1; vx < 2; vx++)	{
						if(!vx && !vy) continue; //continue if we are on the current node
						cx = node.x+vx; cy = node.y+vy;

						//check for map edge
						if(cy < 0 || cy > height || cx < 0 || cx > width) continue;

						//check for walkability and small diagonal gaps that cant be passed
						if (AreaData[cy][cx] & 1) continue;
						if ((vx*vy) && (AreaData[cy][node.x] & 1) && (AreaData[node.y][cx] & 1)) continue;

						newg = node.g + SCORE[Math.abs(vx*vy)];

						var cnode = ng[cy][cx];

						if(!cnode) {
							cnode = new oNode(cx,cy,false,false,node,newg,this[FORWARDHEURISTICS[_fh]](dx, dy, cx, cy)*_factor);
							ng[cy][cx] = cnode;
						}
						else {
							if (cnode.g > newg){
								cnode.closed = false;
								cnode.g = newg;
								cnode.parent = node;
							}
							else continue;
						}
						cnode.f = cnode.g + cnode.h;

						if(!cnode.open) {
							cnode.open = true;
							oq.Insert(cnode);
							//AreaData[cnode.y][cnode.x] |= 0x200000;
						}
					}
				}
				node.open = false;	node.closed = true;
				//AreaData[node.y][node.x] |= 0x100000;
			}
		}
		print("Couldnt find a path to destination");
		return false;
	}

	//////////////////////////////////////////////////////////////////////
	// oMap.FindSorcPath(_sx, _sy, _dx, _dy, _dist, _err, _dstep, _rstep, _algo)
	// -------------------------------------------------------------------
	// returns: path on success, assigns the path to this.Path; false on failure
	// requires an initialized map
	//////////////////////////////////////////////////////////////////////
	function oMap_findsorcpath(_sx, _sy, _dx, _dy, _dist, _err, _dstep, _rstep, _algo) {

		if(!_sx || !_sy || !_dx || !_dy){ 		//basic check for illegal coordinates
			mlprint("mlMap:mlFindSorcPath - The start or end has a 0 coordinate value");
			this.LastError = ("mlMap:mlFindPath - The start or end has a 0 coordinate value");
			return false;
		}

		if (DelayLoadRooms && !DontLoadRooms) {
			this.LoadPos(_sx, _sy);
			this.LoadPos(_dx, _dy);
		}
		
		if(!_isinrange(_sx, _sy))
		{
			mlprint("mlMap.FindSorcPath - The start coord's are out of range");
			this.LastError = ("mlMap.FindPath - The start coord's are out of range");
			return false;
		}
		
		if(!this.IsWalkable(_sx, _sy))
		{
			mlprint("mlMap.FindSorcPath - The start coord's are not walkable");
			this.LastError = ("mlMap.FindPath - The start coord's are not walkable");
			return false;
		}

		if(!_isinrange(_dx, _dy))
		{
			mlprint("mlMap.FindSorcPath - The end coord's are out of range");
			this.LastError = ("mlMap.FindPath - The end coord's are out of range");
			return false;
		}

		if(!this.IsWalkable(_dx, _dy)) {
			var temp = this.FindClosestWalkable(_dx,_dy);
			_dx = temp.x;
			_dy = temp.y;
		}
//		{
//			mlprint("mlMap.FindPath - The end coord's are not walkable");
//			this.LastError = ("mlMap.FindPath - The end coord's are not walkable");
//			return false;
//		}

		if(typeof(_err) != "number" || _err < 0) _err = 0;
		if(typeof(_dstep) != "number" || _dstep < 1) _dstep = 1;
		if(typeof(_rstep) != "number" || _rstep < 1) _rstep = 1;
		if(typeof(_err) != "number" || _err < 0) _err = 0;
		if(typeof(_algo) != "number" || _algo < 0 || _algo > 1) _algo=0;

		if(_algo) {
			var oq = new oFIFO();
		}
		else var oq = new oHeap("h", mlHEAPLOW);

		var minx = this.minx;
		var miny = this.miny;
		var maxx = this.maxx;
		var maxy = this.maxy;
		var width = this.maxx - this.minx-1;
		var height = this.maxy - this.miny-1;

		var AreaData = this.Area;

		var ptd = new Array();
		var fp = new Array();
		var dx = _dx - minx;
		var dy = _dy - miny;
		var sx = _sx - minx;
		var sy = _sy - miny;
		var newg;
		var cx = 0;
		var cy = 0;
		var node;

		var stime = new Date();
		var nodecenters = new Array();
		var distsq = _dist * _dist;

		var _done = false;

		//node grid array used to hold references
		var ng = new Array();
		ng.length = height+1;
		for(var i = 0; i<ng.length; i++){
			ng[i] = new Array();
			ng[i].length = width+1;
		}

		//starting and ending node's
		var enode = new oNode(dx, dy);
		// var fh = this[FORWARDHEURISTICS[_fh]](dx, dy, sx, sy)*_factor;
		var fh = this.sorcheuristic(dx, dy, sx, sy, _dist);
		var snode = new oNode(sx, sy, false, true, -1, 0, fh);
		snode.f = snode.h;
		ng[snode.y][snode.x] = snode;
		oq.Insert(snode);

		// calculate a general point set with the current level of detail
		var pointset = mbm_CalcPointSet(0, 0, _dist, _dstep, _rstep, 0);

		//pdis = new oTerminal(100, 30, 40, 40, 6, 0);

		nextnode:
		while (node = oq.Remove())
		{
			//updateterminal(AreaData, node.x, node.y);

			if(Math.abs(node.x - enode.x) < _err && Math.abs(node.y - enode.y) < _err) {   //Found the destination
//				print("found end");
				
				_done = true;
				this.LastScore = node.f;
//				if(_reduc == 99)
//					return node.f;

				//BUILD PATH USING REFRENCED PARENTS
				var donebuild = false;
				ptd.push(node);
				if (ptd[ptd.length-1].parent!=-1) do {
					ptd.push(ptd[ptd.length-1].parent);
					if (ptd[ptd.length-1].parent==-1)
						donebuild=true;
				} while (!donebuild);
				
				// Reverse the path
				for (var d = ptd.length-1; d>=0; d--) {
					fp.push(ptd[d]);
				}								
				
				this.Path = new Array();
				//Put the offset back in and move to path
				for (var d = 0; d<fp.length; d++)
					this.Path[d] = {x:fp[d].x + minx, y:fp[d].y + miny}

				print("Total pathing time: " + (new Date() - stime));
				return this.Path;

			}
			else {  		// look for adjacent blocks that we attach to and add them to open
				
				// Check for already visited point
//				if (AreaData[node.y][node.x] & 0x100000) continue;
				
				// Check for previous nodes... obfuscation
				for (var i = 0; i < nodecenters.length; i++) {
					if (nodecenters[i].id != node.parent.id) {
						if (mbm_PointInCircle(nodecenters[i], distsq, node)) {
							// print("in circle, skipping");
							continue nextnode;
						}
					}
				}

//				if (!_isopen(AreaData, node.x, node.y)) {
//					continue;
//				}
//				nodecenters.push(node);

//				for (i = 0; i < pointset.length; i++) {
//					points.push({x:pointset[i].x + node.x,y:pointset[i].y + node.y});
//				}
//				points = mbm_CalcPointSet(node.x, node.y, _dist, _dstep, _rstep, 0);

//				print("Adding " + points.length + " points");

				nextpoint:
				for (var i = 0; i < pointset.length; i++) {
					cx = pointset[i].x + node.x;
					cy = pointset[i].y + node.y;
					
					//check for map edge
					if (cy <= 1 || cy >= height - 1 || cx <= 1 || cx >= width - 1) continue;

					//check for walkability and small diagonal gaps that cant be passed
					if (!DontLoadRooms) {
						if (AreaData[cy][cx] == undefined) {
							if (DelayLoadRooms) {
								this.LoadPos(cx + this.minx, cy + this.miny); 
								if (AreaData[cy][cx] == undefined) continue;
							} else continue;
						}
						if (AreaData[cy][cx] & 1) continue;
						if (!_isopen(AreaData, cx, cy)) continue;
					} else {
						var v = this.RoomXY(cx + minx, cy + miny);
						if (v & 1) continue;
						if (!this.IsOpenXY(cx + minx, cy + miny)) continue;
					}
						
					// Check for previous nodes... obfuscation
//					for (var xxx = 0; xxx < nodecenters.length; xxx++) {
//						if (nodecenters[xxx].id == node.parent.id) {
//							if (mbm_PointInCircle(nodecenters[xxx], distsq - 4, {x:cx,y:cy})) {
//								// print("in circle, skipping");
//								continue nextpoint;
//							}
//						}
//					}

//					if ((vx*vy) && (AreaData[cy][node.x] & 1) && (AreaData[node.y][cx] & 1)) continue;

					// Find an "opener" space
					// node = _findopener(AreaData, node);
					


//					newg = node.g + points[i].dist; // SCORE[Math.abs(vx*vy)];
//					newg = node.g + 1;

					var cnode = ng[cy][cx];
					var fh = this.sorcheuristic(dx,dy,cx,cy,_dist);
					// var fh = this[FORWARDHEURISTICS[_fh]](dx, dy, cx, cy)*_factor;

					if(!cnode) {
						cnode = new oNode(cx,cy,false,false,node,node.g + 1,fh);
						ng[cy][cx] = cnode;
					}
					else {
						if (cnode.g > newg){
//							cnode.closed = false;
							cnode.g = newg;
							cnode.parent = node;
						}
						else continue;
					}
					cnode.f = cnode.g + cnode.h;

					if(!cnode.open) {
						cnode.open = true;
						oq.Insert(cnode);
						//AreaData[cnode.y][cnode.x] |= 0x200000;
					}
					
				}
				
				me.overhead(oq.getLength() + " nodes");
//				me.overhead(p2s({x:node.x + minx,y:node.y+miny}));
//				print(p2s({x:node.x + minx,y:node.y+miny}));
//				delay(30);
//				node.open = false;	node.closed = true;
//				AreaData[node.y][node.x] |= 0x100000;
				nodecenters.push(node);
			}
		}
		print("Couldnt find a path to destination");
		return false;
	}

	function oMap_findsorcpath2(_sx, _sy, _dx, _dy, _dist, _err, _dstep, _rstep, _algo) {

		if(!_sx || !_sy || !_dx || !_dy){ 		//basic check for illegal coordinates
			mlprint("mlMap:mlFindSorcPath - The start or end has a 0 coordinate value");
			this.LastError = ("mlMap:mlFindPath - The start or end has a 0 coordinate value");
			return false;
		}

		if (DelayLoadRooms && !DontLoadRooms) {
			this.LoadPos(_sx, _sy);
			this.LoadPos(_dx, _dy);
		}
		
		if(!_isinrange(_sx, _sy))
		{
			mlprint("mlMap.FindSorcPath - The start coord's are out of range");
			this.LastError = ("mlMap.FindPath - The start coord's are out of range");
			return false;
		}
		
		if(!this.IsWalkable(_sx, _sy))
		{
			mlprint("mlMap.FindSorcPath - The start coord's are not walkable");